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

Алгоритм FEAL был разработан криптографами Акихиро Шимизу (Akihiro Shimizu) и Шоджи Миягучи (Shoji Miyaguchi) из японской компании NTT в 1987 г. и представлен на конференции EUROCRYPT'87. Название алгоритма — аббревиатура от Fast data Encipherment ALgorithm (быстрый алгоритм шифрования данных). Стоит сказать, что компания NTT весьма известна и своими более поздними разработками в этой области, в частности:
алгоритм Е2, разработанный компанией NTT с участием специалистов университета г. Иокогама (Япония), участвовал в конкурсе на стандарт шифрования США AES; впрочем, он не попал даже в финал конкурса;
алгоритм Camellia— совместная разработка NTT и еще одной японской компании Mitsubishi Electric — стал одним из победителей (в номинации 128-битных алгоритмов блочного симметричного шифрования) европейского конкурса криптоалгоритмов NESSIE.

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

Структура алгоритма
Структура УУ-раундового алгоритма FEAL-N вместе с процедурой расширения ключа шифрования.

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

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

Процедура расширения ключа
Функция расширения ключа должна выработать N 16-битных ключей раундов, а также 2 64-битных фрагмента для операций XOR, выполняемых в начале и в конце алгоритма. Поскольку один раунд обработки ключа вырабатывает 32-битный фрагмент расширенного ключа, для работы функции расширения ключа требуется (N/2) + 4 раундов.

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

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

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

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

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

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