Примечание автора. В результате обсуждения на форуме были найдены серьёзные недостатки в предложенных методах делающие маловероятным их практическое применение.Более реалистичный метод опубликован здесь.

Данная статья представляет собой окончательный объединенный вариант публиковавшихся ранее статей "Уязвимость методов цифровой подписи на базе алгоритма Эль-Гамаля: ГОСТ Р 34.10-94 и DSA (DSS). Часть 1." и "Универсальная подпись, утверждённая ГОСТом. ( Уязвимость цифровой подписи. Часть 2. )".

1. Вступление.

В настоящее время банковские (и многие другие деловые операции) практически немыслимы без привлечения методов цифровых подписей.

В мире негласным стандартом стали алгоритмы, основанные на методе Эль-Гамаля (El Gamal), в частности - американском стандарте DSA. В Российской Федерации, разумеется, не сочли возможным слепо следовать зарубежным разработкам и применили свой метод, незначительно отличающийся формулой вычисления цифровой подписи. Главным результатом этого нововведения стала возможность произвести махинацию, заключающуюся в отправке неверно подписанного документа, с последующим отказом от него.

Примерная механика мошенничества такова: вначале используется уязвимость ГОСТа, позволяющая вполне легально сформировать "слабую подпись", т.е. подпись, из которой может быть легко вычислен секретный ключ. В принципе, после этого можно отказаться уже от любого документа, но и с другой стороны нельзя доказать, что он не был послан Вами.

Конечно, подобная ситуация уже приемлема, когда Вы распоряжаетесь не своими деньгами, а государственными, но ГОСТ позволяет и большее.

После того как вы "засветили" свой ключ, можно сформировать платёжку на фирму-"однодневоку" с подписью, которая успешно пройдёт все требуемые стандартом проверки, но не будет являться корректной по отношению к данному документу. После этого уже можно смело идти и заявлять о хищении денежных средств.

Чтобы не судиться с банком (т.к. последний может долго и успешно защищаться, переадресовывая Ваши претензии к государственным органам сертификации, навязавшим ему подобную схему проверок) проще застраховать финансовые операции и получить страховку спустя два месяца, по окончании предварительного следствия.

Этой ошибке подвержен только Российский ГОСТ Р 34.10-94 и его новая версия ГОСТ 34.19-2001.

2. Общие положения

Напомним вкратце суть предлагаемого ГОСТ Р 34.10-94 метода.

р- простое число, 2⁵⁰⁹ < р < 2⁵¹² либо 2¹⁰²⁰ < р < 2¹⁰²⁴.
q- простое число, 2²⁵⁴ < q < 2²⁵⁶ и q является делителем для (p-1)
а- целое число, 1 < а < р-1, при этом а^q (mod p) = 1.
...
х- секретный ключ пользователя для формирования подписи.
0 < х < q.
у - открытый ключ пользователя для проверки подписи.
у = а^x (mod p).
...
Процедура подписи сообщения включает в себя следующие этапы:

1. Вычислить h(M) (далее- H)-значение хеш-функции h от сообщения М.
   Если h(M)(mod q)=0, присвоить h(M) значение 0255 1.
2. Выработать целое число k, 0 < k < q.
   
3. Вычислить два значения :
   r=a^k (mod p) и r' = r (mod q).
   Если r' =0, перейти к этапу 2 и выработать другое значение числа k.
   
