MISTY1¶

MISTY1 — это алгоритм симметричного блочного шифрования, разработанный в 1995 году японскими криптографами Мицуру Мацуи и Сёдзи Миягути (компания Mitsubishi Electric). Он относится к классу блочных шифров с размером блока 64 бита и длиной ключа 128 бит. MISTY1 был создан как практичная реализация теоретических принципов, заложенных в семействе шифров MISTY (Mitsubishi Improved Security Technology), и отличается высокой устойчивостью к линейному и дифференциальному криптоанализу. Алгоритм был принят в качестве стандарта японской организации CRYPTREC (Cryptography Research and Evaluation Committees) и рекомендован для использования в государственных и коммерческих системах защиты информации.

¶История создания и стандартизация

Разработка MISTY1 началась в середине 1990-х годов в рамках исследовательского проекта Mitsubishi Electric. Основной целью было создание шифра, который бы обеспечивал доказуемую стойкость против известных методов криптоанализа — в первую очередь линейного и дифференциального. В 1995 году Мацуи и Миягути представили описание алгоритма на конференции Fast Software Encryption (FSE), а в 1997 году — его полную спецификацию.

В 2000 году MISTY1 был включён в список рекомендованных шифров японского проекта CRYPTREC, который оценивает криптографические алгоритмы для использования в государственных информационных системах. В 2003 году алгоритм был стандартизирован Международной организацией по стандартизации (ISO) и Международной электротехнической комиссией (IEC) в стандарте ISO/IEC 18033-3:2005 (блочные шифры). В 2010 году стандарт был пересмотрен, и MISTY1 сохранил свой статус.

Несмотря на то, что MISTY1 не получил такого широкого распространения, как AES или DES, он использовался в ряде коммерческих продуктов, включая системы мобильной связи (например, в стандарте 3GPP для шифрования трафика в UMTS, где применялся его вариант KASUMI), а также в смарт-картах и банковских терминалах.

¶Описание алгоритма

MISTY1 является блочным шифром с размером блока 64 бита и длиной ключа 128 бит. Он использует структуру, основанную на сети Фейстеля с нечётным числом раундов (8 раундов) и дополнительным нелинейным преобразованием на выходе. Алгоритм включает в себя несколько ключевых компонентов:

• Функция FO — основная раундовая функция, которая применяется к правой половине блока. Она состоит из трёх слоёв, каждый из которых включает в себя нелинейное преобразование (S-блоки) и линейное перемешивание.
• Функция FL — дополнительная функция, которая вводится в каждом втором раунде для усиления стойкости. Она выполняет простые операции XOR и AND с использованием ключевых материалов.
• S-блоки — нелинейные таблицы замены. MISTY1 использует два типа S-блоков: S7 (7-битный вход, 7-битный выход) и S9 (9-битный вход, 9-битный выход). Они были специально спроектированы для минимизации корреляции между входом и выходом.
• Генерация раундовых ключей — из 128-битного мастер-ключа с помощью простого алгоритма расширения (ключевого расписания) формируются 8 раундовых ключей по 64 бита каждый, а также дополнительные ключи для функций FL.

Процесс шифрования состоит из следующих этапов:

1. Исходный 64-битный блок делится на левую и правую половины (по 32 бита).
2. Выполняется 8 раундов преобразований с использованием функций FO и FL.
3. После последнего раунда выполняется финальное перемешивание (окончательное преобразование), которое включает в себя операцию XOR с ключом и перестановку половин.
4. Результат объединяется в 64-битный зашифрованный блок.

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

¶Криптоанализ и стойкость

MISTY1 был спроектирован с учётом принципов доказуемой стойкости. Авторы показали, что для взлома полного 8-раундового шифра с помощью линейного криптоанализа потребуется не менее 2^108 известных открытых текстов, а для дифференциального — не менее 2^106. Это значительно превышает практические возможности атак.

Однако в 2015 году группа криптоаналитиков под руководством Юкио Цурумото (Япония) опубликовала работу, в которой представила атаку на MISTY1 с использованием метода интегрального криптоанализа. Атака требовала 2^63.5 выбранных открытых текстов и 2^63.5 операций шифрования, что лишь незначительно быстрее полного перебора (2^128). Несмотря на то, что атака не нарушала практическую стойкость алгоритма, она продемонстрировала, что теоретическая безопасность MISTY1 не является абсолютной.

В 2016 году исследователи из Университета Лёвена (Бельгия) и Университета Кёнхи (Южная Корея) предложили улучшенную атаку, снизившую сложность до 2^63.3. Однако все эти атаки остаются в значительной степени теоретическими и не представляют угрозы для реальных систем, так как требуют огромного объёма данных, недоступного в типичных сценариях.

¶Применение

MISTY1 нашёл применение в нескольких областях:

• Мобильная связь: Вариант MISTY1 под названием KASUMI (также известный как A5/3) используется в стандарте 3GPP для шифрования трафика в сетях UMTS (3G) и LTE (4G). KASUMI был специально адаптирован для работы в условиях ограниченных вычислительных ресурсов мобильных устройств.
• Смарт-карты: Алгоритм применялся в некоторых моделях смарт-карт, выпускавшихся японскими производителями, для защиты данных и аутентификации.
• Банковские системы: MISTY1 использовался в некоторых старых версиях протоколов шифрования для банкоматов и POS-терминалов, хотя впоследствии был вытеснен более современными алгоритмами (например, AES).
• Стандарты ISO/IEC: Как часть стандарта ISO/IEC 18033-3, MISTY1 рекомендован для использования в государственных информационных системах ряда стран, в первую очередь Японии.

¶Критика и ограничения

Основным недостатком MISTY1 считается его 64-битный размер блока, который делает его уязвимым для атак на основе коллизий (например, атаки дня рождения) при шифровании больших объёмов данных (более 2^32 блоков). В современных системах рекомендуется использовать алгоритмы с размером блока 128 бит (например, AES). Кроме того, MISTY1 уступает по производительности более новым шифрам, таким как AES, особенно на архитектурах с поддержкой аппаратного ускорения (AES-NI). В связи с этим в новых проектах MISTY1 практически не применяется, уступая место AES, Camellia или SM4.

¶Интересные факты

• Название MISTY1 не имеет отношения к слову «туман» (misty). Это аббревиатура от Mitsubishi Improved Security Technology, а цифра 1 указывает на первую версию алгоритма.
• MISTY1 стал основой для разработки шифра KASUMI, который, в свою очередь, был подвергнут критике из-за уязвимостей в реализации (например, атака на основе связанных ключей, опубликованная в 2010 году).
• Алгоритм был запатентован компанией Mitsubishi Electric, но патентные ограничения были сняты для некоммерческого использования и для реализации в рамках стандартов ISO/IEC.

¶Источники

• Matsui, M., & Miyaguchi, S. (1995). MISTY1: A Block Cipher Based on a New Structure. Fast Software Encryption (FSE 1995).
• ISO/IEC 18033-3:2005. Information technology — Security techniques — Encryption algorithms — Part 3: Block ciphers.
• CRYPTREC Report 2000. Evaluation of Cryptographic Algorithms.
• Tsurumoto, Y., et al. (2015). Integral Attack on MISTY1. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences.
• Knudsen, L. R., & Mathiassen, J. E. (2000). On the Role of the FL Function in MISTY1. Fast Software Encryption (FSE 2000).