id: Гость   вход   регистрация
текущее время 22:08 28/03/2024
Владелец: unknown редакция от 12/01/2010 11:39 (автор: unknown) Печать
Категории: криптография, криптоанализ, инфобезопасность, симметричное шифрование, защита телефонной связи, атаки
https://www.pgpru.com/Новости/2010/ПерваяПрактическаяАтакаНаA53KASUMI--АлгоритмНовогоСтандартаGSM
создать
просмотр
редакции
ссылки

12.01 // Первая практическая атака на A5/3 (KASUMI) -- алгоритм нового стандарта GSM


Орр Дункельман, Натан Келлер и Ади Шамир с факультета математики и компьютерных наук института Вейцмана представили первую атаку на блочный шифр из стандарта шифрования мобильной связи третьего поколения A5/3 (KASUMI), которая может быть осуществлена за практически доступное время на персональном компьютере.
Нестойкость данного алгоритма была продемонстрирована ранее, но предыдущая атака была непрактичной.


Приватность и безопасность сотовой связи GSM обеспечивается семейством алгоритмов A5. Первые два алгоритма из этого набора A5/1 (первоначально разработанный для европейского рынка) и A5/2 (первоначально разработанный на экспорт) были созданы в конце 1980-х годов и сохранялись в секрете до 1999 года, пока не были раскрыты путём реверс-инженеринга мобильных устройств. После публикации стало ясно, что A5/2 не обеспечивает практически никакой безопасности, A5/1 может быть подвержен практическим атакам различной степени сложности выполнения. Самая последняя из них была анонсирована группой криптографов под руководством Karsten Nohl, опубликовашей 2 терабайта "радужных таблиц" для A5/1, что позволяет легко получать ключ сессии из любого сеанса переговоров с минимальным требованием к аппаратному обеспечению.


В ответ на эти разработки ассоциация GSM заявила, что требуется ускорить переход на новый алгоритм, называемый A5/3, по поводу данного вопроса ожидаются обсуждения на специальной встрече в феврале 2010 года. Алгоритм A5/3 был разработан для GSM-телефонии третьего поколения в 2002 году, а его спецификации были опубликованы в 2003. Он уже реализован в 40% из доступных на данный момент телефонов, но крайне малое количество сотовых операторов из двухсот стран, которые в данный момент используют сотовую телефонию GSM, переключились на данный стандарт. После принятия A5/3 станет самой широкоиспользуемой криптосистемой в мире и её безопасность станет наиболее важной практической задачей криптографии.


Криптосистема A5/3 первоначально основана на блочном шифре MISTY, опубликованном Мацуи на конференции FSE в 1997 году. Размер его блока — 64 бита, ключ 128-бит и он представляет собой сложную рекурсивную сеть Фейстеля в виде структуры из восьми раундов, каждый из которых состоит из трёх раундов, в свою очередь в каждом из которых происходят три раунда нелинейных операций с S-блоками. MISTY обладает доказуемо стойкими своствами против различных типов атак и неизвестно ни одной атаки на его полную версию. Лучшая из опубликованных атак может быть применена против сокращенного до 6 раундов варианта из 8-раундовой версии MISTY и имеет совершенно непрактичное время исполнения свыше 2123.
Однако разработчики A5/3 решили сделать MISTY более быстродействующим и более лёгким в аппаратном исполнении путём упрощения его ключевого расписания и модификации некоторых из его компонентов, назвав новый вариант KASUMI. Разработчики привели аргументы в анализе стойкости KASUMI против атак со связанными ключами и дали заключение, что "удаление FI функций в части ключевого расписания сделает аппаратную часть более компактной и/или уменьшит время установки ключей. Мы ожидаем, что атаки со связанными ключами не будут действовать против этой структуры". Лучшая атака, найденная разработчиками и другими исследователями KASUMI была описана так: "Существуют атаки на основе подобранного открытого текста и/или на основе связанных ключей против KASUMI, сокращённого до 5 раундов. Мы верим, что в последующем анализе возможно расширение области действия некоторых атак до 6 раундов, но не до полного 8-раундового KASUMI".


Возможность лучших атак со связаными ключами на полный KASUMI была показана позднее. Атака имела сложность по требуемым данным 254.6 и 276.1 по времени, что являлось непрактичным, но лучшим, чем простой перебор. В данной работе представлена новая атака, которая требует всего 4 связанных ключа, 226 данных, 230 байтов памяти и 232 шагов времени. Поскольку сложность исполнения так мала, то она была проведена экспериментально на одном PC (Intel Core Duo 2, T7200 CPU — 2GHz, 4MB L2 Cache, 2 GB RAM, Linux-2.6.27, gcc 4.3.2), на котором можно было восстанавливать 96 битов ключа в минуту или полный 128-битовый ключ менее, чем за два часа. Тщательный анализ показывает, что эта атака не может быть применена против оригинального MISTY, поскольку использует последовательность совпадений и редких случайных обстоятельств, которые почему-то произошли, когда MISTY был изменён на KASUMI под влиянием ассоциации GSM. Это вызывает ряд вопросов по поводу дизайна KASUMI и в части процедур его исследования на предмет стойкости к атакам со связанными ключами.


Впервые применённая в данной работе новая версия атаки против KASUMI является усовершенствованием бумеранг-атак (впервые изобретённых Дэвидом Вагнером). Её назвали "сэндвич-атака", поскольку в ней используется различитель, состоящий из трёх частей: толстая часть ("хлеб") сверху, тонкая часть ("мясо") посредине и толстая часть ("хлеб") снизу. Верхняя и нижняя части подразумевают, что в них имеются высоковероятностные дифференциальные характеристики, которые могут быть комбинированы в структуру консистентного квартета при помощи стандартной техники бумеранга. Средняя часть серьёзно снижает вероятность успешного построения бумеранговой структуры, но этот эффект авторам удалось значительно снизить за счёт тщательного анализа взаимодействия частей. Интересно (и в некоторой степени странно), что стоит незначительно изменить ключевое расписание KASUMI (что не окажет никакого влияния на дифференциальные характеристики верхнего и нижнего слоя), как вероятность комбинированного различителя с удивительно высокого значения 2-14 становится равной нулю.


Первое применение сэндвич-атаки против реального шифра помогло снизить время исполнения атаки против KASUMI с непрактично большого 276 до 232. Однако, новая атака использует одновременно как связанные ключи, так и подобранные сообщения, что не может быть применено на практике против того специфического способа использования, которым алгоритм KASUMI используется в качестве стандарта шифрования A5/3 в телефонных сетях GSM третьего поколения. Однако, следует отметить, что замена в этом стандарте шифра MISTY на шифр KASUMI привела к соданию значительно более слабой криптосистемы, использования которой следует избегать в любых приложениях, в которых атаки на связанных ключах могут быть осуществимы.


Источник: Cryptology ePrint Archive