MISTY1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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
2. MISTY1 Supporting document
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  (англ.)