3.36. Алгоритмы MISTY1 и MISTY2

Фрагмент книги "Алгоритмы шифрования. Специальный справочник". © Панасенко Сергей, 2009

Алгоритм MISTY1 разработан в 1995–1996 гг. командой специалистов под руководством известного криптолога Мицуру Мацуи из компании Mitsubishi Electric (Япония). В разработке алгоритма приняли участие Тецуя Ичикава (Tetsuya Ichikawa), Джун Соримачи (Jun Sorimachi), Тошио Токита (Toshio Tokita) и Ацухиро Ямагиши (Atsuhiro Yamagishi) [395]. Известны также две модификации алгоритма MISTY1: MISTY2 и KASUMI, которые будут кратко описаны далее.

Начнем с подробного описания алгоритма MISTY1.

Структура алгоритма MISTY1

Алгоритм MISTY1 имеет весьма необычную структуру – он основан на «вложенных» сетях Фейстеля. Сначала 64-битный шифруемый блок данных разбивается на два 32-битных субблока, после чего выполняется r раундов следующих преобразований (рис. 3.135) [258, 291]:

Рис. 3.135. Структура алгоритма MISTY1

1. Каждый субблок обрабатывается операцией FL (операции описаны далее). Этот шаг выполняется только в нечетных раундах.

2. Над обрабатываемым субблоком выполняется операция FO.

3. Результат этих операций накладывается побитовой логической операцией «исключающее или» (XOR) на необработанный субблок.

4. Субблоки меняются местами.

После заключительного раунда оба субблока еще раз обрабатываются операцией FL.

Рекомендуемым количеством раундов алгоритма является 8, но количество раундов алгоритма может быть также любым, превышающим 8 и кратным четырем.

Рис. 3.136. Операция FL алгоритма MISTY1

Операция FL является достаточно простой. Обрабатываемый ей субблок разбивается на два 16-битных фрагмента, над которыми выполняются следующие действия (рис. 3.136):

где:

• L и R – входные значения левого и правого фрагментов соответственно;
• и  – выходные значения;
• и  – фрагменты j-го подключа i-го раунда для функции FL (процедура расширения ключа подробно описана далее);
• & и | – побитовые логические операции «и» и «или» соответственно.

Рис. 3.137. Операция FO алгоритма MISTY1

Функция FO более интересна – именно она является вложенной сетью Фейстеля (рис. 3.137). Аналогично предыдущим, функцией выполняется разбиение входного значения на два 16-битных фрагмента, после чего выполняются 3 раунда следующих действий:

1. На левый фрагмент операцией XOR накладывается фрагмент ключа раунда , где k – номер раунда функции FO.

2. Левый фрагмент обрабатывается операцией FI.

3. На левый фрагмент накладывается операцией XOR значение правого фрагмента.

4. Фрагменты меняются местами.

После третьего раунда операции FO на левый фрагмент накладывается операцией XOR дополнительный фрагмент ключа .

Рис. 3.138. Операция FI

FI также представляет собой сеть Фейстеля, т. е. это уже третий уровень вложенности. В отличие от сетей Фейстеля на двух верхних уровнях, данная сеть является несбалансированной: обрабатываемый 16-битный фрагмент делится на две части: 9-битную левую и 7-битную правую. Затем выполняются 3 раунда, которые состоят из следующих действий (рис. 3.138):

1. Левая часть «прогоняется» через таблицу замен. 9-битная часть (в раундах №№ 1 и 3) обрабатывается таблицей S9, а 7-битная (в раунде № 2) – таблицей S7. Данные таблицы описаны далее.

2. На левую часть операцией XOR накладывается текущее значение правой части. При этом, если справа 7-битная часть, она дополняется нулями слева, а у 9-битной части удаляются слева два бита.

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

4. Левая и правая части меняются местами.

Для наглядности на рис. 3.138 жирными линиями выделен 9-битный поток данных.

Таблицы S7 и S9 алгоритма MISTY1 могут быть реализованы как с помощью вычислений, так и непосредственно таблицами, хранимыми в энергонезависимой памяти шифрующего устройства [258, 291]. При реализации алгоритма должен выбираться вариант использования таблиц в зависимости от ресурсов шифрующего устройства. Данные таблицы приведены в Приложении 1.

