Алгоритм FEAL История создания алгоритма

Алгоритм FEAL был разработан криптографами Акихиро Шимизу (Akihiro Shimizu) и Шоджи Миягучи (Shoji Miyaguchi) из японской компании NTT в 1987 г. и представлен на конференции EUROCRYPT’87. Название алгоритма — аббревиатура от Fast data Encipherment ALgorithm (быстрый алгоритм шифрования данных).

Стоит сказать, что компания NTT весьма известна и своими более поздними разработками в этой области, в частности:

?     алгоритм Е2 {см. разд. 3.17), разработанный компанией NTT с участием специалистов университета г. Йокогама (Япония), участвовал в конкурсе на стандарт шифрования США AES (см. разд. 2.7); впрочем, он не попал даже в финал конкурса [284];

?     алгоритм Camellia (см. разд. 3.9)— совместная разработка NTT и еще одной японской компании Mitsubishi Electric — стал одним из победителей (в номинации 128-битных алгоритмов блочного симметричного шифрования) европейского конкурса криптоалгоритмов NESSEE (см. разд. 2.2).

Алгоритм FEAL интересен тем, что его разработчики продвигали FEAL как потенциальную замену стандарта шифрования DES — по их мнению, FEAL-4 (число в названии обозначает количество раундов алгоритма) предлагал более быстрое шифрование без потери в его качестве [28]. Кроме того, в FEAL отсутствовали табличные замены, поэтому реализация алгоритма не требовала дополнительной энергонезависимой памяти для хранения таблиц.

Структура алгоритма

Структура УУ-раундового алгоритма FEAL-N вместе с процедурой расширения ключа шифрования (которая будет подробно описана далее) приведена на рис. 3.79 [28,263].

Фактически в каждом раунде алгоритма выполняется лишь обработка правого 32-битного субблока функцией /, которая в качестве второго параметра использует 16-битное значение ключа раунда. Результат обработки накладывается на левый субблок операцией XOR. Перед первым раундом выполняется операция XOR блока шифруемых данных с фрагментом расширенного ключа, а также аналогичное наложение левого субблока на правый. Те же операции в обратном порядке производятся и после финального раунда алгоритма.

Структура функции / представлена на рис. 3.80. Здесь используются лишь три вида преобразований — это операция XOR, а также функции S0 и S{, которые можно описать следующим образом:

Рис. 3.81. Функция fk

Структура процедуры расширения ключа приведена на рис. 3.79. Как видно из рисунка, основой данной процедуры является функция fk, обрабатывающая два 32-битных параметра с получением также 32-битного результата, представляющего собой, в общем случае, ключи двух раундов алгоритма. Функция fk использует те же операции S0, 5j и XOR, что и функция /, но в другой комбинации, которую можно формализовать следующим образом (рис. 3.81):

Почему FEAL не используется

Алгоритм FEAL-4, изначально предлагавшийся в качестве замены стандарта DES, оказался весьма нестоек к различным видам криптоанализа. Та же участь постигла и алгоритм FEAL-8. Алгоритмы же FEAL-16, FEAL-32 и т. д. оказались существенно более стойкими за счет большего количества раундов (хотя для FEAL-16 также были найдены методы вскрытия), однако по той же причине скорость их работы оказалась уже ниже скорости алгоритма DES, так что никаких преимуществ перед DES у FEAL не оказалось. Соответственно, как стандарт шифрования алгоритм FEAL не состоялся.

Фактически сформировалась целая история методов вскрытия алгоритма FEAL, наиболее значительными из которых можно считать следующие.

?      Через год после презентации алгоритма FEAL-4 было опубликовано исследование голландского математика Берта ден Боера (Bert den Boer) [99], в котором была доказана возможность вычисления ключа шифрования данного алгоритма на основе 10 ООО выбранных открытых текстов.

?      В 1990 г. английский исследователь Шон Мерфи (Sean Murphy) существенно улучшил результат предыдущего метода [274], предложив алгоритм вычисления ключа шифрования алгоритма FEAL-4 всего на основе 20 выбранных открытых текстов. Фактически этот алгоритм поставил крест на практическом применении FEAL-4, хотя по современным меркам достаточно и предыдущей атаки — например, один из участников конкурса AES — алгоритм LOKI97 — был отвергнут из-за возможности атаки на основе 256 выбранных или стольких же известных открытых текстов [284], что несопоставимо с числами 20 или 10 000.

?      Тогда же известные израильские криптологи Эли Бихам и Эди Шамир доказали, что алгоритм FEAL-4 можно вскрыть на основе всего 8 выбранных открытых текстов, для вскрытия FEAL-8 достаточно 2000 выбранных или 2 ‘ известных открытых текстов, а для FEAL-16— 2 выбранных или 2465 известных открытых текстов [76]. Это исследование «похоронило» алгоритм FEAL-8 и поставило под сомнение использование алгоритма FEAL-16.

Были и другие криптоаналитические исследования FEAL, например, [189, 290, 292]. А в своей работе [27], адресованной начинающим криптоаналити- кам, Брюс Шнайер утверждает, что «все современные криптоаналитические атаки работают против FEAL». Фактически, по словам Брюса Шнайера, FEAL стал хорошим объектом тренировок как для начинающих криптоаналитиков, так и для профессионалов, изобретающих новые методы криптоанализа.

Кроме того, в 90-х гг. XX века уже не выглядела фантастической возможность полного перебора 264 вариантов 64-битного ключа шифрования алгоритма FEAL. Поэтому его авторами был предложен также FEAL-NX со 128- битным ключом шифрования. Однако FEAL-NX отличался от FEAL-N только измененной процедурой расширения ключа, поэтому не удивительно, что в том же 1991 г. Эли Бихам и Эди Шамир доказали, что вскрытие FEAL-NX не сложнее вскрытия FEAL-N при том же значении N.

И вообще, алгоритм просто не выглядит современным. Например, на конкурсе AES принималась в расчет возможность выполнения процедуры расширения ключа параллельно с раундами шифрования (чтобы не хранить все ключи раундов в памяти, а вычислять их по мере необходимости) [284]. А на рис. 3.79 отчетливо видно, что до первой же операции XOR необходимо выполнить практически всю процедуру расширения ключа, чтобы вычислить подключи, участвующие в этой операции.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100