id: Гость   вход   регистрация
текущее время 02:03 23/01/2020
Владелец: sentaus (создано 20/08/2011 00:05), редакция от 20/08/2011 00:07 (автор: sentaus) Печать
Категории: криптография, криптоанализ, алгоритмы, симметричное шифрование, атаки
https://www.pgpru.com/Новости/2011/АтакаНаВосстановлениеКлючаКриптоалгоритмаAES
создать
просмотр
редакции
ссылки

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

Источник: filehttp://research.microsoft.com/en-us/projects/cryptanalysis/aesbc.pdf


 
— sentaus (20/08/2011 00:07, исправлен 20/08/2011 00:10)   профиль/связь   <#>
комментариев: 1060   документов: 16   редакций: 32

Наверно unknown в отпуске, иначе он бы точно заметил такое гораздо раньше кучи новостных агентств :)

— SATtva (20/08/2011 08:49)   профиль/связь   <#>
комментариев: 11543   документов: 1036   редакций: 4092
Стоит подчеркнуть, что это атака на режим шифрования с фиксированным ключом, т.е. эффективна, только если алгоритм применяется в составе хэш-функции.
— unknown (21/08/2011 02:41)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Спасибо, что опубликовали новость. Мне почему-то казалось, что на нынешнем CRYPTO в программе ничего особо интересного не будет.

2SATtva:

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

Здесь представлена атака с подобранным шифртекстом. Вместо перебора ключей предлагается посчитать набор биклик (зависимостей шифртекстов от внутренних состояний для фрагментов разных ключей) и определённых внутренних состояний (не относящихся к бикликам). Упрощённо – это перебор ключа по частям (сокращение ключевого пространства) – впрочем, как и любая атака (так что это высказывание тривиально ;-) .

Получая доступ к дешифрующему оракулу пока требуется в несколько раз меньше вычислений, чем перебор грубой силой и около 240 – 288 подобранных шифртекстов. Взломщик на основе зависимости шифртекст-открытый текст определяет соответствие – подходит ли она для его предвычесленных биклик. Если да – то восстанавливает секретный ключ. Если нет – то проводит вычисления для получения следующего кандидата – блока шифртекста на подсовывание дешифрующему оракулу.

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

С теоретической точки зрения результат интересный и может при дальнейшем развитии поставить крест на шифрах с облегчённым ключевым расписанием.
— SATtva (21/08/2011 16:23)   профиль/связь   <#>
комментариев: 11543   документов: 1036   редакций: 4092
Интересно. Спасибо за более подробный разбор. Так и получаются ошибочные выводы, если читать о результатах только в обзорах и отзывах (не таких подробных, как Ваши :)) вместо самой работы.
— unknown (21/08/2011 18:29, исправлен 21/08/2011 18:34)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

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

— Гость (21/08/2011 23:03)   <#>
Восстановление ключа AES-128 с вычислительной сложностью 2^(126,1)
А простой перебор этого имеет сложность 2^128 ?
— unknown (22/08/2011 10:52, исправлен 22/08/2011 11:39)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Да, снижение сложности по сравнению с простым перебором всего несколько раз. Нужно ещё и подсовывать жертве подобранные шифртексты на расшифровку неизвестным ключом и получать с неё открытые тексты.


fileBiclique 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.


Однако, по аналогии с ГОСТ, это первый теоретический взлом (за исключением совсем абстрактных атак на поиск различителя и атак со связанными ключами — которые были известны и для ГОСТа). И в отличие от недавних атак на ГОСТ эти атаки не требуют полного исчерпания кодовой книги, а работают со сравнительно небольшим числом блоков шифртекста по отношению к числу возможных из-за размера блока.

"The result is the first theoretical break of the Advanced Encryption Standard – the de facto worldwide encryption standard

© Bogdanov

The attack has been confirmed by the creators of AES, Dr Joan Daemen and Professor Dr Vincent Rijmen, who also applauded it.

© The Inquirer


Т.е., с теоретической точки зрения AES взломан. Разработчики AES подтверждают и аплодируют. Взлом почти такого уровня как и против ГОСТ. (Itai Dinur, Orr Dunkelman, Adi Shamir выступали на RUMP SESSION как "GOSTBUSTERS 2").


