Взлом AES: 1.5 триллиона US$ и менее года вычислений

OpenPGP со ссылкой на Cryptology Eprint Archive сообщает: Исследователи Алекс Бирюков и Йохан Гроссшадль из лаборатории алгоритмики, криптологии и безопасности Университета Люксембурга (LACS) впервые предоставили оценки возможности построения суперкомпьютера для практического взлома AES на основе передовых технологий GPU/ASIC/VLSI, использованных в NVIDIA GT200b. По их расчётам на сегодняшний момент возможности существующего "железа" позволяют осуществлять атаки, на проведение которых требуется 2¹⁰⁰ вычислений. Следует понимать, что эти атаки можно считать практически осуществимыми только гипотетически (например, если вся энергетика, финансы и инфраструктура США будут направлены только на взлом AES в течении года, то это можно считать практически осуществимым взломом, по крайней мере в оценочном плане).

"Практическому взлому" можно считать подверженным не только AES-128, но и AES-256. Следует опять же различать, что даже если гипотетический противник, обладающий доступными в масштабе крупной страны сверхресурсами, потратит их на осуществление взлома, его практичность всё равно остаётся под сомнением: противнику нужно получить доступ к слишком большой утечке данных в рамках исполнения протокола, что может встречаться скорее в лабораторных условиях и ограничивает оценочный характер этого результата ещё в большей степени.

Исследователи рассмотрели две ранее известные атаки на полнораундовый AES, требующие исполнения 2¹⁰⁰ операций. Первая атака — на связанных ключах против AES-256 (Related Key Cryptoanalysis — RKC) — 2^99.5 шагов исполнения и 2⁷⁸ памяти. Такая атака непрактична из-за малой вероятности появления связанных ключей в каком-либо практически используемом криптопротоколе. Несмотря на слишком сильную модель атакующего и невероятное количество предоставляемых ему данных, такая атака преодолевает психологический барьер сложности 2¹⁰⁰.

Вторая атака основана на размене ключей-времени-памяти (Time-Memory-Key — TMK) против AES-128, также известна как атака с множественными целями. В этой атаке фиксированный открытый текст шифруется множеством различных секретных ключей, а целью атакующего является нахождение по крайней мере одного из этих ключей. Используя 2³² целей, TMK-атака имеет сложность предвычислений 2⁹⁶, после чего каждый новый секретный ключ может быть найден с затратами времени 2⁸⁰ и памяти 2⁵⁶. Впервые атака такого рода предложена Хеллманом для инвертирования хэш-функций и использована для создания радужных таблиц.

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

Обе атаки требуют примерно одинаковых затрат и оборудования. Исследователи считают, что организация, способная потратить триллион долларов (что сопоставимо с размером годового оборонного бюджета США), может взломать AES-256 в сценарии RKC и подобных атак в течении года вычислений. Использование десятой части такого бюджета (100 миллиардов US$) достаточно для проведения TMK-атаки на AES-128 с 2³² целями. Такая атака потребует год предвычислений, после чего каждый новый ключ может быть вычисляем за 2⁸⁰ AES-операций, т.е. каждые 8 минут на таком "менее масштабном" суперкомпьютере. Исследователи рассматривают гипотетический проект такого компьютера, названный ими CAESAR (“Cryptanalytic AES ARchitecture”). Эта гипотетическая машина (как TWINKLE или TWIRL), хотя и находится за границей реально доступных ресурсов, но в отличие от "кофейников Шамира", опирается на существующую технологию. Некоторые предположения и близкие прогнозы авторов касаются памяти. Так, реалистично ожидать появления жёстких дисков размером 10-100 терабайт, которых в таком случае потребуется всего 3 · 10¹⁰ — 3 · 10⁹. Столько же потребуется и процессоров. Расходы энергии составят 4 тераватта, что превосходит годовое потребление энергии в США (3.34 тераватта), но развитие энергосберегающих вычислительных технологий позволяют несколько приблизить и эти границы.

По мнению исследователей, проект гипотетического суперкомпьютера CAESAR демонстрирует узкие места в затратах энергии и количестве памяти, но свидетельствует о снижении оценок практической стойкости AES в долговременной перспективе.

Полная статья - на OpenPGP