BugTraq.Ru
Русский BugTraq
http://www.bugtraq.ru/library/crypto/ecdh.html

Дешифровка ECDH
A.V.Komlin (Кобец)
Опубликовано: dl, 19.11.03 09:31

1. Введение

         Данная статья посвящена новому методу атак методов Diffie-Hellman на эллиптических кривых с ключами многоразового использования. Строго говоря, как и в известной "атаке по таймеру" [1] речь идёт не столько об ошибках самого метода и/или программистов, сколько о проблемах, возникающих при практической реализации коммутативных операций над кривыми групп Fp и F2k.
         Метод распределения ключей, предложенный Диффи и Хэллманом в прошлом столетии :) и по сей день считается наиболее эффективным способом аутентификации.
         Суть его очень проста - шифрование с открытым ключём используется только для генерации общего для двух пользователей симметричного ключа, с помощью которого и идёт обмен информацией. Матаппарат несложен:
Пусть y1 = ax1 %p и y2 = ax2 % p - открытые ключи пользователей. Тогда они могут рассчитать известный только им общий ключ по формуле
Q = ax1x2== y1x2 == y2x1;
         Адаптация этого метода к эллиптическим кривым [2] любой группы недолга - нужно лишь заменить операцию возведения в степень операцией умножения. :)
Y1 = x1*A; Y2 = x2*A;
Q = x1*x2*A === x2*Y1 == x1Y2;

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

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

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

3. Примеры простейших атак.

1)Кривая в поле Fp. [2]

         Эллиптическая кривая в этом поле имеет вид
y2 = x3+a*x+b (1)

         Типичная реализация умножения Q=xY имеет вид:

T=Y
FOR i= 0 TO bitsize(x)-1
T= double(T); -- операция удвоения T=2T
if bit(x,i)=1 then
Y=Y+T;
end
END
         Поскольку в операции удвоения и сложения этой кривой не входит b, то можно выбрать кривую с малым порядком группы или просто точку с необычными свойствами.

         Рассмотрим операцию удвоения
(x;y)+(x;y)=(x3;y3) (2)
x3=( (3x2+a)/2y) 2 - 2x mod p; (2x)
y3=(3x2+a)*(x-x3)/2y -y mod p; (2y)

         Что будет, если подставить несуществующую в данной кривой точку Y0=(x0,y0) такую, чтобы, x оставалось постоянным после операций 2x (x3 == x == x0)? Из формулы 2y очевидно, что в этом случае T будет принимать только противоположные значения (x0;y0) и (x0;-y0) == (-1)*(x0;y0), а результирующая точка Q примет одно из трёх значений (0,0) [point of infinity], (x0;-y0) или (x0;y0). Если же в качестве стартового значения использовать не значение Y0 == (x0;y0), а приводящую к нему при какой-либо операции удвоения H = Y0/2 , то результирующе Q будет равно :
H+(odd_bit - nob)*T, где odd_bit- число ненулевых битов в чётных позициях секрета, а nob - в нечётных.
         При 106 битном ключе результирующая точка может иметь не более 53 вариантов. Зная соотношение чётных/нечётных ненулевых битов секретный ключ нетрудно подобрать перебором даже после первого запроса, но никто не мешает нам и повторять операции с Hi=Y2/2i.

         "Отравленную" точку Y0, рассчитать совсем несложно, учитывая, что мы не связаны конкретными значениями x,y.
x0=( (3*x02+a)/2*y) 2 - 2*x0 mod p; (3а)
x = (3x2+a)2/(4*y*y) - 2x (3б)
3x = (3x*x+a)^2 /(4*y*y)
y0^2 mod p = (3x*x+a)2/(12x) mod p (4)

Подставляем x0=1 и получаем
y02 == (3+a)2/12 %p

         Рассмотрим эту задачу на примере приведённой в [2] группы точек F23 (a=1,b=4)
y2 == x3+x+4 mod 23 (1a)

x0=1
y02=4*4/12=16*2 %p =9
Y0= (1;3) или (1;20);
         Подставляя найденные значения в уравнение 1, находим параметр кривой b=7. Теперь можно найти
H=(4,12)
H+H=Y0.

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

         Наиболее перспективными на сегодня считаются кривые в бинарных полях,
y2+x*y = x3+a*x+b

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

         Вспомним одно из их свойств :
(x;y) + (x;x+y) = 0 (point of infinity);
         Очевидно, что точка (0;z) вполне удовлетворяет обоим требованиям, следовательно операция T+T выдаст нулевую точку (кстати, точка (0;b) формально является реально существующей точкой кривой, хотя и не входящей в циклическую группу.) Cоответственно, результатом операции 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 или x4 = -b (в бинарном поле)
         Отсюда следует, что операция удвоения точки
(m1;z1) где m4 = -b ( поля F2m) даст точку (0,z),
соответственно k*(m;z1) будет иметь два варианта в зависимости от значения предпоследнего бита = bit(k,1)*(m;z1)+ d1*(0;z)

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

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

         Полагаю, варьируя значения точек, можно предложить ещё много вариантов атаки, я рассмотрел лишь самые очевидные случаи.

Список литературы и полезные ссылки:

  1. Пауль Кочер. Временной анализ реализаций Диффи-Хеллмана, RSA, DSS и других систем.
  2. Don Jonson, Alfred Menezes, The Elliptic Curve Digital Signature Algoritm. 24-02-2000.
  3. Павел Семьянов. Криптографический ликбез.
  4. Сборник криптобиблиотек с исходными кодами.
  5. Первая редация данной статьи ( с другими примерами) и небольшое обсуждение.
С Уважением, A.V.Komlin, avkvladru@mail.ru


обсудить  |  все отзывы (2)

[19862; 16; 5.5]




  Copyright © 2001-2024 Dmitry Leonov Design: Vadim Derkach