MISTY1 (MISTY1)

MISTY1
Создатель	Мицуру Мацуи, Тэцуя Итикава, Дзюн Соримати, Тосио Токита, Ацухиро Ямагиси
Создан	1995 г.
Опубликован	1996 г.
Размер ключа	128 бит
Размер блока	64 бит
Число раундов	4×n (рекомендуется 8)
Тип	Сеть Фейстеля

MISTY1 (или MISTY-1) — блочный алгоритм шифрования, созданный на основе «вложенных» сетей Фейстеля в 1995 году криптологом Мицуру Мацуи (Mitsuru Matsui) совместно с группой специалистов для компании Mitsubishi Electric. MISTY — это аббревиатура Mitsubishi Improved Security Technology, а также инициалы создателей алгоритма: в разработке алгоритма также приняли участие Тэцуя Итикава (Tetsuya Ichikawa), Дзюн Соримати (Jun Sorimachi), Тосио Токита (Toshio Tokita) и Ацухиро Ямагиси (Atsuhiro Yamagishi) . Алгоритм был разработан в 1995 году, однако прошел лицензирование и был опубликован уже в 1996 году.

MISTY1 — это сеть Фейстеля с изменчивым числом раундов (рекомендовано 8, но оно может быть любым, кратным 4). Алгоритм работает с 64-битными блоками и использует 128-битный ключ. Шифр стал победителем среди алгоритмов, шифрующих 64-битные блоки, на Европейском конкурсе NESSIE . В результате анализа алгоритма, проведённого в рамках этого конкурса и до него, эксперты сделали вывод, что никаких серьёзных уязвимостей данный алгоритм не имеет (они особо отметили, что именно структура алгоритма с вложенными сетями Фейстеля существенно затрудняет криптоанализ). Аналогичные исследования были проведены и в рамках проекта CRYPTREC по выбору криптоалгоритмов для электронного правительства Японии. Эксперты проекта весьма положительно оценили алгоритм MISTY1, сделав вывод, что у него высокий запас криптостойкости, алгоритм имеет высокую скорость шифрования и весьма эффективен для аппаратной реализации.

MISTY1 запатентованный алгоритм. Однако исконный владелец патента, Mitsubishi Electric, объявил, что будет выдавать лицензию на использование бесплатно.

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

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

MISTY разрабатывался как криптосистема, которая может быть использована на практике большим числом прикладных систем, к примеру: программное обеспечение для работы со смарт-картами или в быстрых ATM сетях. Поэтому в основе алгоритма MISTY1 лежат три следующих принципа:

1. Высокий уровень безопасности шифра;
2. Быстрая исполнимость на всех процессорах на время создания алгоритма;
3. Быстрота работы аппаратных средств, основанных на данном алгоритме.

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

1. Логические операции. Операции AND, OR и XOR — наиболее распространённые элементы шифроалгоритмов. И хотя от них нельзя ожидать высокого уровня защищённости, эти операции выполняются быстро и эффективно любыми аппаратными средствами и легко реализуемы в программном обеспечении.
2. Арифметические операции. Шифрование аппаратными средствами приводит к задержкам и повышает время шифрования и передачи данных. Однако время шифрования таких операций как сложение, вычитание, и иногда умножение, для шифров, ориентированных на программную реализацию, вполне соответствуют предлагаемому уровню безопасности.
3. Операции сдвига. Часто используемая операция в криптосистемах, так как дёшево и легко реализуема аппаратно. Стоит заметить, что программная реализация операции сдвига, к примеру 32-битных слов, может выполняться достаточно медленно на процессорах меньшей разрядности.
4. Таблицы перестановок. Подобные операции требовательны к скорости доступа к памяти, что следует учесть при программной реализации алгоритма. Аппаратные средства в свою очередь следует оптимизировать к данному шифру, для выполнения предполагаемых временных ограничений на обработку и передачу информации.

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

1. Каждый субблок обрабатывается операцией FL (операции описаны далее). Этот шаг выполняется только в нечётных раундах.
2. Над обрабатываемым субблоком выполняется операция FO.
3. Результат этих операций накладывается побитовой логической операцией «исключающее или» (XOR) на необработанный субблок.
4. Субблоки меняются местами. После заключительного раунда оба субблока ещё раз обрабатываются операцией FL.

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

Операция FL

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

$R'=R\oplus (L\&KL_{\text{i,j,1}})$

$L'=L\oplus (R'|KL_{\text{i,j,2}})$

где:

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

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

$KL_{\text{i,j,1}}$ и $KL_{\text{i,j,2}}$ — фрагменты j-го подключа i-го раунда для функции FL (процедура расширения ключа подробно описана далее);

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

Операция FO

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

1. На левый фрагмент операцией XOR накладывается фрагмент ключа раунда $KO_{\text{i,k}}$, где k — номер раунда функции FO.
2. Левый фрагмент обрабатывается операцией FI.
3. На левый фрагмент накладывается операцией XOR значение правого фрагмента.
4. Фрагменты меняются местами.

После третьего раунда операции FO на левый фрагмент накладывается операцией XOR дополнительный фрагмент ключа $KO_{\text{i,4}}$.

Операция FI

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

1. Левая часть «прогоняется» через таблицу замен. 9-битная часть (в раундах № 1 и 3) обрабатывается таблицей S9, а 7-битная (в раунде № 2) — таблицей S7. Данные таблицы описаны далее.
2. На левую часть операцией XOR накладывается текущее значение правой части. При этом, если справа 7-битная часть, она дополняется нулями слева, а у 9-битной части удаляются слева два бита.
3. Во втором раунде на левую часть операцией XOR накладывается фрагмент ключа раунда $KI_{\text{i,k,1}}$, а на правую — фрагмент $KI_{\text{i,k,2}}$. В остальных раундах эти действия не выполняются.
4. Левая и правая части меняются местами.

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

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

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

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

