Атака Хеллмана

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 14:09, 29 апреля 2016.

Атака Хеллмана была предложена в 1980-м году для решения задачи нахождения прообраза однонаправленной функции (например, в случае подбора пароля). Метод для DES-алгоритма был назван (Crypt-)Time-MemoryTrade-Off (TMTO).

Описание TMTO

Дано:

Задача: По определить т.е. ключ, на котором получен шифротекст.

Рассмотрим режим ECB ("Electronic Code Book", Электронная кодовая книга).

Для восстановления ключа имеется 1 блок открытого текста и 1 блок шифротекста:

Рассмотрим алгоритм зашифрования:

Если бит, то однозначно ключ не восстановить (по 256 битам невозможно отбраковать 56 бит). В том случае, если любой блок шифртекста отбраковывает примерно половину ключей, то тогда однозначное восстановление ключа возможно[1]. В итоге, не должно остаться эквивалентных ключей, т.е. ключей вида:

Особенности TMTO

Метод - вероятностный (т.к. ключ определяется по шифртексту с некой вероятностью). Аналогично: вероятностным является и метод определении ключа по открытому тексту.

Picture 2 new.png

В атаке Хеллмана[2] время работы уменьшается за счет памяти.

Метод полного перебора

- перебор всех значений.
- время.
- память.

Метод поиска по таблице

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

- время.
- память, где хранятся пары упорядоченные по

Метод Хеллмана является промежуточным между этими двумя методами.

Рассмотрим процесс зашифрования:

Однонаправленная функция: где функция редукции. Т.о. по легко найти но вот найти прообраз возможно за неполиномиальное время.

Необходимо, чтобы размер ключа совпал с размером выхода, т.е.:

В атаке Хеллмана:

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

Поэтапное описание атаки

Этап получения таблицы Этап получения таблицы   H = ( S P j , E P j ) ,   j = 1 , m ¯ {\displaystyle ~H=(SP {j},EP {j}),\ j={\overline {1,m}}}

Хеллман предложил выбрать следующие начальные точки:

где ключи. В памяти хранятся упорядоченные пары На них требуется памяти.

Данный этап проводится предварительно, в режиме off-line.

Оперативный этап

Проходит в режиме on-line. Основная цель - сократить оперативный этап.

Рассмотрим если для некоторой , то или

То есть, возможно, что (из-за функции редукции может случиться "ложное срабатывание").

Таким образом, обрабатываем все ключи, стоящие в столбце номер . Если не обнаруживаем в столбце, считаем:

Если

Вероятность успеха нахождения ключа составляет ( - количество строк и столбцов соответственно). То есть, у метода Хеллмана вероятность успеха выше, чем у метода полного перебора и "табличного" метода . Требуемая память: количество ячеек памяти.

Требуемое время оперативной работы:

Надо повторять этот метод для -таблиц, то есть, менять функцию редукции . Тогда

Дальнейшие улучшения алгоритма

Метод Distinct Points (R. Rivest) (характерные точки). Идея метода заключается в сокращении размера точки и, как следствие, в сокращении перебора.

Метод Rainbow Tables (радужные таблицы). Идея метода заключается в построении таблицы с последовательным применением функций преобразования, вырабатываемых по следующему правилу:

функция фиксированного вида.

Метод Хеллмана пригоден для параллельных вычислений.

Примечания

  1. Для восстановления ключа DES достаточно одного(!) блока шифртекста.
  2. Другие названия атаки: "coffe-break attack", "lunch attack" и др.