Bankir.Ru
7 декабря, среда 00:59

Объявление

Свернуть
Пока нет объявлений.

Механизм мошеничества с цифровой подписью на базе российского стандарта ГОСТ Р 34.10-

Свернуть
X
  • Фильтр
  • Время
  • Показать
Очистить всё
новые сообщения

  • Механизм мошеничества с цифровой подписью на базе российского стандарта ГОСТ Р 34.10-

    Полный вариант статьи здесь
    Big>Механизм мошеничества с цифровой подписью на базе российского стандарта ГОСТ Р 34.10-94 /Big>


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

    &nbsp &nbsp &nbsp &nbsp &nbsp Уважаемый читатель, эта редакция статьи появилась как результат длительного обсуждения на форуме и в личной переписке первоначального сообщения о существовании в ГОСТ Р 34.10-94 ( и его новой редакции ГОСТ 34.19-2001 ) ошибки, приводящей к существованию универсальных (т.е. подходящих сразу ко многим документам) подписей . Фактически, её нынешний текст является результатом коллективного творчества (см. благодарности).

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

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

    &nbsp &nbsp &nbsp &nbsp &nbsp Суть ошибки состоит в том, что для пары ключей (x1,y1) где x1-секретный, а y1-открытый будут существовать формально правильные универсальные подписи вида (x1,1) и (x0,1) (x1!=x0) причём нельзя доказать, что вторая подпись (x0,1) не может быть выдана корректной программой в рамках ГОСТа.
    &nbsp &nbsp &nbsp &nbsp &nbsp Это явно не стыкуется с утверждением п.1.2. ГОСТа :
    &nbsp &nbsp &nbsp &nbsp &nbsp "Внедрение системы ЭЦП на базе настоящего стандарта обеспечивает защиту предаваемых сообщений от подделки, искажения ..."
    &nbsp &nbsp &nbsp &nbsp &nbsp Выводы, доказательства, способ вычисления значений x0 , y1, подписей для ключа x1 и примерная методика мошенничества приведены ниже.



    2. Краткое описание методов формирования и проверки подписи ( взято из ГОСТа).


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





    р- простое число, 2^509 &lt р &lt 2^512 либо 2^1020 &lt р &lt 2^1024 .


    q- простое число, 2^254 &lt q &lt 2^256 и q является делителем для (p-1)


    а- целое число, 1 &lt а &lt р-1, при этом а^q (mod p)=1.


    ...


    х- секретный ключ пользователя для формирования подписи.


    0 &lt х &lt q.


    у - открытый ключ пользователя для проверки подписи.


    у = а^x (mod p).


    ...


    Процедура подписи сообщения включает в себя следующие этапы:





    1. Вычислить h(M) (далее- H)-значение хеш-функции h от сообщения М.


    Если h(M)(mod q)=0, присвоить h(M) значение 0255 1.





    2. Выработать целое число k, 0 &lt k &lt q.


    3. Вычислить два значения :


    r=a^k (mod p) и r' = r (mod q).


    Если r' =0, перейти к этапу 2 и выработать другое значение числа k.


    4. С использованием секретного ключа х пользователя (отправителя


    сообщения) вычислить значение


    ...


    ГОСТ:





    &nbsp &nbsp &nbsp &nbsp &nbsp s= (xr' + kh(M))(mod q).


    ...


    DSA:


    &nbsp &nbsp &nbsp &nbsp &nbsp


    &nbsp &nbsp &nbsp &nbsp &nbsp ( k' * k ) mod q=1; (А1)


    &nbsp &nbsp &nbsp &nbsp &nbsp 0 &lt k' &lt q ;


    &nbsp &nbsp &nbsp &nbsp &nbsp s= (k'(xr+H)) mod q. (А2)


    ...


    Процедура проверки :





    1. Проверить условие: 0 &lt s &lt q и 0 &lt r' &lt 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.

    &nbsp &nbsp &nbsp &nbsp "При совпадении значений r' и u получатель принимает решение о том, что полученное сообщение подписано
    данным отправителем и в процессе передачи не нарушена целостность сообщения, т.е. М1=М"










    3. Первая универсальная подпись, утверждённая ГОСТом .


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


    &nbsp &nbsp &nbsp &nbsp &nbsp В "DSA", этот диапазон задан требованием о мультипликативной инверсии и s=0 при k=iq, i>=0,


    а чем в нашем случае обоснованно это требование? ГОСТом ?!


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


    &nbsp &nbsp &nbsp &nbsp &nbsp


    &nbsp &nbsp &nbsp &nbsp &nbsp Впрочем, мы забежали вперёд. Итак, чем грозит методу отсутствие "физических" ограничений на значение k?


    Рассмотрим ситуацию с k = 0 (или k кратным q);


    r=k^0 =1;


    s=(xr+kH) (mod q) = x (mod q) = x





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


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







    &nbsp &nbsp &nbsp &nbsp &nbsp Рассмотрим случай с секретной подписью 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 &lt 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 &lt q по определению. Отсюда


    (a^v*a^(qv)*a^(-v)*a^(-qv)) =1. Что и требовалось доказать.


    &nbsp &nbsp &nbsp &nbsp &nbsp


    Аналогичные принципы применяются при нахождении доказательства ( области применимости) для прочих 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.


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





    &nbsp &nbsp &nbsp &nbsp &nbsp Разумеется, саму по себе эту подпись использовать нельзя, т.к.:

    1) убедительно объяснить знание посторонним злоумышленником секретного ключа x1 невозможно;

    2) несмотря на формальную математическую корректность подобных значений , легко доказать, что сертифицированная программа не может выдать значение s=x1, при целом k принадлежащем [1;q-1] .



    &nbsp &nbsp &nbsp &nbsp &nbsp Впрочем, раз нашлась одна универсальная подпись, может стоить поискать и другую, более подходящую?



    4. Вторая универсальная подпись...





    &nbsp &nbsp &nbsp &nbsp &nbsp Давайте поподробнее рассмотрим формулу проверки подписи.

    &nbsp &nbsp &nbsp &nbsp &nbsp Пусть нам дан открытый ключ y1. Рассмотрим, чему будет равно проверочное равенство при y0=p-y1



    &nbsp &nbsp &nbsp &nbsp &nbsp u1 = (a^z1*y1^z2 (mod p)) (mod q).

    &nbsp &nbsp &nbsp &nbsp &nbsp u0 = (a^z1*y0^z2 (mod p)) (mod q)=a^z1*(p-y1)^z2 (mod p)) (mod q).



    &nbsp &nbsp &nbsp &nbsp &nbsp Разложим (p-y1)^z2 в ряд по формуле Тейлора:

    &nbsp &nbsp &nbsp &nbsp &nbsp y1^z2= p^z2+ z2*p^(z2-1)*(-y1)/1! + z2*(z2-1)*p^(z2-1)*(-y1)^2/2!+...+ (-y1)^z2

    или проще говоря p*(...) + (-y1)^z2.

    &nbsp &nbsp &nbsp &nbsp &nbsp Отсюда нетрудно увидеть, что при чётном z2, (y0==p-y1)^z2 ( mod p) == y1^z2 ( mod p) , следовательно и u0=u1



    &nbsp &nbsp &nbsp &nbsp &nbsp Следствие: при чётном z2 для открытого ключа y1 (соответствующему x1) можно сформировать корректную подпись с помощью значения x0, такого, что y1= p-y0== p- a^x0 (mod p).

    &nbsp &nbsp &nbsp &nbsp &nbsp Зачем вообще нужна эта головная боль спросите Вы? Затем, что:

    &nbsp &nbsp &nbsp &nbsp &nbsp 1) подпись (x0,1) является универсальной универсальной для пары (x1,y1) при чётном z2, т.е. для 50% документов;

    &nbsp &nbsp &nbsp &nbsp &nbsp 2) x0 -не является секретной парой к y1 ;

    &nbsp &nbsp &nbsp &nbsp &nbsp 3) невозможно доказать, что при cекретном ключе x=x1, набор значений (x0,1) не может быть выдан самой программой.



    &nbsp &nbsp &nbsp &nbsp &nbsp Остаётся только одна проблема: как найти x0 ( и существует ли оно вообще в заданном диапазоне [1; q-1])? Ведь, по определению, решение уравнения a^x0 (mod q)= y0 невозможно.





    5. Определение x0, y1. Расчёт подписей для x1.



    &nbsp &nbsp &nbsp &nbsp &nbsp Найти x0 из y1 - конечно невозможно, но существует обратный путь. Выбираем любое x0, и находим y1=p- (a^x0 mod p).

    &nbsp &nbsp &nbsp &nbsp &nbsp При этом правда невозможно найти истинный секретный ключ x1 (скорее всего его в диапазоне [1; q-1] и не существует) , но это не так страшно. Ведь никто его от нас на самом деле ни требует. Требуются только сымитировать контрольные подписи на его основе. Последние же подбираем при помощи x0, и выбора такого k, что z2 -чётное. На практике, просто формируем подпись с ключём x0, проверяем чётное ли z2 и ,если нет, повторяем процедуру. Вероятность чётности z2 50%, то есть достаточно нескольких итераций.





    6. Примерная схема мошенничества.




    &nbsp &nbsp &nbsp &nbsp &nbsp 1) заявляем своим открытым ключом y1. (т.к. требовать от нас

    предоставления x1 пока никто не вправе). Контрольную подпись подбираем как описано выше .



    &nbsp &nbsp &nbsp &nbsp &nbsp 2) Страхуем свои финансовые операции от форс-мажора и/или банковских

    ошибок в результате неправомерных(ошибочных) действий третьих лиц

    &nbsp &nbsp &nbsp &nbsp &nbsp 3) После этого можно отправить ещё несколько "благовидных" документов,

    формируя подпись имитируя подпись.

    &nbsp &nbsp &nbsp &nbsp &nbsp 4) Наконец, отсылаем документ за подписью (x0,1). Выждав пока он сделает

    своё дело, бежим в страховую компанию, заявляя, что по непонятным нам

    причинам, программа сформировала подпись подходящую к разным документам

    (хотя в ГОСТе заявлено о невозможности этого). Т.е. типичный форс-мажор

    или ошибка третьего лица (разработчика ГОСТа).



    &nbsp &nbsp &nbsp &nbsp &nbsp Разумеется банк (или другой получатель подписи) здесь тоже не страдает. Да и страховая рано или поздно стрясёт деньги с государства, ибо ГОСТ (в лице ФАПСИ)

    гарантировал, что правильный результат, при проверке ЭЦП обеспечивает неизменность документа: &nbsp &nbsp &nbsp &nbsp &nbsp "Внедрение системы ЭЦП на базе настоящего стандарта обеспечивает защиту предаваемых сообщений от подделки, искажения ... При совпадении значений r' и u получатель принимает решение о том, что полученное сообщение подписано данным отправителем и в процессе передачи не нарушена целостность сообщения, т.е. М1=М"



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





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


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


    &nbsp &nbsp &nbsp &nbsp &nbsp Конечно, первопричиной подобной проблемы стала странная позиция разрабочиков стандарта, решивших, что мат. ограничения можно вводить законадательно?!


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


    pre>
    любой специалист в области криптографии вам совершенно

    обоснованно заявит, что стоикость криптосистемы в первую очередь

    зависит от качества ключевой информации ( в том числе и случайного ключа - прим авт.).

    Все остальное есть второстепенно. Можно использовать любой наворочанный алгоритм

    преобразования данных при нулевом ключе. И самое смешное, что

    сертификат от ФАПСИ вы получите. Ибо нет ни одной бумаги на то, как, из чего

    и каким образом должна генерироваться ключевая информация. /pre>



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


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

    &nbsp &nbsp &nbsp &nbsp &nbsp

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

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

    &nbsp &nbsp &nbsp &nbsp &nbsp 2) Не проще ли страховой попытаться доказать, что при данных a,q,p не существует k E [1;q-1], таких что r'== 1 ?

    &nbsp &nbsp &nbsp &nbsp &nbsp Нет. Если бы авторы госта ограничились одной операцией остатка, тогда конечно удалось бы (a^k mod p ==1 только при k==q, что противоречит граничным условиям). Но там есть ещё одна операция остатка - mod q.

    &nbsp &nbsp &nbsp &nbsp &nbsp r'= a^k (mod p) (mod q).



    &nbsp &nbsp &nbsp &nbsp &nbsp Это значит, нам дополнительно придётся доказывать, что не существует значений k таких, что a^k (mod p) == iq+1 где i любое натуральное целое, меньше (p-1/q). Вряд ли это вообще можно доказать аналитически. При переборе придётся проверить все возможные k или i. т.е. даже при "малом" диапазоне p (2^509..512), перебрать примерно 2^256 значений, что займёт несколько столетий.


    &nbsp &nbsp &nbsp &nbsp &nbsp 3) Что делать злоумышленнику, если кто-нибудь догадается затребовать секретный (x1) ключ (или случайный для последней подписи). Ведь их у него нет?

    &nbsp &nbsp &nbsp &nbsp &nbsp Просто отдать ключевую дискету (или токен), предварительно её испортив . На заявление, что дискета не работает ответить, что лично у него всё работало, доказательство - подписанные ранее сообщения и сертификат с контрольной подписью.

    &nbsp &nbsp &nbsp &nbsp &nbsp Со случайным ключём вообще нет поводов для беспокойства, согласно п.4 ГОСТа "число k, которое генерируется в процедуре подписи сообщения ... должно быть уничтожено сразу после выработки подписи."





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

    &nbsp &nbsp &nbsp &nbsp &nbsp Я очень благодарен Д. Леонову, за то, что он рискнул репутацией A HREF="http://www.bugtraq.ru/"> bugtraq.ru /a> и выкладывал, содержащие ошибки черновые варианты сообщений об ошибке до того, как они прошли широкую проверку, и без регулярно мешявшему их на всё новые и новые версии.

    &nbsp &nbsp &nbsp &nbsp &nbsp Неоценимую помощь оказали критика и консультации А. Волчкова - президента A HREF="http://www.libertarium.ru/libertarium/rca"> Российской криптологической ассоциации /a>

    &nbsp &nbsp &nbsp &nbsp &nbsp Также большое спасибо A HREF="http://www.firebox.ru"> И. Камолову /a>, Маркову Н. А., Олегу Ф., Радовцеву Д. , Макаровой О., аспиранту ДВО РАН Осиповой М. А., Наталье Б., Владу ??? (сybervlad), и всем кто присылал замечания и предложения по опубликованным методам.

    &nbsp &nbsp &nbsp &nbsp &nbsp

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



    &nbsp A HREF="http://sssr.h1.ru/4GostR34.11-94.htm">1. ГОСТ Р 34.10-94/A>

    &nbsp A HREF="http://www.bifit.com/gost3410-2001.zip"> 2. ГОСТ 34.19-2001. /A>

    &nbsp A HREF="http://www.bugtraq.ru/cgi-bin/forum.mcgi?type=sb&b=15"> 3.Форум Bugtraq.ru, где обсуждались ранние редакции /A>

    &nbsp A HREF="http://www.libertarium.ru/libertarium/rca">4. Российская криптологическая ассоциация /A>

    &nbsp A HREF="http://www.pvti.ru/dis.htm"> 5.Ещё одна уязвимость цифровой подписи /A>





    &nbsp &nbsp &nbsp &nbsp





    &nbsp &nbsp &nbsp &nbsp &nbsp &nbsp &nbsp &nbsp





    С Уважением
    &nbsp &nbsp &nbsp &nbsp &nbsp &nbsp &nbsp &nbsp


    &nbsp &nbsp &nbsp &nbsp


    A HREF="mailto:tcsvarka@marine.su">А. В. Кобец (Komlin), avkvladru@mail.ru /A>



    Полный вариант статьи здесь

  • #2
    В статье есть ошибка (опечатка) в доказательстве универсальной подписи. Большой роли она не играет, но лучше исправить . Кстати зачем оно (доказательство) вообще нужно, если есть вывод? Только место занимает.

    Об ошибке:
    Оригинал ( по состоянию на утро 21-го)

    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. Что и требовалось доказать.


    Предлагаю более корректный вариант:

    ... i=[(q-1)*v / q] =[v-v/q]=v-1; т.к. v / q =1 по определению

    Отсюда
    (a^v*a^(qv)*a^(-v)*a^(-qv)*a^q) %p %q =a^q % p %q
    По определению (a^q) %p ==1 . Что и требовалось доказать.

    Мораль: не надо писать избыточных доказательств, от них только опечаток больше

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

    Комментарий


    • #3
      Всем доброе утро!

      Хотелось бы добавить небольшой комментарий по поводу приведенной схемы
      универсальной подписи.

      Рассмотренный вариант сводится к вычислению на базе числа x0 значения
      y1 = p - a^{x0} mod p и позиционировании его как открытого ключа.
      При этом утверждается невозможность нахожения соответствующего ему
      x1 (a^{x1} = y1 mod p). Но, как утверждает автор, это и не требуется.

      Далее, участники дискуссии (в частности, Сергей Леонтьев) достаточно
      убедительно продемонстрировали, что такого x1 вообще не существует.
      Но при этом все же осталось неясным, как можно эффективно распознать
      мошенничество (при знании x0 можно доказать, что x1 не существует,
      но x0 известен лишь злоумышленнику, а он вряд ли его выдаст).

      Тем не менее, есть простой и эффективный алгоритм для распознания данной
      схемы, с использованием лишь открытой информации (а именно, ключа y1).
      Для этого достаточно вычислить y1^q mod p. Легко видеть, что
      для любого "честного" открытого ключа это число будет равно 1, а
      для "подставного" (в схеме Komlin'а) - равно p-1.

      В самом деле,

      y^{q} = (a^{x})^{q} = (a^{q}^){x} = 1 mod p ("честный" ключ)

      y1^{q} = (-y)^{q} = (-1)^{q} ( a^{x}^{q} ) = (-1)^{q} = -1 mod p ("подставной" ключ)

      Второе равенство следует из того, что q нечетно.

      Таким образом, ключ y1 может быть отвергнут при регистрации (либо на стадии
      разбора конфликта), поскольку не может быть сформирован корректной
      реализацией ГОСТ.

      Таким образом, "чистая" схема Komlin'а неприменима (может быть распознана
      при попытке применения).

      Тем не менее, это рассуждение не является полным решением вопроса,
      поскольку потенциально возможны различные модификации схемы. Например,
      вместо y1 = p - y0 mod p можно положить y1 = t*y0 mod p, где t^3 = 1 и
      потребовать выполнения условия z2 = 3n вместо z2 = 2n (в обозначениях
      статьи Komlin'а).

      Дальнейшие рассуждения на эту тему - в следующем сообщении.

      С уважением,
      Алексей Чиликов.

      Комментарий


      • #4
        Всем доброе утро!

        В порядке дальнейшего исследования схемы Komlin'а рассмотрим некоторое
        ее обобщение.

        Во-первых, разобъем процедуру проверки подписи на два этапа

        1. Вычисление u'( s,r', M ) = a^{z1} y^{z2} mod p
        2. Вычисление u ( s,r', M ) = u' mod q и сравение u со значением r'

        Назовем подпись (s,r') универсальной для набора сообщений
        M_1, ... M_n, если u( s,r', M_i ) = r' mod q.
        Соответственно, назовем подпись (s,r') сверхуниверсальной
        для набора сообщений M_1, ... M_n, если u'( s,r', M_i ) = r mod p
        и r = r' mod q. (r p).

        Очевидно, что универсальная подпись подходит ко всем сообщениям M_i.
        Также очевидно, что сверхуниверсальная подпись является универсальной
        для того же набора (и тоже подходит ко всем M_i).

        Схема Komlin'а позволяет строить сверхуниверсальные подписи для
        некоторых классов сообщений. Ни один из предложенных вариантов не
        позволяет строить универсальные подписи, не являющиеся
        сверхуниверсальными. Поэтому я полагаю, что будет корректно
        рассматривать сверхуниверсальные подписи в целом, как некоторое
        обобщение идеи Komlin'а (в предыдущем сообщении я приводил еще пример
        сверхуниверсальной подписи).

        Теперь рассмотрим, какие вообще бывают сверхуниверсальные подписи.

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

        Рассмотрим пару сообщений M_1, M_2 и обозначим соответствующие значения
        хеш-функций через h_1, h_2. Рассмотрим систему уравнений:

        a^{z1_1} y^{z2_1} = a^{z1_2} y^{z2_2} = r mod p
        z1_i = s v_i mod q
        z2_i = (q-r) v_i mod q
        v_i = h_i^{q-2} mod q

        Далее имеем

        a^{z1_1-z1_2} y^{z2_1-z2_2} = 1 mod p

        Теперь возникает естественное желание избавиться от редукции по
        модулю q в формулах для z. Поскольку a^q = 1 mod p, то с z1_i проблем не
        возникает. Для работы с z2_i сделаем следующее. Назовем y "хорошим" ключом,
        если y^q = 1 mod p и "плохим" в противном случае.
        Рассмотрим сначала случай "хороших" ключей.
        В этом случае можно записать такое уравнение

        a^{ s (v_1-v_2) } y^{ (q-r) (v_2-v_1) } = 1 mod p

        или же такое

        ( a^{s} y^{-r} ) ^ {v_2-v_1} = 1 mod p

        Отметим, что v_2 != v_1 поскольку h_2 != h_1, а возведение в степень q-2
        по модулю q - обратимая операция. Таким образом имеем

        t^v = 1 mod p, где 0 |v| q-1 , t = ( a^{s} y^{-r} ).

        Однако t^q = 1 mod p.

        Действительно, t^q = ( a^{qs} y^{-qr} ) = (a^q)^s (y^q)^{-r} = 1 mod q

        поскольку y - "хороший" ключ.

        Но тогда t = 1 mod p, так как v и q взаимно просты.
        А значение r = t^{v_1} mod p.

        Следовательно r = 1 mod p для любой сверхуниверсальной подписи, если ключ
        y - хороший.

        Что из этого следует и как разобраться с "плохими" ключами -
        в следующем сообщении.

        С уважением,
        Алексей Чиликов.

        Комментарий


        • #5
          Всем доброе утро!

          Прежде чем сделать выводы из того, что r = 1, попробуем разобраться
          с "плохими" ключами.

          Еще одно определение. Назовем ключ y "честным", если он может быть
          представлен как y = a^x mod p для некоторого x. По сути это обозначает,
          что он может являться открытым ключом в ГОСТе. Действительно, если
          y = a^x mod p, то y = ( a^{x mod q} ) mod p, т.е. y - открытый ключ
          для секретного ключа x' = x mod q (в ГОСТе требуется, чтобы секретный ключ
          не превосходил q).
          Соответственно, ключ, не являющийся "честным", назовем "нечестным".

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

          Утверждение: Ключ "честный" тогда и только тогда, когда он "хороший".

          Действительно, если y = a^x, то y^q = a^{xq} = (a^q)^x = 1 mod p, т.е.
          y - "хороший".
          Обратно, пусть y^q = 1 mod p. Все числа вида a^x mod p (x = 0, 1, ..., q-1)
          различны, их ровно q, и они являются корнями стерени q из 1 в поле F_p.
          Стало быть, других корней нет, а y является корнем. Значит y = a^x mod p при
          некотором x. Очевидно также, что такой x единственен в отрезке [0, q-1].

          Зачем нужно это утверждение? Во-первых, чтобы не рассматривать "плохие"
          ключи. Они не могут быть открытыми ключами, и их бессмысленно
          использовать в схемах подписи - поскольку можно эффективно доказать, что
          парного секретного ключа к ним не существует. Во-вторых, существование
          x, соответствующего y пригодится в последующих рассуждениях.

          Детали - в следующем сообщении.

          С уважением,
          Алексей Чиликов.

          Комментарий


          • #6
            Всем доброе утро!

            Итак, наступило время довести рассуждения до логического конца.

            Теперь у нас имеется "хороший" ключ y, и мы знаем, что r = 1 mod p и
            что существует единственный x, для которого y = a^x mod p. Более того
            ( a^{s} y^{-r} ) = 1 mod p. Заметим, что x мы вычислить не можем,
            но его существование и единственность доказаны лишь на основании открытых
            данных.

            Отсюда имеем a^{s-xr} = 1 mod p , или s = xr mod q.

            Теперь самое время вспомнить, что x есть не что иное, как секретный ключ,
            и в соответствии с процедурой выработки подписи s = xr + kh mod q.
            Отсюда можно сделать вывод, что в данном случае kh = 0 mod q.
            Поскольку h известен и не делится на q, следовательно k делится на q.
            Такая ситуация невозможна для корректной реализации ГОСТ.

            Несложно заметить, что в рассуждениях нигде не предполагалось знание
            секретного x. Т.е., обнаружить попытку применения мошенничества
            с выработкой сверхуниверсальной подписи (частным случаем которой является
            схема Komlin'а) несложно даже с использованием только открытой информации
            (ключа и двух одинаково подписанных сообщений). Более того, можно
            математически доказать некорректность реализации процедуры подписи,
            не зная заранее ни секретного ключа, ни случайного k.

            Однако же представляется интересным сделать еще один шаг.

            Из доказанных равенств

            s = xr mod q
            r = 1

            следует полная компрометация секретного ключа.
            Действительно, x = s mod q.

            Теперь, зная ключ, можно еще раз проверить все ранее проведенные
            рассуждения. Более того, реально единственная сверхуниверсальная подпись
            будет иметь вид (x,1) - первый пример из работы Komlin'а. Все остальные
            сверхуниверсальные подписи требуют выработки "плохого" открытого ключа,
            который может быть эффективно распознан на стадии регистрации
            (по критерию y^q = 1 mod p).

            Таким образом, по моему мнению, представленная схема не может
            быть использована для эффективной атаки на ГОСТ.

            Тем не менее, исследования Komlin'а и материалы обсуждений могут
            представлять большой интерес для разработчиков прикладных решений в
            области ЭЦП.

            Наиболее интересны, на мой взгляд, следующие результаты:

            критерий сверхуниверсальной подписи r = 1 mod p
            критерий проверки открытого ключа y^q = 1 mod p

            Эти проверки есть смысл использовать при практических реализациях ЭЦП.

            С уважением,
            Алексей Чиликов.

            Комментарий

            Пользователи, просматривающие эту тему

            Свернуть

            Присутствует 1. Участников: 0, гостей: 1.

            Обработка...
            X