IX Международная студенческая научная конференция Студенческий научный форум - 2017

Введение

MISTY1 - блочный алгоритм шифрования, создан для компании Mitsubishi Electric криптологом Мицуру Мацуи. Название является аббревиатурой Mitsubishi Improved Security Technology. Алгоритм был разработан в 1995-1996 гг. Известны также две модификации алгоритма MISTY1: MISTY2 и KASUMI

Шифр стал победителем на Европейском конкурсе NESSIE. В результате анализа алгоритма эксперты сделали вывод, что никаких серьёзных уязвимостей данный алгоритм не имеет (преимущественно, благодаря вложенным сетям Фейстеля, что существенно затрудняет криптоанализ). У него высокий запас криптостойкости, алгоритм имеет высокую скорость шифрования и весьма эффективен для аппаратной реализации.

Алгоритм был разработан на основе теории «подтверждённой безопасности» против дифференциального и линейного криптоанализа. Этот алгоритм был спроектирован, чтобы противостоять криптоатакам, известным на момент создания.

С момента публикации Мисти было проведено много исследований, чтобы оценить его уровень безопасности.

Дифференциальный и невозможный дифференциальный криптоанализ высокого порядка эффективно применяется к блочным шифрам с малой степенью. Наилучшие результаты для обоих вариантов были получены для 5-уровневого алгоритмаMISTY1 без FL функций.

Именно FL функции и широкобитные AND/OR операции в сильно затрудняют использование дифференциального криптоанализа, что не мешает проведению в этом направлении все новых исследований и достижению все более близких к решению результатов.

1. Параметры исходных данных

MISTY1 — это шифр на основе вложенных сетей Фейстеля с варьируемым числом раундов. Рекомендовано использование 8-раундовой версии, но может использоваться любое количество раундов, кратное 4-м. Размер блока исходного текста – 64 бита, размер ключа – 128 бит.

Для работы алгоритма также предварительно выполняется процедура расширения ключа, которая для 8-ми раундов вычисляет 1216 битов ключевой информации из 128-битного ключа шифрования.

1. Структура алгоритма

Для удовлетворения требованиям конкурса NESSIE, а также для удовлетворения задачи мультиплатформенности, в алгоритме MISTY1 использовались следующие методы шифрования:

• Логические операции.

• Арифметические операции.

• Операции сдвига.

• Таблицы перестановок.

Структура данного алгоритма представлена на рисунке 1.

Как говорилось выше, алгоритм MISTY1 основан на «вложенных» сетях Фейстеля. Сначала блок исходного текста разбивается на два 32-битных субблока, после чего выполняется r раундов следующих преобразований[1]:

• В каждом нечетном раунде обасубблока обрабатываются операцией FL

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

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

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

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

1. Операция FL.

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

где:

• L и R — входные значения левого и правого фрагментов соответственно;

• L' и R' — выходные значения;

• и — фрагменты j-го подключа i-го раунда для функции FL (процедура расширения ключа подробно описана далее);

• и — побитовые логические операции «и» и «или» соответственно.

Рис.2 - Операция FL

1. Операция FO.

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

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

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

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

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

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

Блок-схема операции FO представлена на рисунке 3.

Рис. 3 - Операция FO

1. Операция FI

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

• Левая часть подвергается обработке S-box. 9-битная часть (в 1-м и 3-м раундах) обрабатывается таблицей S9, а 7-битная (во 2-м раунде) — таблицей S7. Данные таблицы описаны ниже.

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

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

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

На рисунке № 4 жирными линиями выделен 9-битный поток данных.

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

 

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

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

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

• 20 фрагментов ключа (), каждый из которых имеет размер по 16 битов;

• 32 16-битных фрагмента ();

• 24 7-битных фрагмента (при k=4 , то есть в 4-м раунде функции FO, операция FI не выполняется);

• 24 9-битных фрагмента .

Выполняется данное вычисление следующим образом:

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

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

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

1. Необходимые фрагменты расширенного ключа «набираются» по мере выполнения преобразований из массивов…, … и согласно таблицам 1 и 2.

Таблица 1

Назначение
Фрагмент

Таблица 2

Назначение
Фрагмент

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

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

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

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

• вместо операции FL используется обратная ей операция - FLI.

Схемывыполнения функции FLI и процедуры расшифрования приведены на рисунках 6 и 7 соответственно:

1.  

   1. Операция FLI

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

Рис. 6 - Операция FLI

Рис. 7 - Процесс расшифрования

1. Методы анализа

Как говорилось в начале статьи, дифференциальный и невозможный дифференциальный анализы оказались эффективны лишь к версиям шифра с меньшим количеством раундов и без операции FL[2][3]. Тем не менее, на данный момент это направление анализа, особенно использование слабых ключей, наиболее перспективно, т.к. приближено к реальным возможным допущениям при использовании алгоритма.

Так же, ученым из Японии был проведен интегральный анализ полного алгоритма, используя открытых текстов со сложностью вычисления, равной [4].

Линейный анализ дал результаты только для 7-раундовой версии шифра, и также без операции FL[5].

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

1. Заключение

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

Литература:

1. Панасенко С.П. «Алгоритмы шифрования. Специальный справочник» - СПб.: БХВ-Пертербург, 2009 – 576с.

2. An Improved Impossible Differential Attack on MISTY1 Orr Dunkelman1 and Nathan Keller Ecole Normale Sup´erieure D´epartement d’Informatique, CNRS, INRIA 45 rue d’Ulm, 75230 Paris, France. Einstein Institute of Mathematics, Hebrew University. Jerusalem 91904, Israel;

3. Weak Keys of the Full MISTY1 Block Cipher for Related-Key Cryptanalysis - Jiqiang Lu, Wun-She Yap and Yongzhuang We;

4. Integral Cryptanalysis on Full MISTY1 - Yosuke Todo. NTT Secure Platform Laboratories, Tokyo, Japan;

5. Zero-Correlation Linear Cryptanalysis of Reduced-round MISTY1 - Wentan Yi and Shaozhen Chen. State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China.

Код для цитирования: Скопировать