информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Сетевые кракеры и правда о деле ЛевинаSpanning Tree Protocol: недокументированное применениеСтрашный баг в Windows
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Утекший код XP и Windows Server... 
 Дела виртуальные 
 Простое пробивание рабочего/провайдерского... 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
все доски
FAQ
IRC
новые сообщения
site updates
guestbook
beginners
sysadmin
programming
operating systems
theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Подмена подписанного документа в американском стандарте ecdsa 25.10.02 07:09  Число просмотров: 9335
Автор: 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

Эксплойт
<theory> Поиск 








Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2020 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach