Всем добрый вечер!
В порядке дальнейшего исследования схемы 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 - хороший.
Что из этого следует и как разобраться с "плохими" ключами -
в следующем сообщении.
С уважением,
Алексей Чиликов.
> Всем добрый вечер! > > Хотелось бы добавить небольшой комментарий по поводу > приведенной схемы > универсальной подписи. > > Рассмотренный вариант сводится к вычислению на базе числа > 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'а). > > Дальнейшие рассуждения на эту тему - в следующем сообщении. > > С уважением, > Алексей Чиликов. > > > Механизм мошеничества с цифровой подписью на > базе > > российского стандарта ГОСТ Р 34.10-94 > > > > > > > > Вступление. <p> > > В настоящее время банковские ( и многие > другие > > деловые операции) практически немыслимы без > привлечения > > методов цифровых подписей. > > В мире негласным стандартом стали > алгоритмы, > > основанные на методе Эль-Гамаля (El Gamal), в > частности - > > американском стандарте DSA. В Российской Федерации, > > разумеется не сочли возможным слепо следовать > зарубежным > > разработкам и применили свой метод, незначительно > > отличающийся формулой вычисления > > цифровой подписи. Главным результатом этого > нововведения > > стала возможность произвести махинацию с цифровой > подписью > > заключающуюся в отправке неверно подписанного > документа, с > > последующим отказом от него. > > Примерная механика мошенничества такова: > вначале > > используется 1-я уязвимость ГОСТа позволяющая вполне > > легально сформировать "слабую подпись", т.е. подпись, > из > > которой может быть легко вычислен секретный ключ. В > > принципе, после этого можно отказаться уже от любого > > документа, но и с другой стороны нельзя доказать, что > он не > > был послан Вами. > > Конечно, подобная ситуация уже приемлема, когда Вы > > распоряжаетесь не своими деньгами, а государственными, > но > > ГОСТ позволяет и большее. > > После того как вы "засветили" свой ключ, > можно > > сформировать платёжку на ООО- "однодневоку" с > подписью, > > которая успешно пройдёт все требуемые стандартом > проверки, > > но не будет являться корректной, по отношению к > данному > > документу. После этого уже можно смело идти и заявлять > о > > хищении денежных средств. > > Чтобы не судиться с банком (т.к. > последний > > может долго и успешно защищаться, переадресовывая Ваши > > претензии к государственным органам сертификации, > > навязавшим ему подобную схему проверок) проще > застраховать > > финансовые операции и получить страховку спустя два > месяца, > > по окончании предварительного следствия. > > Этой ошибке подвержен только Российский > ГОСТ Р > > 34.10-94. > > > > 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, - фактически , 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. > > > > > > > > 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^0 =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^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) > > > > > > Разумеется, саму по себе это подпись > > использовать нельзя, т.к. объяснить знание посторонним > > злоумышленником x невозможно. Но вот в сочетании с > > предварительной отсылкой "слабой подписи" подобный > вариант > > вполне объясним. > > > > Кроме того, что данная подпись подходит к > любому > > документу она имеет ещё одно замечательное достоинство > , > > очевидно, что подобный набор значений не может быть > выдана > > Вашей программой ни при каких условиях ( это легко > доказать > > исходя из простоты q и требований к значениям > случайного > > ключа и хэша ). Это значит, что выждав сутки, можно > > "просмотреть выписки", и бежать в банк, потом, ещё > сутки с > > непонимающим видом искать "специалиста", и наконец не > > торопясь, бежать в милицию с заявлением о хищении. > Пока они > > вообще поймут, о чём идёт речь, деньги станут уже > > недосягаемы для правоохранительных органов. Скорее > всего, > > потрепав пару дней нервы работникам банка, следователь > > сложит дело в сейф к другим "глухарям". Дальше суд (а > > лучше страховка) и за вычетом небольших накладных > расходов > > Вы удваиваете свой капитал. Разумеется эта схема может > > успешно применяться и банками по отношению друг к > другу, и > > вообще всеми, кто использует ГОСТ по цифровой > подписи. > > > > > > > > 5. Дополнения и комментарии. > > Как такое могло случиться? > > > > > Конечно, первопричиной подобной проблемы > > стало странная позиция разрабочиков госта, решивших, > что > > мат. ограничения можно вооить законадательно?! > > Но есть ещё одна причина исключительно точно > изложенная > > Игорем Камоловым (www.firebox.ru), очень точно > описавшему > > ещё одну проблему ГОСТа > > > > любой специалист в области криптографии вам совершенно
> > обоснованно заявит, что стоикость криптосистемы в
> первую
> > очередь
> > зависит от качества ключевой информации ( в
> том
> > числе и случайного ключа - прим авт.).
> > Все остальное есть второстепенно. Можно использовать
> любой
> > наворочанный алгоритм
> > преобразования данных при нулевом ключе. И самое
> смешное,
> > что
> > сертификат от ФАПСИ вы получите. Ибо нет ни одной
> бумаги на
> > то, как, из чего
> > и каким образом должна генерироваться ключевая
> информация.
> > ---
> > > > > > Вообще-то причина, по которой Россия > решила > > отказаться от общепринятого стандарта малопонятны. (В > > DSA(DSS) и классическом алгоритме Эль-Гамаля, такой > приём > > невозможен, т.к. универсальная подпись будет иметь > вид > > (0,1), что запрещено по определению.) Ссылки на более > > удобный для расчёта алгоритм бессмысленны, т.к. все > > вычисления выполняются компьютером. В вариант, что > > разрабатывавшие ГОСТ математики (и проверявшие его > > криптоаналитики ), решили, что математические > ограничения > > можно вводить законодательно как-то не верится... Что > нам > > остаётся думать??? > > Благодарности > > > Я очень благодарен Д. Леонову, за > то, что > > он рискнул репутацией bugtraq.ru и выкладывал, > содержащие > > ошибки черновые варианты этой статьи до того, как они > > прошли широкую проверку, и без регулярно мешявшего их > на > > всё новые и новые версии. > > > > Также большое спасибо Волчкову А. > А. > > (www.gsmrus.ru), указавшему на серьёзные недоработки > > предыдущих публикаций), а так же Маркову Н. А., Олегу > Ф., > > Радовцеву Д. , Макаровой О. и всем кто присылал > замечания > > и предложения по опубликованным методам. > > > > > > > > > > С Уважением > > > > > > > > <A HREF="mailto:tcsvarka@marine.su">А. В. Кобец > > (Komlin), avkvladru@mail.ru </A>
|