FEAL

FEAL
Создатель	Акихиро Симидзу и Сёдзи Миягути (NTT)
Опубликован	FEAL-4 в 1987; FEAL-N/NX в 1990
Размер ключа	64 бит (FEAL), 128 бит (FEAL-NX)
Размер блока	64 бит
Число раундов	изначально 4, потом 8 и потом переменное количество (рекомендуемое — 32)
Тип	Сеть Фейстеля

FEAL (англ. Fast data Encipherment ALgorithm) — блочный шифр, разработанный Акихиро Симидзу и Сёдзи Миягути — сотрудниками компании NTT.

В нём используются 64-битовый блок и 64-битовый ключ. Его идея состоит и в том, чтобы создать алгоритм, подобный DES, но с более сильной функцией этапа. Используя меньше этапов, этот алгоритм мог бы работать быстрее. К несчастью, действительность оказалась далека от целей проекта.

История

Опубликованный в 1987 году Акихиро Симидзу и Сёдзи Миягути блочный шифр FEAL был разработан с целью повысить скорость шифрования без ухудшения надежности шифра, по сравнению с DES. Первоначально алгоритм использовал блоки размером 64 бита, ключ размером 64 бита и 4 раунда шифрования. Однако, уже в 1988 году была опубликована работа Берта ден Боера, доказывающая достаточность владения 10000 шифротекстов для проведения успешной атаки на основе подобранного открытого текста. К шифру FEAL одному из первых был применен линейный криптоанализ. В том числе в 1992 году Митсуру Мацуи и Ацухиро Ямагиси доказали, что достаточно узнать 5 шифротекстов для проведения успешной атаки.

Для борьбы с обнаруженными уязвимостями создатели удвоили число раундов шифрования, опубликовав стандарт FEAL-8. Однако, уже в 1990 году Генри Гилберт уязвимость и этого шифра перед атакой на основе подобранного открытого текста. Далее в 1992 году Митсуру Матсуи и Ацухиро Ямагиси (Mitsuru Matsui and Atsuhiro Yamagishi) описали атаку на основе открытых текстов, требующую $2^{15}$ известных шифротекстов.

В связи с большим числом успешных атак, разработчиками было принято решение еще усложнить шифр. А именно, в 1990 году был представлен FEAL-N, где N - произвольное четное число раундов шифрования, и представлен FEAL-NX, где X (от англ. extended) обозначает использование расширенного до 128 бит ключа шифрования. Однако данное нововведение помогло лишь частично. В 1991 году Эли Бихам и Ади Шамир (Eli Biham and Adi Shamir), используя методы дифференциального криптоанализа, показали возможность взлома шифра с числом раундов $N\leq 31$ быстрее, чем полным перебором.

Тем не менее, благодаря интенсивности исследования алгоритма шифрования сообществом, были доказаны границы уязвимости шифра перед линейным и дифференциальным криптоанализом. Устойчивость алгоритма с числом раундов большим 26 к линейному криптоанализу показали в своей работе Шихо Мораи, Казумаро Аоки и Казуо Охта (Shiho Moriai, Kazumaro Aoki, and Kazuo Ohta), а в работе Казумаро Аоки, Кунио Кобаяси и Шихо Мораи (Kazumaro Aoki, Kunio Kobayashi, and Shiho Moriai) была доказана невозможность применить дифференциальный криптоанализ к алгоритму, использующему больше 32 раундов шифрования.

Описание

В качестве входа процесса шифрования в алгоритме FEAL-NX используется 64-битовый блок открытого текста. Процесс шифрования разбит на 3 стадии.

1. Предобработка
2. Итеративное вычисление
3. Постобработка

Кроме того, описан процесс генерации раундовых ключей, с которого и начинается шифрование, а также функции $S_{0},\;S_{1},\;F,\;F_{k}$, с помощью которых и производятся преобразования.

Определим (A,B) - операцию конкатенации двух последовательностей бит.

Определим $\phi$ — нулевой блок длины 32 бита.

Функция S

$S_{0}(a,b)$ = циклический сдвиг влево на 2 бита $((a+b)\mod {256})$

$S_{1}(a,b)$ = циклический сдвиг влево на 2 бита $((a+b+1)\mod {256})$

Функция F

Функция F берёт 32 бита данных и 16 битов ключа и смешивает их вместе.

1. $F=F(\alpha ,\beta )=(F_{0},F_{1},F_{2},F_{3})$
2. $\alpha =(\alpha _{0},\alpha _{1},\alpha _{2},\alpha _{3});\;\beta =(\beta _{0},\beta _{1})$
3. $F_{1}=\alpha _{1}\oplus \beta _{0}$
4. $F_{2}=\alpha _{2}\oplus \beta _{1}$
5. $F_{1}=F_{1}\oplus \alpha _{0}$
6. $F_{2}=F_{2}\oplus \alpha _{3}$
7. $F_{1}=S_{1}(F_{1},F_{2})$
8. $F_{2}=S_{0}(F_{2},F_{1})$
9. $F_{0}=S_{0}(\alpha _{0},F_{1})$
10. $F_{3}=S_{1}(\alpha _{3},F_{2})$

