MISTY1
MISTY1 | |
---|---|
Создатель | Мицуру Мацуи, Тэцуя Итикава, Дзюн Соримати, Тосио Токита, Ацухиро Ямагиси |
Создан | 1995 г. |
Опубликован | 1996 г.[1] |
Размер ключа | 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) [2]. Алгоритм был разработан в 1995 году, однако прошел лицензирование и был опубликован уже в 1996 году.
MISTY1 — это сеть Фейстеля с изменчивым числом раундов (рекомендовано 8, но оно может быть любым, кратным 4). Алгоритм работает с 64-битными блоками и использует 128-битный ключ. Шифр стал победителем среди алгоритмов, шифрующих 64-битные блоки, на Европейском конкурсе NESSIE [3][4]. В результате анализа алгоритма, проведённого в рамках этого конкурса и до него, эксперты сделали вывод, что никаких серьёзных уязвимостей данный алгоритм не имеет (они особо отметили, что именно структура алгоритма с вложенными сетями Фейстеля существенно затрудняет криптоанализ). Аналогичные исследования были проведены и в рамках проекта CRYPTREC по выбору криптоалгоритмов для электронного правительства Японии. Эксперты проекта весьма положительно оценили алгоритм MISTY1, сделав вывод, что у него высокий запас криптостойкости, алгоритм имеет высокую скорость шифрования и весьма эффективен для аппаратной реализации.
MISTY1 запатентованный алгоритм. Однако исконный владелец патента, Mitsubishi Electric, объявил, что будет выдавать лицензию на использование бесплатно.[5]
Структура алгоритма
![](https://cdn.xn--h1ajim.xn--p1ai/images/f/fb/Misty1_alg.png)
MISTY разрабатывался как криптосистема, которая может быть использована на практике большим числом прикладных систем, к примеру: программное обеспечение для работы со смарт-картами или в быстрых ATM сетях. Поэтому в основе алгоритма MISTY1 лежат три следующих принципа:
- Высокий уровень безопасности шифра;
- Быстрая исполнимость на всех процессорах на время создания алгоритма;
- Быстрота работы аппаратных средств, основанных на данном алгоритме.
Для удовлетворения данным требованиям в алгоритме MISTY1 использовались следующие методы шифрования:
- Логические операции. Операции AND, OR и XOR — наиболее распространённые элементы шифроалгоритмов. И хотя от них нельзя ожидать высокого уровня защищённости, эти операции выполняются быстро и эффективно любыми аппаратными средствами и легко реализуемы в программном обеспечении.
- Арифметические операции. Шифрование аппаратными средствами приводит к задержкам и повышает время шифрования и передачи данных. Однако время шифрования таких операций как сложение, вычитание, и иногда умножение, для шифров, ориентированных на программную реализацию, вполне соответствуют предлагаемому уровню безопасности.
- Операции сдвига. Часто используемая операция в криптосистемах, так как дёшево и легко реализуема аппаратно. Стоит заметить, что программная реализация операции сдвига, к примеру 32-битных слов, может выполняться достаточно медленно на процессорах меньшей разрядности.
- Таблицы перестановок. Подобные операции требовательны к скорости доступа к памяти, что следует учесть при программной реализации алгоритма. Аппаратные средства в свою очередь следует оптимизировать к данному шифру, для выполнения предполагаемых временных ограничений на обработку и передачу информации.
Алгоритм MISTY1 имеет весьма необычную структуру — он основан на «вложенных» сетях Фейстеля. Сначала 64-битный шифруемый блок данных разбивается на два 32-битных субблока, после чего выполняется r раундов следующих преобразований [6]:
- Каждый субблок обрабатывается операцией FL (операции описаны далее). Этот шаг выполняется только в нечётных раундах.
- Над обрабатываемым субблоком выполняется операция FO.
- Результат этих операций накладывается побитовой логической операцией «исключающее или» (XOR) на необработанный субблок.
- Субблоки меняются местами. После заключительного раунда оба субблока ещё раз обрабатываются операцией FL.
Рекомендуемым количеством раундов алгоритма является 8, но количество раундов алгоритма может быть также любым, превышающим 8 и кратным четырём.
Операция FL
Операция FL является достаточно простой. Обрабатываемый ей субблок разбивается на два 16-битных фрагмента, над которыми выполняются следующие действия:
[math]\displaystyle{ R' = R \oplus (L \& KL_{\text{i,j,1}}) }[/math]
[math]\displaystyle{ L' = L \oplus (R' | KL_{\text{i,j,2}}) }[/math]
где:
L и R — входные значения левого и правого фрагментов соответственно;
L' и R' — выходные значения;
[math]\displaystyle{ KL_{\text{i,j,1}} }[/math] и [math]\displaystyle{ KL_{\text{i,j,2}} }[/math] — фрагменты j-го подключа i-го раунда для функции FL (процедура расширения ключа подробно описана далее);
& и | — побитовые логические операции «и» и «или» соответственно.
Операция FO
Функция FO более интересна — именно она является вложенной сетью Фейстеля. Аналогично предыдущим, функцией выполняется разбиение входного значения на два 16-битных фрагмента, после чего выполняются 3 раунда следующих действий:
- На левый фрагмент операцией XOR накладывается фрагмент ключа раунда [math]\displaystyle{ KO_{\text{i,k}} }[/math], где k — номер раунда функции FO.
- Левый фрагмент обрабатывается операцией FI.
- На левый фрагмент накладывается операцией XOR значение правого фрагмента.
- Фрагменты меняются местами.
После третьего раунда операции FO на левый фрагмент накладывается операцией XOR дополнительный фрагмент ключа [math]\displaystyle{ KO_{\text{i,4}} }[/math].
Операция FI
FI также представляет собой сеть Фейстеля, то есть это уже третий уровень вложенности. В отличие от сетей Фейстеля на двух верхних уровнях, данная сеть является несбалансированной: обрабатываемый 16-битный фрагмент делится на две части: 9-битную левую и 7-битную правую. Затем выполняются 3 раунда, которые состоят из следующих действий:
- Левая часть «прогоняется» через таблицу замен. 9-битная часть (в раундах № 1 и 3) обрабатывается таблицей S9, а 7-битная (в раунде № 2) — таблицей S7. Данные таблицы описаны далее.
- На левую часть операцией XOR накладывается текущее значение правой части. При этом, если справа 7-битная часть, она дополняется нулями слева, а у 9-битной части удаляются слева два бита.
- Во втором раунде на левую часть операцией XOR накладывается фрагмент ключа раунда [math]\displaystyle{ KI_{\text{i,k,1}} }[/math], а на правую — фрагмент [math]\displaystyle{ KI_{\text{i,k,2}} }[/math]. В остальных раундах эти действия не выполняются.
- Левая и правая части меняются местами.
Для наглядности на рисунке жирными линиями выделен 9-битный поток данных.
Таблицы S7 и S9 алгоритма MISTY1 могут быть реализованы как с помощью вычислений, так и непосредственно таблицами, хранимыми в энергонезависимой памяти шифрующего устройства. При реализации алгоритма должен выбираться вариант использования таблиц в зависимости от ресурсов шифрующего устройства.
Расширение ключа
Задача процедуры расширения ключа состоит в формировании следующего набора используемых фрагментов ключа (для 8 раундов алгоритма):
- 20 фрагментов ключа [math]\displaystyle{ KL_{\text{i,j,m}} }[/math] ([math]\displaystyle{ \text{i}=1,3,5,7,9; 1 \leqslant \text{j} \leqslant 2; 1 \leqslant \text{m} \leqslant 2 }[/math]), каждый из которых имеет размер по 16 битов;
- 32 16-битных фрагмента [math]\displaystyle{ KO_{\text{i,k}} }[/math] ([math]\displaystyle{ 1 \leqslant \text{i} \leqslant 2; 1 \leqslant \text{k} \leqslant 4 }[/math]);
- 24 7-битных фрагмента [math]\displaystyle{ KI_{\text{i,k,1}} }[/math] (при [math]\displaystyle{ \text{k}=4 }[/math] , то есть в 4-м раунде функции FO, операция FI не выполняется);
- 24 9-битных фрагмента [math]\displaystyle{ KI_{\text{i,k,2}} }[/math].
Таким образом, процедура расширения ключа вычисляет 1216 битов ключевой информации из 128-битного ключа шифрования алгоритма MISTY1. Выполняется данное вычисление следующим образом:
1. 128-битный ключ делится на 8 фрагментов [math]\displaystyle{ K_{\text{1}}...K_{\text{8}} }[/math] по 16 битов каждый.
2. Формируются значения [math]\displaystyle{ K'_{\text{1}}...K'_{\text{8}} }[/math]: в качестве [math]\displaystyle{ K'_{\text{n}} }[/math] используется результат обработки значения [math]\displaystyle{ K_{\text{n}} }[/math] функцией FI, которая в качестве ключа (то есть совокупности требуемых 7- и 9-битного фрагментов) использует значение [math]\displaystyle{ K'_{\text{n+1}} }[/math] (здесь и далее, если индекс n фрагмента ключа превышает 8, то вместо него используется индекс n-8).
3. Необходимые фрагменты расширенного ключа «набираются» по мере выполнения преобразований из массивов [math]\displaystyle{ K_{\text{1}}...K_{\text{8}} }[/math], [math]\displaystyle{ K'_{\text{1}}...K'_{\text{8}} }[/math] и согласно таблицам ниже.
Назначение | [math]\displaystyle{ KO_{\text{i,1}} }[/math] | [math]\displaystyle{ KO_{\text{i,2}} }[/math] | [math]\displaystyle{ KO_{\text{i,3}} }[/math] | [math]\displaystyle{ KO_{\text{i,4}} }[/math] | [math]\displaystyle{ KI_{\text{i,1}} }[/math] | [math]\displaystyle{ KI_{\text{i,2}} }[/math] | [math]\displaystyle{ KI_{\text{i,3}} }[/math] |
---|---|---|---|---|---|---|---|
Фрагмент | [math]\displaystyle{ K_{\text{i}} }[/math] | [math]\displaystyle{ K_{\text{i+2}} }[/math] | [math]\displaystyle{ K_{\text{i+7}} }[/math] | [math]\displaystyle{ K_{\text{i+4}} }[/math] | [math]\displaystyle{ K'_{\text{i+5}} }[/math] | [math]\displaystyle{ K'_{\text{i+1}} }[/math] | [math]\displaystyle{ K'_{\text{i+3}} }[/math] |
Назначение | [math]\displaystyle{ KL_{\text{i,1,1}} }[/math] | [math]\displaystyle{ KL_{\text{i,2,1}} }[/math] | [math]\displaystyle{ KL_{\text{i,1,2}} }[/math] | [math]\displaystyle{ KL_{\text{i,2,2}} }[/math] |
---|---|---|---|---|
Фрагмент | [math]\displaystyle{ K_{\text{(i+1)/2}} }[/math] | [math]\displaystyle{ K'_{\text{(i+1)2+2}} }[/math] | [math]\displaystyle{ K'_{\text{(i+1)2+6}} }[/math] | [math]\displaystyle{ K_{\text{(i+1)/2+4}} }[/math] |
4. 16-битный фрагмент [math]\displaystyle{ KI_{\text{i,k}} }[/math] делится на 7-битный фрагмент [math]\displaystyle{ KI_{\text{i,k,1}} }[/math] и 9-битный [math]\displaystyle{ KI_{\text{i,k,2}} }[/math].
Расшифрование
Расшифрование производится выполнением тех же операций, что и при зашифровании, но со следующими изменениями:
- фрагменты расширенного ключа используются в обратной последовательности,
- вместо операции FL используется обратная ей операция (обозначим её FLI).
Схема процедуры расшифрования приведена на рис:
Операция FLI
Операция FLI определена следующим образом:
[math]\displaystyle{ L' = L \oplus (R \& KL_{\text{i,j,2}}) }[/math]
[math]\displaystyle{ R' = R \oplus (L' | KL_{\text{i,j,1}}) }[/math]
Безопасность
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.
См. также
Примечания
- ↑ Mitsuru Matsui. «Block encryption algorithm MISTY.» Technical report of IEICE ISEC96-11 (1996-07). (In Japanese).
- ↑ アーカイブされたコピー (недоступная ссылка). Дата обращения: 23 марта 2005. Архивировано 22 марта 2005 года.
- ↑ Архивированная копия . Дата обращения: 3 мая 2009. Архивировано 13 октября 2016 года.
- ↑ Конкурс NESSIE и алгоритм MISTY1 . Дата обращения: 3 мая 2009. Архивировано 30 января 2011 года.
- ↑ IETF Draft TLS MISTY1 01 . Дата обращения: 25 ноября 2011. Архивировано 30 марта 2012 года.
- ↑ http://web.eecs.utk.edu/~dunigan/cs594-cns96/misty1spec.pdf
Литература
- MISTY1 Specification [1]
- MISTY1 Supporting document [2]
- 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 (англ.)