id: Гость   вход   регистрация
текущее время 13:22 29/03/2024
Владелец: unknown (создано 01/06/2009 17:20), редакция от 01/06/2009 17:30 (автор: unknown) Печать
Категории: криптография, криптоанализ, алгоритмы, симметричное шифрование, атаки
http://www.pgpru.com/Новости/2009/ПерваяАтакаНаПолнораундовыйAESДоказываетЕгоОтличиеОтМоделиИдеальногоШифра
создать
просмотр
редакции
ссылки

01.06 // Первая атака на полнораундовый AES доказывает его отличие от модели идеального шифра


//Первая атака на полнораундовый AES доказывает его отличие от модели идеального шифра


Исследователи Alex Biryukov, Dmitry Khovratovich and Ivica Nikoli из Люксембургского Университета опубликовали работу "Distinguisher and Related-Key Attack on the Full AES-256" и приложение к ней, содержащее результаты практических расчётов. Работа была fileранее анонсирована в коротком докладе на конференции EUROCRYPT-2009.


В данной работе создан различитель на основе подобранных ключей и описана атака на основе связаных ключей. Авторами введено понятие дифференциальной q-мультиколлизии, которая может быть создана для AES с незначительными затратами памяти за q 267 шагов, в то время как по доказательствам авторов для идеального шифра это значение должно быть O(q^^(128 * ( (q-1)/(q+1) ) )^^ – (или $O(q\cdot 2^{\frac{q-1}{q+1}128})$ в LaTeX форматировании).


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


Теоретические результаты авторы использовали для создания первой известной атаки на полнораундовый AES (14 раундов): различитель на связанных ключах, требующий 235 ключей и 2120 данных и времени при несущественных затратах памяти. Далее этот различитель преобразуется в атаку на восстановление ключа на основе 2131 затрат времени и 265 памяти.


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


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


Интересно, что доказательство неидеальности шифра авторы построили на очень жёсткой модели открытого ключа – "open key model". Противник не ищет неизвестный ключ и не пытается дешифровать сообщение. Противник знает ключ и открытый текст, в этой модели он обладает теми же полномочиями, что и обычные пользователи шифра. Цель противника – подбирая ключи доказать отличие шифра от идеальной модели. Эта часть атаки по определению непрактична.


По мнению авторов, которое разделяется многими криптографами, обнаружение любого свойства, закономерности или различителя (кроме тривиальных), отличающие шифр от идеальной модели (Ideal Cipher Model или Random Oracle Model) даже при знании ключа и открытого текста свидетельствует о его потенциальной нестойкости.


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


Интересным также оказалось использование усовершенствованых методов дифференциального криптоанализа и метода триангуляции.
Возможно эти методы в дальнейшем откроют путь к более сильным атакам.


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


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


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


 
Несколько комментариев (6) [показать комментарии/форму]
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3