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]:

Раунд алгоритма MISTY1

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

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

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

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

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

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

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

Операция FL алгоритма MISTY1

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

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

Формула

Формула

где:

Операция FO алгоритма MISTY1

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

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

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

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

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

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

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

Операция FI алгоритма MISTY1

Рис. 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.

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

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

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

Алгоритм MISTY1: расшифрование

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

Операция FLI алгоритма MISTY1

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

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

Формула

Формула

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

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

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

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

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

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

Рис. 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].

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

Рис. 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]:

Алгоритм 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-подобной структурой, поскольку данная структура весьма успешно зарекомендовала себя с точки зрения криптостойкости и быстродействия.

Алгоритмы шифрования...

Rambler's Top100 OZON.ru

Перейти на главную страницу

Карта сайта

Перейти к информации о книге

Последнее обновление: 18 января 2013 г.