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
комментариев: 1515 документов: 44 редакций: 5786
комментариев: 9796 документов: 488 редакций: 5664
Новость дополнена. Других подробностей нет.
Один из создателей Twofish (David Wagner) заявлял примерно следующее: "Не используйте Twofish, используйте Rijndael. С Twofish всё в порядке, но про проблемы с AES в случае новых достижений криптографии, шансы узнать гораздо больше". Шнайер конечно был менее категоричен в своих заявлениях.
Twofish достаточно сложный алгоритм и непривлекательный для исследователей в области открытой криптографии. Зачем искать дыру в Twofish, когда больший эффект на публику произведёт работа по AES? А в случае практического успеха это даст ещё и экономическо-политические последствия: ведь это официальный стандарт шифрования в США и главный стандарт в области симметричных шифров для открытой криптографии в остальном мире. Национальные стандарты имеют меньшее значение. А Twofish – вообще не стандарт (хотя является альтернативным стандартом де-факто, как в области поточных шифров существует неофициальый стандарт RC4).
комментариев: 1515 документов: 44 редакций: 5786
http://www.cio-world.ru/bsolutions/e-safety/320673/
комментариев: 9796 документов: 488 редакций: 5664
Да, во время конкурса комманда Шнайера развернула даже по мнению некоторых слегка агрессивную рекламу своего алгоритма, бомбардировали оппонентов массой поверхностных по мнению других наблюдателей работ, но после него признали победу Rijndael как на честном соревновании.
Против Rijndael выступал также Шамир, но его шифр Serpent оказался потенциально более уязвим к алгебраическому криптоанализу, чем даже Rijndael (из-за малого размера S-блоков, а не их структуры).
Шифр Рона Райвиста RC6 казалось бы совсем простой, в нём никаких лазеек и быть не может, но он оказался одним из наименее стойких среди финалистов даже против известных атак. А если в нём увеличивать число раундов, то он начинает терять преимущества в скорости.
Шифр MARS от IBM проектировался неаккуратно и в его дизайне были выявлены ошибки и неудачные с практической точки зрения решения, кроме того он очень запутан, труден для анализа.
По многим показателям он идеален, но не универсален (большие 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), то очень большая нагрузка идёт на процессор. Иногда даже приходится использовать криптоакселераторы.
комментариев: 1515 документов: 44 редакций: 5786
Если интересует только надёжность используйте каскадные шифры.
комментариев: 9796 документов: 488 редакций: 5664
На роль запасного или даже второго кандидата, если не могут выбрать единый стандарт претендовал Serpent, но тогда не был открыт алгебраический криптоанализ.
Вообще работа, которая лежит в основе данной новости довольно мутная, к тому же это черновик, в котором глюки даже в оформлении. Автор малоизвестен в криптографическом сообществе. Вполне может оказаться, что новый метод линейного криптоанализа на деле малоэффективен, а внутренний линейный код как лазейка в алгоритме – вообще бред. А может и нет.
Вот "разгром" аналогичной работы от людей весьма даже скептически настроенных по отношению к Rijndael.
Может и по этой работе будет серьёзное опровержение.
комментариев: 9796 документов: 488 редакций: 5664
Серьёзного опровержения работа пока не удостоилась
Краткое мнение от Nicolas T. Courtois – автор алгебраического криптоанализа и ряда модельных алгебраических атак на AES/Rijndael