Введение
Блок-шифр
KASUMI — это блок-шифр, используемый в системах мобильной связи UMTS, GSM и GPRS. В UMTS KASUMI применяется в алгоритмах конфиденциальности (f8) и целостности (f9) под названиями UEA1 и UIA1 соответственно. В GSM KASUMI используется в генераторе ключевого потока A5/3, а в GPRS — в генераторе ключевого потока GEA3. KASUMI был разработан для 3GPP группой экспертов по алгоритмам безопасности (SAGE), входящей в состав европейского органа по стандартизации ETSI, для использования в системе безопасности UMTS. В связи с ограниченным временем, отведенным на стандартизацию 3GPP, вместо разработки нового шифра SAGE договорилась с группой технических спецификаций 3GPP (TSG) по системным аспектам безопасности 3G (SA3) о том, чтобы основать разработку на существующем алгоритме, который уже прошел некоторую оценку и был запатентован корпорацией Mitsubishi Electric Corporation. Исходный алгоритм был незначительно модифицирован для упрощения аппаратной реализации и соответствия другим требованиям, предъявляемым к безопасности мобильной связи 3G. KASUMI назван в честь оригинального алгоритма MISTY1 — 霞み (hiragana かすみ, romaji kasumi) — это японское слово, означающее «туман». В январе 2010 года Орр Данкельман, Натан Келлер и Ади Шамир опубликовали статью, в которой продемонстрировали возможность взлома KASUMI с использованием связанной атаки по ключу и весьма скромных вычислительных ресурсов; эта атака неэффективна против MISTY1.
(SAGE), a part of the European standards body ETSI. Because of schedule pressures in 3GPP standardization, instead of developing a new cipher, SAGE agreed with
3GPP technical specification group (TSG) for system aspects of 3G security (SA3) to base the development
on an existing algorithm that had already undergone some evaluation. and patented
by Mitsubishi Electric Corporation. The original algorithm was slightly modified for easier hardware implementation and to
meet other requirements set for 3G mobile communications security. KASUMI is named after the original algorithm MISTY1 — 霞み (hiragana かすみ, romaji kasumi) is the Japanese word for "mist". In January 2010, Orr Dunkelman, Nathan Keller and Adi Shamir released a paper showing that they could break Kasumi with a related key attack and very modest computational resources; this attack is ineffective against MISTY1.
Криптоанализ
В 2001 году Кюн (2001) представил невозможную дифференциальную атаку на шесть раундов KASUMI. В 2003 году Элад Баркан, Эли Бихам и Натан Келлер продемонстрировали атаки типа «человек посередине» против протокола GSM, которые обходили шифр A5/3 и, таким образом, взламывали протокол. Однако этот подход не атакует сам шифр A5/3. Полная версия их работы была опубликована позднее в 2006 году. В 2005 году израильские исследователи Эли Бихам, Орр Дункельман и Натан Келлер опубликовали атаку типа «связанный ключ» (boomerang attack) на KASUMI, которая позволяет взломать все 8 раундов быстрее, чем полный перебор. Для атаки требуется 254,6 выбранных открытых текстов, каждый из которых был зашифрован одним из четырех связанных ключей, и имеет временную сложность, эквивалентную 276,1 шифрованиям KASUMI. Хотя это очевидно не является практической атакой, она ставит под сомнение некоторые доказательства безопасности протоколов 3GPP, которые основывались на предполагаемой стойкости KASUMI. В 2010 году Дункельман, Келлер и Шамир опубликовали новую атаку, позволяющую злоумышленнику восстановить полный ключ A5/3 с помощью атаки на связанные ключи. Временная и пространственная сложность атаки достаточно малы, чтобы авторы смогли осуществить её за два часа на настольном компьютере Intel Core 2 Duo, даже используя неоптимизированную эталонную реализацию KASUMI. Авторы отмечают, что эта атака может быть неприменима к способу использования A5/3 в системах 3G; их основной целью было дискредитировать заверения 3GPP в том, что их изменения в MISTY не окажут существенного влияния на безопасность алгоритма.