информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
За кого нас держат?Страшный баг в WindowsАтака на Internet
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
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Быстрая дешифровка секретов в распределениях ключей по Diffie-Hellman на эллиптических кривых. Черновик. 11.11.03 16:01  Число просмотров: 5261
Автор: Komlin Статус: Незарегистрированный пользователь
Отредактировано 12.11.03 13:18  Количество правок: 4
<"чистая" ссылка>
Быстрая дешифровка секретов в распределениях ключей по Diffie-Hellman на эллиптических кривых.
Всем привет! Выкладываю черновик статьи в надежде получить ценные замечания, советы и предложения или просто огрестись за свои ошибки... :)

Черновик статьи.

I. Введение.

Данная статья посвящена новому методу атак методов DH на эллиптических кривых с ключами многоразового использования с использованием «несуществующей точки». Строго говоря, как и в известной «атаке по таймеру» [1] речь идёт не столько об ошибках самого метода и/или программистов, а о скрытых ловушках, возникающих при общепринятых методах эффективной реализации коммутативных операций над кривыми групп Fp и F2k.
Метод, предложенный Диффи-Хэллманом в прошлом столетии и по сей день считается наиболее эффективным способом аутентификации.
Суть его очень проста – шифрование с открытым ключём используется только для генерации общего для двух пользователей симметричного ключа, с помощью которого и идёт обмен информацией. Матаппарат также несложен:
Пусть y1=a^x1 %p и y2=a^x2%p открытые ключи пользователей. Тогда они могут рассчитать известный только им общий ключ по формуле
Q=a^x1^x2==y1^x2==y2^x1;
Адаптация этого метода к эллиптическим кривым любой группы также несложна – нужно лишь заменить операцию возведения в степень операцией умножения. :)
Y1=x1*A; Y2=x2*A;
Q=x1*x2*A===x2*Y1==x1^Y2;

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

Главная потенциальная слабость этого метода довольно очевидна - атакуемому объекту приходится выполнять операции над значениями, предоставленными посторонним лицом. Отчасти этот недостаток нивелируется тем, что при передачи значения происходит возврат не рассчитанного ключа, а лишь зашифрованного им значения, но это ограничение нередко можно обойти.
На этом, например, основаны атаки на «чётный бит» или метод малых групп.
Поэтому на реализацию DH обычно налагают доп. требования, например простоту (p-1)/2 в стандартном методе, или простой порядок группы точек в EC.

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

На первый взгляд эта возможность не открывает каких-либо серьёзных перспектив, т.к. итоговый ключ всё равно не виден, но ниже показано, что выбирая специальные (нереальные) сочетания значений координат , можно резко ограничить перечень возможных значений выдаваемого симметричного ключа и определить его простым перебором, получая в награду ценнейшую информацию об секретном ключе.
Конкретные решения зависят от атакуемой реализации, ниже приведено два простейших из них для эллиптических кривых ( в полях Fp и F2k, стандартизированных (FIPS 186-2) ).

Примеры простейших дешифровок
1. Дешифровка в поле Fp.

Если у Вас под рукой есть какая-нибудь библиотека или приложение для работы с EC попробуйте выполнить операцию удвоения с точкой вида (z,0).
Если исходить из формул -
(x;y)+(x;y)=(x3;y3)
x3=( (3x^2+a)/2y) ^2 - 2x mod p;
y3=(3x^2+a)*(x-x3)/2y -y mod p;

результатом должно быть прерывание "Деление на ноль". Не надейтесь! Ни один из вызовов аварийно не завершится!
90 % библиотек (например crypto++, ECLib) выдали точку (0,0) [point of infinity] ! Оставшиеся 10% (например - asmEC-intel.zip) - (2z;0) или (fastcrypto ) (z;0)!!!

Наиболее интересный случай 2 объясняется просто:

Дело в том, что вместо операции деления на практике используется умножение на число обратное делителю, которое находится по теореме ферма (y'=y^(p-2) mod p) или модифицированному методу Eвклида.
x3=( (3x^2+a)*(2y)^(p-2) ) ^2 - 2x
При y=0 формула существенно упрощается
x3= -2x;
y3= 0;

Поскольку в правильном множестве точек деления на ноль (y=0) не могло возникнуть по определению, то этот случай по видимому и не отслеживался (в целях оптимизации).

Случай 1 объясняется ещё проще - большинство авторов библиотек, зная что точек c y=0 не существуют, используют это значение как признак нулевой точки (в целях экономии памяти) и воспринимают задание как операцию с нулевой точкой, возвращая предопределённое zero.
Случай 3 - объяснить не могу, наверное это результат какой-то обработки DivideByZero.

Для нас особенно интересен случай 2.
Рассмотрим стандартную реализацию умножения точки на скаляр
Q=xY;

T=Y
FOR i= 0 TO bitsize(x)-1
T= T+T; -- операция удвоения T=2T
if bit(x,i)=1 then
Y=Y+T;
...
NEXT

Нетрудно видеть, что при отсутствии проверки деления (случай 2) последовательность значений T со стартовым значением (z,0) будет иметь вид
(z;0) , (-2z;0), (4z;0) … ((2^i)z;0)
а результирующее Q - сумму этих значений в поле x с учётом побитовых коэффициентов.
_x(Q)= bit(k,1)*z- bit(k,2)*2z+ bit(k,2)*4z - ... = Sum( (-2)^i* bit(k,i)*z)
_y(Q)=0
Таким образом получается ослабленные ключи, которые вполне реально вскрыть за разумное время.
Подставляя различные стартовые значения для z можно построить обычную систему уравнений длиной порядка bitsize(p), решение которой тривиально.

2) Дешифровка в поле F2m.

Наиболее перспективными на сегодня считаются кривые в бинарных полях, т.к. операции над ними занимают выполняются быстрее. Недавно FIPS-186 дополнен из списком из семи кривых этой группы, кроме того, к использованию рекомендованы кривые Koblitz'a (b=1).

Вспомним одно из их свойств :
(x;y) + (x;x+y) = 0 (point of infinity);
Очевидно, что точка (0;z) вполне удовлетворяет обоим требованиям, следовательно операция T+T выдаст нулевую точку (кстати, точка (0;b) формально является реально существующей точкой кривой, хотя и не входящей в циклическую группу.) Соответственно, результатом операции k*(0;z) будет точка (0,z) если k нечётное или нулевая точка если k mod 2=0.
Таким образом мы узнали первый бит секретного ключа, далее d1.

Рассмотрим операцию удвоения (x;y)+(x;y).
x3=x*x + b/(x*x); (в поле F2m)
при x3=0 следует x*x+b(x*x)==0 или x^4=-b (в поле F2m)
Отсюда следует, что операция удвоения точки
(m1;z1) где m^4=-b ( поля F2m) даст точку (0,z),
соответственно k*(m;z1) будет иметь два варианта в зависимости от значения предпоследнего бита = bit(k,1)*(m;z1)+ d1*(0;z), осталось только перебрать их.

Значения следующих битов мы можем установить решая уравнения
x^4+mi*x^2+b=0 в простом бинарном поле и подставляя их в качестве исходных точек.

Разумеется реальность нижеописанной атаки зависит от реализации - что проверяется первым - совпадение точек или их противоположность.

Полагаю, вариьируя значения точек, можно предложить ещё много вариантов атаки, я рассмотрел лишь самые очевидные случаи.
Пока, всё! Большая просьба высказывать свои замечания и предложения. Не исключено, что я где-то сильно ошибаюсь, поэтому и публикую данный черновик в форуме.
<theory> Поиск 






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


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