KASUMI

KASUMI — это блочный симметричный алгоритм шифрования, разработанный в конце 1990-х годов консорциумом 3GPP (3rd Generation Partnership Project) для обеспечения конфиденциальности и целостности данных в сетях мобильной связи третьего поколения (3G/UMTS). Алгоритм является модификацией японского шифра MISTY1, созданного Мицуру Мацуи, и адаптирован для работы в системах с ограниченными вычислительными ресурсами, таких как мобильные телефоны и базовые станции.

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

Разработка KASUMI была продиктована необходимостью замены устаревших и уязвимых алгоритмов безопасности, использовавшихся в сетях второго поколения (2G/GSM), таких как A5/1 и A5/2. В 1999 году в рамках проекта 3GPP была сформирована группа по стандартизации криптографических алгоритмов. Основой для нового шифра послужил MISTY1, представленный Мицуру Мацуи в 1995 году. MISTY1 отличался высокой криптостойкостью и доказанной устойчивостью к дифференциальному и линейному криптоанализу. Однако для повышения производительности в мобильных устройствах в MISTY1 были внесены изменения: упрощена структура S-блоков (таблиц подстановки) и изменены некоторые логические операции. Полученный алгоритм получил название KASUMI (от яп. 霞 — «туман» или «дымка»).

В 2000 году KASUMI был официально принят в качестве базового алгоритма для функций конфиденциальности (f8) и целостности (f9) в стандарте UMTS (Universal Mobile Telecommunications System). Впоследствии он также использовался в сетях LTE (4G) для защиты служебного трафика.

Устройство алгоритма

KASUMI представляет собой 64-битный блочный шифр с длиной ключа 128 бит. Он использует классическую структуру Фейстеля (Feistel network), состоящую из 8 раундов. Каждый раунд включает в себя три основные функции: FL (функция смешивания), FO (функция нелинейного преобразования) и FI (функция внутреннего преобразования).

Структура раунда

• Функция FL — это простая линейная операция, выполняемая над левой половиной блока. Она использует два 16-битных подключевых слова (KL) и состоит из операций XOR (исключающее ИЛИ) и AND (логическое И). FL применяется в каждом нечётном раунде (1, 3, 5, 7) к левой половине данных перед функцией FO, а в каждом чётном раунде (2, 4, 6, 8) — к правой половине после FO.
• Функция FO — это нелинейное преобразование, построенное на трёх последовательных вызовах функции FI. FO использует 48-битный подключ (KO) и 48-битный ключ (KI). Каждый вызов FI внутри FO обрабатывает 16-битный фрагмент данных.
• Функция FI — это 16-битное нелинейное преобразование, являющееся ядром алгоритма. Она состоит из четырёх S-блоков: двух 9-битных (S9) и двух 7-битных (S7), а также операции XOR и расширения. S9 и S7 являются фиксированными таблицами подстановки, определёнными в спецификации 3GPP. FI обеспечивает основную криптостойкость алгоритма.

Генерация ключей

Из исходного 128-битного мастер-ключа с помощью линейного алгоритма (Key Schedule) генерируются 8 наборов раундовых подключей для каждой из функций (FL, FO, FI). Процесс генерации включает циклические сдвиги и XOR-операции с константами.

Применение

KASUMI используется в двух основных функциях стандарта 3GPP:

• Функция f8 (шифрование) — обеспечивает конфиденциальность передаваемых данных. KASUMI в этой функции работает в режиме счётчика (CTR — Counter Mode). Шифр генерирует поток ключевых битов, который накладывается на открытый текст с помощью операции XOR. Для каждого сеанса связи используется уникальный начальный вектор (COUNT-C), что предотвращает повторное использование ключевого потока.
• Функция f9 (контроль целостности) — обеспечивает аутентификацию сообщений и защиту от модификации. KASUMI в этой функции работает в режиме CBC-MAC (Cipher Block Chaining Message Authentication Code). На основе передаваемых данных и секретного ключа вычисляется 32-битный код аутентификации (MAC-I), который проверяется на стороне приёмника.

Оба режима (f8 и f9) стандартизированы и являются обязательными для реализации в сетях UMTS и LTE.

Криптоанализ и уязвимости

Несмотря на то, что KASUMI был разработан на основе криптостойкого MISTY1, его упрощённая структура сделала алгоритм уязвимым для ряда атак.

• 2001 год: Криптоаналитики Антуан Жу и Кобби Нинио (Antoine Joux, Kobbi Nissim) обнаружили, что KASUMI уязвим для атаки на связанных ключах (related-key attack) — разновидности атаки, при которой злоумышленник может анализировать шифротексты, полученные на разных, но связанных ключах. Эта атака, однако, не представляла практической угрозы для сетей 3G, так как требовала доступа к нескольким сеансам связи с известными ключами.
• 2005 год: Исследователи из Университета Кента (Великобритания) и Технического университета Дармштадта (Германия) представили атаку на основе времени (timing attack), использующую неравномерность выполнения операций S-блоков на разных платформах. Для защиты от этой атаки были рекомендованы программные и аппаратные контрмеры.
• 2010 год: Группа исследователей из Университета Твенте (Нидерланды) и Университета Кента опубликовала работу, в которой продемонстрировала практическую атаку на KASUMI. Используя метод «связанных ключей» и «бумерангов» (bumerang attack), им удалось восстановить 128-битный ключ шифрования за 2^32 операций (около 4 миллиардов), что значительно меньше полного перебора (2^128). Атака была реализована на обычном персональном компьютере за несколько часов. Это означало, что KASUMI больше не может считаться криптостойким для защиты конфиденциальных данных в долгосрочной перспективе.
• 2011 год: В ответ на выявленные уязвимости 3GPP ввёл в стандарт LTE (4G) новый алгоритм шифрования — 128-EEA3 (Snow 3G) и 128-EIA3 (ZUC), которые постепенно вытеснили KASUMI для защиты пользовательского трафика. KASUMI остался в качестве опции для обратной совместимости и защиты служебного трафика.

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

Основной критикой KASUMI является то, что его упрощение по сравнению с MISTY1 привело к снижению криптостойкости. Несмотря на то, что MISTY1 до сих пор считается надёжным алгоритмом, KASUMI был скомпрометирован атаками на связанных ключах. Кроме того, 64-битный размер блока считается устаревшим для современных стандартов безопасности, так как при шифровании больших объёмов данных (более 2^32 блоков) возрастает вероятность коллизий в режиме счётчика.

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

• Название «KASUMI» было выбрано как отсылка к японскому слову «туман», что символизирует неопределённость и скрытность.
• Алгоритм MISTY1, на основе которого создан KASUMI, был включён в число финалистов европейского проекта NESSIE (New European Schemes for Signatures, Integrity and Encryption) в 2003 году.
• В отличие от A5/1 (GSM), который был взломан в 2009 году с использованием распределённых вычислений и облачных сервисов, KASUMI не был взломан в реальных условиях сетей 3G, так как атаки на связанных ключах требуют специфических условий, не встречающихся в стандартной работе операторов связи.

Источники

• 3GPP TS 35.201: «3rd Generation Partnership Project; Technical Specification Group Services and System Aspects; 3G Security; Specification of the 3GPP Confidentiality and Integrity Algorithms; Document 1: f8 and f9 Specification».
• 3GPP TS 35.202: «Document 2: KASUMI Specification».
• Matsui, M. (1995). «New Block Encryption Algorithm MISTY». Fast Software Encryption (FSE).
• Joux, A., Nissim, K. (2001). «Related-Key Attacks on KASUMI». Advances in Cryptology — CRYPTO 2001.
• Biham, E., Dunkelman, O., Keller, N. (2005). «A Related-Key Boomerang Attack on KASUMI». Journal of Cryptology.
• Dunkelman, O., Keller, N., Shamir, A. (2010). «A Practical-Time Related-Key Attack on the KASUMI Cryptosystem Used in GSM and 3G Telephony». Advances in Cryptology — CRYPTO 2010.