Гарантии твердости для AES

14

Многие криптосистемы с открытым ключом имеют доказуемую безопасность. Например, криптосистема Рабина доказуемо так же сложна, как и факторинг.

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

Примечание: я знаком с операциями AES (AddRoundKey, SubBytes, ShiftRows и MixColumns). Кажется, что жесткость AES проистекает из операции MixColumns, которая, в свою очередь, должна унаследовать свою трудность от некоторой сложной проблемы над полями Галуа (и, таким образом, алгеброй). Фактически, я могу перефразировать мой вопрос следующим образом: «Какая сложная алгебраическая задача гарантирует безопасность AES?»

М.С. Дусти
источник

Ответы:

8

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

Кроме того, книга The Design of Rijndael очень хорошо читается и обсуждает теорию и философию криптографии.

Аарон Стерлинг
источник
1
Хорошее объяснение. Благодарю. На самом деле, у меня был доступ к книге, но я не знал, какую часть читать (относительно моего вопроса). Вы предлагаете какую-нибудь специальную главу или раздел?
MS Dousti
3
Я прочитал его более двух лет назад из библиотеки, поэтому у меня нет оглавления, и я не уверен, что смогу дать конкретный ответ на ваш вопрос, за исключением того, что мне понравился способ они разработали S-блоки, чтобы быть легко осуществимыми. Тем не менее, одно, что я могу предложить, - это объяснение Стинсона AES и других сетей подстановочно-перестановочной криптографии: теория и практика. Это 3-я глава издания, которое у меня есть, и похоже, что вы можете бесплатно скачать книгу по этой ссылке: ebookee.com/…
Аарон Стерлинг,
1
Спасибо за предложение книги Стинсона. Не могли бы вы также взглянуть на оглавление The Design of Rijndael и посмотреть, напоминает ли оно что-нибудь полезное?
MS Dousti
2
Спасибо за ссылку! :-) Да, раздел 3.6 и глава 5 были мне очень интересны, потому что они обсуждали «почему», а не просто «что».
Аарон Стерлинг
10

Как сказал Дэвид, у нас нет таких сокращений для AES. Однако это не означает, что криптосистема Рабина или RSA более безопасна, чем AES. На самом деле, я бы доверял (по крайней мере, односторонней, возможно, также псевдо-случайной) безопасности блочных шифров, таких как AES / DES и т. Д. (Возможно, с немного большим количеством раундов, чем обычно используется), чем предположению, что факторинг это трудно, именно потому, что нет алгебраической структуры, и поэтому сложнее представить, что будет какой-то прорывной алгоритм.

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

Боаз Барак
источник
Спасибо Вооз. Я думаю, что конструкция Luby-Rackoff - это та, которая обеспечивает доказуемую псевдо-случайность на основе DES-подобных структур, верно?
MS Dousti
3
да. Точнее, вы начинаете с односторонней функции, конвертируете ее в псевдослучайный генератор с помощью Hastad, Impagliazzo, Luby, Levin, затем конвертируете ее в псевдослучайную функцию с помощью Goldreich, Goldwasser, Micali, затем действительно используете Luby-Rackoff для преобразования ее в псевдослучайная перестановка (то есть block ci pher)
Вооз Барак
6

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

Но этот ответ педантичен: для типичного развернутого блочного шифра у нас нет доказуемого анализа безопасности в смысле проблемы «сокращение до вычисления». Были предложения для блочных шифров с уменьшением безопасности, но вычислительный багаж, необходимый для облегчения сокращения, делает их неконкурентоспособными с более эффективными схемами, такими как алгоритмы AES.

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

Дэвид Кэш
источник