4. С использованием секретного ключа х пользователя (отправителя
   сообщения) вычислить значение
   ...
   ГОСТ:
   
   s= (xr' + kh(M))(mod q).
   ...
   DSA:
   
   ( k' * k ) mod q=1; (А1)
   0 < k' < q ;
   s= (k'(xr+H)) mod q. (А2)
   ...
   

3. Первая ошибка ГОСТА

Представим себе ситуацию, когда генерируется значение k=1 (r'= a ). Нетрудно заметить, что
s = (H+rx) mod q
отсюда, для любого H2=H+N можно легко вычислить подпись s2=(S2+N) (mod q)

И, самое главное, уравнение (h+ax) mod q =s, при известных h,q,s решается за несколько секунд.

На первый взгляд ничего особо страшного - вероятность наступления подобного события чрезвычайно мала - порядка ( 10^-78), хотя, например, при тотальной проверке неким недобросовестным сотрудником банка (или, при передаче по открытым сетям, хакером) всех входящих подписей на предмет r=a (согласно ГОСТУ программа подписи может иметь общее a для всех своих пользователей, что и делает, например, ЦБ РФ), от неприятностей не гарантирован никто!

Впрочем, куда вероятнее теперь другая ситуация, когда будет умышленно формироваться нестойкая подпись, с целью опротестования последующих платёжек - ведь доказать, что подобная подпись была сформированна неслучайно невозможно, учитывая требование п. 4.7. ГОСТа ("Целое число k, которое генерируется в процедуре подписи сообщения , должно быть секретным и должно быть уничтожено сразу после выработки подписи." (Зачем?!!! Если уж злоумышленник доберётся до компьютера отправителя, то он не мудрствуя, сам секретный ключ заберёт...) .

К "сожалению", непосредственно использовать применять известный ключ ещё рановато, т.к. Вы всё же не сможете убедительно доказать, что платёжку посылали другие лица. (Хотя для бухгалтера гос. учреждения и такая схема вполне приемлема, ибо доказать что отсылал их именно он также невозможно.). Но не стоит радоваться так, как давно известно, жулика российский закон не обидит :)

4. Вторая ошибка (универсальная подпись, утверждённая ГОСТом)

Давайте повнимательнее посмотрим на фразу "k- целое число, 0 < k < q."

В "DSA" этот диапазон задан требованием о мультипликативной инверсии и s=0 при k=iq, i>=0, а чем в нашем случае обоснованно это требование? ГОСТом ?!

При внимательном изучении метода выясняется, что существуют многочисленные частные случаи, наборов (x,p,q) в которых это требование не имеет математической основы. Фактически, его поддержание лежит на добросовестности создателя подписи, т.е. вещи, отвергаемой по определению:) (В самом деле, зачем тогда вообще цифровая подпись нужна?).

Впрочем, мы забежали вперёд. Итак, чем грозит методу отсутствие "физических" ограничений на значение k?
Рассмотрим ситуацию с k = 0 (или k кратным q);
r=k⁰ =1;
s=(xr+kH) (mod q) = x (mod q).

Нетрудно видеть, что в этом случае цифровая подпись не зависит от значений H. Т. е. теоретически, может служить подписью к любому сообщению!!!

Возникает логичный вопрос: как же так, ведь значение h входит в формулу проверки подписи. Вообще-то этим вопросом можно и не задаваться, а проверить приём для своего набора (p,q,x) экспериментально, но я всё же приведу доказательство сокращения h.

Рассмотрим случай с секретной подписью x=1. Открытая подпись y=a;

Для удостоверения подписи проверяется равенство
r= (a^s1 y^s2 (mod p)) (mod q), где
s1= sv (mod q); s2=(q-r)v (mod q); v= H^(q-2) (mod q);
В нашем случае ситуация выглядит чуть проще ( учитывая, что x,s,r=1, y=a и v < q):
1=(a^v a^{((q-1)v (mod p))} ( mod p)) mod q.
(q-1)v mod q - можно представить как (q-1)v - iq, где i результат целочисленного деления i=[(q-1)*v / q] =v-[v/q]=v, т.к. v < q по определению. Отсюда
(a^v*a^(qv)*a^(-v)*a^(-qv)) =1. Что и требовалось доказать.

Аналогичные принципы применяются при нахождении доказательства (области применимости) для прочих x, следует только учесть, что:

1. y=a^x (mod p) = a^x - ip. y^v = (a^x)^v + (ipva^x)^(v-1) + ... pi = a^(xv) + p*(...);
   y^v (mod p) = a^xv (mod p).
   
2. a^q (mod p)=1 => a^(qz) (mod p) = 1.

Т.е, для открытого ключа y=a , мы можем в качестве подписи любого сообщения прислать (1,1). В более общем случае (x,1)

Разумеется, саму по себе эту подпись использовать нельзя, т.к. убедительно объяснить знание посторонним злоумышленником x невозможно. Но вот в сочетании с предварительной отсылкой "слабой подписи" подобный вариант вполне объясним.

Кроме того, что данная подпись подходит к любому документу? она имеет ещё одно замечательное достоинство: очевидно, что подобный набор значений не может быть выдан Вашей программой ни при каких условиях (это легко доказать, исходя из простоты q и требований к значениям случайного ключа и хэша). Это значит, что выждав сутки, можно "просмотреть выписки", и бежать в банк, потом, ещё сутки с непонимающим видом искать "специалиста", и наконец не торопясь, бежать в милицию с заявлением о хищении. Пока они вообще поймут, о чём идёт речь, деньги станут уже недосягаемы для правоохранительных органов. Скорее всего, потрепав пару дней нервы работникам банка, следователь сложит дело в сейф к другим "глухарям". Дальше суд (а лучше страховка) и за вычетом небольших накладных расходов Вы удваиваете свой капитал. Разумеется эта схема может успешно применяться и банками по отношению друг к другу, и вообще всеми, кто использует ГОСТ по цифровой подписи.

5. Дополнения и комментарии

Как такое могло случиться?

Конечно, первопричиной подобной проблемы стала странная позиция разрабочиков стандарта, решивших, что мат. ограничения можно вводить законадательно?! Но есть ещё одна причина исключительно точно изложенная Игорем Камоловым (www.firebox.ru), описавшим ещё одну проблему ГОСТа .

любой специалист в области криптографии вам совершенно 
обоснованно заявит, что стоикость криптосистемы в первую 
очередь зависит от качества ключевой информации 
(в том числе и случайного ключа - прим авт.). 
Все остальное есть второстепенно. Можно использовать любой 
наворочанный алгоритм преобразования данных при нулевом 
ключе. И самое смешное, что сертификат от ФАПСИ вы получите. 
Ибо нет ни одной бумаги на то, как, из чего и каким образом 
должна генерироваться ключевая информация. 

Вообще-то причина, по которой Россия решила отказаться от общепринятого стандарта, малопонятна. (В DSA(DSS) и классическом алгоритме Эль-Гамаля такой приём невозможен, т.к. универсальная подпись будет иметь вид (0,1), что запрещено по определению). Ссылки на более удобный для расчёта алгоритм бессмысленны, т.к. все вычисления выполняются компьютерами, чья производительность стремительно растёт. В вариант, что разрабатывавшие ГОСТ математики (и проверявшие его криптоаналитики ), решили, что математические ограничения можно вводить законодательно как-то не верится... Что нам остаётся думать???

Часто задаваемые вопросы

1) Во многих ли программах пройдёт этот трюк? (разработчики наверняка принимают какие-то дополнительные меры предосторожности ? )

Ответ:речь шла о проблемах именно ГОСТа. Возможный профессионализм российских разработчиков никак не снимает вины с ФАПСИ. Да и где гарантия, что с конкрентной программой вам повезёт. Яркий пример тому указал А. Волчков:

:в программе iBank компании Бифит в качетве k использовалось 
системное время в момент подписания документа, далее все очевидно.
Самое смешное, что была дырка сделана в строгом соответствии c п.4 
(последний абзац) разрешавщим снимать число k и c физического датчика 

2) Проблема встречной атаки:

> Простите за жаргон, который ниже.
> Основная фишка состоит в том, что если злоумышленник, 
> использует спец. значения k, то он попадает на ответный 
> ход - по спецзначениям k, мы получаем его x, после чего 
> начинаем его огорчать. 
> Аналогично, если он даст нам спец. y, мы получим х и 
> опять огорчим его.


Разумеется, риск нарваться на ответный взлом есть ( он есть вообще во всех
атаках т.к. невольно ослабляешь и свою защиту). 
Впрочем, реально он невелик т.к. у атакующего 
a) преимущество неожиданности, левую фирму для молниеносного ухода
 денег надо готовить заранее, на подставных, в другой стране 
 и т.д :;
