MISTY1 - блочный алгоритм шифрования, создан для компании Mitsubishi Electric криптологом Мицуру Мацуи. Название является аббревиатурой Mitsubishi Improved Security Technology. Алгоритм был разработан в 1995-1996 гг. Известны также две модификации алгоритма MISTY1: MISTY2 и KASUMI
Шифр стал победителем на Европейском конкурсе NESSIE. В результате анализа алгоритма эксперты сделали вывод, что никаких серьёзных уязвимостей данный алгоритм не имеет (преимущественно, благодаря вложенным сетям Фейстеля, что существенно затрудняет криптоанализ). У него высокий запас криптостойкости, алгоритм имеет высокую скорость шифрования и весьма эффективен для аппаратной реализации.
Алгоритм был разработан на основе теории «подтверждённой безопасности» против дифференциального и линейного криптоанализа. Этот алгоритм был спроектирован, чтобы противостоять криптоатакам, известным на момент создания.
С момента публикации Мисти было проведено много исследований, чтобы оценить его уровень безопасности.
Дифференциальный и невозможный дифференциальный криптоанализ высокого порядка эффективно применяется к блочным шифрам с малой степенью. Наилучшие результаты для обоих вариантов были получены для 5-уровневого алгоритмаMISTY1 без FL функций.
Именно FL функции и широкобитные AND/OR операции в сильно затрудняют использование дифференциального криптоанализа, что не мешает проведению в этом направлении все новых исследований и достижению все более близких к решению результатов.
Параметры исходных данных
MISTY1 — это шифр на основе вложенных сетей Фейстеля с варьируемым числом раундов. Рекомендовано использование 8-раундовой версии, но может использоваться любое количество раундов, кратное 4-м. Размер блока исходного текста – 64 бита, размер ключа – 128 бит.
Для работы алгоритма также предварительно выполняется процедура расширения ключа, которая для 8-ми раундов вычисляет 1216 битов ключевой информации из 128-битного ключа шифрования.
Структура алгоритма
Для удовлетворения требованиям конкурса NESSIE, а также для удовлетворения задачи мультиплатформенности, в алгоритме MISTY1 использовались следующие методы шифрования:
Логические операции.
Арифметические операции.
Операции сдвига.
Таблицы перестановок.
Структура данного алгоритма представлена на рисунке 1.
Как говорилось выше, алгоритм MISTY1 основан на «вложенных» сетях Фейстеля. Сначала блок исходного текста разбивается на два 32-битных субблока, после чего выполняется r раундов следующих преобразований[1]:
В каждом нечетном раунде обасубблока обрабатываются операцией FL
Над обрабатываемым субблоком выполняется операция FO.
Результат этих операций накладывается логической операцией «исключающее или» (XOR) на необработанный субблок.
Субблоки меняются местами. После заключительного раунда оба субблока ещё раз обрабатываются операцией FL.
Рис.1 - Структура алгоритмаMISTY1
Операция FL.
Обрабатываемый32-битный субблок разбивается на два 16-битных фрагмента, к которым применяются следующие операции(рисунок 2):
где:
L и R — входные значения левого и правого фрагментов соответственно;
L' и R' — выходные значения;
и — фрагменты j-го подключа i-го раунда для функции FL (процедура расширения ключа подробно описана далее);
и — побитовые логические операции «и» и «или» соответственно.
Рис.2 - Операция FL
Операция FO.
Именно эта функция является вложенной сетью Фейстеля. Здесь, как и ранее, выполняется разбиение входного значения на два 16-битных фрагмента, проходящих 3 раунда следующих преобразований:
На левый фрагмент операцией XOR накладывается фрагмент ключа ,где k — номер раунда функции FO.
Левый фрагмент обрабатывается операцией FI.
На левый фрагмент накладывается операцией XOR значение правого фрагмента.
Фрагменты меняются местами.
После третьего раунда операции FO на левый фрагмент накладывается операцией XOR дополнительный фрагмент ключа.
Блок-схема операции FO представлена на рисунке 3.
Рис. 3 - Операция FO
Операция 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 могут быть реализованы как с помощью вычислений, так и непосредственно таблицами.
Расширение ключа
Для 8 раундов алгоритма результатом процедуры расширения ключа будет следующий набор ключевых значений:
20 фрагментов ключа (), каждый из которых имеет размер по 16 битов;
32 16-битных фрагмента ();
24 7-битных фрагмента (при k=4 , то есть в 4-м раунде функции FO, операция FI не выполняется);
24 9-битных фрагмента .
Выполняется данное вычисление следующим образом:
128-битный ключ делится на 8 фрагментов … по 16 битов каждый.
Формируются значения…(рисунок 5): в качестве используется результат обработки значения функцией FI, которая в качестве ключа (то есть совокупности требуемых 7- и 9-битного фрагментов) использует значение(если индекс n фрагмента ключа превышает 8, то вместо него используется индекс n-8).
Рис. 5 - Формирование промежуточных ключей
Необходимые фрагменты расширенного ключа «набираются» по мере выполнения преобразований из массивов…, … и согласно таблицам 1 и 2.
Таблица 1
Назначение |
|||||||
Фрагмент |
Таблица 2
Назначение |
||||
Фрагмент |
16-битный фрагмент делится на 7-битный фрагмент и 9-битный .
Расшифрование
Расшифрование производится выполнением тех же операций, что и при зашифровании, но со следующими изменениями:
фрагменты расширенного ключа используются в обратной последовательности,
вместо операции FL используется обратная ей операция - FLI.
Схемывыполнения функции FLI и процедуры расшифрования приведены на рисунках 6 и 7 соответственно:
Операция FLI
Операция FLI определена следующим образом:
Рис. 6 - Операция FLI
Рис. 7 - Процесс расшифрования
Методы анализа
Как говорилось в начале статьи, дифференциальный и невозможный дифференциальный анализы оказались эффективны лишь к версиям шифра с меньшим количеством раундов и без операции FL[2][3]. Тем не менее, на данный момент это направление анализа, особенно использование слабых ключей, наиболее перспективно, т.к. приближено к реальным возможным допущениям при использовании алгоритма.
Так же, ученым из Японии был проведен интегральный анализ полного алгоритма, используя открытых текстов со сложностью вычисления, равной [4].
Линейный анализ дал результаты только для 7-раундовой версии шифра, и также без операции FL[5].
Т.к. MISTY1 создавался, в том числе, из расчета на аппаратную реализацию, имеет смысл дифференциальный анализ, основанный на использовании атаки по ошибкам вычислений, что в данном случае приближено к реальности.
Заключение
Таким образом, была подробно описана структура алгоритма шифрования MISTY1 и рассмотрены методы его анализа, наиболее прагматичные направления исследования. Далее предстоит создание программной реализации для более детального рассмотрения алгоритма и набор статистических данных для полного исследования и поиска оптимального подхода к анализу MISTY1.
Литература:
Панасенко С.П. «Алгоритмы шифрования. Специальный справочник» - СПб.: БХВ-Пертербург, 2009 – 576с.
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;
Weak Keys of the Full MISTY1 Block Cipher for Related-Key Cryptanalysis - Jiqiang Lu, Wun-She Yap and Yongzhuang We;
Integral Cryptanalysis on Full MISTY1 - Yosuke Todo. NTT Secure Platform Laboratories, Tokyo, Japan;
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.