id: Гость   вход   регистрация
текущее время 14:35 29/03/2024
Владелец: unknown (создано 21/06/2007 11:38), редакция от 24/06/2007 17:36 (автор: unknown) Печать
Категории: криптография, софт, криптоанализ, политика, алгоритмы, симметричное шифрование, атаки, программные закладки, спецслужбы
https://www.pgpru.com/Новости/2007/06-21-ЛазейкаВAesСлишкомНевероятночТобыБытьПравдой
создать
просмотр
редакции
ссылки

21.06 // Крипто // Лазейка в AES. Слишком невероятно, чтобы быть правдой?


Warren D. Smith из математического отделения Temple University в Филадельфии опубликовал работу "1. AES seems weak. 2. Linear time secure cryptography" (см. также здесь под номером 100), в которой утверждает, что алгоритм шифрования AES (Rijndael) обладает скрытыми уязвимостями к новым видам линейного криптоанализа, которые позволяют осуществить атаку на основе 64w шифрований, где w — минимальное расстояние Хэмминга.


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


Автор обобщает основные подозрения вокруг Rijndael: например способ построения алгебраических S-блоков, которые являются комбинацией нахождения обратного значения в конечном поле и линейной операции, что должно давать стойкий нелинейный S-блок. Это удобно с практической точки зрения (универсальность, компактность, быстродействие), но плохо обосновано теоретически по отношению возможностей новых видов криптоанализа (в частности алгебраического, который успешно развивается в настоящее время).


Далее автор, не занимаясь алгебраическим криптоанализом, использует линейный криптоанализ, представляя детали алгоритма (S-блоки, линейную часть, раундовые подключи) в обобщённом виде, как электрическую схему с проводами, переключателями переходами и источниками шума, Он записывает линейные соотношения в виде уравнений, которые затем представляет в виде характеристических векторов, которые в свою очередь образуют бинарный линейный код в поле GF2 ("код из кода" по терминологии автора).


Далее с полученным кодом можно работать методами, известными в теории кодов (что ещё никто ранее широко не применял в линейном криптоанализе). Это позволяет проводить совершенно новые методы, например детектировать в зашифрованном тексте английский язык и проводить атаки на основе только шифртекста.
После этого он доказывает, что сложность взлома зависит от расстояния Хэмминга в "коде из кода",


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


Но в данной работе обращается внимание на то, что построение алгоритма осуществлялось без учёта расстояния Хэмминга в "коде из кода", Если создателям алгоритма удалось проектировать алгоритм с ослабляющим кодом, то они получают лазейку в алгоритме. К сожалению найти такой "код из кода" (если он существует) очень сложно. Автор лишь показывает, что криптоанализ возможен и при незнании кода, а при знании он возможен при сравнительно небольших затратах,


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


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


Автор работы в лучшем случае может создать на данный момент ситуацию, при которой алгоритм Rijndael (а также его предшественник DES) будет иметь недоказанную стойкость по отношению не только к алгебраическому, но и линейному криптоанализу с использованием линейных кодов. Кроме того, множество из существующих алгоритмов не может сегодня считаться свободными от слабых линейных кодов, И наконец, если взамен линейных кодов, будут проектироваться алгоритмы с учётом циклических и более сложных кодов, не приведёт ли это к тому, что и они будут взломаны противником, который обладает большим запасом знаний в криптоанализе и может их рассматривать на другом уровне абстракции?


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


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


 
— Гость (24/06/2007 07:14)   <#>
Комментарии будут? Интересно, насколько все это достоверно? Р
— spinore (24/06/2007 08:47)   профиль/связь   <#>
комментариев: 1515   документов: 44   редакций: 5786
Ага, все бегом побежали перешифровывать разделы с AES на Twofish :-)
— unknown (24/06/2007 17:56, исправлен 24/06/2007 21:01)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Комментарии будут? Интересно, насколько все это достоверно?