б) фактор времени - при современном компьютерном контроле за счётом 
 насчёт действительно левой платёжки он может поднять шум, прежде чем 
 фирма успеет её реализовать (всё таки деньги пару часов идут, и для 
 их получения нужно придерживаться установленного порядка, иначе 
 причастность банка будет очевидна):

3) Как решить (h+ax) (mod q)=s. (ч.3 статьи):

при известных H,q,a,s x= (s-h) *a**(-1) (mod q), 
a**(-1) находится либо по алгоритму Евклида, либо a**(-1) = a**(q-1)
А. Волчков

Благодарности

Я очень благодарен Д. Леонову, за то, что он рискнул репутацией bugtraq.ru и выкладывал содержащие ошибки черновые варианты этой статьи до того, как они прошли широкую проверку, и постоянно менял их на всё новые и новые версии.

Неоценимую помощь оказали критика и консультации А. Волчкова - президента Российской криптологической ассоциации

Также большое спасибо И. Камолову , Маркову Н. А., Олегу Ф., Радовцеву Д. , Макаровой О. и всем кто присылал замечания и предложения по опубликованным методам.

Полезные ссылки

1. ГОСТ Р 34.10-94
2. ГОСТ 34.19-2001.
3. Bugtraq.ru
4. Российская криптологическая ассоциация
5. Ещё одна уязвимость цифровой подписи