Надвигающаяся угроза для криптографии со стороны квантовых компьютеров заставила срочно менять действующие примитивы асимметричной криптографии — обмен ключами (ECDH) и цифровые подписи (RSA, ECDSA, EdDSA) — которые уязвимы для квантового алгоритма Шора. Однако существующих симметричных методов криптографии (AES, SHA-2, SHA-3) или уровней их стойкости это не коснулось.
В индустрии бытует заблуждение, что квантовые компьютеры вдвое ослабят безопасность симметричных ключей, и для обеспечения того же 128-битного уровня защиты потребуется перейти на 256-битные ключи. Это неточная интерпретация ускорения, которое несут в себе квантовые алгоритмы. Она не отражена ни в одном из нормативных стандартов и рискует отвлечь внимание от реально необходимой работы по переходу к постквантовой системе криптографии. Обычно это заблуждение происходит из недопонимания применимости другого квантового метода — алгоритма Гровера.
AES-128, как и SHA-256, обеспечивает достаточную защиту от атак с применением квантовых компьютеров. Переход в постквантовую эпоху не требует изменения длины симметричных ключей. Это почти единогласное мнение среди профильных экспертов и органов стандартизации, которое нужно распространить среди остальной части IT-сообщества. И дальше в статье я подкреплю это утверждение техническими аргументами со ссылками на авторитетные источники.
Ускорение Гровера
Алгоритм Гровера — это квантовый алгоритм, который позволяет найти «правильный ответ» в пространстве поиска неструктурированной функции f, имеющем размер N, за π/4×√N вызовов этой функции.
И зачастую это определение понимают так, что алгоритм Гровера может найти ключ AES-128 за 264 запросов к оракулу. Но на практике это не так, поскольку выполнение подобной атаки в одном последовательном потоке займёт сотни тысяч лет, а её распараллеливание приведёт к увеличению общих вычислительных затрат.
Вот несколько важных нюансов касательно этого алгоритма:
квантовый оракул функции f должен быть реализован как часть квантовой схемы,
вызовы оракула должны происходить последовательно один за другим,
важно, что лучшим способом распараллеливания атаки является разделение пространства поиска (Zalka, 1997).
Почему последний пункт важен? Потому что в отличие от типичных атак брутфорсом, которые идеально распараллеливаются, разделение пространства поиска ведёт к падению эффективности квадратичного ускорения Гровера.
Возьмём, к примеру, классический подбор брутфорсом 64-битного ключа, когда каждая попытка занимает 5 нс (~16 тактов при 3 ГГц). Выполнение такого подбора на одном процессоре займёт примерно 2⁶⁴ × 5 нс ≈ 3 000 лет.
Тогда мы распределяем его по 2¹⁶ = 65 536 CPU, каждый из которых будет перебирать 2(64-16) = 248 ключей в течение 248 x 5 нс ≈ 16 дней.
Обратите внимание, что общий объём произведённой системой работы не изменился:
Именно поэтому мы считаем 64-битные ключи слабыми: при распараллеливании атаки они подбираются очень быстро. Если же атака выполняется последовательно, таких рисков не возникает.1
А теперь попробуем провернуть аналогичную атаку, но с использованием алгоритма Гровера для подбора 128-битного ключа. Как и ранее, последовательное выполнение
…операций нецелесообразно. Поэтому мы снова распараллеливаем атаку по 216 квантовых компьютеров, каждый из которых перебирает
В каждом вычислительном узле нам потребуется проделать
Заметьте, не 248!
Сокращение пространства поиска в 216 раз внутри квадратного корня экономит лишь 28 единиц работы на каждый узел, в то время как в классическом случае экономия составляет все 216.
В итоге общий объём работы всей системы возрос с 264 до
…так как распараллеливание атаки приводит к ослаблению эффекта квадратичного ускорения алгоритма.
Конкретные расчёты
Всё это даёт нам интуитивное понимание, почему алгоритм Гровера не поддаётся эффективному распараллеливанию. И чтобы окончательно увидеть, является ли он всё же угрозой, нам нужно произвести расчёты на конкретных порядках величин.
Для начала потребуется определить, сколько последовательных операций (гейтов) мы можем выполнить. Будем консервативны и предположим, что используем квантовую архитектуру с высокой тактовой частотой (на основе сверхпроводящих кубитов), и что выполнение одного гейта занимает 1 мкс.2 Если мы хотим продолжать атаку (без отключения питания и потери точности) в течение 10 лет, то максимальная последовательность гейтов («глубина») составит
Теперь нужно понять, сколько последовательных гейтов потребуется для подбора AES-128 внутри квантовой схемы. Ляо и Ло (2025) представили высокооптимизированный оракул Гровера для AES-128 с глубиной 232 T-гейта (и «шириной» схемы 724 — что, грубо говоря, означает количество кубитов, одновременно задействованных в вычислениях).
Теперь можно найти наименьший коэффициент распараллеливания, который позволит удержать каждый вычислительный узел в пределах максимальной глубины 248 (то есть обеспечит завершение вычислений на этих гипотетических квантовых компьютерах в течение 10 лет).
Это означает, что нам потребуется 140 триллионов квантовых схем из 724 логических кубитов, все из которых для взлома AES-128 с помощью алгоритма Гровера будут работать параллельно в течение 10 лет.
В качестве альтернативы затраты на эту атаку можно выразить в виде её DW-стоимости (произведения глубины на ширину), что будет аналогично произведению числа тактов и ядер в классических вычислительных системах.
Обратите внимание, что в отличие от вариантов реализации алгоритма Шора (и квантовой коррекции ошибок), которые за последние годы значительно улучшились, в этой формуле всего два члена, которые можно оптимизировать — глубина (232) и ширина (724) оракула Гровера для AES-128. Но они привносят в общую стоимость лишь 17 бит сложности, и потенциал по их оптимизации, похоже, почти исчерпан. В той же работе Ляо и Ло смогли на 7,5 бит уменьшить самую первую оценку, выведенную Грасслем и др. (2015), а также на 1,5 бита — самую раннюю оценку конкретно для алгоритма Гровера, вычисленную Жаком и др. (2019).
Сравнение с алгоритмом Шора
К слову, о Шоре. Как этот алгоритм показывает себя в случае недавно разобранных квантовых атак против 256-битных эллиптических кривых? Всё же некоторые считают, или раньше считали такие атаки неосуществимыми, хотя я всегда призывал воспринимать их всерьёз.
В исследовании Баббуш и др. (2026) указано, что Шор выполняется за
…на что уйдут минуты на архитектуре с «быстрыми» гейтами в 10 мкс (то есть в 10 раз медленнее тех, которые мы рассматривали выше).
Взлом AES-128 с помощью алгоритма Гровера в 430 000 000 000 000 000 000 000 раз дороже, чем взлом 256-битных эллиптических кривых с помощью Шора.
Подтверждение от NIST
Национальный институт стандартов и технологий США (National Institute of Standards and Technology, NIST) — это организация, которая запустила международный конкурс по созданию стандартов для постквантовой криптографии и выпустила спецификации ML-KEM и ML-DSA.
NIST не только считает AES-128 достаточно защищённым, но и сделала его бенчмарком для проверки безопасности постквантовых примитивов. AES-128 по определению задаёт первую категорию постквантовой стойкости3.
Обосновывая целесообразность применения AES-128, NIST опирается на те же наблюдения, которые мы разбирали выше, и вводит понятие MAXDEPTH — максимальной глубины последовательных вычислений, которая вынуждает использовать распараллеливание и снижает эффект квадратичного ускорения алгоритма Гровера.
Важно отметить, что категории безопасности, основанные на этих эталонных примитивах, обеспечивают значительно большую степень квантовой стойкости, чем может предположить простейший анализ. К примеру, категории 1, 3 и 5 определяются на основе блочных шифров, которые можно взломать с помощью алгоритма Гровера с его квадратичным ускорением. Но этот алгоритм требует длинных цепочек последовательных вычислений, что очень сложно реализовать на практике. В реальной атаке необходимо запускать множество отдельных экземпляров алгоритма параллельно, что снижает эффективность квадратичного ускорения.
NIST в своих вычислениях использует менее оптимизированные (а значит, и менее консервативные) квантовые схемы AES из работы Грассля и др. (2015), уступающие схемам Ляо и Ло (2025). При этом институт закладывает в расчёты более высокую скорость логических гейтов, что, наоборот, повышает консервативность вычислений. Однако итоговые затраты оказываются примерно в том же диапазоне и ведут к тем же выводам.
«Дополнительным доказательством служит документ NIST IR 8547 ipd («Переход на постквантовые стандарты криптографии»), который запрещает использование всех квантово-уязвимых алгоритмов после 2035 года. Тем не менее в разделе 4.1.3 институт подтверждает, что все размеры ключей AES остаются разрешёнными».
Существующие стандарты NIST по симметричной криптографии — включая хэш-функции, XOF, блок-шифры, KDF и DRBG — значительно менее уязвимы к известным квантовым атакам, чем стандарты асимметричной криптографии SP 800-56A, SP 800-56B и FIPS 186. В частности, все одобренные NIST симметричные примитивы, обеспечивающие минимум 128 бит классической защиты, в системе стандартизации PQC из пяти категорий относятся как минимум к категории 1 (см. таблицу 1).
Наконец, в FAQ по постквантовой криптографии есть прямой ответ на вопрос «стоит ли нам удваивать размер ключей AES».
Нужно ли нам уже сегодня удваивать длину ключей AES для защиты от угрозы атак с помощью квантовых компьютеров? (добавлено 11.18.18)
Алгоритм Гровера позволяет квантовым компьютерам подбирать ключи методом перебора, используя квадратично меньше шагов, чем требуется в классическом случае. На первый взгляд, это может натолкнуть на мысль, что при атаке с помощью квантового компьютера получится взломать симметричный шифр с длиной ключа, вдвое большей, чем при использовании стандартных компьютеров. Однако здесь присутствует несколько ослабляющих факторов, указывающих на то, что алгоритм Гровера не будет ускорять полный подбор ключа в ожидаемой степени. Во-первых, квантовые вычислительные системы будут дороже в создании и использовании, чем классические. Кроме того, в 1997 году Залка доказал, что для получения полноценного квадратичного ускорения все шаги алгоритма Гровера должны выполняться последовательно. В реальном же мире, где криптографические атаки опираются на обширное распараллеливание обработки, преимущество алгоритма Гровера будет меньше.
Если учесть эти ослабляющие факторы, высока вероятность, что при атаке на AES преимущество алгоритма Гровера окажется малым или вовсе будет отсутствовать, и AES-128 останется достаточно защищённым ещё не одно десятилетие. Более того, даже если квантовые компьютеры окажутся намного дешевле, чем ожидается, известная сложность распараллеливания алгоритма Гровера предполагает, что AES-192 и AES-256 всё равно останутся защищёнными ещё очень долго. Естественно, это предполагает, что ни одна новая криптографическая уязвимость — будь то в классическом или квантовом криптоанализе — AES не затронет.
Исходя из этого понимания, в текущих приложениях вполне можно продолжать применять AES с размером ключей 128, 192 или 256 бит. Как только на горизонте возникнет потребность в переходе на новые алгоритмы симметричного шифрования или хэш-функции, NIST выпустит соответствующее руководство. Ну а пока пользователи должны следовать действующим рекомендациям и правилам — в частности, не использовать любой механизм, обеспечивающий менее 112 бит классической стойкости.
NIST по этому поводу говорит однозначно: 128-битных ключей достаточно.
Подтверждение от BSI
А что насчёт других органов стандартизации? Федеральное управление по информационной безопасности Германии (Federal Office for Information Security, BSI) недавно опубликовало стандарт BSI TR-02102-1 (Криптографические механизмы: рекомендации и длина ключей) с обновлениями в области постквантовой криптографии.
Алгоритм Гровера в нём упоминается вскользь и с меньшей однозначностью, чем у NIST, но общий вывод аналогичен:
Для использования в новых криптографических системах рекомендуются следующие блок-шифры:
AES-128, AES-192, AES-256
В той же публикации авторы советуют отказываться от уязвимых для квантовых компьютеров примитивов (среди которых не указан AES-128) ещё раньше, чем NIST:
Использование исключительно классических механизмов согласования ключей рекомендуется только до конца 2031 года; подробнее читайте в разделе 2.3.
Подтверждение от Сэмюэля Жака
Сэмюэль Жак занимает должность доцента кафедры комбинаторики и оптимизации в Университете Ватерлоо, специализируясь на криптографии и квантовых вычислениях. Возможно, вам знакома его работа «Landscape of Quantum Computing».
Когда я уже выполнил все вышеприведённые расчёты, мне вдруг попалась вот эта презентация от 2024 года. Честно говоря, я почувствовал себя несколько глупо, так как проделал ту же работу и с меньшим опытом в предметной области. Зато меня порадовало, что наши заключения очень схожи: запас прочности настолько велик, а влияние используемых экспертами допущений и оптимизаций столь мало, что мы раз за разом приходим к одним и тем же выводам.
Он говорит о том, насколько трудно создать даже один логический кубит. Я сознательно игнорирую этот фактор в расчётах выше, так как мы исходим из сценария, в котором масштабируемая квантовая коррекция ошибок всё же будет реализована — иначе нам не пришлось бы беспокоиться даже об асимметричной криптографии.
Жак также говорит о декогеренции, на которую я лишь намекнул, ставя под сомнение тот факт, что квантовый компьютер реально сможет работать десять лет без перебоев — хотя именно это мы и закладываем в свои консервативные расчёты.
Он правильно подмечает, что правильной метрикой для оптимизации оракула схем Гровера является «глубина² × ширина», поскольку глубина определяет как затраты, так и общий предел длительности вычислений. Это говорит о том, что схема Ляо и Ло (2025) может не являться оптимальной, и Жак использует схему из работы Янга и др. (2022), но приходит к очень похожим результатам.
Наконец, он пишет, что каждый логический T-гейт в архитектуре поверхностного кода требует 216 физических операций, поэтому в формуле всё ещё не хватает членов для вычисления реалистичной оценки необходимых ресурсов.
Почему бы всё равно не усилить защиту?
Весь постквантовый переход направлен на уменьшение гипотетических рисков, так почему бы не перестраховаться и с симметричными ключами? Потому что ресурсы не бесконечны, изменения потребуют существенных затрат, и здесь важна общая координация.
Отрасль стремится внедрить постквантовую криптографию, так как эксперты сулят угрозу для асимметричных алгоритмов. И напротив, те же эксперты говорят, что для симметричной криптографии угрозы нет.
Симметричное шифрование достаточно отдалено от асимметричного, поэтому мы не можем просто сменить его как бы заодно, чтобы сэкономить. К примеру, изменение согласованного вычисления TLS-ключей и алгоритмов цифровой подписи в инфраструктуре PKI никак не связано с изменением поддерживаемых наборов шифров.
Объединение необходимых и необязательных изменений приведёт к перегрузке систем и трате ресурсов, которые можно было бы направить на срочные обновления. Нам повезло, что мы можем не трогать системы симметричной криптографии. Нужно ценить эту возможность и сосредоточить силы на реально важной работе, которой предостаточно.
В этом вопросе также есть аспект сложности и координации — модернизация любой открытой экосистемы вроде TLS или любых решений, реализованных в разных библиотеках и языках программирования, требует утверждения общей цели. Намного проще согласовать нечто технически точное — мы можем либо сразу во всём согласиться, либо убедить друг друга с помощью технических аргументов. Если же наша цель оказывается необязательной или недостаточно определённой, то возникают проблемы совместимости и приходится одновременно поддерживать несколько субъективных подходов, что дополнительно всё усложняет.
А как же CNSA 2.0?
Действительно, существует один режим нормативного соответствия, требующий использования 256-битных симметричных ключей: CNSA 2.0.
Но он всё же не является адаптацией конкретно под квантовую угрозу. CNSA 2.0 требует 256-битного уровня безопасности для всего точно так же, как и его предшественник — Suite B — требовал подобной защиты для сверхсекретных документов. В действительности он даже предписывает использовать алгоритмы ML-KEM-1024 и ML-DSA-87. Как я понимаю, его задача — избежать той фрагментации, которую вносят «уровни защищённости», выбрав один избыточный примитив для всех конфигураций.
Если учесть, что в CNSA 2.0 в качестве стандарта для 256-битного уровня защищённости утвердили AES-256 (а не какой-то гипотетический AES-512), это только подтверждает, что алгоритм Гровера не ослабляет стойкость AES вдвое.
Похоже, профили CNSA 2.0 будут реализованы в Go, так как формула «256 бит для всего» — это чётко обозначенный ориентир, который вряд ли изменится. И пусть это не концепция «безопасно и разумно», какую предпочёл бы я, но на неё мы хотя бы все можем опереться. Чего не скажешь про подход «безопасно и разумно, но с поправкой на частичное недопонимание некоторыми стойкости отдельных алгоритмов», в случае которого у разных людей будет своё видение правильного решения.
Получается, 256-битные ключи бесполезны?
Я считаю, что 256-битные «уровни защищённости» находятся где-то между лишним «успокоительным» и нумерологией. Как сказал один мой коллега, «Мы не верим в то, что можно досчитать до 2128», но это не означает, что 256-битные ключи (или размеры блоков) не могут быть полезны в случаях, когда необходимо гарантировать реальный 128-битный уровень защиты.
Когда существует угроза коллизий и атакующий может сыграть на эффекте парадокса дней рождения, разрядность защиты фактически уменьшается вдвое, и для обеспечения 128 бит стойкости вам уже нужно получить 256-битный хэш (именно поэтому SHA-128 не существует). Аналогичным образом, в случае многоцелевых атак, когда вероятность успеха злоумышленника оценивается как шанс взлома одного из множества сообщений/ключей, может потребоваться дополнительный запас прочности, зависящий от того, как именно используются одноразовые числа (nonce).
Однако все эти вопросы находятся в ведении инженеров-криптографов, проектирующих протоколы, и не входят в сферу решений о политиках безопасности или системного администрирования. Грамотно построенные протоколы уже учитывают все эти нюансы. К примеру, TLS с AES-128 соответствует 128-битному уровню защиты с большим запасом прочности на случай многоцелевых атак — всё благодаря правильной схеме обработки одноразовых чисел.
Как один из таких инженеров-криптографов я реально хочу, чтобы все шифры использовали 256-битные ключи, так как это бы упростило мне жизнь. Но:
Мы уже проделали масштабную работу по налаживанию работы со 128-битными ключами, и если начнём переход сейчас, то просто растратим силы вместо того, чтобы направить их на действительно важный постквантовый переход.
К сожалению, для AES-256 было заложено больше раундов шифрования, чем для AES-128, что сделало его неоправданно медленнее.
Сноски
Существуют последовательные атаки, которые действительно были истолкованы как более практичные, чем есть на самом деле. Например, атака на статический вариант Диффи-Хеллмана на базе Curve25519 или ristretto255 методом опроса оракула потребует 263,5 запросов. И это звучит вполне реализуемо, если не учитывать, что они должны выполняться последовательно, а значит, атака в самом оптимистичном сценарии растянется на двести лет. ↩
Под «гейтом» здесь имеется в виду логический Т-гейт, а не физический. На сверхпроводящих кубитах физические гейты выполняются за ~100 нс, но логический Т-гейт на машине с системой коррекции ошибок на основе поверхностного кода выполняется намного медленнее. Опубликованные исследователями оценки по длительности выполнения Т-гейтов лежат в диапазоне от 1 до нескольких десятков мкс, то есть 1 мкс представляет достаточно консервативный (для нас) вариант. ↩
А достаточно ли первой категории? Разве мы не используем ML-KEM-768 и ML-DSA-44 из-за того, что они соответствуют второй и третьей категориям соответственно? Мы делаем это не потому, что первой категории недостаточно, а из-за того, что криптоанализ решёток может развиться и сместить ML-KEM-768 или ML-DSA-44 в первую категорию. В отношении AES таких беспокойств нет. К тому же он и был выбран в качестве эталона для определения соответствия категории 1. ↩