Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Подмена подписанного документа в американском стандарте ecdsa 25.10.02 07:09 Число просмотров: 9711
Автор: Komlin Статус: Незарегистрированный пользователь
Отредактировано 28.10.02 12:46 Количество правок: 9
|
English version below : http://www.bugtraq.ru/cgi-bin/forum.cgi?type=sb&b=15&m=62564 .
Подмена подписанного документа в новом американском стандарте ЭЦП ECDSA.
Вступление.
Сегодняшний мир практически немыслим без систем электронной цифровой подписи. Незаметно для себя с ними работает любой пользователь интернета. Именно эти методы обеспечивают функциональность и оперативность современного банковского сектора. Несмотря на это, сами стандарты ЭЦП ещё очень молоды и находятся в стадии совершенствования. Один из наиболее перспективных стандартов ANSI X.9-62 ECDSA от 1999 г. – модификация DSA для эллиптических кривых. К сожалению, в процессе адаптации этого стандарта не были полностью учтены все особенности операций с эллиптическими кривыми, что и дало возможность имитировать подмену подписанного документа.
Одно из основных требований к методам цифровой подписи – невозможность нахождения за разумное время двух или более документов подходящих к одной подписи (и наоборот). Для этого в дополнение к механизму ЭЦП используется процедура хэширования (в DSA это SHA-1), в результате которого в соответствие к каждому документу ставится очень большое и непредсказуемое число (далее – хэш), которое собственно и подписывается.
Подавляющее большинство атак производится именно на эту процедуру с целью нахождения способа получения документов, с одинаковыми хэшами (или различающимися на заданную величину).
В этой работе использован несколько иной подход: была сделана попытка путём модификации выбираемых пользователем ключей, найти такие значения подписи , чтобы они подходили одновременно к двум заранее выбранным значениям хэша. Выяснилось, что рядовому пользователю схемы ЭЦП это вполне по силам, если он специальным образом выберет значение своих ключей (секретного личного (private key) и секретного случайного (per-message secret)). При этом пользователю нет необходимости в модификации внешних параметров ЭЦП. Для наглядности ниже иллюстрируется подмена подписи для утверждённых NIST наборов параметров федерального пользования.
Полагаю, что правовые последствия существования общей подписи к двум документам в комментариях не нуждаются.
Описание ошибки.
В матаппарате новейшего американского стандарта ЭЦП известного как ECDSA (DSA для эллиптических кривых) [1 cтр. 25-30] существует серьёзная ошибка, позволяющая выбрать такое значение секретного ключа, чтобы получить одинаковые подписи для разных документов.
Описанная ошибка отличается от уже известных и сходных по последствиям DSKS (Duplicate Signature Key Selection) [1 стр. 30-32] , тем, что не требует участия злоумышленника в выборе параметров подписи (G,n и т.д.). Таким образом, она доступна практически любому пользователю ЭЦП, а не только самим разработчиками программ ЭЦП.
В описании сохранены обозначения принятые в стандарте.
Эта ошибка вызвана равенством x-координат противоположных точек эллиптической кривой
_x(G)==_x(-G) . (1)
Легко увидеть, что из nG=0, следует (n-1)G= -G. (2)
Отсюда:
r1= _x(kG)==r2=_x( (n-1)kG)==r (3)
где k – случайный ключ (per-message secret) подписи для простоты принимаемый за 1.
Вывод формул для случая k >1 аналогичен.
Пусть нам необходимо подобрать одинаковую подпись для сообщений M1 и М2 (вернее, для их хэшей e1,e2). Мы можем рассчитать личный секретный ключ (private key) d такой, что подписи для этих сообщений будут одинаковыми.
Пусть k1=1, k2=n-1, тогда r1=r2=r=x(G). (3a)
Посмотрим внимательнее на формулу подписи:
s=k’(e+dr) mod n (4)
В нашем случае
s1=k1’(e1+dr) mod n (4a)
s2=k2’(e2+dr) mod n (4б)
где
k1'*k1 mod n =1 ; k1'=1 ;
k2’*(n-k1) mod n =1; k2'=n-1
e1=SHA(M1); e2=SHA(M2)
Очевидно, что s2=s1=s если
(e1+dr) == (n-1)*(e2+dr) (mod n) (5)
2dr=(n-1)(e2+e1) (mod n) (5б)
Отсюда легко находится d:
d=z’(n-1)(e2+e1) mod n (6)
где
z’*(2r) mod n==1 mod n
Таким образом, мы получаем абсолютно одинаковые подписи (s,r) для разных сообщений.
---------------------------------------------------
Исправить эту ошибку несложно. Нужно всего лишь обеспечить доказательную генерацию d/
Например: выбирается случайное значение Seed0
Личный ключ d:=SHA-1(Seed0)
Сохраняются оба значения.
В этой схеме желаемое значение d выбрать не получится.
Время генерации ключа конечно увеличиться, но ведь оно не критично в большинстве случаев.
Ещё один вариант: передавать в качестве подписи не (s,r), а (s,R), где R=kG.
С Уважением A.V. Komlin
Подробное описание стандарта ECDSA и основных известных атак на него приведено в книге
The Eliptic Curve Digital Signature Algorithm (ECDSA)
Don Johnson (Gerticom Research), Alfred Menezes (University of Waterloo) February 24, 2000
Эта книга доступна в PDF-формате по адресу:
http://rook.uinc.ru/pdf/ecdsa.zip
На указанной ниже страничке находится Java-апплет, позволяющий в интерактивном режиме за несколько секунд расчитать одинаковые подписи и требуемые для этого ключи для любых двух разных сообщений, в пяти стандартных кривых NIST или в любой своей.
http://www.venue.ru/sign1.htm
Код апплета не обфусцирован, желающие могут посмотреть его JAD'ом.
----------------
Контрольный пример
Curve-192 (NIST)
M1- "ECDSA is GOOD"
M1- "ECDSA is BAD"
k=1
d - 302035990567828412089108831099891370757859899245436683119
s - 3138550867696141607436413456015998514180639734009232307827
r - 602046282375688656758213480587526111916698976636884684818
Эксплойт
|
- Подмена подписанного документа в американском стан... - Komlin 25.10.02 07:09 [9711]
|
|
|
подробно о проекте
Анализ криптографических сетевых...
