Метод дифференциального криптоанализа

Алгоритм ММВ оперирует 32-битовыми подблоками текста (х₀, х₁, х₂, x₃) и 32-битовыми подблоками ключа (k₀, k₁, k₂, k₃). Это упрощает реализацию алгоритма на современных 32-битовых   процессорах. Чередуясь с операцией   XOR, шесть раз используется нелинейная функция f. Вот этот алгоритм (все операции с индексами выполняются по модулю 4):

x_i = x_i Å  k_i для i = 0..3

f(х₀, х₁, х₂, x₃)

x_i = x_i Å  k_i+1 для i = 0..3

f(х₀, х₁, х₂, x₃)

x_i = x_i Å  k_i+2 для i = 0..3

f(х₀, х₁, х₂, x₃)

x_i = x_i Å  k_i для i = 0..3

f(х₀, х₁, х₂, x₃)

x_i = x_i Å  k_i+1 для i = 0..3

f(х₀, х₁, х₂, x₃)

x_i = x_i Å  k_i+2 для i = 0..3

f(х₀, х₁, х₂, x₃)

 

Функция f исполняется в три шага:

1. x_i = с_i * x_i  для i = 0..3 (Если на входе умножения одни единицы, то на выходе - тоже одни единицы).
2. Если младший значащий бит х₀ = 1, то x₀ = х₀ Å  С. Если младший значащий байт х₃ = 0, то х₃ = х₃ Å  С.
3. x_i = х_i-1 Å   x_i Å   х_i+1 для i = 0..3. 

 

Все операции с индексами  выполняются по модулю 4. Операция умножения на шаге 1 выполняется по модулю 2³²-1. Специальный случай для данного алгоритма: если второй операнд равен 2³²-1, результат тоже равен 2³²-1. В алгоритме используются следующие константы:

С = 2ааааааа

c₀ = 025f1cdb            

c₁ = 2*c₀

с₂=2³ *с₀

с₃=2⁷ *с₀

Константа С - «простейшая» константа  без круговой симметрии, высоким троичным весом и нулевым младшим значащим битом. У константы с₀ есть другие особые характеристики. Константы c₁, с₂ и с₃ - сдвинутые версии с₀, и служат для предотвращения атак, основанных на симметрии.

Расшифрование выполняется  в обратном порядке, Этапы 2 и 3 инверсны им самим. На этапе 1 вместо с_i используется с_i^-1 . Значение с₀^-1 = 0dad4694 .

 

1.  Стойкость алгоритма  ММВ

Схема алгоритма ММВ  обеспечивает на каждом раунде значительное и независимое от ключа рассеивание. ММВ изначально проектировался в расчете на отсутствие слабых ключей.

ММВ – это уже мертвый  алгоритм. Это утверждение справедливо  по многим причинам, хотя криптоанализ ММВ и не был опубликован. Во-первых, алгоритм проектировался без учета требования устойчивости к линейному криптоанализу. Устойчивость к дифференциальному криптоанализу обеспечил выбор мультипликативных множителей, но о существовании линейного криптоанализа авторы не знали.

Во-вторых, Эли Бихам  реализовал эффективную атаку с  подобранным ключом, использующую тот  факт, что все раунды идентичны, а развертка ключа – просто циклический сдвиг на 32 бита. В третьих, несмотря на эффективность программной реализации ММВ, аппаратное исполнение менее эффективно по сравнению с DES.

Дэймен предлагает желающим улучшить алгоритм ММВ сначала проанализировать умножение по модулю с помощью линейного криптоанализа и подобрать новый множитель, а затем сделать константу С различной на каждом раунде. Затем улучшить развертку ключа, добавляя к ключам раундов константы с целью устранения смещения. Однако сам он не стал заниматься этим, а разработал алгоритм 3-Way.

 

3.7. Алгоритм Blowfish

Blowfish - это алгоритм, разработанный Брюсом Шнайером специально для реализации на больших микропроцессорах. Алгоритм Blowfish не запатентован. При проектировании алгоритма Blowfish Шнайер пытался удовлетворить следующим критериям:

• Скорость. Программа, реализующая алгоритм Blowfish на 32-битовых микропроцессорах, шифрует данные со скоростью 26 тактов на байт.
• Компактность. Для исполнения программной реализации алгоритма Blowfish достаточно 5 Кбайт памяти.
• Простота. В алгоритме Blowfish используются только простые операции: сложение, XOR и подстановка из таблицы по 32-битовому операнду. Анализ его схемы несложен, что снижает риск ошибок реализации алгоритма.
• Настраиваемая стойкость. Длина ключа Blowfish переменна и может достигать 448 бит.

 