Расшифрование

Расшифрование производится выполнением тех же операций, что и при зашифровании, но со следующими изменениями:

• фрагменты расширенного ключа используются в обратной последовательности;
• вместо операции FL используется обратная ей операция (обозначим ее FLI).

Схема процедуры расшифрования приведена на рис. 3.139.

Рис. 3.139. Расшифрование алгоритмом MISTY1

Рис. 3.140. Операция FLI алгоритма MISTY1

Операция FLI определена следующим образом (рис. 3.140):

Расширение ключа

Задача процедуры расширения ключа состоит в формировании следующего набора используемых фрагментов ключа (для 8 раундов алгоритма):

• 20 фрагментов ключа (; ; ), каждый из которых имеет размер по 16 битов;
• 32 16-битных фрагмента (, );
• 24 7-битных фрагмента  (при , т. е. в 4-м раунде функции FO, операция FI не выполняется);
• 24 9-битных фрагмента .

Таким образом, процедура расширения ключа вычисляет 1216 битов ключевой информации из 128-битного ключа шифрования алгоритма MISTY1. Выполняется данное вычисление следующим образом:

1. 128-битный ключ делится на 8 фрагментов  по 16 битов каждый.

2. Формируются значения (рис. 3.141): в качестве используется результат обработки значения функцией FI, которая в качестве ключа (т. е. совокупности требуемых 7- и 9-битного фрагментов) использует значение (здесь и далее, если индекс n фрагмента ключа превышает 8, то вместо него используется индекс ).

Рис. 3.141. Формирование промежуточных ключей в алгоритме MISTY1

3. Необходимые фрагменты расширенного ключа «набираются» по мере выполнения преобразований из массивов  и согласно табл. 3.81 и 3.82.

Таблица 3.81

Таблица 3.82

4. 16-битный фрагмент делится на 7-битный фрагмент и 9-битный .

Алгоритм MISTY2

В отличие от MISTY1, алгоритм MISTY2 не участвовал в конкурсе NESSIE (см. разд. 2.2) и не снискал такой широкой известности. MISTY2 незначительно отличается от MISTY1: он использует те же функции, но в несколько другой последовательности.

Структура MISTY2 приведена на рис. 3.142. В данном алгоритме существует не 2, а 4 различных типа раундов, которые выполняются поочередно, после чего повторяются требуемое количество раз [255, 257].

Рис. 3.142. Структура алгоритма MISTY2

Структура раунда 1 (после приведенных далее операций в каждом раунде субблоки меняются местами):

1. Оба субблока обрабатываются операцией FL.

2. Левый субблок обрабатывается операцией FO.

3. Значение правого субблока обрабатывается операцией FL и накладывается на левый субблок операцией XOR.

Структура раунда 2:

1. Левый субблок обрабатывается операцией FO.

2. Значение правого субблока накладывается на левый.

Структура раунда 3:

1. Левый субблок обрабатывается операцией FO.

2. Значение правого субблока обрабатывается операцией FL и накладывается на левый.

Структура раунда 4 аналогична раунду 2.

Процедура расширения ключа, а также структура операций FO и FL аналогичны описанным выше для алгоритма MISTY1. Рекомендуемым количеством раундов для MISTY2 является 12, а не 8.

Алгоритм MISTY2 является более быстродействующим, чем MISTY1 при возможности параллельной обработки данных, поскольку данный алгоритм может выполнять по 2 раунда параллельно [257, 310].

Алгоритм KASUMI

Алгоритм KASUMI несколько больше отличается от MISTY1, чем MISTY2. Основные отличия таковы [138]:

• операция FL обрабатывает только один субблок, но в каждом раунде;
• в данной операции присутствует дополнительное действие – вращение одного из обрабатываемых фрагментов на 1 бит;
• в операции FO используется 3 фрагмента ключа, а не 4;
• в операции FI используется 4 «прогона» данных через таблицы замен, а не 3, причем таблицы замен также изменены;
• принципиально изменена процедура расширения ключа.

