20.08 // Атака на восстановление ключа криптоалгоритма AES
Метод биклик, использованный ранее против хэш-функций оказался эффективен против полнораундового AES.
Исследователи Andery Bogdanov, Dmitry Khovratovich и Christian Rechberger представили на Crypto 2011 следующие результаты:
- Восстановление ключа AES-128 с вычислительной сложностью 2^(126,1)
- Восстановление ключа AES-192 с вычислительной сложностью 2^(189,7)
- Восстановление ключа AES-256 с вычислительной сложностью 2^(254,4)
- Более простые ранее не описанные атаки на AES с уменьшенным числом раундов
- Атаки на нахождение прообразов в функциях сжатия, основанных на полнораундовом AES
Источник: http://research.microsoft.com/en-us/projects/cryptanalysis/aesbc.pdf
комментариев: 1060 документов: 16 редакций: 32
Наверно unknown в отпуске, иначе он бы точно заметил такое гораздо раньше кучи новостных агентств :)
комментариев: 11558 документов: 1036 редакций: 4118
комментариев: 9796 документов: 488 редакций: 5664
2SATtva:
Как раз интересно, что ни фиксированного ключа, ни связанных ключей не требуется. Эта путаница пошла действительно с метода взлома хэшей.
Здесь представлена атака с подобранным шифртекстом. Вместо перебора ключей предлагается посчитать набор биклик (зависимостей шифртекстов от внутренних состояний для фрагментов разных ключей) и определённых внутренних состояний (не относящихся к бикликам). Упрощённо – это перебор ключа по частям (сокращение ключевого пространства) – впрочем, как и любая атака (так что это высказывание тривиально ;-) .
Получая доступ к дешифрующему оракулу пока требуется в несколько раз меньше вычислений, чем перебор грубой силой и около 240 – 288 подобранных шифртекстов. Взломщик на основе зависимости шифртекст-открытый текст определяет соответствие – подходит ли она для его предвычесленных биклик. Если да – то восстанавливает секретный ключ. Если нет – то проводит вычисления для получения следующего кандидата – блока шифртекста на подсовывание дешифрующему оракулу.
В практическом смысле большинство каналов связи аутентифицированы и придумать правдободобный сценарий для такого вклинивания со своими шифртекстами сложно (но можно). Это не считая пока незначительного выигрыша по сравнению с грубой силой (практическая неддостижимость).
С теоретической точки зрения результат интересный и может при дальнейшем развитии поставить крест на шифрах с облегчённым ключевым расписанием.
комментариев: 11558 документов: 1036 редакций: 4118
комментариев: 9796 документов: 488 редакций: 5664
Возможно, противоречия с работой там и нет. Как правильно отметил в новости sentaus, атака работает в том числе и для нахождения различителя между AES и идеальным шифром в составе строительного блока хэш-функции. Но это не самая интересная часть работы (в отличие от поиска секретного ключа с подобранными шифртекстами и предвычислением биклик для полнораундового AES). Такие различители были известны и ранее и попытки применить каждый новый метод для того, чтобы попинать AES ещё и в этом качестве, стали уже традиционным развлечением.
комментариев: 9796 документов: 488 редакций: 5664
Да, снижение сложности по сравнению с простым перебором всего несколько раз. Нужно ещё и подсовывать жертве подобранные шифртексты на расшифровку неизвестным ключом и получать с неё открытые тексты.
Biclique Cryptanalysis of the Full AES Or: Why you might want to rename AES-128 into AES-126 in a few minutes
AES-128 переименовывается в AES-126.
Однако, по аналогии с ГОСТ, это первый теоретический взлом (за исключением совсем абстрактных атак на поиск различителя и атак со связанными ключами — которые были известны и для ГОСТа). И в отличие от недавних атак на ГОСТ эти атаки не требуют полного исчерпания кодовой книги, а работают со сравнительно небольшим числом блоков шифртекста по отношению к числу возможных из-за размера блока.
© Bogdanov
© The Inquirer
Т.е., с теоретической точки зрения AES взломан. Разработчики AES подтверждают и аплодируют. Взлом почти такого уровня как и против ГОСТ. (Itai Dinur, Orr Dunkelman, Adi Shamir выступали на RUMP SESSION как "GOSTBUSTERS 2").
P.S. Если кто-то думает, что другие шифры надёжнее, то это лишь потому, что они малоисследованы.
комментариев: 9796 документов: 488 редакций: 5664
Любопытно напомнить сравнительно широко известный документ, который недавно всплыл в обсуждениях в связи с subj:
The Twofish Team's Final Comments on AES Selection //Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, Niels Ferguson, Tadayoshi Kohno, Mike Stay.
Это заявление команды Шнайера на финале конкурса AES, опубликованное 15 мая 2000 года.
На основании имеющихся на тот момент сведений о криптоанализе, они рассчитали критерий стойкости всех пяти финалистов, как простое отношение числа взломанных раундов к общему числу раундов шифра. Чуть более сложное отношение было предложено для шифра MARS, т.к. там используются неодинаковые раунды (гетерогенная структура раундов). Единица соответствует взломанному шифру, чем больше число — тем более стойкий шифр.
Вот что у них получилось в итоге:
Примечание: Rijndael — это соответственно шифр, который стал финалистом: AES-128 (10 раундов), AES-192 (12 раундов), AES-256 (14 раундов). Последние три позиции — нестандартные варианты шифров с увеличенным числом раундов.
Вот что писали Шнайер и компания в 2000 году, и персонально сейчас Шнайер считает в своём блоге, что он был прав.
Что произошло дальше, известно ещё более широко. NIST проигнорировал замечания команды Шнайера и не стал требовать от финалистов увеличения числа раундов в обмен на увеличение безопасности. Политика свелась к тому, чтобы из пяти финалистов выбрать самый практичный и быстрый, но в финале уже не принимать "спекуляций" по поводу безопасности. Конкурс NIST для хэшей SHA-3 проходит аналогично и Шнайер уже "просёк фишку" заранее — проект его команды достаточно рискованно разменивает безопасность на скорость и другие практические качества. Как почти и все остальные из пяти финалистов.
комментариев: 9796 документов: 488 редакций: 5664
И ещё для этого в Майкрософт на работу внедрились!
комментариев: 9796 документов: 488 редакций: 5664
Давайте тогда рассмотрим вопрос здесь.
Внутренние состояния {Si} подшифра f (финальных раундов AES) преобразуются в шифртекст Cj. Варианты внутренних состояний и варианты шифртекстов образуют двудольный граф, состоящий из биклик, заданных ключами {ki,j} для функции fk(S) = C
Сгруппировав ключи в биклики можно ограничить число ключей, требуемых для перебора из-за неидеальности ключевого расписания.
Для вычисления биклик используют дифференциальные свойства, следы, оставляемые ключами во внутреннем состоянии шифра, локальные коллизии и прочие неидеальности ключевого расписания. В работе их приведено множество — есть простор для дальнейших исследований.
Там очень долго описываются разные типы биклик — длинные, независимые.
Атака очень комплексная — сначала используется встреча посредине, а остаток раундов шифра доламывается бикликами ключей. И всё это работает пока только по принципу адаптивно-подобранных шифртекстов.
Как расписать понятно? Там очень долго, много нюансов и разных техник.