Алгоритм Blowfish оптимизирован для применения в системах, не практикующих частой смены ключей, например, в линиях связи и программах автоматического шифрования файлов. При реализации на 32-битовых микропроцессорах с большим размером кэша данных, например, процессорах Pentium и PowerPC, алгоритм Blowfish заметно быстрее DES. Алгоритм Blowfish не годится для применения в случаях, где требуется частая смена ключей, например, в коммутаторах пакетов, или в качестве однонаправленной хэш-функции. Большие требования к памяти не позволяют использовать этот алгоритм в смарт-картах.

 

3.7.1. Описание алгоритма Blowfish

Blowfish представляет собой 64-битовый блочный алгоритм шифрования с ключом переменной длины. Алгоритм состоит из двух частей: расширения ключа и шифрования данных. Расширение ключа преобразует ключ длиной до 448 битов в несколько массивов подключей общим размером 4168 байт.

Шифрование данных заключается  в последовательном исполнении простой функции 16 раз. На каждом раунде выполняются зависимая от ключа перестановка и зависимая от ключа и данных подстановка. Используются только операции сложения и XOR над 32-битовыми словами. Единственные дополнительные операции каждого раунда - четыре взятия данных из индексированного массива.

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

Рис 3. Алгоритм Blowfish

 

Р-массив состоит из восемнадцати 32-битовых подключей:

Р₁,Р₂,...,Р₁₈

Каждый из четырех 32-битовых S-блоков содержит 256 элементов:

S_1,0, S_1,1,…, S_1,255

S_2,0, S_2,2,…, S_2,255

S_3,0, S_3,3,…, S_3,255

S_4,0, S_4,4,…, S_4,255

Алгоритм Blowfish представляет собой сеть Файстеля, состоящей из 16 раундов. На вход подается 64-битовый элемент данных х. Для зашифрования данных:

Разбить  х на  две  32-битовых половины: x_L, x_R

Для i от 1 до 16:

x_L = x_L Å   P_i

x_R = F (x_L) Å   x_R

Переставить x_L и x_R

Переставить x_L и x_R (отнять последнюю перестановку)

x_R = x_R Å   P₁₇

x_L = x_L Å   P₁₈

Объединить x_L и x_R

 

Рис. 4. Функция F

 

Функция F рассчитывается следующим образом ( Рис. 4.):

Разделить x_L на четыре 8-битовых фрагмента: а, b, с и d

F(x_L) = ((S_1,a + S_2,bmod2³²)Å  S_3,c) + S_4,dmod2³²                                          

Расшифрование выполняется  точно так же, как и зашифрование,  но Р₁,Р₂,...,Р₁₈ используются в обратном порядке.

В реализациях Blowfish, в которых требуется очень высокая скорость, цикл должен быть развернут, а все ключи храниться в кэше.

Подключи рассчитываются с помощью самого алгоритма Blowfish. Вот какова точная последовательность действий.

1. Сначала Р-массив, а затем четыре S-блока по порядку инициализируются фиксированной строкой. Эта строка состоит из шестнадцатеричных цифр π.
2. Выполняется операция XOR над Р₁ с первыми 32 битами ключа, XOR над Р₂ со вторыми 32 битами ключа, и т.д. для всех битов ключа (вплоть до Р₁₈). Операция XOR выполняется циклически над битами ключа до тех пор, пока весь Р-массив не будет инициализирован.
3. Используя подключи, полученные на этапах 1 и 2, алгоритм Blowfish шифрует строку из одних нулей.
4. Р₁ и Р₂ заменяются результатом этапа 3.
5. Результат этапа 3 шифруется с помощью алгоритма Blowfish и модифицированных подключей.
6. Р₃ и Р₄ заменяются результатом этапа 5.
7. Далее по ходу процесса все элементы Р-массива, а затем все четыре S-блока по порядку заменяются выходом постоянно меняющегося алгоритма Blowfish.

 

Всего для генерации  всех необходимых подключей требуется 521 итерация. Приложения могут сохранять подключи - нет необходимости выполнять процесс их получения многократно.

 

3.7.2. Стойкость алгоритма Blowfish

Серж Воденэ (Serge Vaudenay) исследовал алгоритм Blowfish с известными S-блоками и r раундами. Как оказалось, дифференциальный криптоанализ может восстановить Р-массив с помощью 2^8r+1 подобранных открытых текстов. Для некоторых слабых ключей, которые генерируют плохие S-блоки (вероятность выбора такого ключа составляет 1/2¹⁴), эта же атака восстанавливает Р-массив с помощью всего 2^4г+1 подобранных открытых текстов. При неизвестных S-блоках эта атака может обнаружить использование слабого ключа, но не может восстановить сам ключ (и также S-блоки и Р-массив). Эта атака эффективна только против вариантов с уменьшенным числом раундов и совершенно безнадежна против 16-раундового алгоритма Blowfish. Разумеется, важно и открытие слабых ключей, хотя они, вероятно, использоваться не будут. Слабым называют ключ, для которого два элемента данного S-блока идентичны. До выполнения расширения ключа невозможно установить факт слабости ключа.

