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

1. Введение.

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

Речь идёт о подписи, доказуемая вероятность получения (в том числе преднамеренного) которой меньше вероятности подбора хэша или ключа.

Эта возможность появилась благодаря нескольким (безобидным по отдельности ) недоработкам нового российского ГОСТа 34.19-2001: неудачным граничным условиям и отсутствию чётких требований к генерации одного из параметров подписи (точки P).

Существуют два возможных механизма мошенничества :

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

С учётом того, что внедрение нового стандарта начнётся со второй половины нынешнего (2002) года, условия складываются весьма подходящие.

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

Эта ошибка в зависимости от реализации может иметь место и в ECDSA.

2. Описание ошибки.

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

Простейший их случай следует из равенства h==s==r.

Для DSA

h==s== r=ya (mod p) (mod q) ( y=a^x(mod p), x-секретный ключ ,p,q простые q < < p)

ГОСТа Р 34.10-94

h==s==r=ay^(q-1) (mod p) (mod q) ( -//- )

ГОСТа 34.19-2001

h==s==r= x(P-Q) (mod q) ( Q=dP, d-секретный ключ, qP==0, q - простое, x(P) - означает x-координата точки P, 0 -нулевая точка)

ECDSA

h==s==r = x(Q-P) (mod q) (-//-).

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

(Один из обобщённых вариантов формул дан в сообщении А. Чиликова ).

Давайте рассмотрим обратную ситуацию: можно ли вычислить (подобрать) значения открытого ключа для заданного хэша. Из приведённых формул хорошо видно, что вероятность такого решения = q/p.

С учётом диапазонов граничных условий "старых" методов вероятность подбора в DSA составляет < 2^-300, действующем ГОСТе ~ 2^-256. Проверить сущестрование ключа для заданного числа можно по формуле h^q (mod p)==1

Иная ситуация в методах с эллиптическими кривыми: в ECDSA диапазоны p, q не оговорены, в вводимом российском стандарте p > 2^256, q принадлежит (1^254; 1^256). Т.е. вероятность обратного решения около 1/4!( из определения поля и формул ГОСТа № 1, 4-7 следует , что координаты x,y любых точек кривой целые числа < p).

Проверить допустимость ключа Q можно по формуле qH=0. Q=P-H(h) ( H(h) - точка с x-координатой h, y-координату можно рассчитать по уравнению кривой).

Таким образом, если разработчики программы ограничатся минимально рекомендуемым диапазоном p, вполне возможно, незначительно варьируя текстом документа (например пробелами в поле "примечания" платёжки) подобрать такое значение ключа проверки, что подпись для данного документа может быть рассчитана без знания секретного ключа. На этом же основании вполне можно и отказаться от неё (схемы мошенничества ниже).

У нас осталась одна нерешенная проблема: как теперь вычислить секретный ключ?

В случае когда сообщник выбирает граничные условия "найти" секретный ключ совсем несложно. Главное заранее указать "коллеге" какому h он должен соответствовать.

Выберем любым приемлемым методом q (или пару q *P1==0) . В ГОСТе процедура выбора параметров подписи никак не регламентируется и не описывается:

"Параметрами схемы ЦП являются:

...

точка P !=0 эллиптической кривой E, с координатами (xp,yp),удовлетворяющая равенству qP==0)."

Легко видеть, что на самом деле в качестве P может выступать и любая точка кратная P.

Подберём как описано в выше хэш h такой, что q H(h) ==0. Укажем в качестве граничного значения P=nH (по определению P кратная H кратна и P1), где n -любое.

Тогда открытый и секретный ключи равны соответственно Q=P-H, d=n' - 1

где n' обратное n. n'n== 1(mod q) или n'=n^(q-2) (mod q)

После этого формируем ключ, сертификат X.509, отсылаем пару нормальных сообщений и, наконец, запланированное сообщение с подписью h (h,h). Учитывая, что:

a) подпись легко рассчитывается без знания секретного ключа (h0==r0==s0==x(P-Q)),

б) вероятность случайного формирования (или даже умышленного подбора для h0) подобной "трижды симметричной" подписи ==1/q^2, что даже выше чем просто подбор хэша (1/q).

