Механизм мошеничества с цифровой подписью на базе российского стандарта ГОСТ Р 34.10-94
1. Вступление.
Уважаемый читатель, эта редакция статьи появилась как результат длительного обсуждения на форуме и в личной переписке первоначального сообщения о существовании в ГОСТ Р 34.10-94 ( и его новой редакции ГОСТ 34.19-2001 ) ошибки, приводящей к существованию универсальных (т.е. подходящих сразу ко многим документам) подписей . Фактически, её нынешний текст является результатом коллективного творчества (см. благодарности).
В настоящее время банковские ( и многие другие деловые операции) практически немыслимы без привлечения методов цифровых подписей.
В мире негласным стандартом стали алгоритмы, основанные на методе Эль-Гамаля (El Gamal), в частности - американском стандарте DSA. В Российской Федерации, разумеется не сочли возможным слепо следовать зарубежным разработкам и применили свой метод, незначительно отличающийся формулой вычисления
цифровой подписи. Главным результатом этого нововведения стала возможность произвести махинацию, заключающуюся отказе от подписанного документа
Суть ошибки состоит в том, что для пары ключей (x1,y1) где x1-секретный, а y1-открытый будут существовать формально правильные универсальные подписи вида (x1,1) и (x0,1) (x1!=x0) причём нельзя доказать, что вторая подпись (x0,1) не может быть выдана корректной программой в рамках ГОСТа.
Это явно не стыкуется с утверждением п.1.2. ГОСТа :
"Внедрение системы ЭЦП на базе настоящего стандарта обеспечивает защиту предаваемых сообщений от подделки, искажения ..."
Выводы, доказательства, способ вычисления значений x0 , y1, подписей для ключа x1 и примерная методика мошенничества приведены ниже.
2. Краткое описание методов формирования и проверки подписи ( взято из ГОСТа).
Напомним вкратце суть предлагаемого ГОСТ Р 34.10-94 метода.
р- простое число, 2^509 < р < 2^512 либо 2^1020 < р < 2^1024 .
q- простое число, 2^254 < q < 2^256 и 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)
...
Процедура проверки :
1. Проверить условие: 0 < s < q и 0 < r' < q.
Если хотя бы одно из этих условий не выполнено, то подпись считается недействительной.
2. Вычислять h(M1 )-значение хеш-функции h от полученного сообщения М1 .
3. Вычислить значение v= (h(M1 ))^q-2 (mod q)
4. Вычислить значения:z1 = sv (mod q) и z2 = (q-r' ) v (mod q)
5. Вычислить значение u = (a^z1 y^z2 (mod p)) (mod q)
6. Проверить условие: r' = u.
"При совпадении значений r' и u получатель принимает решение о том, что полученное сообщение подписано
данным отправителем и в процессе передачи не нарушена целостность сообщения, т.е. М1=М"
3. Первая универсальная подпись, утверждённая ГОСТом ;).
Давайте повнимательнее посмотрим на фразу "k- целое число, 0 < k < q."
В "DSA", этот диапазон задан требованием о мультипликативной инверсии и s=0 при k=iq, i>=0,
а чем в нашем случае обоснованно это требование? ГОСТом ?!
При внимательном изучении метода, выясняется, что существуют многочисленные частные случаи, наборов (x,p,q) в которых это требование не имеет математической основы. Фактически, его поддержание лежит на добросовестности создателя подписи, т.е. вещи, отвергаемой по определению:) (В самом деле, зачем тогда вообще цифровая подпись нужна?).
Впрочем, мы забежали вперёд. Итак, чем грозит методу отсутствие "физических" ограничений на значение k?
Рассмотрим ситуацию с k = 0 (или k кратным q);
r=k^0 =1;
s=(xr+kH) (mod q) = x (mod q) = x
Нетрудно видеть, что в этом случае цифровая подпись не зависит от значений 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^v^x + ipva^x^(v-1) + ... pi= a^(xv) + p*(...);
y^v (mod p)= a^xv (mod p).
2) a^q (modp)=1 => a^(qz) (mod p)=1.
Т.е, для открытого ключа y=a , мы можем в качестве подписи любого сообщения прислать (1,1). В более общем случае, для пары ключей (x1,y1) - (x1,1)
Разумеется, саму по себе эту подпись использовать нельзя, т.к.:
1) убедительно объяснить знание посторонним злоумышленником секретного ключа x1 невозможно;
2) несмотря на формальную корректность подобных значений , легко доказать, что сертифицированная программа не может выдать значение s=x1, при целом k принадлежащем [1;q-1] .
Впрочем, раз нашлась одна универсальная подпись, может стоить поискать и другую, более подходящую?
4. Вторая универсальная подпись...
Давайте поподробнее рассмотрим формулу проверки подписи.
Пусть нам дан открытый ключ y1. Рассмотрим, чему будет равно проверочное равенство при y0=p-y1
u1 = (a^z1*y1^z2 (mod p)) (mod q).
u0 = (a^z1*y0^z2 (mod p)) (mod q)=a^z1*(p-y1)^z2 (mod p)) (mod q).
Разложим (p-y1)^z2 в ряд по формуле Тейлора:
y1^z2= p^z2+ z2*p^(z2-1)*(-y1)/1! + z2*(z2-1p^(z2-1)-y1)^2/2!+...+ (-y1)^z2
или проще говоря p*(...) + (-y1)^z2.
Отсюда нетрудно увидеть, что при чётном z2, (y0==p-y1)^z2 ( mod p) == y1^z2 ( mod p) , следовательно и u0=u1
Следствие: при чётном z2 для открытого ключа y1 (соответствующему x1) можно сформировать корректную подпись с помощью значения x0, такого, что y1= p-y0== p- a^x0 (mod p).
Зачем вообще нужна эта головная боль спросите Вы? Затем, что:
1) подпись (x0,1) является универсальной универсальной для пары (x1,y1) при чётном z2, т.е. для 50% документов;
2) x0 -не является секретной парой к y1 ;
3) невозможно доказать, что при cекретном ключе x=x1, набор значений (x0,1) не может быть выдан самой программой.
Остаётся только одна проблема как найти x0 ( и существует ли оно вообще в заданном диапазоне [1; q-1])? Ведь по определению решение уравнения a^x0 (mod q)= y0 невозможно.
5. Определение x0, y1. Расчёт подписей для x1.
Найти x0 из y1 - конечно невозможно, но существует обратный путь. Выбираем любое x0, и находим y1=p- (a^x0 mod p).
При этом правда невозможно найти истинный секретный ключ x1 (скорее всего его в диапазоне [1; q-1] и не существует) , но это не так страшно. Ведь никто его от нас на самом деле ни требует. Требуются только сымитировать контрольные подписи на его основе. Последние же подбираем при помощи x0, и выбора такого k, что z2 -чётное. На практике, просто формируем подпись с ключём x0, проверяем чётное ли z2 и ,если нет, повторяем процедуру. Вероятность чётности z2 50%, то есть достаточно нескольких итераций.
6. Примерная схема мошенничества.
1) заявляем своим открытым ключом y1. (т.к. требовать от нас
предоставления x1 пока никто не вправе) Контрольную подпись подбираем как описано выше .
2) Страхуем свои финансовые операции от форс-мажора и/или банковских
ошибок в результате неправомерных(ошибочных) действий третьих лиц
3) После этого можно отправить ещё несколько "благовидных" документов,
формируя подпись имитируя подпись.
4) Наконец отсылаем документ за подписью (x0,1). Выждав пока он сделает
своё дело, бежим в страховую компанию, заявляя, что по непонятным нам
причинам, программа сформировала подпись подходящую к разным документам
(хотя в ГОСТе заявлено о невозможности этого). Т.е. типичный форс-мажор
или ошибка третьего лица (разработчика ГОСТа).
Разумеется банк (или другой получатель подписи) здесь тоже не страдает. Да и страховая рано или поздно стрясёт деньги с государства, ибо ГОСТ (в лице ФАПСИ)
гарантировал, что правильный результат, при проверке ЭЦП обеспечивает неизменность документа: "Внедрение системы ЭЦП на базе настоящего стандарта обеспечивает защиту предаваемых сообщений от подделки, искажения ... При совпадении значений r' и u получатель принимает решение о том, что полученное сообщение подписано данным отправителем и в процессе передачи не нарушена целостность сообщения, т.е. М1=М"
Поэтому страховщик, скорее всего не станет тратить деньги, время и репутацию на сомнительный по результатам суд с клиентом ибо доказать факт умышленного мошенничества c учётом нормы УК "все сомнения толкуются в пользу обвиняемого" практически невозможно, а строгих доказательств невозможности случайного формирования подписи ему привести не удастся.
7. Дополнения и комментарии.
Как такое могло случиться?
Конечно, первопричиной подобной проблемы стала странная позиция разрабочиков стандарта, решивших, что мат. ограничения можно вводить законадательно?!
Но есть ещё одна причина исключительно точно изложенная Игорем Камоловым (www.firebox.ru), описавшем ещё одну проблему ГОСТа .
любой специалист в области криптографии вам совершенно
обоснованно заявит, что стоикость криптосистемы в первую очередь
зависит от качества ключевой информации ( в том числе и случайного ключа - прим авт.).
Все остальное есть второстепенно. Можно использовать любой наворочанный алгоритм
преобразования данных при нулевом ключе. И самое смешное, что
сертификат от ФАПСИ вы получите. Ибо нет ни одной бумаги на то, как, из чего
и каким образом должна генерироваться ключевая информация.
---
Вообще-то причина, по которой Россия решила отказаться от общепринятого стандарта малопонятны. (В DSA(DSS) и классическом алгоритме Эль-Гамаля, такой приём невозможен, т.к. универсальная подпись будет иметь вид (0,1), что запрещено по определению). Ссылки на более удобный для расчёта алгоритм бессмысленны, т.к. все вычисления выполняются компьютерами, чья производительность стремительно растёт. В вариант, что разрабатывавшие ГОСТ математики (и проверявшие его криптоаналитики ), решили, что математические ограничения можно вводить законодательно как-то не верится... Что нам остаётся думать???
Часто задаваемые вопросы
1) Во многих ли программах пройдёт этот трюк? (разработчики наверняка принимают какие-то дополнительные меры предосторожности ? )
Ответ:речь шла о проблемах именно ГОСТа. Возможный профессионализм российских разработчиков никак не снимает вины с ФАПСИ. Да и где гарантия, что с конкрентной программой вам повезёт. Яркий пример тому указал А. Волчков :
:в программе iBank компании Бифит в качетве k использовалось системное время в момент подписания документа,
далее все очевидно.
Самое смешное, что была дырка сделана в строгом соответствии c п. 4 (последний абзац)
разрешавщим снимать число k и c физического датчика
---
< 2) А не проще ли страховой доказать, что при данных a,q,p не существует k E [1;q-1], таких что r'== 1 ?
Нет. Если бы авторы госта ограничились одной операцией остатка, тогда конечно удалось бы (a^k mod p ==1 только при k==q, что противоречит граничным условиям). Но там есть ещё одна операция отстатка - mod q.
r'= a^k (mod p) (mod q).
Это значит нам дополнительно придётся доказывать, что не существует значений k таких, что a^k (mod p) == iq+1 где i любое натуральное целое, меньше (p-1/q). Вряд ли это вообще можно доказать аналитически. При переборе придётся проверить все возможные k или i. т.е. даже при "малом" диапазоне p (2^509..512), перебрать примерно 2^256 значений, что займёт несколько столетий.
Благодарности
Я очень благодарен Д. Леонову, за то, что он рискнул репутацией <A HREF="http://www.bugtraq.ru/"> bugtraq.ru </a> и выкладывал, содержащие ошибки черновые варианты сообщений об ошибке до того, как они прошли широкую проверку, и без регулярно мешявшему их на всё новые и новые версии.
Неоценимую помощь оказали критика и консультации А. Волчкова - президента <A HREF="http://www.libertarium.ru/libertarium/rca"> Российской криптологической ассоциации </a>
Также большое спасибо <A HREF="http://www.firebox.ru"> И. Камолову </a>, Маркову Н. А., Олегу Ф., Радовцеву Д. , Макаровой О., аспиранту ДВО РАН Осиповой М. А., и всем кто присылал замечания и предложения по опубликованным методам.
Полезные ссылки
<A HREF="http://sssr.h1.ru/4GostR34.11-94.htm">1. ГОСТ Р 34.10-94</A>
<A HREF="http://www.bifit.com/gost3410-2001.zip"> 2. ГОСТ 34.19-2001. </A>
<A HREF="http://www.bugtraq.ru"> 3.Форум Bugtraq.ru, где обсуждались ранние редакции </A>
<A HREF="http://www.libertarium.ru/libertarium/rca">4. Российская криптологическая ассоциация </A>
<A HREF="http://www.pvti.ru/dis.htm"> 5.Ещё одна уязвимость цифровой подписи </A>
С Уважением
<A HREF="mailto:tcsvarka@marine.su">А. В. Кобец (Komlin), avkvladru@mail.ru </A>
HTM - вариант статьи
|
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
