Примечание: впервые этот документ был опубликован год назад (28-10-02), в рассылках securityfocus и местном форуме. К сожалению, найти свободное время и вернуться к этой проблеме удалось только через год. Надеюсь за прошедшее время ошибка не потеряла свою актуальность :)

Ссылки на первые обсуждения на форумах:
//bugtraq.ru/cgi-bin/forum.mcgi?type=sb&b=15&m=62248
English version
http://dom.bankir.ru/showthread.php?threadid=24299

Вступление

Сегодняшний мир практически немыслим без систем электронной цифровой подписи. Незаметно для себя с ними работает любой пользователь интернета. Именно эти методы обеспечивают функциональность и оперативность современного банковского сектора. Несмотря на это, сами стандарты ЭЦП ещё очень молоды и находятся в стадии совершенствования. Один из наиболее перспективных стандартов 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 (А. Кобец), avkvladru@mail.ru

Подробное описание стандарта 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://skagi.net/ecdsa/sign1.htm

Контрольный пример