02.01 // Первая оценка возможности практического взлома AES: 1.5 триллиона US$ и менее года вычислений

Исследования в области специальных аппаратных средств для взлома шифров насчитывают почти столетнюю историю. В 1938 году польские математики, возглавляемые Марианом Режевски, создали электромеханическое устройство под названием "Бомба" (Bomba Kryptologiczna), позволившее им взломать немецкий шифр Enigma за счёт полного перебора положений 17576 роторов. Этот успех был развит английскими криптографами (с ведущей ролью Алана Тюринга и Гордона Велчмана), которые создали удачные машины для взлома шифров, позволившие силам союзников читать сообщения, зашифрованные Энигмой в ходе Второй Мировой войны. Параллельные усилия в криптоанализе другого немецкого шифра, Lorenz SZ40/42, привели к созданию первого в мире программируемого компьютера Colossus. Он содержал 1500 вакуумных ламп и был способен обрабатывать 5000 знаков в секунду.

В 1980 году Померанц и др. создали аппаратную архитектуру, названную Quasimodo для факторизации больших чисел с помощью алгоритма квадратичного решета. Quasimodo был построен, но не функционировал должным образом. Проект DES Cracker (также известный как Deep Crack) — это машина параллельного поиска ключа, разработанная организацией EFF в конце 1990-х с суммарным бюджетом всего 210000 US$. Deep Crack содержал около 1500 специальных микросхем и требовал по крайней мере 9 дней для нахождения 56-битного ключа DES за счёт атаки "грубой силой". Также в конце 1990-х Шамир предложил TWINKLE — электрооптическое устройство для выполнения шага просеивания в алгоритме NFS (решета числового поля). По его оценкам одного такого чипа было бы достаточно, чтобы за приемлемое время факторизовать 512-битные числа и, соответственно, взламывать 512-битные RSA-ключи. TWIRL, улучшенная модификация TWINKLE предполагала уменьшение полного времени просеивания до 10 минут. Оба эти устройства остались чисто гипотетическими, но привлекли значительное внимание криптосообщества и вызвали рост последующих исследований. Типичным примером стало появление устройства COPACOBANA на основе паралльной архитектуры FPGA (ПЛИС) для успешного криптоанализа шифров с 64-битным ключом (KeeLoq, DES и A5/1).

Дальнейший интерес связан с изучением возможностей графических процессоров (GPU) и специализированных микросхем ASIC.

Исследователи Алекс Бирюков и Йохан Гроссшадль из лаборатории алгоритмики, криптологии и безопасности Университета Люксембурга (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⁷⁸ памяти. Такая атака непрактична из-за малой вероятности появления связанных ключей в каком-либо практически используемом криптопротоколе. В простейшем случае используется простое соотношение K' = K ⊕ C, улучшенная версия этой же атаки (бумеранг-атака со связанными ключами) использует соотношение K' = F⁻¹ (F(K) ⊕ C) = R_C (K), где K, K' — неизвестные связанные ключи, F — раундовая функция ключевого расписания AES-шифрования, C — навязываемая атакующим константа. Несмотря на слишком сильную модель атакующего и невероятное количество предоставляемых ему данных, такая атака преодолевает психологический барьер сложности 2¹⁰⁰.

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

Применительно к шифрам TMK-атака позволяет перебирать только часть пространства поиска за счёт оптимизации по требуемому параметру. В случае если сообщения (файлы) с одним и тем же заголовком шифруются множественными ключами, такую ситуацию можно признать практичной. Если пространство поиска N = 2ⁿ (n = 128 для AES-128), то располагая шифрованием фиксированного открытого текста D_k различными ключами, необходимо перебрать только N / D_k точек в пространстве. Для этого нужно использовать t / D_k шифротаблиц вместо t, что означает уменьшение памяти до M = mt / D_k (где m — количество начальных-конечных точек в таблице Хеллмана). Затраты времени T = t / D_k · t · D_k = t² на основе исходной оптимизации Хеллмана (меньше проверок таблиц — больше точек с данными). Наконец, правило останова для матрицы N = mt² — состояние минимизации расходов покрытия матрицы в результате проявления эффекта парадокса дней рождения. Используя правило останова для матрицы и сокращая параметры m и t, получаем формулу оптимизации: N² = T(MD_k)².

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

Обе атаки требуют примерно одинаковых затрат и оборудования. Исследователи считают, что организация, способная потратить триллион долларов (что сопоставимо с размером годового оборонного бюджета США), может взломать 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 тераватта), но развитие энергосберегающих вычислительных технологий позволяют несколько приблизить и эти границы.

В качестве перспективных факторов авторы рассматривают также:

• Продолжение действия закона Мура для ближайших десятилетий, хотя и с некоторым замедлением.
• Успехи в криптоанализе AES, снижающие сложность атак. Такие успехи являются спорадическими и непредсказуемыми, поэтому оценить влияние этого фактора сложно.
• Появление магнито-электронных (спинтронных) компьютеров со значительно сниженным энергопотреблением.
• Появление оптоэлектронных компьютеров, значительно снижающих энергопотребление для массированных вычислений.
• Появление 3D-оптических накопителей. Уже сейчас достижим размер в 1 терабайт для дисков, аналогичных DVD. Возможно появление 100-терабайтных носителей.
• Распространение квантовой голографии. В 2009 году уже был продемонстрирован результат возможности записи 3 эксабайт (2^61.5 байт) на квадратный дюйм.

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

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