Криптоанализ FEAL

Успешный криптоанализ FEAL-4, FEAL с четырьмя этапами, был выполнен с помощью вскрытия с выбранными открытыми текстами [201], а позже слабость этого алгоритма была показана в [1132]. Последнее вскрытие, выполненное Сином Мерфи (Sean Murphy), было первым опубликованным вскрытием, использовавшим дифференциальный криптоанализ, и для него потребовалось только 20 выбранных открытых текстов. Ответом разработчиков стал 8-этапный FEAL [1436, 1437, 1108], криптоанализ которого был представлен Бихамом и Шамиром на конференции SECURICOM '89 [1424]. Для вскрытия FEAL-8 с выбранными открытыми текстами потребовалось только 10000 блоков [610], что заставило разработчиков алгоритма засучить рукава и определить FEAL-N [1102, 1104], алгоритм с переменным числом этапов (конечно же, большим 8).

Бихам и Шамир применили против FEAL-N дифференциальный криптоанализ, хотя они могли бы еще быстрее вскрыть его грубой силой (с помощью менее, чем 264 шифрований выбранного открытого текста) для N , меньшего 32. [169]. Для вскрытия FEAL-16 нужно 228 выбранных или 246.5 известных открытых текстов. Для вскрытия FEAL-8 требуется 2000 выбранных или 237.5 известных открытых текстов. FEAL-4 может быть вскрыт с помощью всего 8 правильно выбранных открытых текстов.

Разработчики FEAL определили также модификацию FEAL - FEAL-NX, в которой используется 128-битовый ключ (см. Рис. 13-7) [1103, 1104]. Бихам и Шамир показали, что для любого значения N FEAL-NX со 128-битовым ключом взламывать не сложнее, чем FEAL-N с 64-битовым ключом [169]. Недавно был предложен FEAL-N(X)S, усиливающий FEAL за счет динамической функции обмена местами [1525].

[image]

Рис. 13-7. Обработка ключа в FEAL-NX.

Более того. В [1520] было представлено другое вскрытие FEAL-4, требующее только 1000 известных открытых текстов, и FEAL-8, для которого нужно только 20000 известных открытых текстов. Другие вскрытия приведены в [1549, 1550]. Наилучшим является выполненное Мицуру Мацуи (Mitsuru Matsui) и Атшуиро Ямагиши (Atshuiro Yamagishi) [1020]. Это было первое применение линейного криптоанализа, и оно позволило вскрыть FEAL-4 с помощью 5 известных открытых текстов, FEAL-6 - с помощью 100 известных открытых текстов, а FEAL-8 - с помощью 215 известных открытых текстов. Дальнейшие уточнения можно найти в [64]. Дифференциальный криптоанализ позволяет вскрывать FEAL-8, используя только 12 выбранных открытых текстов [62]. Кто бы не изобрел новый метод криптоаналитического вскрытия, кажется, что он всегда сначала пробует его на FEAL.

Патенты

FEAL запатентован в Соединенных Штатах [1438], соответствующие патенты приняты к рассмотрению в Англии, Франции и Германии. Желающий лицензировать использование алгоритма должен связаться с Дераптаментом интеллектуальной собственности (Intellectual Property Department), NTT, 1-6 Uchisaiwai-cho, 1-chome, Chiyada-ku, 100 Japan.