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

Si

Ф-Ф

Si


bo

e<—ф


a0

a

a

 


16 битов

a 32 бита


 



a



Рис. 13-4. Функция f.

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

На 8-й представлена блок-схема функции генерации ключа. Сначала 64-битовый ключ делится на две пол о-


вины, к которым применяются операции XOR и функции fh как показано на схеме. На 7-й показана блок-схема функции/*. Два 32-битовых входа разбиваются на 8-битовые блоки, объединяемые и заменяемые в соответс т-вии со схемой. S0 и Si определяются, как показано на рисунке. Затем в алгоритме шифрования/дешифрирования используются 16-битовые блоки ключа.

На микропроцессоре 80286/10 МГц ассемблерная реализация FEAL-32 может шифровать данные со скор о-стью 220 Кбит/с. FEAL-64 может шифровать данные со скоростью 120 Кбит/с [1104].

 

 

 

 

 

 

 

 

 

 

 

 

 

32 бита Блок ключа J64 бита 32 бита
  А0        
  '     Во
  г- L  
Ко, К, к р      
       
  А, 1       •
  '     в,
  А I- L (Т>«  
Кг, К$ Г   kV*  
< ^ | _:'
  А7 1 ' D7\ А, 32 бита в7
KU, Ki5 < ■

а0

X


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

а 32 бита

a
a
 
~о<
 
-е«-

«X

Si

So

й 32 бита

 


 


So h©<-х2


*ф—►


Si


аи й,. - 8 бит


 


Y


|32 бита

/ф,й)


Y=S0(X ,X2)=Rot2((X+X2) mod 256) Y=Si(Xi,X2)=Rot2((Xi+X2+1) mod 256) Y: выходные 8 битов, хьХ2 (8 битов): входы Rot2(Y): циклический сдвиг влево на 2 бита 8-битовых данных у

Рис. 13-6. Функция/^.

Успешный криптоанализ 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 дифференциальный криптоанализ, хотя они могли бы еще б ы-стрее вскрыть его грубой силой (с помощью менее, чем 2 м шифрований выбранного открытого текста) для N , меньшего 32. [169]. Для вскрытия FEAL-16 нужно 228 выбранных или 246'5 известных открытых текстов. Для вскрытия FEAL-8 требуется 2000 выбранных или 237'5 известных открытых текстов. FEAL-4 может быть вскрыт с помощью всего 8 правильно выбранных открытых текстов.

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

Блок ключа («L|KR): 128 битов Обработка бита четности Q

KL

Kb, AC,

Кг, Кз

Кл, Къ

Kn+A, Kn+5

Kn+ 6 , Kn+ 7

Kr1 Kr2

Kr


K2(M): левая половина вг(16 битов) К2(М)+1: правая половина вг (16 битов) Число итераций: Д//2+4


Q^/CriqKrz, г=1, 4, 7, ...
QfKri, r=2, 5, 8, ...

Q,=KR2, r=3, 6, 9, ...


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

Более того. В [1520] было представлено другое вскрытие FEAL-4, требующее только 1000 известных откр ы-тых текстов, и FEAL-8, для которого нужно только 20000 известных открытых текстов. Другие вскрытия прив е-дены в [1549, 1550]. Наилучшим является выполненное Мицуру Мацуи (Mitsura Matsui) и Атшуиро Ямагиши


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