Новость дополнена. Других подробностей нет.


Ага, все бегом побежали перешифровывать разделы с AES на Twofish


Один из создателей Twofish (David Wagner) заявлял примерно следующее: "Не используйте Twofish, используйте Rijndael. С Twofish всё в порядке, но про проблемы с AES в случае новых достижений криптографии, шансы узнать гораздо больше". Шнайер конечно был менее категоричен в своих заявлениях.

Twofish достаточно сложный алгоритм и непривлекательный для исследователей в области открытой криптографии. Зачем искать дыру в Twofish, когда больший эффект на публику произведёт работа по AES? А в случае практического успеха это даст ещё и экономическо-политические последствия: ведь это официальный стандарт шифрования в США и главный стандарт в области симметричных шифров для открытой криптографии в остальном мире. Национальные стандарты имеют меньшее значение. А Twofish – вообще не стандарт (хотя является альтернативным стандартом де-факто, как в области поточных шифров существует неофициальый стандарт RC4).
— spinore (24/06/2007 21:29)   профиль/связь   <#>
комментариев: 1515   документов: 44   редакций: 5786
А что про Blowfish, такая же ситуация как с Twofish? Просто под OpenBSD сейчас шифрование дисков только через Blowfish работает...
— Гость (24/06/2007 22:22)   <#>
документ [27] написан авторами «конкурирующего» с Rijndael алгоритма Twofish; в нем настолько убедительно доказывается преимущество Twofish над остальными финалистами конкурса (аналогичные доказательства приведены и в работе [29]), что после его прочтения выбор Rijndael (а не Twofish) в качестве стандарта AES начинает удивлять.

27. Schneier B., Kelsey J., Whiting D., Wagner D., Hall C., Ferguson N., Kohno T., Stay M. The Twofish Team’s Final Comments on AES Selection. // http://csrc.nist.gov – May 15, 2000.

29. Schroeppel R. AES Comments. // Public Comments Regarding The Advanced Encryption Standard (AES) Development Effort. Round 2 Comments – http://csrc.nist.gov – University of Arizona – May 15, 2000.

http://www.cio-world.ru/bsolutions/e-safety/320673/
— unknown (25/06/2007 01:42)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

документ [27] написан авторами «конкурирующего» с Rijndael алгоритма Twofish; в нем настолько убедительно доказывается преимущество Twofish над остальными финалистами конкурса (аналогичные доказательства приведены и в работе [29]), что после его прочтения выбор Rijndael (а не Twofish) в качестве стандарта AES начинает удивлять.

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

Против Rijndael выступал также Шамир, но его шифр Serpent оказался потенциально более уязвим к алгебраическому криптоанализу, чем даже Rijndael (из-за малого размера S-блоков, а не их структуры).

Шифр Рона Райвиста RC6 казалось бы совсем простой, в нём никаких лазеек и быть не может, но он оказался одним из наименее стойких среди финалистов даже против известных атак. А если в нём увеличивать число раундов, то он начинает терять преимущества в скорости.

Шифр MARS от IBM проектировался неаккуратно и в его дизайне были выявлены ошибки и неудачные с практической точки зрения решения, кроме того он очень запутан, труден для анализа.




А что про Blowfish, такая же ситуация как с Twofish? Просто под OpenBSD сейчас шифрование дисков только через Blowfish работает...



По многим показателям он идеален, но не универсален (большие S-блоки и подключи очень надёжно и медленно генерируются из самого ключа, используя сам шифр blowfish но это не подходит для смарт-кард или серверов, где ключи часто меняются, он неэффективен на 64-битных процессорах). Однако операция линейного смешения после S-блоков XOR-ADD-XOR в некоторых работах считается ненадёжной, хотя ни в одной реальной атаке это применено не было.

Другая проблема – малый размер блока – 64 бит не позволяет шифровать большие объёмы данных на одном ключе, сейчас используют только 128-битные по размеру блока (не путать с размером ключа) шифры.

