AES encryption not as tough as you think

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

Предыдущие работы освещались
здесь и здесь.

Можно только дополнить новость ссылкой на последнюю работу.

Related-key атаки это непонятный сценарий.

Раньше их вообще всерьёз не рассматривали.
Но теоретический прогресс и "неожиданные события" всегда знаете ли "внушают опасения".

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

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

Это же надо чтобы выбирались специальные "плохие" ключи при шифровании.

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

Как его можно приложить к практическому ускорению взлома?

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

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

Пока что конкретно в случае модели атаки связанных ключей уже получается, что AES-256 не более стоек, чем AES-128.

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

Новость дополнена

А почему дефолтово PGP использует при асимметричном шифровании по стандарту именно AES в связке? Разве там так критична скорость? Не лучше было бы поставить по умолчанию какой-нить фиш? Чем обоснован выбор AES'а для такой задачи? Ведь время на выполнение шифрования/расшифрования асимметрики много больше необходимого времени на работу с блочным шифром, и логично было бы выбрать предполагающийся самым стойким блочный шифр.

Чем обоснован выбор AES'а для такой задачи?

Тем, что это де-факто международный стандарт, в отличие от фишей.

логично было бы выбрать предполагающийся самым стойким блочный шифр.

Я подчеркнул ключевое здесь слово. Вопрос вот в чём: если бы внимание фишам, серпентам и всем остальным уделялось столько же, сколько стандартному Rijndael, в каком бы они были сейчас состоянии?

В GnuPG можете впринципе прописать в свойствах ключа и конфиге другой шифр.

Только развивая то, что сказал SATtva — отдельные криптографы высказывали предположения, что вполне возможно, что у Twofish есть теоретические дефекты в процедуре разворачивания S-блоков из ключа, а Serpent более уязвим к гипотетическому алгебраическому криптоанализу, чем Rijndael, только кто готов сейчас потратить сейчас столько сил и времени в человеко-часах (которые реально растягиваются на долгие годы) на исследований этих смутных предположений — эти шифры же не стали стандартом.

В GnuPG можете впринципе прописать в свойствах ключа и конфиге другой шифр.

В PGP тоже можно поменять. А разве в последних версиях GnuPG не AES по умолчанию?

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

Я подчеркнул ключевое здесь слово. Вопрос вот в чём: если бы внимание фишам, серпентам и всем остальным уделялось столько же, сколько стандартному Rijndael, в каком бы они были сейчас состоянии?

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

НИСТ выбрал финалиста по итогам большого голосования с участие нескольких сотен ведущих криптографов для выбора финалиста из пяти кандидатов, прошедших в финал.

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

На уровне догадок и спекуляций часть криптографов для финалистов вывели понятие "security margin" — что-то вроде запаса прочности.

Rijndael и RC6 имели невысокий "security margin", а Mars, Serpent и Twofish — "высокий".

Часть участников предлагали ввести Serpent "запасным финалистом" и утвердить два шифра на стандарт, хотя бы в случае явных разногласий.

NIST отказался от понятия "security margin", считая что все вопросы стойкости должны были быть решены до финала и рассматривал только реальные доказательства нестойкости, если таковые вдруг внезапно бы ещё появились. НИСТ также отказался от выбора запасного финалиста и призвал выбирать на голосовании среди всех пяти финалистов, как из примерно равных по криптостойкости, больше делая упор уже на практические качества. Большинство проголосовало за Rijndael.

Слабый "security margin" RC6 подтвердился, возможно при более тщательном анализе именно этот шифр оказался бы слабее Rijndael. У шифра Mars уже в процессе конкурса выявились ошибки в доказательстве стойкости к дифференциальному криптоанализу, что снизило его репутацию, авторы от него неформально открестились. Фирма IBM не сняла с него патентные ограничения и явно не определила его патентный статус, так что после конкурса он не получил дорогу в свободное ПО. Аналогично произошло и с RC6.

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

был одним из самых быстрых на большинстве нужных операций.

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

Спасибо, сейчас стало понятнее. В общем, слухи о большей криптостойкости остальных алгоритмов, видимо, были несколько преувеличены.

Создание по всем критериям хорошего, универсального и доверямого криптостандарта — невероятно сложная задача.

Скорее это ещё даже не задача, а вопрос оконцептуальной построимости такого алгоритма, и не есть ли всё крипто security via obscurity (Коблиц, etc).

"security via obscurity" — этот термин уже зарезервирован для более простого понятия: умышленное утаивание деталей системы безопасности вместо её полного и открытого анализа. Дескать, если раскрыть, всё равно всё поломают, мы лучше сами всё изобретём и никому не скажем, как это работает и будем наивно полагать, что мы во-первых настолько умнее всех остальных, что не наделаем хотя-бы тривиальных ошибок в своей системе безопасности, а во-вторых сможем сохранить всё в секрете.

Коблитц поднимал вопрос о другом — что в криптографии необходимо чётко определить, что является "невозможным" и через сведения доказательства взлома к этой "невозможности" доказать стойкость. Он скорее утверждает, что "невозможное" определить нельзя, можно определить только неизвестное, неясное на данный момент развития знаний. А это подрывает доверие к "доказуемой безопасности", на которой построена вся современная криптография.

С этой точки зрения да, концептуально получается, что никакой алгоритм не имеет доверямой стойкости. И вопрос о построении такого алгоритма остаётся нерешённым.

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

Почему всё-же теоретические атаки на AES имеют такое значение? Потому что атаки со связаными ключами при всей их непрактичности считались невозможными. А именно на максимально точном знании, что является невозможным и построена криптография. А тут после десяти лет полной уверенности, за полгода доказывается, что это не так, причём за последний месяц атаку улучшили примерно так в 2¹⁰⁰ раз. Неслабый прогресс. Да, в реальности это всё ещё непрактично, но чего после этого стоят все оценки безопасности, которые неточны на тридцать порядков?

После обновления стандарта хэшей не планируют обновлять блочные шрифты?

Шрифты это конечно шифры.

После обновления стандарта хэшей не планируют обновлять блочные...

...шифры

Нет. Но хитрый Шнайер придумал так, что если его хэш Skein станет финалистом, то есть большой шанс, что встроенный в него блочный шифр Threefish станет тоже стандартом де-факто и всем будет удобнее использовать Skein как универсальный симметричный криптопримитив. А уж разработчики железа-то как будут довольны из-за такой экономии!