А. В. Кобец (Komlin). Механизмы махинации с подписью в новом российском стандарте ЭЦП ГОСТ 34.19-2001. 16.05.2002 1. Введение. Как правило, уязвимость в методах цифровой подписи ищется в области подбора хэша

или расчета секретного ключа. В данной статье используется другой подход: поиск "спорной" подписи такой, что нельзя доказать, что она отправлена владельцем секретного ключа. Речь идет о подписи, доказуемая вероятность получения (в том числе преднамеренного) которой меньше вероятности подбора хэша или ключа. Эта возможность появилась благодаря нескольким (безобидным по отдельности) недоработкам нового российского ГОСТа 34.19-2001: неудачным граничным условиям и отсутствию четких требований к генерации одного из параметров подписи (точки ). Существуют два возможных механизма мошенничества. Первый и наиболее "надежный" (позволяющий убедительно утверждать о взломе со стороны) доступен лицам имеющим отношение к выбору параметров подписи (например разработчикам программы, сотрудникам банка и т.д.). При нем выбирается значение точки, позволяющей создать "фальшивую" подпись для заданного значения хэша. Этим может воспользоваться сообщник (ведь при грамотном поведении предварительный сговор доказать практически невозможно). При этом способе вполне можно получить "утраченную" сумму, например с помощью страховки. С учетом того, что внедрение нового стандарта начнется со второй половины нынешнего (2002) года, условия складываются весьма подходящие. Второй доступен любому пользователю, но в нем злоумышленник может рассчитывать лишь на то, что его вину нельзя строго доказать (в основном благодаря несовершенству российского УПК). Конечно, многих устроит и такой вариант, но все он рискован. Эта ошибка в зависимости от реализации может иметь место и в ECDSA. 2. Описание ошибки. Достаточно давно известны формулы, позволяющие вычислить значение подписи для некоторого хэша без знания секретного ключа. Простейший их случай следует из равенства Для DSA:

--- простые, ( ). (-//-).., --- секретный ключ, Для ГОСТа Р 34.10-94:

Для ГОСТа 34.19-2001:, --- простое, Для ECDSA:

--- -координата точки (, --- секретный ключ,, --- нулевая точка).

(-//-).

В учебниках описаны и несколько вариантов более общих формул, но все они отличаются общим свойством - невозможностью получения заданного значения хэша и случайного открытого ключа ( ). Вероятность подбора значений не превышает (вероятности подбора ключа), поэтому какой-либо угрозы они не представляют. Вернее не представляли. (Один из обобщенных вариантов формул дан в сообщении А. Чиликова ). Давайте рассмотрим обратную ситуацию: можно ли вычислить (подобрать) значения открытого ключа для заданного хэша. Из приведенных формул хорошо видно, что вероятность такого решения равна. С учетом диапазонов граничных условий "старых" методов вероятность подбора в DSA составляет, действующем ГОСТе. Проверить существование ключа для заданного числа можно по формуле. Иная ситуация в методах с эллиптическими кривыми: в ECDSA диапазоны не оговорены, в вводимом российском стандарте, принадлежит. Т.е. вероятность обратного решения около ! (из определения поля и формул ГОСТа N1, 4-7 следует, что координаты любых точек кривой --- целые числа ). Проверить допустимость ключа можно по формуле. ( точка с -координатой, -координату можно рассчитать по уравнению кривой). -- Таким образом, если разработчики программы ограничатся минимально рекомендуемым диапазоном, вполне возможно, незначительно варьируя текстом документа (например пробелами в поле "примечания" платежки) подобрать такое значение ключа проверки, что подпись для данного документа может быть рассчитана без знания секретного ключа. На этом же основании вполне можно и отказаться от нее (схемы мошенничества ниже). У нас осталась одна нерешенная проблема: как теперь вычислить секретный ключ? В случае когда сообщник выбирает граничные условия "найти" секретный ключ совсем несложно. Главное заранее указать "коллеге" какому h он должен соответствовать. Выберем любым приемлемым методом (или пару ). В ГОСТе процедура выбора параметров подписи никак не регламентируется и не описывается. "Параметрами схемы ЦП являются:... точка эллиптической кривой, с координатами равенству )." Легко видеть, что на самом деле в качестве,удовлетворяющая.

может выступать и любая точка, кратная Подберем, как описано выше, хэш такой, что. Укажем в качестве граничного значения (по определению кратная кратна и ), где --- любое. Тогда открытый и секретный ключи равны соответственно --- обратное, или.,, где После этого формируем ключ, сертификат X.509, отсылаем пару нормальных сообщений и, наконец, запланированное сообщение с подписью. Учитывая, что: a) подпись легко рассчитывается без знания секретного ключа ( б) вероятность случайного формирования (или даже умышленного подбора для ) подобной "трижды симметричной" подписи равна, что даже выше, чем просто подбор хэша ( ), можно смело заявлять, что эту подпись отсылали не Вы, а кто-то сторонний подобрал хэш для простейшего случая "независимой" подписи. Если деньги и не вернут (банк за дырки стандарта не ответчик) то уж посадить за мошенничество точно не смогут. Есть и второе решение (кстати, применимое ко всей линейке методов): перейти к более общим подписям вида ( ). В этой схеме сообщник не нужен. Вычисление пары ключей производится по формулам (они следуют из приведенных в форуме, но дополнительно позволяют определить секретный ключ): (или, ( ). IMHO, этот способ конечно проще, но и рискованнее, т.к. подобная схема может быть вскрыта обвинением (хотя догадаться о схеме не значит доказать ей применение). Кроме здесь вероятность появления подписи и подбора хэша одинакова ( ). Также непонятно, почему "сторонний злоумышленник" выбрал конкретное сочетание вместо более простого случая. Поэтому есть некоторый риск получить приговор или по крайней мере посидеть в СИЗО до суда. Примечание: аналогичная схема принципиально возможна и в ECDSA, но там все зависит от выбора параметров разработчиком. Кроме того, в FIPS-2 имеются рекомендованные образцы кривых и параметров подписи. Поэтому стандартные примеры уязвимы только для ошибок второго типа. Никаких предположений об результатах процесса я строить не могу, т.к. американские законы о коммерческом мошенничестве гораздо старше и совершеннее российских. 3. Возможные схемы мошенничества Классическая ситуация: бухгалтеру крупного госучреждения очень хочется сбросить крупную сумму на ООО "Однодневка", но при этом не хочется объяснять, зачем :). ),, ), Последовательность действий: 1) готовится несколько вариантов платежки (достаточно 4--8);

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

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

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

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