Не известны факты успешного  криптоанализа алгоритма Blowfish. В целях безопасности не следует реализовывать Blowfish с уменьшенным числом раундов. Компания Kent Marsh Ltd. встроила алгоритм Blowfish в свой продукт FolderBolt, предназначенный для обеспечения защиты Microsoft Windows и Macintosh. Кроме того, алгоритм входит в Nautilus и PGPfone.

 

3.8. Алгоритм RC5

RC5 представляет собой блочный шифр с множеством параметров: размером блока, размером ключа и числом раундов. Он изобретен Роном Ривестом и проанализирован в RSA Laboratories.

В алгоритме RC5 предусмотрены три операции: XOR, сложение и циклические сдвиги. На большинстве процессоров операции циклического сдвига выполняются за постоянное время, переменные циклические сдвиги представляют собой нелинейную функцию. Эти циклические сдвиги, зависящие как от ключа, так и от данных - интересная операция.

В RC5 используется блок переменной длины, но в приводимом примере будет рассмотрен 64-битовый блок данных. Шифрование использует 2r+2 зависящих от ключа 32-битовых слов - S₀, S₁, S₂,... S_2r+1 - где r - число раундов. Для зашифрования сначала нужно разделить блок открытого текста на два 32-битовых слова: А и В. (При упаковке байтов в слова в алгоритме RC5 соблюдается соглашение о прямом порядке (little-endian) байтов: первый байт занимает младшие биты регистра А и т.д.) Затем:

A=A + S₀

B = B + S₀

Для i от 1 до r:

A = ((AÅ    B) <<< B) + S_2i

В = ((ВÅ    А) <<< А) + S_2i+1

Выход находится в регистрах А и В.

Расшифрование тоже несложно. Нужно  разбить блок открытого текста на два слова, А и В, а затем:

Для i от r до 1 с шагом -1: 

B = ((B - S_2i+1) >>> A)Å    A

  A = ((A - S_2i) >>> B)Å    B

B = B – S_i  

A = A - S₀                                             

Символом «>>>»  обозначен циклический сдвиг вправо. Конечно же, все сложения и вычитания выполняются по модулю 2³².

Создание массива ключей сложнее, но тоже прямолинейно. Сначала байты  ключа копируются в массив L из с 32-битовых слов, дополняя при необходимости заключительное слово нулями. Затем массив S инициализируется при помощи линейного конгруэнтного генератора по модулю 2³²:

S₀ = Р                                                                                                                                                                                                                                                                               

Для i от 1 до 2(r + 1) - 1:

S_i = (S_i-1 + Q) mod 2³²

где P = 0xb7e15163 и Q = 0x9e3779b9, эти константы основываются на двоичном представлении е и phi.

Наконец, нужно подставить  L в S:

i = j = 0

A = B = 0

Выполнить 3n раз (где п - максимум от 2(r + 1) и с):

A = S _i= (S_i + A + B) <<< 3                                                                               

B= L_i = (L_i + A + B) <<< (A + B)

i = (i + 1) mod 2(r +1)

i = (j +1) mod с

 

В действительности RC5 представляет собой семейство алгоритмов. Выше был определен RC5 с 32-битовым словом и 64-битовым блоком, но нет причин, запрещающих использовать этот же алгоритм с 64-битовым словом и 128-битовым блоком. Для w=64, Р и Q равны 0xb7e151628aed2a6b и 0x9e3779b97f4a7c15, соответственно. Ривест обозначил различные реализации RC5 как RC5-w/r/b, где w - размер слова, r - число раундов, a b - длина ключа в байтах.

RC5 - новый алгоритм, но RSA Laboratories потратила достаточно много времени, анализируя его работу с 64-битовым блоком. После 5 раундов статистика выглядит очень убедительно. После 8 раундов каждый бит открытого текста влияет не менее чем на один циклический сдвиг. Дифференциальная атака требует 2²⁴ подобранных открытых текстов для 5 раундов, 2 - для 10 раундов, 2⁵³ - для 12 раундов и 2⁶⁸ - для 15 раундов. Конечно же, существует только 2⁶⁴ возможных открытых текстов, поэтому такая атака неприменима к алгоритму с 15 и более раундами. Оценка возможности линейного криптоанализа показывает, что алгоритм устойчив к нему после 6 раундов. Ривест рекомендует использовать не менее 12, а лучше 16, раундов. Это число может меняться.