P.S. Если кто-то думает, что другие шифры надёжнее, то это лишь потому, что они малоисследованы.

— unknown (25/08/2011 10:51, исправлен 25/08/2011 10:53)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Любопытно напомнить сравнительно широко известный документ, который недавно всплыл в обсуждениях в связи с subj:


fileThe 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, т.к. там используются неодинаковые раунды (гетерогенная структура раундов). Единица соответствует взломанному шифру, чем больше число — тем более стойкий шифр.


Вот что у них получилось в итоге:


AlgorithmSafety factor
MARS1.90
RC61.18
Rijndael1.11/1.33/1.56
Serpent3.56
Twofish2.67
34-round RC62.00
18-round Rijndael2.00
24-round Rijndael2.67

Примечание: Rijndael — это соответственно шифр, который стал финалистом: AES-128 (10 раундов), AES-192 (12 раундов), AES-256 (14 раундов). Последние три позиции — нестандартные варианты шифров с увеличенным числом раундов.


Вот что писали Шнайер и компания в 2000 году, и персонально сейчас Шнайер считает в своём блоге, что он был прав.


Помните, что коэффициент безопасности, равный единице, соответствует взломанному шифру. Поэтому, даже умеренные успехи в криптоанализе поставят под угрозу RC6 и Rijndael. В своих комментариях к первому раунду (конкурса) Ларс Кнудсен рекомендовал, чтобы коэффициент безопасности для AES был бы равен по крайней мере 2 [Knu99]. Мы всецело поддерживаем эту рекомендацию. Самая худшая вещь, которая может случиться с AES — это успешная атака в течении десятилетия от текущего момента, даже "академическая атака". Не только потому, что это приведёт к опустошению во многих системах, но также и потому, что это поставит под угрозу конфиденциальные данные, зашифрованные до взлома. На основании имеющейся крайне поверхностной информации, мы просто не имеем права повзволять ввязываться в авантюру с относительно низким множителем безопасности.
По нашему мнению, Twofish и Serpent — оба имеют хорошие коэффициенты безопасности, MARS — близок к этому, но RC6 и Rijndael явно требуют большего количества раундов. В таблице показано, что 34 раунда RC6 и 18 раундов Rijndael будут иметь коэффициент безопасности 2. Для повышения коэффициента безопасности Rijndael до уровня Twofish, Rijndael потребует 24 раундов. Разумеется, увеличение числа раундов в результате скажется соответствующим образом на производительности. Это должно быть принято во внимание при сравнении с увеличенным числом раундов

Что произошло дальше, известно ещё более широко. NIST проигнорировал замечания команды Шнайера и не стал требовать от финалистов увеличения числа раундов в обмен на увеличение безопасности. Политика свелась к тому, чтобы из пяти финалистов выбрать самый практичный и быстрый, но в финале уже не принимать "спекуляций" по поводу безопасности. Конкурс NIST для хэшей SHA-3 проходит аналогично и Шнайер уже "просёк фишку" заранее — проект его команды достаточно рискованно разменивает безопасность на скорость и другие практические качества. Как почти и все остальные из пяти финалистов.

— Гость (25/08/2011 22:28)   <#>
Я так понимаю, что двухкаскадный AES (то есть если зашифровать ещё раз уже зашифрованное) обеспечит желаемый коэффициент безопасности :)
— Гость (26/08/2011 12:54)   <#>
Это что получается? Судя по фамилиям, иностранцы "cломали" ГОСТ, а русские "сломали" AES? "Холодная война" в криптографии?
— unknown (26/08/2011 13:05)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

И ещё для этого в Майкрософт на работу внедрились!
— Гость (03/09/2011 21:33)   <#>
Кто может понятно расписать суть атаки?
— unknown (04/09/2011 01:01)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Зачем размещать вопрос в двух местах?

Давайте тогда рассмотрим вопрос здесь.

Внутренние состояния {Si} подшифра f (финальных раундов AES) преобразуются в шифртекст Cj. Варианты внутренних состояний и варианты шифртекстов образуют двудольный граф, состоящий из биклик, заданных ключами {ki,j} для функции fk(S) = C

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

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

Там очень долго описываются разные типы биклик — длинные, независимые.

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

Как расписать понятно? Там очень долго, много нюансов и разных техник.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3