Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| | | | |
Зачем спорить с банком, если есть страховка? 17.04.02 16:09 Число просмотров: 2830
Автор: cybervlad <cybervlad> Статус: Elderman
|
> cybervlad - много придирок не по делу (реклама, "X-на
> заборе" и т.д.). Насчёт "юридической защиты" - это конечно
> хорошо, но всё-таки латание дыр,да и с крупными клиентами
> такой номер врядли пройдёт.
насчет рекламы - в результате глюка пропал мой ответ, в котором я подробно высказался на эту тему.
> и без тебя придумают :))). В этом cybervlad прав. Заметь, у
> него не было серьёзных замечаний по математике. Там всё
> правильно.
замечаний не было, потому что я ее не проверял - верил на слово.
собственно, даже за правильными выкладками проблемы не видно.
поехали по порядку.
1. какой смысл расматривать k=0, если из стандарта ЯВНО следует, что это невозможно (0 < k < q). соответственно, последующие рассуждения - в сад.
2. k=1. такая гипотеза делается мнимым злоумышленником (Александр говорит о способе "разгласить" ключ и остаться читстым) на основании r=a. но k=1 ничем не отличается от других предварительно посчитанных вариантов, только r будет сравниваться не с a, а с другой константой. единственная уникальность k=1 в том, что можн овычислять подпись не зная ключа, но нафига мучиться, если X при известном k легко вычисляется?
вероятность k=1 не выше других значений. реальный злоумышленник никогда не будет даже пытаться использовать это предпололжение, посему заявление абонента о случайной утечке не канают.
3. y1=y-p вообще ни в какие ворота не лезет. для УЦ есть документальное свидетельство принадлежности данного открытого ключа абоненту (собственноручная подпись на распечатке). он знать ничего не знает о секретном ключе Х. как и что доказывать? если пытаться предъявить "истинный" ключ Х, то не срастется проверка y1= a^ x. а если его "потерять" - еще худе, потому как единственное доказательство заверенная распечатка открытого ключа. однозначно, что подпись мог сформировать только обладатель Х (соответствующего Y) или обладатель X1 (соответствующего Y1). вычислить x по y - нерешаемая задача (с этим-то хоть спорить не будем?). утверждение, что мифический злоумышленник вычислил Х (т.к. в случае "утери" предполагается что у клиента был ключ Х1) врядли будет принято судом в качестве неопровержимого доказательства, ибо также можно утверждать, что кто-то просто "угадал" секретный ключ.
|
|
<theory>
|
Механизм мошеничества с цифровой подписью на базе российского стандарта 12.04.02 07:09 [Бяша, Biasha, !mm]
Автор: Komlin Статус: Незарегистрированный пользователь
Отредактировано 13.05.02 11:26 Количество правок: 6
|
Уважаемые читатели это сообщение успело устареть. Более подбробное и полное описание новых ошибок находится в библиотеке bugtraq.ru
Ссылка на статью ниже:
Ошибка в Новом ГОСТе
|
| |
Пресса об ошибке :) 13.05.02 11:52
Автор: Экспертик Статус: Незарегистрированный пользователь
|
Удивительно, но наша пресса в кои-то веки откликнулась на проблемы ЭЦП.
Ссылка:
http://webplanet.ru/article/873.html
Что ещё интереснее, там всё правильно написано, да ещё очень неплохой комментарий дан насчёт возможной причины ошибок.
----------------------
Как указывал президент российской ассоциации криптологов А. Волчков:
«... технологии защиты гостайны несколько иные, и по этому мысля
«государственными категориями» бизнес схемы легко упустить».
Действительно, основная задача ФАПСИ — разработка средств защиты
гостайны. Какому нормальному секретчику придёт в голову мысль
неправильно выбирать пароль?
Если рассматривать ситуацию с шифрованием и защитой от искажения
подобные приёмы бессмысленны по определению. Цифровая подпись же
решает совсем иные задачи — однозначную идентификацию лица
пославшего сообщение, т.е. защиту от непорядочности именно
шифрующего, не так-то легко перестроить мышление на 180 градусов.
Отсюда и все проблемы российских стандартов ЭЦП.
------------------
Не иначе сам Волчков писал :)
В общем согласна, только хотелась бы заметить, что плохие пароли обычно видираются не специально а по разгильдяйству, поэтому процедуре выработки пароля следует уделять не меншуе внимание, чем алгоритму шифровки.
|
| |
Черновик статьи. Ваши замечания(предложения)? 04.05.02 18:37
Автор: 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>
|
| | |
Статья выложенна в "библиотеку" 07.05.02 11:29
Автор: Komlin Статус: Незарегистрированный пользователь
|
Спасибо всем кто принял участие в обсуждении представленного материала.
Статья выложенна в библиотеку по адресу
Статья
|
| |
Ошибка не нова, новы результаты её применения к новому ГОСТу 28.04.02 17:23
Автор: (Не)Случайный посетитель Статус: Незарегистрированный пользователь
Отредактировано 28.04.02 17:33 Количество правок: 2
|
Уважаемые коллеги, описанная ошибка не столь уж и нова. Проблема расчёта подписи без секретного ключа в методах El-Gamal'я известна около 7 лет.
См. например книгу В. В. Ищенко "Основы современной криптологии", издание 1995 г.
стр. 219
" Следует также заметить, что ещё один вид подписей (n,n) может быть сформирован и без участия секретного ключа ... Вероятность этого крайне мала из-за принятого условия q<<p и не снижает стойкости метода по сравнению с подбором ключа".
Именно поэтому для DSS требуется подтверждение владения ключём.
Описанный Комлином случай r=s=h=(q-d+1)Q (mod q) (и его модификация r=s, описанная ниже А. Чиликовым) являются частным вариантом этого утверждения.
Новым в данном сообщении является отмеченный Aлександром Комлиным факт, что вероятность саморасчёта подписи в применении к новому ГОСТу приобретает приемлемые величины, а требование подтвержения владения ключём явно не отображено.
Разумеется, я не смею утверждать, что A. V. Komlin ( или А. Чиликов) не выводили этих формул самостоятельно (они очевидны), но хотелось бы отметить, что акцент в опубликованной заметке следовало сделать на идее определения открытого ключа для заданных значений хэша и вероятности её осуществления в ГОСТе.
Вывод очевидных истин в начале статьи необязателен, он только утомляет читателя.
|
| | |
Ошибка не нова, новы результаты её применения к новому ГОСТу 30.04.02 03:43
Автор: Serge3 Статус: Незарегистрированный пользователь
Отредактировано 30.04.02 03:44 Количество правок: 1
|
Здравствуйте,
> …
> а требование подтверждения владения ключом явно не
> отображено.
Не согласен, в разделе “5.2 Параметры цифровой подписи” стр. 7 “рабочего экземпляра ГОСТ Р 34.10-2001", высказано само требование владения ключом: “Каждый пользователь схемы цифровой подписи должен обладать личными ключами: - ключом подписи – целым числом d...”. А механизмы реализации проверки выполнения этого требования (путём подтверждения или иными путями) относятся к системам ЭЦП (СКЗИ) и выходят за рамки самого стандарта.
Ситуация с d полностью аналогична ситуации с k (или с другими параметрами и/или промежуточными величинами…), т.е. стандарт наложил требование или ограничение, а как оно должно быть реализовано дело уже конкретной системы ЭЦП (СКЗИ). Или ситуации с обсуждавшимся ранее требованиям на p, q, a, k, x и y в п.3 ГОСТ Р 34.10-94 стр. 1.
> Вывод очевидных истин в начале статьи необязателен, он
> только утомляет читателя.
Согласен, вместо изложения вывода формул лучше сослаться, причём по возможности, на учебник. Это для тех, кому не очевидно. А оставить только оценку трудоёмкости подбора открытого ключа и соответствующей подписи для различных алгоритмов.
> очевидны), но хотелось бы отметить, что акцент в
> опубликованной заметке следовало сделать на идее
> определения открытого ключа для заданных значений хэша и
> вероятности её осуществления в ГОСТе.
А так же на необходимости соблюдать все требования стандарта в системах ЭЦП (СКЗИ).
--
LSE, Сергей Леонтьев, Крипто-Про, http://www.CryptoPro.ru
|
| | | |
Как обойти требование проверки секретного ключа 03.05.02 16:43
Автор: Komlin Статус: Незарегистрированный пользователь
|
> “Каждый пользователь схемы
> цифровой подписи должен обладать личными ключами: - ключом
> подписи – целым числом d...”. А механизмы реализации
> проверки выполнения этого требования (путём подтверждения
> или иными путями) относятся к системам ЭЦП (СКЗИ) и выходят
> за рамки самого стандарта.
> LSE, Сергей Леонтьев, Крипто-Про, http://www.CryptoPro.ru
Re: Сергей как я уже упоминал выше абсолютно безнадёжная (для государства) ситуация складывается при взаимной заинтересованности сторон в имитации финансовых потерь (с целью предъявления иска ФАПСИ или просто списания прибылей, благо эта схема не имеет верхней границы убытка).
Нетрудно создать программу которая будет удовлетворять всем нормам ГОСТа, в том числе проверять существование ключа контрольной подписью ( о процедуре проверке существования в госте ни слова, поэтому применим любой метод, тем более общепринятый).
Делается это так. Контрольная подпись проверяется по заданному хэшу h0.
Полученная подпись и хэш заносятся в разряд скомпроментированых (всё как
обычно).
Вот только пример хэша (h0) для контрольной подписи (s0,r0) выбирается заранее на основе уже расчитанного открытого ключа (Q).
Значение h0 расчитывается от случайных (a,b).
r0=X(a*P-b*Q)
h0=b'r
s0=a'h
Предсказать значение h0 в этом случае конечно невозможно, но это и не нужно, главное заранее согласовать его с получателем сертификата :)
Теперь у нас есть доказательство существования секретного ключа (сертификат).
Пусть прокуратура объясняет его наличие если собирается обвинить "Алису" в мошенничестве.
------------------------
Re: Юрию aka "Неслучайный посетитель":
Как Вы сами мне указали
"в описании DSA было чётко написанно , что наличие ключа
подтверждается по факту подписи контрольного_документа_
следовательно, этот трюк там не проходит ==> утверждение, что ГОСТ уступает своим однокласникам справедливо.
|
| | | | |
Как обойти требование проверки секретного ключа 03.05.02 17:47
Автор: Serge3 Статус: Незарегистрированный пользователь
Отредактировано 03.05.02 18:08 Количество правок: 3
|
Здравствуйте,
> Нетрудно создать программу, которая будет удовлетворять всем
> нормам ГОСТа
Не согласен. Если в стандарте сказано, что должен владеть, то это означает, что система ЭЦП (СКЗИ) должна обеспечить выполнение этого условия таким образом, что ЛЮБЫЕ ДОПУСТИМЫЕ действия нарушителя не смогут нарушить его выполнения. В противном случае, система ЭЦП (СКЗИ) не полностью удовлетворяет требованиям стандарта.
> , в том числе проверять существование ключа
> контрольной подписью ( о процедуре проверке существования в
> госте ни слова, поэтому применим любой метод, тем более
> общепринятый).
Так сказать, общепринятым методом можно назвать запрос на сертификат X.509 <http://www.ietf.org/rfc/rfc2459.txt> в формате CRMF (PKCS#10) <http://www.ietf.org/rfc/rfc2510.txt, http://www.ietf.org/rfc/rfc2511.txt, http://www.rsasecurity.com/rsalabs/pkcs/pkcs-10/index.html>, который, грубо говоря, содержит подпись на секретном ключе абонента от значения хэш-функции вычисленной по конкатенации открытого ключа абонента и реквизитов абонента.
На первый взгляд, наличие такого запроса подтверждает владение абонентом секретным ключом. К недостаткам, следует отнести не полноту контроля реализации требования ГОСТ Р 34.10-94 о случайности секретного ключа, т.к. обычные регламенты на основе X.509 удовлетворяются проверкой на не повторяемостью открытых ключей абонентов.
> ...
> Re: Юрию aka "Неслучайный посетитель":
> Как Вы сами мне указали
> "в описании DSA было чётко написано, что наличие ключа
> подтверждается по факту подписи контрольного_документа_
>
> следовательно, этот трюк там не проходит ==>
> утверждение, что ГОСТ уступает своим одноклассникам
> справедливо.
Что-то я в FIPS 186-2 (см. http://csrc.nist.gov/publications/fips/fips186-2/fips186-2.pdf), который полностью описывает DSA, не заметил этих требований. Вероятно, я плохо смотрел. Александр, пожалуйста, уточните ссылку и предписанный алгоритм проверки.
--
LSE, Сергей Леонтьев, Крипто-Про, http://www.CryptoPro.ru
|
| | | | | |
Тогда просто "найдём" секретный ключ :) 04.05.02 10:54
Автор: Komlin Статус: Незарегистрированный пользователь
Отредактировано 04.05.02 11:01 Количество правок: 1
|
Ниже описан способ как найти секретный и открытый ключи для подписи h (h,h) в случае, когда подписывающий самы выбирает граничные условия (это не противоречит ГОСТУ) или имеет место сговор для имитации убытков. Заодно даны комментарии к предыдущим ответам.
> Не согласен. Если в стандарте сказано, что должен владеть,
> то это означает, что система ЭЦП (СКЗИ) должна обеспечить
> выполнение этого условия таким образом, что ЛЮБЫЕ
> ДОПУСТИМЫЕ действия нарушителя не смогут нарушить его
> выполнения.
А как насчёт НЕДОПУСТИМЫХ, но НЕДОКАЗУЕМЫХ?
Вообще-то я не согласен. Подпись по хэшу неплохая проверка,а
разработчик программы не должен отслеживать ещё и ошибки ГОСТа :), но что бы не спорить давайте просто найдём секретный ключ, чтобы строго выполнить требования X.509.
> который, грубо говоря, содержит подпись на секретном
> ключе абонента от значения хэш-функции вычисленной по
> конкатенации открытого ключа абонента и реквизитов
> абонента.
Собственно, в описанной ситуации взаимной заинтересованности, или случае когда подписывающий сам выбирает граничные условия "найти" секретный ключ совсем несложно.
Выберем любым приемлемым методом q P==0 (далее P0). В ГОСТе эта процедура никак не регламентируется и не описывается поэтому наверное стоит использовать приёмы ECDSA ( может ФАПСИ выпускала какие-нибудь рекомендации?). Легко видеть, что на самом деле в качестве P может выступать любая точка кратная P0.
Подберём как описанно в статье хэш h такой, что точка H(x=h) кратна P0 (qH==0).
Укажем в качестве граничного значения P=nH (по определению P кратная H кратна и P0), где 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).
>
> > ...
> > Re: Юрию aka "Неслучайный посетитель":
...
> > следовательно, этот трюк там не проходит ==>
> Что-то я в FIPS 186-2 (см.
> http://csrc.nist.gov/publications/fips/fips186-2/fips186-2.
> pdf), который полностью описывает DSA, не заметил этих
> требований. Вероятно, я плохо смотрел.
Я тоже - это утверждение высказал Юрий, ему я и отвечал.
Юрий отзовитесь!!!
Впрочем, в свете сказанного выше, это уже неважно.
>
> --
> LSE, Сергей Леонтьев, Крипто-Про, http://www.CryptoPro.ru
|
| | |
Ошибка не нова, новы результаты её применения к новому ГОСТу 29.04.02 05:21
Автор: Komlin Статус: Незарегистрированный пользователь
|
Уважаемый Юрий.
Я разумеется не претендую на авторство формул соответствия между ключём и хэшем,
они действительно очевидны и скорее всего общеизвестны. Полагаю Алексей Чиликов тоже.
Скорее всего в материалах конференций можно найти и другие удобные формулы для
конктретного параметра.
Новым в предложенном методе являлась идея подбирать корректный открытый ключ исходя
из документа (Или из документа и подобранного r такого, что R(r) == (Pi), X(R)<q
как предлагает Алексей)
И , как правильно Вы заметили, тот факт , что из-за неудачно подобранного соотношения q/p <1/4
эти операции в новом ГОСТе могут быть произведены за малое время.
По поводу компоновки документа
> Уважаемые коллеги, описанная ошибка не столь уж и нова.
> Проблема расчёта подписи без секретного ключа в методах
> El-Gamal'я известна около 7 лет.
>
> См. например книгу В. В. Ищенко "Основы современной
> криптологии", издание 1995 г.
>
> стр. 219
>
> " Следует также заметить, что ещё один вид подписей (n,n)
> может быть сформирован и без участия секретного ключа ...
> Вероятность этого крайне мала из-за принятого условия
> q<<p и не снижает стойкости метода по сравнению с
> подбором ключа".
>
> Именно поэтому для DSS требуется подтверждение владения
> ключём.
>
> Описанный Комлином случай r=s=h=(q-d+1)Q (mod q) (и его
> модификация r=s, описанная ниже А. Чиликовым) являются
> частным вариантом этого утверждения.
>
> Новым в данном сообщении является отмеченный Aлександром
> Комлиным факт, что вероятность саморасчёта подписи в
> применении к новому ГОСТу приобретает приемлемые величины,
> а требование подтвержения владения ключём явно не
> отображено.
>
> Разумеется, я не смею утверждать, что A. V. Komlin ( или А.
> Чиликов) не выводили этих формул самостоятельно (они
> очевидны), но хотелось бы отметить, что акцент в
> опубликованной заметке следовало сделать на идее
> определения открытого ключа для заданных значений хэша и
> вероятности её осуществления в ГОСТе.
>
> Вывод очевидных истин в начале статьи необязателен, он
> только утомляет читателя.
>
>
>
>
>
|
| | |
Суть ошибки именно в большом q/p и вычислении ключа по h. Сам подбор ключа рассмотрен даже в учебниках 29.04.02 03:25
Автор: Экспертик Статус: Незарегистрированный пользователь
|
> Уважаемые коллеги, описанная ошибка не столь уж и нова.
> Проблема расчёта подписи без секретного ключа в методах
> El-Gamal'я известна около 7 лет.
>
> См. например книгу В. В. Ищенко "Основы современной
> криптологии", издание 1995 г.
Суть ошибки именно в большом q/p и вычислении ключа по h. Сам подбор ключа рассмотрен даже в учебниках
Новым в данном сообщении является отмеченный Aлександром
> Комлиным факт, что вероятность саморасчёта подписи в
> применении к новому ГОСТу приобретает приемлемые величины,
> а требование подтвержения владения ключём явно не
> отображено.
А также идея вычислять Q (открытый ключ) по H
> Разумеется, я не смею утверждать, что A. V. Komlin ( или А.
> Чиликов) не выводили этих формул самостоятельно (они
> очевидны), но хотелось бы отметить, что акцент в
> опубликованной заметке следовало сделать на идее
> определения открытого ключа для заданных значений хэша и
> вероятности её осуществления в ГОСТе.
Именно так там и деется
> Вывод очевидных истин в начале статьи необязателен, он
> только утомляет читателя.
Ну не для всех они очевидные.
|
| |
Серьёзная ошибка в новом ГОСТе 28.04.02 12:51
Автор: Lexy Статус: Незарегистрированный пользователь
|
Всем доброе утро!
Можно показать более общий факт, чем тот который указан автором.
А именно:
Для любых значений h, s, r, если существует точка R, такая что X(R) = r,
можно найти открытый ключ Y, такой что подпись (s,r) будет корректна
для сообщения с хешем h.
Иными словами, не надо требовать, чтобы хеш
сообщения был X-координатой некоторой точки, и для каждого сообщения
можно построить много "независимых" подписей (с разными открытыми
ключами).
Делается это так:
Пусть заданы h = h(M), s, r, r = X(R).
Вычисляем
z1 = sh^{-1} mod p
z2 = -rh^{-1} mod p
Вычисляем
Q = z2^{-1} (R - z1 P);
Убеждаемся, что
C = z1 P + z2 Q = z1 P + (R - z1 P) = R
X(C) = X(R) = R
Таким образом, подпись (s,r) подходит для хеша h (т.е сообщения M).
При этом нет никаких ограничений на h, следовательно можно подписывать
любые сообщения (вероятность равна 100%, а не q/p).
Аналогичные рассуждения, видимо, проходят и для остальных стандартов.
Осталась одна проблема - никто (в том числе и злоумышленник) не знает
секретного ключа d для Y. Таким ообразом, ключ Y - одноразовый, им можно
подписать только сообщение M. И что будет делать мошенник, если его
попросят подписать что-то еще?
Вывод - достаточно при регистрации ключа потребовать подписания
контрольного сообщения.
С уважением,
Алексей Чиликов.
|
| | |
Вероятность такая же. 28.04.02 16:47
Автор: Экспертик Статус: Незарегистрированный пользователь
|
Приветствую Алексей.
Ваш предложение (s==r) вместо (h==r==s) конечно упрощает оригинальный Комлинский метод, но вероятность его такая же (q/p).
r= X(C) %q == X(kP) %q, следовательно мы не можем строго утверждать
что для Q = z2^{-1} (R - z1 P);
qQ==0
Мы можем это утверждать только с вероятностью q/p.
То есть это по прежнему ошибка именно нового ГОСТа (и возможно ECDSA - надо только разобраться с его диапазонами)
Кстати я не согласна с утверждением A.V.K что для ГОСТа "худшая" вероятность составляет 1/16
IMHO в худшем случае вероятность 2^254 / 2^256 = 1/4.
Это конечно не принципиально, но пару секунд на подборе сэкономит. ;)
> Всем доброе утро!
>
> Можно показать более общий факт, чем тот который указан
> автором.
> А именно:
> Для любых значений h, s, r, если существует точка R, такая
> что X(R) = r,
> можно найти открытый ключ Y, такой что подпись (s,r) будет
> Вычисляем
> Q = z2^{-1} (R - z1 P);
>
> Убеждаемся, что
> C = z1 P + z2 Q = z1 P + (R - z1 P) = R
>
> X(C) = X(R) = R
>
> Таким образом, подпись (s,r) подходит для хеша h (т.е
> сообщения M).
>
> При этом нет никаких ограничений на h, следовательно можно
> подписывать
> любые сообщения (вероятность равна 100%, а не q/p).
>
> Аналогичные рассуждения, видимо, проходят и для остальных
> стандартов.
>
> Осталась одна проблема - никто (в том числе и
> злоумышленник) не знает
> секретного ключа d для Y. Таким ообразом, ключ Y -
> одноразовый, им можно
> подписать только сообщение M. И что будет делать мошенник,
> если его
> попросят подписать что-то еще?
>
> Вывод - достаточно при регистрации ключа потребовать
> подписания
> контрольного сообщения.
>
> С уважением,
> Алексей Чиликов.
|
| | | |
И все же не такая :)) 29.04.02 02:46
Автор: Lexy Статус: Незарегистрированный пользователь
|
Добрый вечер, Наталья!
Я не совсем понял, почему Вы решили, что s == r ?
Я написал, что для h подходит подпись вида (s, r), где s любое,
а r = X(R). При этом, естественно, R должно быть допустимой
точкой эллиптической кривой, то есть qR = 0. Но это решается
перебором R, и не накладывает ограничений на h.
Легко проверить, что тогда и qQ = 0 (что и требуется).
Суть в том, что можно подписать любое сообщение, а не только
те, у которых хороший хеш.
Вообще же, я согласен с Юрием (a-ka НеСлучайный Посетитель) -
выкладки довольно просты, а интересен контекст применения.
Т.е. необходимо потребовать проверку ключа при регистрации.
С уважением,
Алексей Чиликов
> Приветствую Алексей.
>
> Ваш предложение (s==r) вместо (h==r==s) конечно упрощает
> оригинальный Комлинский метод, но вероятность его такая же
> (q/p).
>
> r= X(C) %q == X(kP) %q, следовательно мы не можем строго
> утверждать
> что для Q = z2^{-1} (R - z1 P);
>
> qQ==0
>
> Мы можем это утверждать только с вероятностью q/p.
> То есть это по прежнему ошибка именно нового ГОСТа (и
> возможно ECDSA - надо только разобраться с его
> диапазонами)
>
>
>
> Кстати я не согласна с утверждением A.V.K что для ГОСТа
> "худшая" вероятность составляет 1/16
> IMHO в худшем случае вероятность 2^254 / 2^256 = 1/4.
>
> Это конечно не принципиально, но пару секунд на подборе
> сэкономит. ;)
>
|
| | | | |
Нет. Именно такая q/p:))) 29.04.02 03:13
Автор: Экспертик Статус: Незарегистрированный пользователь
Отредактировано 29.04.02 11:45 Количество правок: 2
|
> Я написал, что для h подходит подпись вида (s, r), где s
> любое,
> а r = X(R). При этом, естественно, R должно быть допустимой
> точкой эллиптической кривой, то есть qR = 0. Но это
> решается
> перебором R, и не накладывает ограничений на h.
> Легко проверить, что тогда и qQ = 0 (что и требуется).
Имелось в виду, что с учётом r' =kP %q вероятность встретить при переборе qR==0 и составляет q/p.
То есть перебирать всяко придётся, что h, что r. Т. е метод применим только для ГОСТа (возможно и для ECDSA ).
Хотя конечно перебирать r быстрее и проще, чем варьировать пробелами в документе вычисляя подходящее h (если это имеет значение при переборе 4-х вариантов).
> Я не совсем понял, почему Вы решили, что s == r ?
Подождите, тогда уже я не совсем поняла, как в Вашем методе, посторонний зная Q, h, может рассчитать для них обратно s,r?
Ведь суть ошибки была не просто в вычеслении Q для M (h,e), но и в вычислении любым желающим подписи для них.
Мне не неясно, как из формулы Q = z2^{-1} (R - z1 P), получить обратно R, с учётом того, что X(R) входит в z2==X(R)*e %q?
> Суть в том, что можно подписать любое сообщение, а не
> только
> те, у которых хороший хеш.
Суть Комлиновской статьи и была в том, что в практических условиях хороший хэш можно подобрать для любого документа, например варьируя пробелами.
> Вообще же, я согласен с Юрием (a-ka НеСлучайный Посетитель)
> -
> выкладки довольно просты, а интересен контекст применения.
> Т.е. необходимо потребовать проверку ключа при регистрации.
Или проверку qQ==0 (y^q %q ==1) как Вы и предлагали в прошлом комментарии.
Вообще непонятно как авторы ГОСТа могли его пропустить. Или мы что-то недопонимаем?
> С уважением,
> Алексей Чиликов
>
> > Приветствую Алексей.
> >
> > Ваш предложение (s==r) вместо (h==r==s) конечно
> упрощает
> > оригинальный Комлинский метод, но вероятность его
> такая же
> > (q/p).
> >
> > r= X(C) %q == X(kP) %q, следовательно мы не можем
> строго
> > утверждать
> > что для Q = z2^{-1} (R - z1 P);
> >
> > qQ==0
> >
> > Мы можем это утверждать только с вероятностью q/p.
> > То есть это по прежнему ошибка именно нового ГОСТа (и
> > возможно ECDSA - надо только разобраться с его
> > диапазонами)
> >
> >
> >
> > Кстати я не согласна с утверждением A.V.K что для
> ГОСТа
> > "худшая" вероятность составляет 1/16
> > IMHO в худшем случае вероятность 2^254 / 2^256 = 1/4.
> >
> > Это конечно не принципиально, но пару секунд на
> подборе
> > сэкономит. ;)
> >
|
| | |
Серьёзная ошибка в новом ГОСТе 28.04.02 16:17
Автор: Komlin Статус: Незарегистрированный пользователь
Отредактировано 28.04.02 16:23 Количество правок: 2
|
Добрый день Алексей
Если не трудно сообщите мне Ваше мыло (на avkvladru@mail.ru)
Спасибо , Ваше предложение ещё больше упрощает дело, т.к. не надо тратить время на подбор h (хотя и перебрать десяток значений было нетрудно).
> Аналогичные рассуждения, видимо, проходят и для остальных
> стандартов.
Увы, мне кажется что нет, ведь в "обычных" метотах r= a^x mod p mod q ,
значит мы не можем гарантировать что рассчитанный y будет в диапазоне допустимых значений.
Вернее можем, но с той же вероятностью (q/p).
> Осталась одна проблема - никто (в том числе и
> злоумышленник) не знает
> секретного ключа d для Y. Таким ообразом, ключ Y -
> одноразовый, им можно
> подписать только сообщение M. И что будет делать мошенник,
> если его
> попросят подписать что-то еще?
Проще всего, не дожидаясь этой просьбы передать ключевой дискету (токен) в руки получателя (следователя) предварительно испортив.
Потом заявить, что всё работало.
Или
Сослаться на то, что после появления подписи, решили, что данный ключ был узнан (подобран) и сгенерили новый (старый естественно не сохранили). И только потом выяснили что подпись можно было рассчитать без ключа и решили судиться.
Впрочем, как я уже писал этот приём лучше проводить при обоюдной заинтересованности сторон с целью выдвижения претензий к государству.
> Вывод - достаточно при регистрации ключа потребовать
> подписания
> контрольного сообщения.
Это я и предлагал. Можно придумать и другие методы защиты, но суть в том, что это должно бы быть прописано разработчиками стандарта, а не нами.
> С уважением,
> Алексей Чиликов.
|
| |
Серьёзная ошибка в новом ГОСТе 28.04.02 03:45
Автор: Serge3 Статус: Незарегистрированный пользователь
|
Здравствуйте,
> …
> документу подпись без знания секретного ключа (далее
> назовем эту подпись "независимой") . Эта ошибка
> присутствует во всех методах основанных на идее Эль-Гамаля,
Есть у меня смутные воспоминания о том, что где-то в 90-х годах в рекомендации X.509 (или около них) была добавлена рекомендация (требование) о необходимости подтверждения со стороны клиента PKI факта владения закрытым ключом. Может быть, оно появилось в результате обнаружения фактов того же типа, о DSS, а быть может другого, о RSA или чего ни будь ещё. Как ни будь, надо будет найти хвосты.
> но из-за неудачно сформированных требований к граничным
> условиям именно в новой редакции ГОСТа она имеет
> наибольшую вероятность практические перспективы.
Мне кажется, что в ECDSA ("новой" редакции DSA) вероятность выше.
> ...
> Вероятность того, что требуемое Q
> окажется корректным ключём q/2p (учитывая квадратичную
> связь между x,y). Проверить допустимость полученного ключа
> Q можно по формуле qQ=0.
Похоже на правду. Малые значения p, в основном, связаны с математическими и техническими ограничениями на поле EC(F(p)). И, поэтому, общеприняты.
> Таким образом, если разработчики
> программы ограничатся минимально рекомендуемым диапазоном
> p, вполне возможно, незначительно варьируя текстом
> документа подобрать такое значение ключа проверки, что
> подпись для данного документа может быть рассчитана без
> знания секретного ключа. На этом же основании вполне можно
> и отказаться от неё.
Подогнать значение хэш-функции от документа под необходимые значения открытого ключа (ей) считается не возможным.
Так что реальным "опасным воздействием" может быть только получение открытого ключа, при котором подпись будет "независимой" для данного документа.
Но, по-моему, в общепринятой модели угроз для ЭЦП это бессмысленно. Да и в произвольном случае, не ясно к каким "опасным последствиям" это может привести, ведь за пользователем регистрируется открытый ключ по любому.
Опять всё сводится к тому, что бы зарегистрировать открытый ключ, подписать уже один единственный документ и отмазываться, типа "я – не я и подпись не моя". Так что, надо рыть дальше.
--
LSE, Сергей Леонтьев, Крипто-Про, http://www.CryptoPro.ru
|
| | |
Серьёзная ошибка в новом ГОСТе 28.04.02 04:57
Автор: Komlin Статус: Незарегистрированный пользователь
|
> Здравствуйте,
> Мне кажется, что в ECDSA ("новой" редакции DSA) вероятность
> выше.
Выше врядли, разве что такая же .Надо будет посмотреть
Но по-моему там хэш 128 а p 256. Соответственно ~ вероятность 2^-256
>
> > ...
> > Вероятность того, что требуемое Q
> > окажется корректным ключём q/2p (учитывая квадратичную
> > связь между x,y). Проверить допустимость полученного
> ключа
> > Q можно по формуле qQ=0.
>
> Похоже на правду. Малые значения p, в основном, связаны с
> математическими и техническими ограничениями на поле
> EC(F(p)). И, поэтому, общеприняты.
>
> > Таким образом, если разработчики
> > программы ограничатся минимально рекомендуемым
> диапазоном
> > p, вполне возможно, незначительно варьируя текстом
> > документа подобрать такое значение ключа проверки, что
> > подпись для данного документа может быть рассчитана
> без
> > знания секретного ключа. На этом же основании вполне
> можно
> > и отказаться от неё.
>
> Подогнать значение хэш-функции от документа под необходимые
> значения открытого ключа (ей) считается не возможным.
> Так что реальным "опасным воздействием" может быть только
> получение открытого ключа, при котором подпись будет
> "независимой" для данного документа.
Имеется в виду обратный процес. Выбираете документ и его хэш, e. Подгоняете под него открытый ключ,так, чтобы подпись для e была "независимой" (вероятность этого == q/2p~ 1/2- 1/16 ). То есть сформировав c десяток незначительно отличающихся редакций документа (например пробелами в поле примечания) можно выбрать из них такой что для него имеется "независимая подпись"
> Но, по-моему, в общепринятой модели угроз для ЭЦП это
> бессмысленно. Да и в произвольном случае, не ясно к каким
> "опасным последствиям" это может привести, ведь за
> пользователем регистрируется открытый ключ по любому.
В том, что он заявит, что этот документ подписал не он а подпись вычисленна в рез-те ошибки ГОСТа
Обратное доказать невозможна .
> Опять всё сводится к тому, что бы зарегистрировать открытый
> ключ, подписать уже один единственный документ и
> отмазываться, типа "я – не я и подпись не моя". Так что,
> надо рыть дальше.
Да. А чем плох этот приём при обоюдной заинтересованности сторон?
Ведь по законону контрольная подпись нигде не требуется - эта уже мера дополнительной комплексной защиты. Так что и одной подписи может хватить.
|
| | | |
Серьёзная ошибка в новом ГОСТе 28.04.02 06:44
Автор: Serge3 Статус: Незарегистрированный пользователь
|
Здравствуйте,
> > Мне кажется, что в ECDSA ("новой" редакции DSA) вероятность
> > выше.
> Выше вряд ли, разве что такая же. Надо будет посмотреть
> Но, по-моему там хэш 128 а p 256. Соответственно ~
> вероятность 2^-256
Старый, добрый SHA-1 – 160 бит. На счёт новой хэш-функции я не в курсе.
FIPS-2 (см. http://csrc.nist.gov/publications/fips/fips186-2/fips186-2.pdf) алгоритм не определяет, но определяет кривые для федерального использования. Общее описание в п.1.1 стр.24 достаточно похожее по размерностям (кофакторы: 1, 2 или 4, а по другому и не могло быть:) на наш ГОСТ Р 34.10-2001. При описании кривых п.2-3 стр.28-48 следует иметь в виду следующее соответствие обозначений (ГОСТ-ECDSA): p – p, q – r, m – m.
--
LSE, Сергей Леонтьев, Крипто-Про, http://www.CryptoPro.ru
|
|
|
подробно о проекте
Анализ криптографических сетевых...