Функция $F_{k}$

Функция $F_{k}$ работает с двумя 32 битовыми словами.

1. $F_{k}=F_{k}(\alpha ,\beta )=(F_{k_{0}},F_{k_{1}},F_{k_{2}},F_{k_{3}})$
2. $\alpha =(\alpha _{0},\alpha _{1},\alpha _{2},\alpha _{3});\;\beta =(\beta _{0},\beta _{1},\beta _{2},\beta _{3})$
3. $F_{k_{1}}=\alpha _{1}\oplus \alpha _{0}$
4. $F_{k_{2}}=\alpha _{2}\oplus \alpha _{3}$
5. $F_{k_{1}}=S_{1}(F_{k_{1}},(F_{k_{2}}\oplus \beta _{0}))$
6. $F_{k_{2}}=S_{0}(F_{k_{2}},(F_{k_{1}}\oplus \beta _{1}))$
7. $F_{k_{0}}=S_{0}(\alpha _{0},(F_{k_{1}}\oplus \beta _{2}))$
8. $F_{k_{3}}=S_{1}(\alpha _{3},(F_{k_{2}}\oplus \beta _{3}))$

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

В результате генерации раундовых ключей, из полученного на вход ключа длиной 128 бит получается набор из N+8 раундовых ключей $K_{i}$, длиной 16 бит каждый. Данный результат получается в результате следующего алгоритма.

1. Разделение входного ключа на левый и правый ключ: $K=(K_{L},K_{R})$, они имеют длину 64 бита.
2. Обработка ключа $K_{R}=(K_{R1},K_{R2})$
3. Введение временной переменной $Q_{r}$ для $1\leq r\leq {\frac {N}{2}}+4$:
   • $Q_{r}=K_{R1}\oplus K_{R2},\;r=3i-2,\;i\in \mathbb {N}$
   • $Q_{r}=K_{R1},\;r=3i-1,\;i\in \mathbb {N}$
   • $Q_{r}=K_{R2},\;r=3i-1,\;i\in \mathbb {N}$
4. Обработка ключа $K_{L}=(A_{0},B_{0})$
5. Введение временной переменной $D_{0}=\phi$
6. Последовательное вычисление $K_{i}$
   1. $D_{r}=A_{r-1}$
   2. $A_{r}=B_{r-1}$
   3. $B_{r}=F_{k}(A_{r-1},(B_{r-q}\oplus D_{r-1})\oplus Q_{r}))=(B_{r_{0}},B_{r_{1}},B_{r_{2}},B_{r_{3}})$
   4. $K_{2(r-1)}=(B_{r_{0}},B_{r_{1}})$
   5. $K_{2(r-1)+1}=(B_{r_{2}},B_{r_{3}})$

Предобработка

На начальной стадии блок данных $P$ готовится к итеративной процедуре шифрования.

1. $P=(L_{0},R_{0})$
2. $(L_{0},R_{0})=(L_{0},R_{0})\oplus (K_{N},K_{N+1},K_{N+2},K_{N+3})$
3. $(L_{0},R_{0})=(L_{0},R_{0})\oplus (\phi ,L_{0})$

Итеративная обработка

На этой стадии с блоком данных производится N раундов перемешивания битов по следующему алгоритму.

1. $R_{r}=L_{r-1}\oplus F(R_{r-1},K_{r-1})$
2. $L_{r}=R_{r-1}$

Постобработка

Задача этой стадии - подготовить почти готовый шифротекст к выдаче.

1. $P=(R_{N},L_{N})$
2. $P=P\oplus (\phi ,R_{N})$
3. $P=P\oplus (K_{N+4},K_{N+5},K_{N+6},K_{N+7})$

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

Источники

• Eli Biham, Adi Shamir: Differential Cryptanalysis of Feal and N-Hash. EUROCRYPT 1991: 1—16
• Bert den Boer, Cryptanalysis of F.E.A.L., EUROCRYPT 1988: 293—299
• Henri Gilbert, Guy Chassé: A Statistical Attack of the FEAL-8 Cryptosystem. CRYPTO 1990: 22—33.
• Shoji Miyaguchi: The FEAL Cipher Family. CRYPTO 1990: 627—638
• Shoji Miyaguchi: The FEAL-8 Cryptosystem and a Call for Attack. CRYPTO 1989: 624—627
• Mitsuru Matsui, Atsuhiro Yamagishi: A New Method for Known Plaintext Attack of FEAL Cipher. EUROCRYPT 1992: 81—91
• Sean Murphy, The Cryptanalysis of FEAL-4 with 20 Chosen Plaintexts. J. Cryptology 2(3): 145—154 (1990)
• A. Shimizu and S. Miyaguchi, Fast data encipherment algorithm FEAL, Advances in Cryptology — Eurocrypt '87, Springer-Verlag (1988), 267—280.
• Anne Tardy-Corfdir, Henri Gilbert: A Known Plaintext Attack of FEAL-4 and FEAL-6. CRYPTO 1991: 172—181

Ссылки

• Пример реализации FEAL-NX на языке C