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

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

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

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

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

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

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

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

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

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

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

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

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