Быстрый поиск

Реферат: Композиции шифров

Рис. 1. Одна итерация алгоритма Madryga

Поскольку каждый байт данных влияет на два байта слева и на один байт справа от себя, после восьми проходов каждый байт шифртекста зависит от 16 байтов слева и 8 байтов справа.

При зашифровании каждая итерация внутреннего цикла устанавливает рабочий кадр на предпоследний байт открытого текста и циклически перемещает его к третьему с конца байту открытого текста. Сначала весь ключ подвергается операции XOR со случайной константой и затем циклически сдвигается вправо на 3 бита (ключ и данные двигаются в разных направлениях, чтобы минимизировать избыточные операции с битами ключа). Младшие три бита младшего байта рабочего кадра сохраняются, они определяют циклический сдвиг остальных двух байтов. Далее конкатенация двух старших байтом циклически сдвигается влево на переменное число битов (от 0 до 7). Затем над младшим байтом рабочего кадра выполняется операция XOR с младшим байтом ключа. Наконец рабочий кадр смещается вправо на один байт и весь процесс повторяется.

Случайная константа предназначена для превращения ключа в псевдослучайную последовательность. Длина константы должна быть равной длине ключа. При обмене данными абоненты должны пользоваться одной и той же константой. Для 64-битового ключа Мадрига рекомендует константу 0x0fle2d3c4b5a6978.

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

3.2.2. Криптоанализ алгоритма Madryga

Ученые Квинслендского технического университета (Queensland University of Technology) исследовали алгоритм Madryga и некоторые другие блочные шифры. Они обнаружили, что лавинный эффект при преобразовании открытого текста в шифртекст в этом алгоритме не проявляется. Кроме того, во многих шифртекстах доля единиц превышала доли нулей.

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

Алгоритм состоит только из линейных операций (циклический сдвиг и 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) Создают таблицу ключей из 256 10-байтовых ключей, используя секретный ключ.

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

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).