можно смело заявлять, что эту подпись отсылали не Вы, а кто-то сторонний подобрал хэш для простейшего случая "независимой" подписи. Если деньги и не вернут (банк за дырки стандарта не ответчик) то уж посадить за мошенничество точно не смогут.

Есть и второе решение (кстати, применимое ко всей линейке методов): перейти к более общим подписям вида h1 (r1,r1). (h1!=r1). В этой схеме сообщник не нужен.

Вычисление пары ключей производится по формулам (они следуют из приведённых в форуме , но дополнительно, позволяют определить секретный ключ)

r1= x(P) (или x(nP) )

r'*r1 == 1(mod q)

Q=(1-h0*r')P

d=1-h0*r' (1-h0*r'*n).

IMHO, этот способ конечно проще, но и рискованнее, т.к. подобная схема может быть вскрыта обвинением (хотя догадаться о схеме не значит доказать ей применение). Кроме здесь вероятность появления подписи и подбора хэша одинакова (1/q). Также непонятно, почему "сторонний злоумышленник" выбрал конкретное сочетание h1,r1 вместо более простого случая h0 (h0,h0). Поэтому есть некоторый риск получить приговор или по крайней мере посидеть в СИЗО до суда.

Примечание: аналогичная схема принципиально возможна и в ECDSA, но там всё зависит от выбора параметров p,q разработчиком. Кроме того, в FIPS-2 имеются рекомендованные образцы кривых и параметров подписи. Поэтому стандартные примеры уязвимы только для ошибок второго типа. Никаких предположений об результатах процесса я строить не могу, т.к. американские законы о коммерческом мошенничестве гораздо старше и совершенние российских.

3. Возможные схемы мошенничества

Классическая ситуация: бухгалтеру крупного госучреждения очень хочется сбросить крупную сумму на ООО "Однодневка", но при этом не хочется объяснять, зачем :).

Последовательность действий:

1) готовится несколько вариантов платёжки (достаточно 4-8);

2) находится общий язык с одним из сотрудников банка (разработчиков программы), что при переходе на новый ГОСТ будет выбрано значение P, кратное одному из хэшей (или наоборот сотрудник банка выходит с подобным предложением);

3) по вводу программы формируется пара ключей как описанно выше;

4) отсылается пара-тройка нормальных платёжек;

5) отсылается заготовленная "фальшивка";

6) убедившись, что платёжка сделала своё дело, бухгалтер утверждает, что он ничего не отсылал.

7) приглашенные эксперты достаточно быстро констатируют три факта:

a) подпись легко рассчитывается без знания секретного ключа (h==r==s==x(P-Q));

b)вероятность формирования подобной "трижды симметричной" подписи ==1/q*q, что даже выше чем просто подбор хэша (1/q);

c) по видимому речь идёт о каком-то взломе.

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

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

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

2) Для коммерческих структур возможен вариант с предварительной страховкой форс-мажора в банковских и торговых операциях. В этом случае влетает страховая компания. Банк также становится невольным сообщником мошенника. Последовательность та же, что и в случае 1 ( В российских условиях у этой схемы есть иной риск: не дожить до получения страховки ;) ).

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

Во всех этих схемах есть общая деталь: крайним окажется государство, т.е. наши с Вами карманы

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

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

Неоценимую помощь оказали критика и консультации А. Волчкова - президента Российской криптологической ассоциации , С. Леонтьева http://CryptoPro.ru , А. Чиликова, И. Камолова , Маркова Н. А., Олега Ф., Радовцева Д. , Макаровой О., аспиранта ДВО РАН Осиповой М. А., Натальи Б., Влада ??? (aka сybervlad), и всех, кто присылал замечания и предложения по опубликованным методам.

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

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


С Уважением
А. В. Кобец (Komlin), avkvladru@mail.ru

обсудить  |  все отзывы (14)
Выберите оценку 10 (изумительно) 9 (отлично) 8 (хорошо) 7 (неплохо) 6 (средненько) 5 (сойдет) 4 (так себе) 3 (слабо) 2 (плохо) 1 (отвратительно) Вернуться в раздел Перейти к рейтингу Перейти к обсуждению Вернуться к статье	[37340; 2; 5.5]