Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
|
Substitution of document signed under new american format ecdsa 28.10.02 11:55 Число просмотров: 10799
Автор: Komlin Статус: Незарегистрированный пользователь
Отредактировано 29.10.02 05:21 Количество правок: 1
|
Substitution of document signed under new American format ECDSA
Introduction.
Contemporary world is practically impossible without systems of electronic digital signature (EDS). Every Internet user imperceptibly for himself uses them. It is these methods which ensure functionality and efficiency of contemporary banking sector. Despite this fact the EDS standards themselves are very young and are at the stage of perfection. One of the most perspective standards is ANSI X.9-62 ECDSA of 1999 - DSA for elliptic curves. In the process of adaptation all peculiarities of the operations with the elliptic curves were not taken into account to full extent and it gave an opportunity to imitate substitution of the signed document.
One of the main requirements to the methods of digital signature is the impossibility to find within reasonable period of time two or more documents corresponding one signature (or vice versa). In addition to the EDS mechanism the procedure of hashing is used (in DSA it is SHA-1) which results in assigning to each document very large and unpredictable number (hereinafter referred to as hash) which is signed.
The majority of the attacks is aimed at this procedure in order to find method of receiving documents with identical hashes (or hashes which differ at given value).
This work uses slightly different approach: there is made an attempt by modification of the keys chosen by the user to find such meanings of the signature so that they match two previously determined hash values. It was determined that it can be done by ordinary user of EDS scheme, if he specially chooses value for his keys: private key and per-message secret. In this case the user does not need to modify domain parameters of EDS. For the purpose of clearness below is given an illustration of the substitution of signature for approved NIST sets of parameter of federal use.
I suppose that there is no need to comment legal consequences of the existence of common signature for two documents.
Description of the mistake
Mathematical apparatus of the latest American standard of electronic digital signature know as ECDSA (DSA for elliptic curves) [1 page 25-30] contains grave mistake which makes it possible to choose value of secrete code in order to get identical signatures for various documents. The described mistake differs from the already known, having similar consequences DSKS (Duplicate Signature Key Selection) [1, page 30-32] as it does not require participation of the criminal in selection of signature parameters (G,n etc). Thus it is available for almost any EDS user and not only to EDS software engineers.
The description retains symbols adopted in the standard.
The mistake is caused by the equality of x-coordinates of the opposite points of the elliptic curve
_x(G)= =_x(-G). (1)
It is easy to see that from nG=0 follows that (n-1)G=-G (2)
Thus
rl = _x(kG) == r2=_x( (n-1)kG) == r (3)
where k - per-message secret of the signature for the purpose of simplicity taken for 1.
The development of formula for k>1 is analogous.
Let we need to select identical signature for messages M1 and M2 ( or rather for their hashes e1 and e2). We can calculate such private key d that signatures for these messages will be identical.
Let k1 = 1, k2 =n-1, then r1 = r2=r=_x(G) (3a)
Lets take a closer look at the formula of the signature:
S: = k'(e+dr)(mod n) (4)
s1=k1'(e1+dr) mod n (4 a)
s2=k2'(e2+dr) mod n (4 b)
where
k1'*k1 mod n = 1; k1' = 1
k2'*(n-k1) mod n = 1; k2'= n-1
e1 = SHA(M1); e2=SHA(M2)
This implies that s2=s1=s if
(e1+dr) = = (n-1)*(e2+dr) (mod n) (5)
2dr = (n-1)(e2+e1) (mod n) (5b)
From here it is easy to find d:
d = z'(n-1)(e2+e1) mod n (6)
where
z'*(2r) mod n = = 1 mod n
Thus we get absolutely identical signatures (s, r) for various messages.
---------------------------------------------------
It is not difficult to correct this mistake. It is only necessary to provide for demonstrative generation of d.
For example, random variable Seed0 is chosen.
Private key d : = SHA-1(Seed0)
Both values are retained.
It is impossible to select desirable value d in this scheme.
Of course, the time of key generation will increase, but it is not critical in the majority of cases.
There is one more option: to send as signature not (s,r) but rather (s, R) where R=kG.
Sincerely yours,
A.V. Komlin
Detailed description of ECDSA standard and known attacks at it is given in the book
The Elliptic Curve Digital Signature Algorithm (ECDSA)
Don Johnson (Gerticom Research), Alfred Menezes (University of Waterloo) February 24, 2000.
The book is available in PDF format at http://rook.unic.ru/pdf/ecdsa.zip.
--------------------------
The mentioned below page contains Java-applet allowing to calculate within several seconds in the interactive mode identical signatures and required keys for any two different messages in five standard NIST curves or in any its own
http://www.venue.ru/sign1en.htm
The applet code us not closed ant one can look it through with JAD.
Exploit
|
|
<theory>
|
Подмена подписанного документа в американском стандарте ecdsa 25.10.02 07:09
Автор: 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
Эксплойт
|
|
Подмена подписанного документа в американском стандарте ecdsa 01.11.02 13:21
Автор: pms Статус: Незарегистрированный пользователь
|
Все это может быть и хорошо, только как быть с первым пунктом генерации подписи под сообщением: выбрать случайное или псевдослучайное число k??? По числу r, являющемуся x-координатой точки G, легко понять, что значение k выбрано отнюдь не случайно.
|
|
Substitution of document signed under new american format ecdsa 28.10.02 11:55
Автор: Komlin Статус: Незарегистрированный пользователь
Отредактировано 29.10.02 05:21 Количество правок: 1
|
Substitution of document signed under new American format ECDSA
Introduction.
Contemporary world is practically impossible without systems of electronic digital signature (EDS). Every Internet user imperceptibly for himself uses them. It is these methods which ensure functionality and efficiency of contemporary banking sector. Despite this fact the EDS standards themselves are very young and are at the stage of perfection. One of the most perspective standards is ANSI X.9-62 ECDSA of 1999 - DSA for elliptic curves. In the process of adaptation all peculiarities of the operations with the elliptic curves were not taken into account to full extent and it gave an opportunity to imitate substitution of the signed document.
One of the main requirements to the methods of digital signature is the impossibility to find within reasonable period of time two or more documents corresponding one signature (or vice versa). In addition to the EDS mechanism the procedure of hashing is used (in DSA it is SHA-1) which results in assigning to each document very large and unpredictable number (hereinafter referred to as hash) which is signed.
The majority of the attacks is aimed at this procedure in order to find method of receiving documents with identical hashes (or hashes which differ at given value).
This work uses slightly different approach: there is made an attempt by modification of the keys chosen by the user to find such meanings of the signature so that they match two previously determined hash values. It was determined that it can be done by ordinary user of EDS scheme, if he specially chooses value for his keys: private key and per-message secret. In this case the user does not need to modify domain parameters of EDS. For the purpose of clearness below is given an illustration of the substitution of signature for approved NIST sets of parameter of federal use.
I suppose that there is no need to comment legal consequences of the existence of common signature for two documents.
Description of the mistake
Mathematical apparatus of the latest American standard of electronic digital signature know as ECDSA (DSA for elliptic curves) [1 page 25-30] contains grave mistake which makes it possible to choose value of secrete code in order to get identical signatures for various documents. The described mistake differs from the already known, having similar consequences DSKS (Duplicate Signature Key Selection) [1, page 30-32] as it does not require participation of the criminal in selection of signature parameters (G,n etc). Thus it is available for almost any EDS user and not only to EDS software engineers.
The description retains symbols adopted in the standard.
The mistake is caused by the equality of x-coordinates of the opposite points of the elliptic curve
_x(G)= =_x(-G). (1)
It is easy to see that from nG=0 follows that (n-1)G=-G (2)
Thus
rl = _x(kG) == r2=_x( (n-1)kG) == r (3)
where k - per-message secret of the signature for the purpose of simplicity taken for 1.
The development of formula for k>1 is analogous.
Let we need to select identical signature for messages M1 and M2 ( or rather for their hashes e1 and e2). We can calculate such private key d that signatures for these messages will be identical.
Let k1 = 1, k2 =n-1, then r1 = r2=r=_x(G) (3a)
Lets take a closer look at the formula of the signature:
S: = k'(e+dr)(mod n) (4)
s1=k1'(e1+dr) mod n (4 a)
s2=k2'(e2+dr) mod n (4 b)
where
k1'*k1 mod n = 1; k1' = 1
k2'*(n-k1) mod n = 1; k2'= n-1
e1 = SHA(M1); e2=SHA(M2)
This implies that s2=s1=s if
(e1+dr) = = (n-1)*(e2+dr) (mod n) (5)
2dr = (n-1)(e2+e1) (mod n) (5b)
From here it is easy to find d:
d = z'(n-1)(e2+e1) mod n (6)
where
z'*(2r) mod n = = 1 mod n
Thus we get absolutely identical signatures (s, r) for various messages.
---------------------------------------------------
It is not difficult to correct this mistake. It is only necessary to provide for demonstrative generation of d.
For example, random variable Seed0 is chosen.
Private key d : = SHA-1(Seed0)
Both values are retained.
It is impossible to select desirable value d in this scheme.
Of course, the time of key generation will increase, but it is not critical in the majority of cases.
There is one more option: to send as signature not (s,r) but rather (s, R) where R=kG.
Sincerely yours,
A.V. Komlin
Detailed description of ECDSA standard and known attacks at it is given in the book
The Elliptic Curve Digital Signature Algorithm (ECDSA)
Don Johnson (Gerticom Research), Alfred Menezes (University of Waterloo) February 24, 2000.
The book is available in PDF format at http://rook.unic.ru/pdf/ecdsa.zip.
--------------------------
The mentioned below page contains Java-applet allowing to calculate within several seconds in the interactive mode identical signatures and required keys for any two different messages in five standard NIST curves or in any its own
http://www.venue.ru/sign1en.htm
The applet code us not closed ant one can look it through with JAD.
Exploit
|
|
Контрольный пример и эксплойт :) 25.10.02 15:44
Автор: Komlin Статус: Незарегистрированный пользователь
Отредактировано 27.10.02 09:52 Количество правок: 3
|
На указанной ниже страничке находится 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
Эксплойт
|
|
|
подробно о проекте
Анализ криптографических сетевых...
