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

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

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

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

В этом нет ничего похожего на мощь S-блоков DES.

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

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

NewDES

NewDES (новый DES) был спроектирован в 1985 году Робертом Скоттом (Robert Scott) как возможная замена DES [1405, 364]. Алгоритм не является модификацией DES, как может показаться из его названия. Он оперирует 64-битовыми блоками шифротекста, но использует 120-битовый ключ. NewDES проще, чем DES, в нем нет начальной и заключительной перестановок. Все операции выполняются над целыми байтами. (На самом деле NewDES ни коим образом не является новой версией DES, название было выбрано неудачно.)

Блок открытого текста делится на восемь 1-байтовых подблоков: B₀, B₁, . . ., B₆, B₇. Затем подблоки проходят через 17 этапов. В каждом этапе восемь действий. В каждом действии один из подблоков подвергается операции XOR с частью ключа (есть одно исключение), заменяется другим байтом с помощью функции f и затем подвергается операции XOR с другим подблоком, который и заменяется результатом. 120-битовый ключ делится на 15 подблоков ключа: K₀, K₁, . . ., K₁₃, K₁₄. Процесс легче понять, увидев его схему, чем прочитав его описание. Алгоритм шифрования NewDES показан на Рис. 13-2.

Рис. 13-2. NewDES.

Функция f выводится из Декларации независимости. Подробности можно найти в [1405].

Скотт показал, что каждый бит блока открытого текста влияет на каждый бит шифротекста уже после 7 этапов. Он также проанализировал функцию f и не нашел каких-либо очевидных проблем. NewDES обладает той же комплиментарностью, что и DES [364]: если E_K(P} = C, то E_K'(P'} = C'. Это уменьшает объем работы, необходимой для вскрытия грубой силой, с 2¹¹⁰ действий до 2¹¹⁹. Бихам заметил, что любое изменение полного байта, примененное ко всем байтам ключа и данных, также приводит к комплиментарности [160]. Это уменьшает объем грубого вскрытия до 2¹¹² действий.

Это не является критичным, но предложенное Бихамом криптоаналитическое вскрытие со связанными ключами может вскрыть NewDES с помощью 2³³ выбранных открытых текстов для выбранных ключей за 2⁴⁸ действий [160]. Хотя такое вскрытие требует много времени и в большой степени является теоретическим, оно показывает, что NewDES слабее, чем DES.

FEAL

FEAL был предложен Акихиро Шимузу (Akihiro Shimizu) Шоджи Миягучи (Shoji Miyaguchi) из NTT Japan [1435]. В нем используются 64-битовый блок и 64-битовый ключ. Его идея состоит в том, чтобы создать алгоритм, подобный DES, но с более сильной функцией этапа. Используя меньше этапов, этот алгоритм мог бы работать быстрее. К несчастью действительность оказалась далека от целей проекта.

Описание FEAL

На Рис. 13-3 представлена блок-схема одного этапа FEAL. В качестве входа процесса шифрования используется 64-битовый блок открытого текста. Сначала блок данных подвергается операции XOR с 64 битами ключа. Затем блок данных расщепляется не левую и правую половины. Объединение левой и правой половин с помощью XOR образует новую правую половину. Левая половина и новая правая половина проходят через n этапов (первоначально четыре). На каждом этапе правая половина объединяется с помощью функции f с шестнадцатью битами ключа и с помощью XOR - с левой половиной, создавая новую правую половину. Исходная правая половина (на начало этапа) становится новой левой половиной. После n этапов (не забывайте, что левая и правая половины не переставляются после n-го этапа) левая половина снова объединяется с помощью XOR с правой половиной, образуя новую правую половину, затем левая и правая соединяются вместе в 64-битовое целое. Блок данных объединяется с помощью XOR с другими 64 битами ключа, и алгоритм завершается.

Рис. 13-3. Один этап FEAL.

Функция f берет 32 бита данных и 16 битов ключа и смешивает их вместе. Сначала блок данных разбивается на 8-битовые кусочки, которые затем объединяются с помощью XOR и заменяют друг друга. Блок-схема функции f представлена на Рис. 13-4. Две функции S₀и S₁ определяются следующим образом:

S₀(a,b) = циклический сдвиг влево на два бита ((a + b) mod 256)

S₁(a,b) = циклический сдвиг влево на два бита((a + b + 1) mod 256)

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

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

