На тему: «Композиции шифров» (стр. 4 )

Формальный анализ этого алгоритма не производит впечатления особо надежного. При поверхностном знакомстве с ним Эли Бихам пришел к следующим выводам:

Алгоритм состоит только из линейных операций (циклический сдвиг и XOR), незначительно изменяемых в зависимости от данных.

Это ничуть не напоминает мощь S-блоков DES.

Четность всех битов шифртекста и открытого текста неизменна и зависит только от ключа. Поэтому, обладая открытым текстом и соответствующим шифртекстом, можно предсказать четность шифртекста для любого открытого текста.

Само по себе ни одно из этих замечаний нельзя назвать убийственным, однако этот алгоритм не вызывает у многих криптоаналитиков положительных эмоций. Некоторые вообще не рекомендуют использовать алгоритм Madryga.

3.3. Алгоритм REDOC

REDOC II представляет собой еще один блочный алгоритм, разработанный Майклом Вудом (Michael Wood) для корпорации Cryptech. В нем используются 20-байтовый (160-битовый) ключ и 80-битовый блок.

Алгоритм REDOC II выполняет все манипуляции - перестановки, подстановки и операции XOR с ключом - с байтами. Этот алгоритм удобен для программной реализации. В REDOC II использованы переменные таблицы функций. В отличие от алгоритма DES, имеющего фиксированный (хотя и оптимизированный с точки зрения стойкости) набор таблиц подстановок и перестановок, в REDOC II используются зависимые от ключа и открытого текста наборы таблиц (по сути, S-блоки). В REDOC II 10 раундов, каждый раунд состоит из сложной последовательности манипуляций с блоком.

Другая уникальная особенность REDOC II — использование масок. Это числа - производные таблицы ключей, которые используются для выбора таблиц данной функции для данного раунда. Для выбора таблиц функций используются как значение данных, так и маски.

При условии, что самое эффективное средство взлома этого алгоритма - лобовое вскрытие, REDOC II весьма надежен: для восстановления ключа требуется 2160 операций. Томас Кузик (Thomas Cusick) выполнил криптоанализ одного раунда REDOC II, но расширить вскрытие на несколько раундов ему не удалось. Используя дифференциальный криптоанализ, Бихам и Шамир успешно выполнили криптоанализ одного раунда REDOC II с помощью 2300 подобранных открытых текстов. Они не сумели расширить эту атаку на несколько раундов, но им удалось получить три значения маски после четырех раундов. Были и другие попытки криптоанализа.

3.3.1 Алгоритм REDOC III

Алгоритм REDOC III представляет собой упрощенную версию REDOC II, тоже разработанную Майклом Вудом. Он оперирует с 80-битовым блоком. Длина ключа может изменяться и достигать 2560 байт (204800 бит). Алгоритм состоит только из операций XOR над байтами ключа и открытого текста, перестановки и подстановки не используются.

1) Создают таблицу ключей из байтовых ключей, используя секретный ключ.

2) Создают два 10-байтовых блока масок M1 и М2. M1 представляет собой результат операции XOR первых байтовых ключей, а М2 - результат операции XOR вторых байтовых ключей.

3) Для шифрования 10-байтового блока:

a. Выполняют операцию XOR с первым байтом блока данных и первым байтом M1. Выбирают ключ в таблице ключей, рассчитанной в раунде 1. Используют вычисленное значение XOR в качестве индекса таблицы. Выполняют операцию XOR с каждым, кроме первого, байтом блока данных и соответствующим байтом выбранного ключа.

b. Выполняют операцию XOR со вторым байтом блока данных и вторым байтом M1. Выбирают ключ в таблице ключей, рассчитанной в раунде 1. Используют вычисленное значение XOR в качестве индекса таблицы. Выполните операцию ХОR с каждым, кроме второго, байтом блока данных и соответствующим байтом выбранного ключа.

c. Продолжают эти действия со всем блоком данных (с 3-10 байтами), пока не будет использован каждый байт для выбора ключа из таблицы после выполнения операции XOR с ним и соответствующим значением M1. Затем выполняют операцию XOR с каждым, кроме использованного для выбора ключа, байтом, и ключом.

d. Повторяют этапы а-с для М2.