6) убедившись, что платежка сделала свое дело, бухгалтер утверждает, что он ничего не отсылал. 7) приглашенные эксперты достаточно быстро констатируют три факта: a) подпись легко рассчитывается без знания секретного ключа ( b)вероятность формирования подобной "трижды симметричной" подписи равна что даже выше чем просто подбор хэша ( );

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

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

, Во всех этих схемах есть общая деталь: крайним окажется государство, т.е. наши с Вами карманы. 4. Благодарности Я очень благодарен Д. Леонову, за то, что он рискнул репутацией bugtraq.ru и выкладывал содержащие ошибки черновые варианты сообщений до того, как они прошли широкую проверку. Неоценимую помощь оказали критика и консультации А. Волчкова --- президента Российской криптологической ассоциации, С. Леонтьева А. Чиликова, И. Камолова, Маркова Н. А., Олега Ф., Радовцева Д., Макаровой О., аспиранта ДВО РАН Осиповой М. А., Натальи Б., Влада ??? (aka сybervlad), и всех, кто присылал замечания и предложения по опубликованным методам. 5. Полезные ссылки 1. ГОСТ Р 34.10-94. 2. ГОСТ 34.19-2001. 3. Форум Bugtraq.ru, где обсуждались ранние редакции. 4. Российская криптологическая ассоциация. 5. Еще одна уязвимость цифровой подписи. 6.FIPS-2 (описание DSA, ECDSA и рекомендованные параметры подписи). С уважением, mailto:tcsvarka@marine.su Комментарий Н. П. Варновского: Сообщение состоит из двух разнородных частей. В первой из них описывается способ подделки подписей для некоторых схем электронной подписи, впрочем, давно и хорошо известный. К этой части есть одно терминологическое замечание: автор называет этот способ подделки ошибкой, хотя на самом деле его некорректно квалифицировать даже как слабость схемы подписи. Очевидно, что для любой схемы подписи существуют методы, которые подделывают подпись (как с определением секретного ключа, так и без) с ненулевой вероятностью. Все известные на сегодня методы, включая и тот, который описан в сообщении, не представляют никакой угрозы стойкости схем подписи, поскольку вероятность подделки лишь незначительно отличается от вероятности угадывания секретного ключа. Надо каким-то образом эту вероятность повысить. Попытка сделать это предпринимается во второй части сообщения. Здесь всякая криптография заканчивается и автор увлеченно описывает возможные схемы мошенничества, смакуя различные уголовные подробности, вплоть до перспективы посидеть в СИзо. По этой части мы ограничимся тремя замечаниями.

1. В сообщении говорится, что в новом ГОСТе процедура выбора параметров никак не регламентируется и не описывается. Вообще, если в каком-либо стандарте на криптографическую схему нет значений параметров и алгоритмов их выбора, то это скорее достоинство, а не недостаток. Представим, например, что принят стандарт схемы подписи, в котором указано, что длина модуля должна быть равна 256 битам. А через некоторое время специалисты по теории чисел предлагают новый метод дискретного логарифмирования и выясняется, что эту длину необходимо увеличить до 512 битов. И что же, из-за этого принимать новый стандарт? Идеальный вариант, по-видимому, таков: специалисты-разработчики схемы стандарта периодически публикуют рекомендуемые значения параметров. То же самое относится и к алгоритмам выбора параметров. 2. Все описываемые в сообщении схемы мошенничества основываются на совершенно непонятно откуда взявшейся уверенности автора в том, что эксперт, получив подпись для хэш-значения и увидев, что, даст иное заключение о подлинности подписи, чем в случае, когда это равенство не выполняется. Непонятно, чем, скажем, подпись (2837, 2837) для хэша 2837 лучше или хуже, чем подпись (1923, 4155)? А что должен делать, по мнению автора, эксперт, если он увидит тройку (0001, 0002, 0003) или (1234, 5678, 9012)? 3. Забудем обо всех достижениях научно-технического прогресса и обратимся к традиционному гангстерскому сценарию ограбления банка. Можно ли ограбление осуществить таким образом, чтобы преступление почти наверняка осталось нераскрытым? Нет проблем! Для этого достаточно, чтобы вашими сообщниками были правление, совет директоров и охрана того банка, который вы собираетесь грабить!    Книги, научные публикации