02.07 // Новые бумеранг-атаки по методу связанных ключей на AES

Новая криптоаналитическая атака на AES, которая быстрее простого перебора:

Related-key Cryptanalysis of the Full AES-192 and AES-256
Alex Biryukov и Dmitry Khovratovich.

В аннотации авторы представляют две атаки на связанных ключах на полный алгоритм AES. Для AES-256 показано, что атака на восстановление ключа работает для всех ключей и имеет сложность 2¹¹⁹, что лучше недавнего предыдущего результата атаки Biryukov-Khovratovich-Nikolic, которая к тому же работает только для ограниченного класса слабых ключей.
Вторая атака – первый криптоанализ полного AES-192. Обе атаки являются бумеранг-атаками, основанными на недавней идее нахождения локальных коллизий в блочных шифрах и расширении на основе бумеранг-техники с переключением, чтобы захватить большее число раундов в середине.

В своём письме авторы уточняют, что более тщательный анализ может снизить сложность с 2¹¹⁹ до 2^110.5 по данным и времени.

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

Комментарий Брюса Шнайера: "Несмотря на то, что атака лучше простого перебора и некоторые криптографы могут обозначить такой алгоритм как "взломанный" – результаты всё ещё за пределами наших вычислительных возможностей. Атака является и возможно навсегда останется чисто теоретической. Но стоит помнить: атаки всегда становятся только лучше, а не хуже. С другой стороны, продолжает увеличиваться их число. Хотя нет причин для паники или отказа от использования AES, или принятия нового стандарта от НИСТ, это уже представляет проблему для некоторых кандидатов на конкурс SHA-3: для хэш-функций, основанных на AES".

Авторы приводят краткие разъяснения по поводу новых атак на AES:

В.: Это первый результат в криптоанализе полного AES?

О.: Да. Ранее самые успешные атаки работали только против сокращённых версий: 10 раундов (из 12) для AES-192, 10 раундов (из 14 для AES-256).

В.: Эта атака практична?

О.: Нет. Даже после улучшений нам всё ещё нужно более 2¹⁰⁰ шифрований, что находится за пределами вычислительных мощностей человечества. Более того, эта атака работает в модели атак со связанными ключами, которые подразумевают более мощного атакующего, чем в модели с независимыми ключами.

В.: Что из себя представляет модель атаки со связанными ключами?

О.: В этой модели атакующий может наблюдать результаты процесса зашифрования/расшифрования на различных секретных ключах. Атакующий знает (или даже сам способен выбирать) соотношение между различными ключами, но не знает самих ключей. Например, соотношение может быть просто значением XOR с известной константой: K_B = K_A xor C или более сложная связь вида K_B = F( K_A ), где F – произвольная функция, выбранная атакующим. В реальной жизни такие зависимости могут возникнуть при сбоях в аппаратном обеспечении или плохо спроектированных протоколах безопасности.

В.: В вашей работе для конференции CRYPTO вы показали практичную атаку на AES в модели с открытым ключом — что это значит?

O.: Это значит, что AES-256 практически взломан как хэш-функция и поэтому не может использоваться как готовый элемент ("plug-and-play") в различных конструкциях, основанных на доказуемой безопасности.

В.: Стоит ли мне продолжать использовать AES-192 и AES-256?

О.: Да. Наши атаки не представляют никакой существенной угрозы в использовании AES, но следите внимательно за прогрессом в криптоанализе.

В.: Означает ли это, что AES-256 слабее, чем AES-128?

O.: Теоретически – да. Практически – они оба всё ещё обеспечивают комфортный уровень безопасности.

В.: Как это затрагивает AES-128?

О.: Мы не знаем как атаковать полный AES-128 на основании этой идеи. Однако, мы ожидаем прогресс в криптоанализе сокращённых версий AES-128.

В.: Можно ли исправить эту уязвимость?

О.: Эта уязвимость может быть исправлена, только это потребует очень серьёзных изменений в дизайне. В частности та часть шифра, которая называется ключевым расписанием, должна быть переработана. Это также можно исправить увеличением числа раундов для всех версий, но это сделает шифр намного более медленным.

В.: Какой эффект это окажет на конкурс SHA-3 и на заявки на него, в которых содержатся хэш-функции, основанные на AES?

O.: Немного заявок содержат использование AES в явном виде, так что мы не ожидаем, что много функций пострадают от атаки. Однако, основополагающие идеи могут быть использованы в криптоанализе некоторых кандидатов, содержащих элементы похожие на AES.

В.: Как была открыта эта уязвимость? Почему она не была открыта во время конкурса AES и не была открыта в течении последующих десяти лет?

О.: Уязвимость была открыта, когда мы стали рассматривать AES как хэш-функцию и стали пытаться искать уязвимости, характерные для хэш-функций. Мы думаем, что большинство криптографов использовали только техники, ориентированные на блочные шифры, против которых AES был хорошо защищён разработчиками. Другая причина в том, что AES-256 вероятно получил меньше внимания со стороны криптоаналитиков, чем AES-128, хотя по иронии именно AES-256 предназначен для защиты более чувствительной информации, чем AES-128.

В.: Можете ли вы кратко описать какие свойства шифра привели к такой уязвимости?

O.: Ключ AES многократно используется в ходе шифрования после того как он развёрнут в ходе процесса, называемого ключевым расписанием. Мы установили, что малые изменения ключа вызывают малые изменения в процессе шифрования и могут быть нейтрализованы с высокой вероятностью, что даёт атакующему контроль над распространением дифференциальных изменений. Мы называем такую нейтрализацию локальной коллизией (понятие из криптоанализа хэш-функций). Некоторые последовательные локальные коллизии могут склеиваться друг с другом вместе в длинные 7-раундовые разности образцов прохождения (также называемые дифференциальными характеристиками или дифференциальными путями), которые имеют очень высокие вероятности — такие о которых ни один криптоаналитик не мог раньше и мечтать. Мы называем их волшебными путями AES-256.

Вскоре, Alex Biryukov, Orr Dunkelman, Nathan Keller, Dmitry Khovratovich и Adi Shamir опубликовали новую работу, в которой понизили уровень сложности предыдущих атак на AES-256 с 2¹²⁶ и 2¹¹⁹ по времени до всего 2³⁹ затрат по времени на двух связанных ключах, но только для 9 раундов из 14-ти. Предыдущая атака требовала 4 связанных ключа и 2¹²⁰ шагов по времени выполнения.

Эту атаку можно развить и до 10 раундов (2¹⁷² шагов), но только при неполной модели связанных ключей (так называемых связанных подключей).

Источник: Schneier on Security