FEAL

FEAL (Fast Data Encipherment Algorithm) — семейство симметричных блочных шифров, разработанных японскими криптографами Акихиро Симидзу и Сёдзи Миягути из компании Nippon Telegraph and Telephone (NTT) в 1987 году. Шифр был создан как быстрый и эффективный алгоритм для программной реализации на 8- и 16-битных процессорах, что было актуально для аппаратного обеспечения того времени. FEAL стал одним из первых шифров, подвергшихся интенсивному криптоанализу, что выявило его уязвимости и привело к созданию нескольких модификаций, вплоть до FEAL-8X и FEAL-NX.

История

Разработка FEAL началась в середине 1980-х годов в исследовательском центре NTT. Основной целью было создание алгоритма, превосходящего по скорости и программной эффективности господствовавший тогда стандарт DES (Data Encryption Standard). DES был ориентирован на аппаратную реализацию и использовал 56-битный ключ, что к концу 1980-х годов уже считалось недостаточным для некоторых применений. FEAL был предложен как альтернатива для систем, где требовалась высокая скорость шифрования при ограниченных вычислительных ресурсах, например, в смарт-картах и встраиваемых устройствах.

Первая версия, FEAL-4, была опубликована в 1987 году. Она имела 4 раунда шифрования и 64-битный блок. Однако уже в 1988 году криптоаналитики Шон Мёрфи и Эли Бихам продемонстрировали атаку на FEAL-4, используя дифференциальный криптоанализ — метод, который впоследствии стал одним из основных инструментов анализа блочных шифров. В ответ NTT выпустила версию FEAL-8 с 8 раундами, но и она была взломана в 1991 году. Последующие версии (FEAL-16, FEAL-32, FEAL-N, FEAL-NX) увеличивали количество раундов, но фундаментальные недостатки алгоритма, связанные с простотой нелинейных преобразований, не были устранены.

К середине 1990-х годов FEAL был признан небезопасным для практического использования. Тем не менее, его история сыграла важную роль в развитии криптографии: он стал одним из первых «полигонов» для тестирования методов дифференциального и линейного криптоанализа.

Классификация

FEAL относится к классу симметричных блочных шифров с сетью Фейстеля. В такой сети блок данных делится на две половины, которые обрабатываются итеративно с использованием раундовой функции. Ключевые характеристики семейства:

• Размер блока: 64 бита (8 байт).
• Длина ключа: 64 бита (8 байт), хотя эффективная длина ключа в некоторых версиях составляет 56 бит из-за отбрасывания битов чётности.
• Количество раундов: варьируется от 4 (FEAL-4) до 32 (FEAL-32) и более (FEAL-N, FEAL-NX).

Основные версии:

Устройство и принцип работы

FEAL основан на сети Фейстеля. Каждый раунд состоит из трёх основных операций: подстановки (S-блоки), перестановки (циклический сдвиг) и сложения с раундовым ключом. Ключевой особенностью является использование простых нелинейных функций, что делает алгоритм быстрым, но слабым.

Раундовая функция

Раундовая функция FEAL (обозначается как f-функция) принимает на вход 32-битный блок данных и 16-битный раундовый ключ. Она состоит из двух этапов:

1. Сложение с ключом: 32-битный блок делится на два 16-битных слова, которые складываются по модулю 2 с раундовым ключом.
2. Нелинейное преобразование: каждое 16-битное слово проходит через два S-блока (S0 и S1), которые отображают 8-битные входы в 8-битные выходы. S-блоки основаны на простых арифметических операциях: сложение по модулю 256 и циклический сдвиг.

Функция S0(x, y) = (x + y) mod 256, циклический сдвиг влево на 2 бита. Функция S1(x, y) = (x + y + 1) mod 256, циклический сдвиг влево на 2 бита.

Эта простота является главной уязвимостью: S-блоки не обладают достаточной нелинейностью и лавинным эффектом.

Генерация раундовых ключей

Процедура расширения ключа (key schedule) в FEAL также проста. 64-битный мастер-ключ делится на две 32-битные половины, которые затем обрабатываются с помощью раундовой функции для получения 16-битных раундовых ключей. В версии FEAL-NX мастер-ключ имеет длину 128 бит, что увеличивает стойкость к атакам полным перебором.

Криптоанализ и уязвимости

FEAL стал одним из первых шифров, взломанных с помощью дифференциального криптоанализа — метода, разработанного Эли Бихамом и Ади Шамиром в конце 1980-х годов. Этот метод анализирует влияние различий во входных данных на различия в выходных данных, что позволяет восстановить ключ.

• FEAL-4: взломан с использованием 8 выбранных открытых текстов (или 2^28 известных текстов). Атака была продемонстрирована в 1988 году.
• FEAL-8: взломан с использованием 2^15 выбранных открытых текстов.
• FEAL-16 и FEAL-32: более устойчивы, но всё же уязвимы: для FEAL-16 требуется около 2^28 выбранных текстов, для FEAL-32 — около 2^65, что близко к границе практической реализуемости.
• FEAL-NX: атаки на эту версию требуют большего количества текстов, но алгоритм всё равно считается слабым по сравнению с современными стандартами (AES, Twofish).

Помимо дифференциального, к FEAL применим и линейный криптоанализ, который использует линейные аппроксимации нелинейных функций. Для FEAL-4 линейная атака требует около 2^24 известных открытых текстов.

Применение

Ввиду доказанной небезопасности, FEAL не рекомендуется к использованию в современных системах защиты информации. Тем не менее, в конце 1980-х — начале 1990-х годов он применялся в некоторых продуктах NTT, в том числе в системах шифрования факсимильной связи и в ранних версиях смарт-карт. Также FEAL использовался в качестве учебного примера в криптографических курсах для демонстрации методов дифференциального и линейного криптоанализа.

Значение для криптографии

Несмотря на свою уязвимость, FEAL сыграл важную роль в развитии криптографии. Он стал одним из первых шифров, на котором были практически продемонстрированы мощные методы криптоанализа, что стимулировало разработку более стойких алгоритмов. В частности, опыт анализа FEAL повлиял на создание стандарта AES (Rijndael), который использует более сложные и нелинейные S-блоки. FEAL также показал, что простота и скорость не должны достигаться за счёт криптографической стойкости.

Источники

• Shimizu, A., & Miyaguchi, S. (1987). Fast Data Encipherment Algorithm FEAL. Transactions of the IEICE, J70-D(7), 1413–1423.
• Biham, E., & Shamir, A. (1991). Differential Cryptanalysis of FEAL and N-Hash. Advances in Cryptology — EUROCRYPT '91, 1–16.
• Murphy, S. (1988). The Cryptanalysis of FEAL-4 with 8 Chosen Plaintexts. Journal of Cryptology, 1(2), 119–128.
• Menezes, A. J., van Oorschot, P. C., & Vanstone, S. A. (1996). Handbook of Applied Cryptography. CRC Press. — Глава 7, раздел 7.4.