Композиции шифров
и внутреннего цикла к открытому тексту.
Внутренний цикл превращает открытый текст в шифртекст и выполняется
однократно над каждым 8-битовым блоком (байтом) открытого текста. Таким
образом, весь открытый текст последовательно восемь раз обрабатывается
алгоритмом.
Итерация внутреннего цикла оперирует с 3-байтовым окном данных,
называемым рабочим кадром (Рис. 1.). Это окно сдвигается на 1 байт за
итерацию. (При работе с последними 2 байтами данные полагаются циклически
замкнутыми). Первые два байта рабочего кадра циклически сдвигаются на
переменное число позиций, а для последнего байта исполняется операция XOR с
несколькими битами ключа. По мере перемещения рабочего кадра все байты
последовательно циклически сдвигаются и подвергаются операции XOR с частями
ключа. Последовательные циклические сдвиги перемешивают результаты
предыдущих операций XOR и циклического сдвига, причем на циклический сдвиг
влияют результаты XOR. Благодаря этому процесс в целом обратим.
|Движущийся |WF(1) |WF(2) | |WF(3) | | | |
|рабочий кадр | | | | | | | |
| |8 битов|8 битов| |8 битов | | | |
| |ROT | | | | | |
|Перемещение |Объект сдвига | | |Счетчик сдвига | | |
| |16 бит | |3 бита | | |
| | | | |XOR | | | |
|Хэш ключа |1|2|3|… |KL | | |
| | | | | | | | |
Рис. 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).
Чтобы повысить устойчивость алгоритма к дифференциальному
криптоанализу и избавиться от к
| | скачать работу |
Композиции шифров |