• 20 фрагментов ключа $KL_{\text{i,j,m}}$ (${\text{i}}=1,3,5,7,9;1\leqslant {\text{j}}\leqslant 2;1\leqslant {\text{m}}\leqslant 2$), каждый из которых имеет размер по 16 битов;
• 32 16-битных фрагмента $KO_{\text{i,k}}$ ($1\leqslant {\text{i}}\leqslant 2;1\leqslant {\text{k}}\leqslant 4$);
• 24 7-битных фрагмента $KI_{\text{i,k,1}}$ (при ${\text{k}}=4$ , то есть в 4-м раунде функции FO, операция FI не выполняется);
• 24 9-битных фрагмента $KI_{\text{i,k,2}}$.

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

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

2. Формируются значения $K'_{\text{1}}...K'_{\text{8}}$: в качестве $K'_{\text{n}}$ используется результат обработки значения $K_{\text{n}}$ функцией FI, которая в качестве ключа (то есть совокупности требуемых 7- и 9-битного фрагментов) использует значение $K'_{\text{n+1}}$ (здесь и далее, если индекс n фрагмента ключа превышает 8, то вместо него используется индекс n-8).

3. Необходимые фрагменты расширенного ключа «набираются» по мере выполнения преобразований из массивов $K_{\text{1}}...K_{\text{8}}$, $K'_{\text{1}}...K'_{\text{8}}$ и согласно таблицам ниже.

Назначение	$KO_{\text{i,1}}$	$KO_{\text{i,2}}$	$KO_{\text{i,3}}$	$KO_{\text{i,4}}$	$KI_{\text{i,1}}$	$KI_{\text{i,2}}$	$KI_{\text{i,3}}$
Фрагмент	$K_{\text{i}}$	$K_{\text{i+2}}$	$K_{\text{i+7}}$	$K_{\text{i+4}}$	$K'_{\text{i+5}}$	$K'_{\text{i+1}}$	$K'_{\text{i+3}}$

Назначение	$KL_{\text{i,1,1}}$	$KL_{\text{i,2,1}}$	$KL_{\text{i,1,2}}$	$KL_{\text{i,2,2}}$
Фрагмент	$K_{\text{(i+1)/2}}$	$K'_{\text{(i+1)2+2}}$	$K'_{\text{(i+1)2+6}}$	$K_{\text{(i+1)/2+4}}$

4. 16-битный фрагмент $KI_{\text{i,k}}$ делится на 7-битный фрагмент $KI_{\text{i,k,1}}$ и 9-битный $KI_{\text{i,k,2}}$.

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

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

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

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

Операция FLI

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

$L'=L\oplus (R\&KL_{\text{i,j,2}})$

$R'=R\oplus (L'|KL_{\text{i,j,1}})$

Безопасность

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

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

Дифференциальный криптоанализ высокого порядка эффективно применяется к блочным шифрам с малой степенью. Мисти содержит 2 look-up таблицы S7 и S9, обе с малой ad, 3 и 2 соответственно. Поэтому достаточно много статей посвящены дифференциальному криптоанализу мисти. Наилучший результат был получен для 5-уровневого алгоритма без FL функций. Однако именно присутствие FL функций и широкобитных AND/OR операции в них сильно затрудняет использование дифференциального криптоанализа высокого порядка.

Невозможный дифференциальный анализ также применим к блочному шрифту с одинаковым значением подключа в каждом раунде (или в каждом n-ом раунде). И так как MISTY1 имеет достаточно простую систему расширения ключа, вполне естественно рассмотреть применимость данной атаки к данному алгоритму. Лучший результата для подобной атаки был также получен при рассмотрении алгоритма без FL функций.

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

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

Применение и модификации

Существует модификация данного алгоритма — MISTY2. Однако она не получила широкой известности вследствие низкого уровня криптостойкости.

Так же получила распространение модификация MISTY1 — алгоритм KASUMI — в 2000 году стал стандартом шифрования мобильной связи W-CDMA.

См. также

• KASUMI
• MISTY2
• NESSIE
• CRYPTREC

Литература

1. MISTY1 Specification [1]
2. MISTY1 Supporting document [2]
3. 3.36. Алгоритмы MISTY1 и MISTY2 из книги «Алгоритмы шифрования. Специальный справочник», Сергей Панасенко, 2009, ISBN 978-5-9775-0319-8

• NESSIE (англ.). — Официальный сайт NESSIE.
• License statement (англ.). — MISTY1 License statement. Архивировано из оригинала 30 марта 2012 года.

Ссылки

• RFC 2994
• Mitsubishi — About MISTY  (англ.)
• MISTY1 patent statement from Mitsubishi  (англ.)
• John Savard’s description of MISTY  (англ.)
• SCAN’s entry on MISTY1  (англ.)
• «CRYPTREC Report 2002; Report of the Cryptographic technique evaluation (FY 2002)» — Детальное описание алгоритма (недоступная ссылка)  (англ.)
• Vol.100/December 2002 Mitsubishi Electric ADVANCE  (англ.)
• Supporting Document of MISTY1  (англ.)
• Block Ciphers: Security Proofs, Cryptanalysis, Design, and Fault Attacks (недоступная ссылка)  (англ.)
• Alex Biryukov. Block Ciphers and Stream Ciphers: The State of the Art  (англ.)