Попытка перевести blowfish в 128-битовый блок существует и называется Kaweichel, но не получила никаких отзывов.

Twofish тщательно сконструированный алгоритм, но сложный для анализа. Он тоже не является идеальным. Зависимые от ключа S-блоки размером 8x8 в целях экономии разворачиваются из блоков 4x4. Некоторые исследователи утверждают, что в итоге получается отклонение от идеально случайного распределения в наработанном материале S-блоков, причём весьма существенное. Также для разворачивания подключей используется масса всяких трюков и запутанных алгебраических операций, которые исследователям, несогласным со Шнайером кажутся странными. Если не большинство, то многие считают, что Rijndael обоснован лучше, чем Twofish, шнайер и его приверженцы считают наоборот. Обоснование стойкости Rijndael более точное, но более формальное – у Twofish более обширное и построено не только на строгих расчётах, но и догадках и прогнозах относительно будущего в криптоанализе.

Интересно, что новый из признанных уже после конкурса AES – шифр Anubis от Vincent Rijmen (одного из создателей Rijndael)
для экономии ресурсов использует инволюции и рекурсивную структуру разворачивания S-блока (4x4 -> 8x8), что тоже привело к появлению специфических атак.

Попытки переделать алгоритм IDEA на 128-битный блок (MESH, FOX, IDEA NXT) тоже оказались не особо удачными.

Т.о. идеального шифра с точки зрения безопасности не существует. А проблема в том, что нужен быстрый, экономичный и универсальный шифр. Здесь Rijndael вне конкуренции. Например, когда серверу нужно шифровать много соединений (платёжные системы, VPN, серверы сети tor), то очень большая нагрузка идёт на процессор. Иногда даже приходится использовать криптоакселераторы.
— Гость (25/06/2007 03:06)   <#>
Пусть будет быстрый и эконмичный, но почему наряду с ним нет стандартного, пусть медленного, но очень надёжнго?
— spinore (25/06/2007 03:41)   профиль/связь   <#>
комментариев: 1515   документов: 44   редакций: 5786
Пусть будет быстрый и эконмичный, но почему наряду с ним нет стандартного, пусть медленного, но очень надёжнго?

Если интересует только надёжность используйте каскадные шифры.
— unknown (25/06/2007 09:45)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Пусть будет быстрый и экономичный, но почему наряду с ним нет стандартного, пусть медленного, но очень надёжнго?

На роль запасного или даже второго кандидата, если не могут выбрать единый стандарт претендовал Serpent, но тогда не был открыт алгебраический криптоанализ.

Вообще работа, которая лежит в основе данной новости довольно мутная, к тому же это черновик, в котором глюки даже в оформлении. Автор малоизвестен в криптографическом сообществе. Вполне может оказаться, что новый метод линейного криптоанализа на деле малоэффективен, а внутренний линейный код как лазейка в алгоритме – вообще бред. А может и нет.

Вот "разгром" аналогичной работы от людей весьма даже скептически настроенных по отношению к Rijndael.

Может и по этой работе будет серьёзное опровержение.
— unknown (09/07/2007 17:18, исправлен 09/07/2007 17:19)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Может и по этой работе будет серьёзное опровержение.

Серьёзного опровержения работа пока не удостоилась



"AES is weak? No panic. A weird and badly written paper by Warren D. Smith that contains many mistakes. The attack is a bit of a stretch: starting from an incorrect linear approximation assumption for the S-boxes, a heuristic attack is derived."

"AES уязвим? Без паники. Странная и плохо написанная работа Уоррена Смита содержит много ошибок. Эта лишь с большой большой натяжкой является атакой: исходя из некорректных линейных приближений, допущенных для S-блоков выводится эвристическая атака"



Краткое мнение от Nicolas T. Courtois – автор алгебраического криптоанализа и ряда модельных алгебраических атак на AES/Rijndael

Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3