Алгоритм KASUMI является стандартом шифрования данных в сетях сотовой связи третьего поколения. Существует мнение, что алгоритм KASUMI менее стоек, чем MISTY1, поскольку существуют атаки на его полнораундовую версию. По данным, приведенным в [236], KASUMI проигрывает MISTY1 по всем основным параметрам. В частности, несмотря на существенно более простую процедуру расширения ключа, расширение ключа в KASUMI выполняется в 2 раза медленнее, чем в MISTY1. Хотя считается, что изменения, внесенные в MISTY1 с целью получения алгоритма KASUMI, должны были, наоборот, усилить алгоритм [83].

Подробное описание KASUMI и результатов его криптоанализа можно найти в разд. 3.27.

Помимо алгоритмов MISTY2 и KASUMI, часть преобразований алгоритма MISTY1 используются и в алгоритме Camellia, который подробно описан в разд. 3.9.

Криптоанализ алгоритмов MISTY1 и MISTY2

Алгоритм MISTY1 вызвал огромный интерес у криптологов как благодаря своему участию в конкурсе NESSIE, так и из-за своего родства с не менее известным алгоритмом KASUMI.

Первичный криптоанализ алгоритма выполнен его разработчиками, его результаты опубликованы в [259]. Авторы алгоритма доказали криптостойкость алгоритма к линейному и дифференциальному криптоанализу, а также утверждают, что MISTY1 устойчив к сдвиговым атакам, использованию невозможных дифференциалов и ряду других атак.

В 2001 г. невозможные дифференциалы для атаки на варианты MISTY с уменьшенным числом раундов применил Ульрих Кюн: 4-раундовый MISTY1 вскрывается при наличии выбранных открытых текстов с помощью тестовых операций шифрования; для атаки на 5-раундовый MISTY2 требуется выбранных открытых текстов и операций [230]. Он же в 2002 г. предложил принципиально новую атаку (названную «slicing attack»), действующую против MISTY1, которой для вскрытия 4-раундового MISTY1 требуется существенно меньше ресурсов: выбранных открытых текстов и операций шифрования [231].

В том же 2001 г. известные криптоаналитики Ларс Кнудсен и Дэвид Вагнер предложили атаку на MISTY1 и MISTY2 методом интегрального криптоанализа. Данная атака позволяет вскрыть 5-раундовый MISTY1 при наличии выбранных открытых текстов выполнением операций шифрования или 6-раундовый MISTY2 при наличии выбранных открытых текстов выполнением операций [226]. Эти результаты являются лучшими из опубликованных для алгоритмов MISTY на текущий момент.

Проводились исследования и модифицированных вариантов алгоритма. В частности, в [370] исследован вариант без функций FL. Вскрывается 6 раундов алгоритма MISTY1 без FL-функций при наличии выбранных открытых текстов выполнением операций.

В результате анализа алгоритма MISTY1, проведенного в рамках конкурса NESSIE и до него, эксперты сделали вывод, что никаких серьезных уязвимостей данный алгоритм не имеет (они особо отметили, что именно структура алгоритма с вложенными сетями Фейстеля существенно затрудняет криптоанализ [307]). На этот вывод повлияли и результаты исследований алгоритма KASUMI, который, как было сказано выше, использует те же преобразования, что и MISTY1. В результате MISTY1 был выбран победителем конкурса NESSIE среди 64-битных алгоритмов блочного симметричного шифрования [305].

Аналогичные исследования были проведены и в рамках проекта CRYPTREC по выбору криптоалгоритмов для электронного правительства Японии. Эксперты проекта весьма положительно оценили алгоритм MISTY1, сделав вывод, что у него высокий запас криптостойкости, алгоритм имеет высокую скорость шифрования и весьма эффективен для аппаратной реализации [126].

Анализ алгоритмов семейства MISTY активно продолжается и в настоящее время. В качестве примера можно привести совсем недавнюю работу [238], в которой выполняется проверка стойкости преобразования FO против дифференциального криптоанализа. Стоит сказать и о том, что некоторые эксперты (например, в [310]) предрекают, что в ближайшем будущем будут появляться новые алгоритмы с MISTY-подобной структурой, поскольку данная структура весьма успешно зарекомендовала себя с точки зрения криптостойкости и быстродействия.

Перейти на главную страницу Карта сайта Перейти к информации о книге