Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Универсальная подпись, утверждённая ГОСТом. :( ( Уязвимость цифровой подписи. Часть 2. ) 06.04.02 08:14 Число просмотров: 2715
Автор: Komlin Статус: Незарегистрированный пользователь
Отредактировано 09.04.02 10:33 Количество правок: 8
|
Универсальная подпись, утверждённая ГОСТом. ( Уязвимость цифровой подписи. Часть 2. )
1. Предисловие.
В настоящей статье сделана попытка (надеюсь успешная) подобрать значения, которые не являясь цифровой подписью к документу, в то же время не могут быть отличены получателем от подлинной подписи в рамках действующего ГОСТа.
Этой ошибке подвержен только Российский ГОСТ Р 34.10-94. Её наличие стало результатом произведённого "упрощения" американского DSA. Ниже приводится доказательство, что по крайней мере в частных случаях, подпись вида (x,1) где x- минимальный из возможных секретных ключей, соответствующих заданному открытому , подходит к любому сообщению независимо от его хэш-кода! Например, для всех открытых ключей y=a подходит подпись (1,1).
Напомним вкратце суть предлагаемого ГОСТ Р 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, - фактически , k' не может принять значение =1 согласно (А1)
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.
2. Описание уязвимости.
Давайте повнимательнее посмотрим на фразу 2: "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).
Нетрудно видеть, что в этом случае цифровая подпись не зависит от значений H. Т. е. теоретически, может служить подписью к любому сообщению!!!
Возникает логичный вопрос: как же так, ведь значение h входит в формулу проверки подписи. Вообще-то этим вопросом можно и не задаваться, а проверить приём для своего набора (p,q,x) экспериментально, но я всё же приведу доказательство сокращения h.
3. Вариант доказательства.
Рассмотрим случай с секретной подписью 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). В более общем случае (x',1), где a^x' (mod q)= a^x (mod q).
4. Последствия.
До тех пор, пока это ограничение не введено возможен следующий вариант действий:
1. отсылаете документ (договор, платёжку, свидетельские показания, цифровой чек и т. д.), заверенный подобной подписью.
2. убедившись, что он сделал своё дело, смело опротестовываете его заявляя, что вы посылали совсем другой или не посылали вообще ничего (на основании того факта, что подпись подходит для любого сообщения);
3. если Вы посылали документ с x'=x можно также заявить, что такая подпись вообще не могла быть сформирована для документа H ( при условии,что q-действительно простое, хотя строго доказать последнее врядли возможно), и если получатель (банк) принял его, то это проблемы банка.
Конечно, вернёт ли суд Вам деньги по подобной платёжке неизвестно (негосударственный банк не обязан отвечать за проблемы госстандарта), но и строго доказать, что подделка Ваших рук дело, тоже никто не сможет. Если пересылались не свои деньги ( а например государственные) и такой вариант вполне приемлем.
5. Дополнения и комментарии.
A) Как найти x'
В описанном выше подходе всё же имеется один небольшой недостаток. В ложной подписи Вы выдаёте значение секретного ключа, x. Но и этого можно избежать, найдя x' такое, что a^x (mod q) = a^x' (mod q).
Простейший путь, состоит в осознании, что требование о простоте q по сути формально . Оно необходимо лишь для повышения стойкости алгоритма к перебору... Но злоумышленник, разумеется, преследует иную цель. Тот, факт, что q не является простым при размерности числа 2^256 проверить в настоящее время практически невозможно (это задача о разложении на простые множители 256-битного числа). Да и особого смысла это доказательство не имеет. Обратите, что и при формировании граничных значений подписи они не подбираются, а вычисляются по рекомендованным алгоритмам.
Последовательность действий.
1) Под каким-нибудь благовидным предлогом отказываемся от старого ключа и граничных значений (например, испортилась дискета или жесткий диск)
2) Вычисляем простые t,f порядка 2^126...127, q=t*f;
3) Дальше действуем, как в госте, с той разницей, что находим не a^q (mod p)=1 , а a^t (mod p)=1. Методика, разумеется, та же (раздел 6.C ГОСТа), только вместо q подставляем t (или f)
В этом случае выполнение равенства a^q mod p=1 вытекает из свойств операции "mod" ( если a (mod b) = 1, то a^c (mod b)=1). Отсюда следует , что x'=x+t!
Для защиты от этого приёма достаточно исключить из диапазона допустимых значений r=1 (П. 6.1. ГОСТа дать в редакции: "1. Проверить условие:0 < s < q и 1 < r' < q.",- вместо "1. Проверить условие:0 < s < q и 1 < r' < q."
Б) Ещё один универсальный ключ'
Из формулы проверки подписи хорошо видно, что для y=1 универсальной подписью является (s, (a^(sv (mod q)) (mod p)) (mod q)). (см. форум).
Секретным ключём в этом случае является t. (см. 5.А)
В) Можно ли доказать факт мошенничества?
В приходящих ответных письмах встретились вопросы, можно ли доказать факт умышленного мошенничества, т. к. в ключе имеется x (если об этом до данной статьи следователь вообще смог бы догадаться)? Думаю, что нет.
Во-первых необязательно использовать именно x раз есть гомологи( x'). (см. выше (5.А)). Во-вторых всегда можно сослаться на глюки ПО или искажение данных при передаче, незамедлительно использованное использованные недобросовестными сотрудниками банка. В третьих можно заявить, что x с требуемым остатком от деления было как-то подобранно, но так как злоумышленники не могли быть уверены, что это именно то значение ключа, они использовали универсальную подпись. и т.д. Пусть следователи попробуют доказать обратное ( но вначале им ещё надо разобраться, что вообще произошло).
Проще всего первый вариант (применение x'). Даже если для его обнаружения использовалось непростое q, это практически невозможно доказать в ближайшую сотню лет. Впрочем и в обратном случае следователь ничего не добьётся. Числа получались с помощью стандартной программы, почему она выдала именно такие значения неизвестно.
Всё возможные доказательства будут только косвенными (если конечно на Вашем компъютере не осталось следов подбора), первопричиной инцидента являлась ошибка ГОСТа, отвечать за которую пользователи не обязаны.
6. Как такое могло случиться?
Вообще-то причина, по которой Россия решила отказаться от общепринятого стандарта малопонятны. (В DSA(DSS) и классическом алгоритме Эль-Гамаля, такой приём невозможен, т.к. универсальная подпись будет иметь вид (0,1), что запрещено по определению.) Ссылки на более удобный для расчёта алгоритм бессмысленны, т.к. все вычисления выполняются компьютером. В вариант, что разрабатывавшие ГОСТ математики (и проверявшие его криптоаналитики ГРУ), решили, что математические ограничения можно вводить законодательно как-то не верится... Что нам остаётся думать???
Искренне Ваш
А. В. Кобец (Komlin), avkvladru@mail.ru
Открытое обсуждение, доступное для незарегистрированных пользователей здесь
|
- Универсальная подпись, утверждённая ГОСТом. :( ( У... - Komlin 06.04.02 08:14 [2715]
|
|
|
подробно о проекте
Анализ криптографических сетевых...
