информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Все любят медЗа кого нас держат?Сетевые кракеры и правда о деле Левина
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Три миллиона электронных замков... 
 Doom на газонокосилках 
 Умер Никлаус Вирт 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
все доски
FAQ
IRC
новые сообщения
site updates
guestbook
beginners
sysadmin
programming
operating systems
theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Черновик статьи. Ваши замечания(предложения)? 04.05.02 18:37  Число просмотров: 4333
Автор: Komlin Статус: Незарегистрированный пользователь
Отредактировано 05.05.02 13:29  Количество правок: 1
<"чистая" ссылка>
Серьёзная ошибка нового российского стандарта ЭЦП ГОСТ 34.19-2001.
       
        1. Введение.
       
        Как правило, уязвимость в методах цифровой подписи ищется в области подбора хэша, или расчета секретного ключа. В данной статье используется другой подход: поиск "спорной" подписи, такой, что нельзя доказать, что она отправлена владельцем секретного ключа.
        Речь идёт о подписи, доказуемая вероятность получения (в том числе преднамеренного) которой меньше вероятности подбора хэша или ключа.
       
        Эта возможность появилась благодаря нескольким (безобидным по отдельности ) недоработкам нового российского ГОСТа 34.19-2001: неудачным граничным условиям и отсутствию чётких требований к генерации одного из параметров подписи (точки P).
       
        Существуют два возможных механизма мошенничества :
        Первый и наиболее "надёжный" (позволяющий убедительно утверждать о взломе со стороны) доступен лицам имеющим отношение к выбору параметров подписи (например разработчикам программы, сотрудникам банка и т.д.). При нём выбирается значение точки P, позволяющей создать "фальшивую" подпись для заданного значения хэша. Этим может воспользоваться сообщник (ведь при грамотном поведении предварительный сговор доказать практически невозможно). При этом способе вполне можно получить "утраченную" сумму, например с помощью страховки.
        С учётом того, что внедрение нового стандарта начнётся со второй половины нынешнего (2002) года, условия складываются весьма подходящие.
       
        Второй доступен любому пользователю, но в нём злоумышленник может рассчитывать лишь на то, что его вину нельзя строго доказать ( в основном благодаря несовершенству российского УПК ) . Конечно, многих устроит и такой вариант, но всё же "лучше поделиться".
       
        Эта ошибка в зависимости от реализации может иметь место и в ECDSA.
       
       
       
        2. Описание ошибки.

        Достаточно давно известны формулы, позволяющие вычислить значение подписи для некоторого хэша без знания секретного ключа.
        Простейший их случай следует из равенства h==s==r.
       
        Для DSA
        h==s== r=ya %p %q ( y=a^x%p, x-секретный ключ ,p,q простые q < < p)
        ГОСТа Р 34.10-94
        h==s==r=ay^(q-1) %p %q ( -//- )
        ГОСТа 34.19-2001
        h==s==r= x(P-Q) % q ( Q=dP, d-секретный ключ, qP==0,
        ECDSA
        h==s==r = x(Q-P) %q (-//-).
        q - простое, x(P) - означает x-координата точки P, 0 -нулевая точка)
       
        В учебниках описаны и несколько вариантов более общих формул, но все они отличаются общим свойством - невозможностью получения заданного значения хэша и случайного открытого ключа (r) . Вероятность подбора значений не превышает 1/q (вероятности подбора ключа), поэтому какой-либо угрозы они не представляют. Вернее не представляли.
        (Один из обобщённых вариантов формул дан в сообщении А. Чиликова
        http://www.bugtraq.ru/cgi-bin/forum.mcgi?type=sb&b=15&m=46106 ).
       
        Давайте рассмотрим обратную ситуацию: можно ли вычислить (подобрать) значения открытого ключа для заданного хэша. Из приведённых формул хорошо видно, что вероятность такого решения = q/p.
        С учётом диапазонов граничных условий "старых" методов вероятность подбора в DSA составляет < 2^-300, действующем ГОСТе ~ 2^-256. Проверить сущестрование ключа для заданного числа можно по формуле h^q %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(nP)
        r'*r1 == 1(mod q)
        Q=(1-z)P
        z = h0r'
        d=1-z
       
        IMHO, этот способ конечно проще, но и рискованнее, т.к. подобная схема может быть вскрыта обвинением (хотя догадаться о схеме не значит доказать ей применение). Кроме здесь вероятность появления подписи и подбора хэша одинакова (1/q). Также непонятно, почему "сторонний злоумышленник" выбрал конкретное сочетание h1,r1 вместо более простого случая h0 (h0,h0). В есть некоторый риск получить приговор или по крайней мере посидеть в СИЗО до суда. IMHO, лучше поделиться.
       
        Примечание: аналогичная схема принципиально возможна и в 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. Благодарности

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

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

         

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



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

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

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

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

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

  <A HREF="http://csrc.nist.gov/publications/fips/fips186-2/fips186-2.pdf"> 6.FIPS-2 ( описание DSA, ECDSA и рекомендованные параметры подписи ) </A>




       





               





С Уважением
               


       


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


<theory> Поиск 






Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach