Bankir.Ru
4 декабря, воскресенье 19:13

Объявление

Свернуть
Показать больше
Показать меньше

Быстрая дешифровка секретов в распределениях ключей по Diffie-Hellman на EC

Свернуть
X
  • Фильтр
  • Время
  • Показать
Очистить всё
новые сообщения

  • Быстрая дешифровка секретов в распределениях ключей по Diffie-Hellman на EC

    Быстрая дешифровка секретов в распределениях ключей по 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 в простом бинарном поле и подставляя их в качестве исходных точек

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

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

  • #2
    Я не математик, но не понимаю, как можно брать 4-ю степень из отрицательного числа -b. Может какая-то опечатка?
    Разве в кривых допускаются комплексные числа?

    Комментарий


    • #3
      Михаил, спасибо за отклик, но Вы не заметили, что
      речь шла об ограниченных полях.
      В них запись m^4=-b - просто условность. Ей соответствует конкретное позитивное число, зависящие от вида поля,


      Например для кривых Коблица (Koblitz), данное уравнение сводится к
      m^4=1;

      Александр.
      Последний раз редактировалось nilmok; 12.11.2003, 04:55.

      Комментарий


      • #4
        Привет AVK.

        С интересом прочитал твою статью и выкладываю накопившиеся замечания прямо в форум (копию послал тебе письмом).

        По методу.

        I. Описанная тобой схема сложения точек в практическом применении имеет множество вариаций, например использование разложения в базисах выше двоичного (не понятый тобой случай 3), оптимизированные формулы расчёта для повторяющихся заданных операций и т.д. и т.п.
        Поэтому практическое применение "нереальной" точки очень ограничено и возможно в основном, для лиц детально знакомых с внутренней архитектурой атакуемого продукта, т.е. инсайдеров.
        II. Существующие схемы применения аутентификации по DH (SSL) имеют несколько уровней защиты, серьёзно осложняющих задачу "тестирования" исходного секретного ключа.


        По примерам (твой первый пример мне совсем не понравился. Думаю, практического значения он не имеет).

        I. Описанная в первом примере атака - скорее следствие неграмотнго написания алгоритмов, чем слабость метода.
        II. "Слабость" получившегося ключа из первого примера - вопрос спорный и может быть использована далеко не в каждом симметричном алгоритме. Правильнее говорить об "ослаблении" ключа за счёт обнуления половины его битов.
        III. Кривые в бинарных полях из второго примера ещё не приобрели сколько-нибудь широкого распространения даже в ECDSA. В России их судьба ещё темнее из-за принятия в качестве стандарта единственной кривой поля Fp.

        Подводя итоги:
        Не могу отрицать возможность проведения атак "нереальной точкой", но сильно сомневаюсь в их массовом применении.

        Желаю дальнейших успехов.
        Сергей Резниченко.

        P.S. Какой у тебя сейчас телефон, не могу дозвониться?

        Комментарий


        • #5
          Привет Сергей. Спасибо за ответ.


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


          Инсайдеры – тоже люди, а если серьёзно, то всё больше приложений начинает пользоваться стандартными библиотеками или выкладывать свой код для обсуждения.

          (твой первый пример мне совсем не понравился. Думаю, практического значения он не имеет).

          Главная задача примера – его понятность (или запоминаемость). Именно по этим критерия он и выбирался, а не по эффективности.


          III. Кривые в бинарных полях из второго примера ещё не приобрели сколько-нибудь широкого распространения даже в ECDSA. В России их судьба ещё темнее из-за принятия в качестве стандарта единственной кривой поля Fp.


          Две беды в России: дороги и дураки указывающие какой дорогой идти.
          Надеюсь, наиболее эффективные методы потихоньку пробъют себе дорогу и у нас.


          Не могу отрицать возможность проведения атак "нереальной точкой", но сильно сомневаюсь в их массовом применении.


          Массовыми такие атаки не были и не будут.


          P.S. Телефон не менялся. [/QUOTE]

          Комментарий


          • #6
            Исправленная и переработанная с учётом замечаний статья опубликованна в окончательном варианте по адресу

            http://www.bugtraq.ru/library/crypto/ecdh.html

            В новой редакции заменён пример атаки на кривую Fp на более универсальный и не зависящий от реализации операции удвоения.

            Комментарий

            Пользователи, просматривающие эту тему

            Свернуть

            Присутствует 1. Участников: 0, гостей: 1.

            Обработка...
            X