Это несложный и скоростной алгоритм. На процессоре 80386 с тактовой частотой 33МГц он шифрует данные со скоростью 2.75 Мбит/сек. По оценке Вуда, конвейеризированный процессор с трактом данных 64 бит и тактовой частотой 20 МГц может шифровать данные со скоростью свыше 1.28 Гбиг/сек.

Алгоритм REDOC III нестоек. Он уязвим к дифференциальному криптоанализу. Для восстановления обеих масок достаточно около 223 подобранных открытых текстов.

3.4. Алгоритм LOKI

Алгоритм LOKI разработан в Австралии и впервые представлен в 1990 году в качестве возможной замены DES. В нем используются 64-битовый блок и 64-битовый ключ.

Используя дифференциальный криптоанализ, Бихам и Шамир взламывали алгоритм LOKI с 11 и менее раундами быстрее, чем лобовым вскрытием [170]. Более того, алгоритм характеризуется 8-битовой комплементарностью, что упрощает лобовое вскрытие в 256 раз.

Как показал Ларе Кнудсен (Lars Knudsen), алгоритм LOKI с 14 и менее раундами уязвим дифференциальному криптоанализу. Кроме того, если в LOKI используются альтернативные S-блоки, то полученный шифр, вероятно, тоже уязвим дифференциальному криптоанализу.

3.4.1. Алгоритм LOKI91

В ответ на описанные выше вскрытия разработчики LOKI вернулись за чертежную доску и пересмотрели свой алгоритм. В результате появился алгоритм LOKI91. (Предыдущая версия LOKI была переименована в LOKI89).

Чтобы повысить устойчивость алгоритма к дифференциальному криптоанализу и избавиться от комплементарности, в исходный проект были внесены следующие изменения:

1. Алгоритм генерации подключей модифицирован с тем, чтобы половины переставлялись не после каждого, а после каждого второго раунда.

2. Алгоритм генерации подключей модифицирован так, что число позиций циклического сдвига левого подключа составляло то 12, то 13 битов.

3. Исключены начальная и заключительная операции XOR с блоком и ключом.

4. Изменена функция S-блока с целью сгладить профили XOR S-блоков (чтобы повысить их устойчивость к дифференциальному криптоанализу), и исключить все значения х, для которых f(x) = 0, где f - комбинация Е-, S- и Р-блоков.

Алгоритм LOKI не запатентован - реализовать и использовать LOKI может кто угодно.

3.4.2. Описание алгоритма LOKI91

Механизм алгоритма LOKI91 подобен DES (Рис. 2). Блок данных расщепляется на левую и правую половины и проходит 16 раундов, что весьма напоминает DES. В каждом раунде правая половина сначала подвергается операции XOR с частью ключа, а затем расширяющей перестановке (Табл. 3).

Рис. 2. Алгоритм LOKI91

Таблица 3. Перестановка с расширением

4,	3,	2,	1,	32,	31,	30,	29,	28,	27,	26,	25,
28,	27,	26,	25,	24,	23,	22,	21,	20,	19,	18,	17,
20,	19,	18,	17,	16,	15,	14,	13,	12,	11,	10,	9,
12,	11,	10,	9,	8,	7,	6,	5,	4,	3,	2,	1

48-битовый выход разделяется на четыре 12-битовых блока. В каждом блоке выполняется такая подстановка с использованием S-блока: берется каждый 12-битовый вход, 2 старших и 2 младших бита используются для образования номера r, а восемь внутренних битов образуют номер с. Выход S-блока, О, имеет следующее значение:

О(r,с) = (с + ((r*17) Å 0xff) & 0xff)31 mod Pr

Таблица 4. Значения Pr

r	1,	2,	3,	4,	5,	6,	7,	8,	9,	10,	11,	12,	13,	14,	15,	16
Pr	375,	379,	391,	395,	397,	415,	419,	425,	433,	445,	451,	463,	471,	477,	487,	499

Затем четыре 8-битовых результата снова объединяются, образуя 32-битовое число, которое подвергается операции перестановки, описанной в табл. 3. Наконец, для получения новой левой половины выполняется операция XOR правой половины с прежней левой половиной, а левая половина становится новой правой половиной. После 16 раундов для получения окончательного шифртекста снова выполняется операция XOR над блоком и ключом.