На Рис. 13-5 представлена блок-схема функции генерации ключа. Сначала 64-битовый ключ делится на две половины, к которым применяются операции XOR и функции f_k, как показано на схеме. На Рис. 13-6 показана блок-схема функции f_k. Два 32-битовых входа разбиваются на 8-битовые блоки, объединяемые и заменяемые в соответствии со схемой. S₀ и S₁ определяются, как показано на рисунке. Затем в алгоритме шифрования/дешифрирования используются 16-битовые блоки ключа.

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

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

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

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

Успешный криптоанализ 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 нужно 2²⁸ выбранных или 2^46.5 известных открытых текстов. Для вскрытия FEAL-8 требуется 2000 выбранных или 2^37.5 известных открытых текстов. FEAL-4 может быть вскрыт с помощью всего 8 правильно выбранных открытых текстов.

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

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

Более того. В [1520] было представлено другое вскрытие FEAL-4, требующее только 1000 известных открытых текстов, и FEAL-8, для которого нужно только 20000 известных открытых текстов. Другие вскрытия приведены в [1549, 1550]. Наилучшим является выполненное Мицуру Мацуи (Mitsuru Matsui) и Атшуиро Ямагиши (Atshuiro Yamagishi) [1020]. Это было первое применение линейного криптоанализа, и оно позволило вскрыть FEAL-4 с помощью 5 известных открытых текстов, FEAL-6 - с помощью 100 известных открытых текстов, а FEAL-8 - с помощью 2¹⁵ известных открытых текстов. Дальнейшие уточнения можно найти в [64]. Дифференциальный криптоанализ позволяет вскрывать FEAL-8, используя только 12 выбранных открытых текстов [62]. Кто бы не изобрел новый метод криптоаналитического вскрытия, кажется, что он всегда сначала пробует его на FEAL.

Патенты

FEAL запатентован в Соединенных Штатах [1438], соответствующие патенты приняты к рассмотрению в Англии, Франции и Германии. Желающий лицензировать использование алгоритма должен связаться с Дераптаментом интеллектуальной собственности (Intellectual Property Department), NTT, 1-6 Uchisaiwai-cho, 1-chome, Chiyada-ku, 100 Japan.

REDOC

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

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

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

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

REDOC III

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

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

(2) Создать 2 10-байтовых блока маски M₁ и M₂. M₁ представляет собой XOR первых 128 10-байтовых ключей, а M₂ - XOR вторых 128 10-байтовых ключей.

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

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

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

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

(d) Повторить для M₂ этапы (a)-(c).

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

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

Патенты и лицензии

Обе версии REDOC запатентованы в Соединенных штатах [1614]. Рассматриваются и иностранные патенты. При заинтересованности в REDOC II или REDOC III обращайтесь к Майклу Вуду (Michael C. Wood, Delta Computec, Inc., 6647 Old Thompson Rd., Syracuse, NY 13211).

LOKI

LOKI разработан в Австралии и впервые был представлен в 1990 году в качестве возможной альтернативы DES [273]. В нем используются 64-битовый блок и 64-битовый ключ. Общая структура алгоритма и использования ключа описана в [274, 275], а схема S-блоков - в [1247].

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

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

LOKI91

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

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

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

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

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

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

Описание LOKI91

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

Рис. 13-8. LOKI91.

Табл. 13-1.
Перестановка с расширением

48-битовый результат делится на четыре 12-битовых блока, для каждого из которых выполняется следующая подстановка с использованием S-блока: берется каждый 12-битовый вход, по 2 крайних левых и крайних правых бита используются для получения номера r, в 8 центральных бит образуют номер c. Результатом S-блока - O - является следующее значение:

O(r,c) = (c + ((r* 17) Å 0xff) & 0xff)³¹ mod P_r

P_r приведено в Табл. 13-2.

Табл. 13-2.
P_r

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

Табл. 13-3.
Перестановка с помощью P-блока

Подключи из ключа выделяются достаточно прямолинейно. 64-битовый ключ разбивается на левую и правую половины. На каждом этапе подключом является левая половина. Далее она циклически сдвигается влево на 12 или 13 битов, затем после каждых двух этапов левая и правая половины меняются местами. Как и в DES для шифрования и дешифрирования используется один и тот же алгоритм с некоторыми изменениями в использовании подключей.