без паники и всерьез
подробно о проекте
 |  |
Анализ криптографических сетевых...| главная | обзор | RSN | блог | библиотека | закон | бред | форум | dnet | о проекте |  |
|
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 в простом бинарном поле подставляя их в качестве исходных точек. Разумеется, реальность нижеописанной атаки зависит от реализации - что проверяется первым - совпадение точек или их противоположность. Полагаю, варьируя значения точек, можно предложить ещё много вариантов атаки, я рассмотрел лишь самые очевидные случаи. Список литературы и полезные ссылки:
|
 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
