Моё мнение о срочности внедрения квантово-устойчивой криптографии изменилось всего за несколько месяцев. Настало время рассказать о причинах этого.
Уже давно ходили слухи об ожидаемом и неожиданном прогрессе в области криптографически-релевантных квантовых компьютеров (CRQC), но за последние недели мы получили два публичных примера.
Во-первых, Google опубликовала статью, в которой существенно снизила ожидаемое количество кубитов и вентилей, требуемых для взлома 256-битных эллиптических кривых наподобие NIST P-256 и secp256k1, из-за чего в архитектурах с высокими тактовыми частотами (например, в кубитах со сверхпроводимостью) реализация атаки становится возможной за считанные минуты. Авторы странным образом1 делают упор только на криптовалюты и пулы памяти, но гораздо более важными последствиями могут стать практические MitM-атаки на WebPKI.
Вскоре после этого была опубликована статья Oratomic, демонстрирующая, что благодаря улучшению коррекции ошибок 256-битные эллиптические кривые можно взломать с помощью всего лишь 10000 физических кубитов (при условии наличия нелокальной связи, которую, похоже, обеспечивают нейтральные атомы). Такая атака была бы медленнее, но даже взлом одного ключа в месяц может привести к катастрофическим последствиям.
На второй странице статьи есть вот такой замечательный график (Babbush et al. — это упомянутая мной статья Google, к которой авторы второй, предположительно, имели предварительный доступ):
В целом, похоже на то, что всё движется: оборудование становится лучше, алгоритмы — малозатратнее, требования к коррекции ошибок — ниже.
Честно скажу, что не понимаю всей той физики, которая приведена в этих статьях. Это не моя работа и не моя предметная область. Моя работа заключается в оценке рисков от лица пользователей, доверивших мне свою безопасность. Я знаю лишь то, что говорят нам, как минимум, настоящие специалисты.
Хизер Эдкинс и Софи Шмиег говорят нам, что «новые области квантовых вычислений могут быть ближе, чем кажется», и ставят дедлайн на 2029 год, то есть 33 месяца. До текущего месяца никто не устанавливал столь агрессивный график.
Скотт Ааронсон сообщает, что «самый чёткий посыл, который можно сделать общественности, заключается в необходимости срочного перехода на постквантовые криптосистемы». Можно провести здесь параллели с тем, как в 1939-1940 годах прекратились публичные исследования ядерного распада.
Хронология, всего несколько недель назад представленная на RWPQC 2026, была гораздо более плотной, чем ещё пару лет назад, но и она уже частично устарела. Раньше шутили, что квантовые компьютеры уже тридцать лет обещают выпустить через десять лет. Что ж, теперь это уже не так: сроки начали сдвигаться.
Вы можете подумать: «Ну, это может быть плохо, а может и не произойти!», но я хочу донести до вас, насколько are важно всё это прямо сейчас. Вопрос не в том, уверены ли мы на 100%, что CRQC будут существовать в 2030 году, а в том, уверены ли мы на 100%, что CRQC НЕ будут существовать в 2030 году. Я просто не понимаю, как неспециалист может слушать то, что говорят специалисты, и думать: «Мне виднее, на самом деле вероятность меньше одного процента». Помните, что на кону жизни ваших пользователей2.
Иными словами, даже если наиболее вероятный результат заключается в том, что мы за всю свою жизнь не увидим CRQC, это совершенно неважно, ведь наши пользователи не желают вероятности защиты «больше, чем 50/50»3.
Да, статьи о собаке со счётами забавны и благодаря ним вы можете выглядеть на форумах умным и неординарным. Но это не работа, и эти аргументы выдают отсутствие экспертизы. Процитирую Скотта Ааронсона:
Как только вы поймёте квантовую отказоустойчивость, вопросы типа «когда же вы разложите на множители 35 при помощи алгоритма Шора?» становятся похожими на вопрос «когда же вы произведёте хотя бы маленький ядерный взрыв?», заданный участникам Манхэттенского проекта в 1943 году.
Наша работа — не в том, чтобы испытывать скепсис относительно тем, в которых мы не специалисты. Наша работа — снижение правдоподобных угроз, а авторитетные специалисты говорят нам о непосредственной угрозе.
Подведём итог: может оказаться так, что через десять лет прогнозы окажутся ошибочными, но сейчас всё выглядит так, что скоро они окажутся правы, и этот риск неприемлем.
Что дальше
Что это конкретно значит? Это значит, что нам нужно готовиться к выпуску.
Увы, нам нужно выкатывать то, что у нас есть4, а именно длинные подписи ML-DSA, засовываемые в места, рассчитанные на короткие подписи ECDSA, например, в X.509; исключение составляют Merkle Tree Certificates для WebPKI, которые, к счастью, достаточно длинные.
Не такую статью я хотел написать. Уже несколько месяцев у меня лежит драфт, в котором объясняется, что нам нужно уже реализовать постквантовый обмен ключами, но у нас есть время для адаптации протоколов под более длинные подписи, потому что все они проектировались, исходя из предположения о дешевизне подписей. К сожалению, моя статья уже неактуальна: у нас нет времени, если нам нужно закончить не к 2035, а к 2029 году.
В области обмена ключами миграция на ML-KEM проходит достаточно хорошо, но:
Любой непостквантовый обмен ключами должен теперь считаться потенциальной активной компрометацией; о нём следует уведомлять пользователя, как это делается в OpenSSH, потому что очень сложно сделать так, чтобы все секреты, переданные через соединение или зашифрованные в файле, хранились меньше трёх лет.
Нам стоит на долгое время забыть об неинтерактивном обмене ключами (non interactive key exchange, NIKE); в постквантовом инструментарии у нас есть только KEM (которые однонаправленно аутентифицируются без интерактивности).
Больше не имеет смысла разворачивать новые непостквантовые схемы. Я понимаю, что спаривания были удобны. Я понимаю, что всё постквантовое раздражающе большое. Я знаю, что мы, по сути, только что разобрались, как безопасно реализовывать ECDSA через P-256. Я знаю, что может и не найтись практичных постквантовых эквивалентов для пороговых подписей или identity-based encryption. Поверьте, я знаю, что это больно, но ситуация именно такова.
Мне кажется, что гибридная классическая + постквантовая аутентификация больше не имеет смысла и что она нас лишь замедлит; нам следует двигаться напрямую к ML-DSA-446. Гибридный обмен ключами реализовать довольно просто: там используются эфемерные ключи, и для составного приватного ключа даже не требуется определённого типа или формата передачи. Пару лет назад имело смысл подстраховаться таким подходом. С аутентификацией ситуация другая, и даже несмотря на скорую публикацию draft-ietf-lamps-pq-composite-sigs-15 с 18 составными ключами, все мы потеряем драгоценное время, пока будем разбираться, как обрабатывать эти составные ключи и как раскрывать их пользователям. Кроме того, прошло два года после появления гибридов Kyber, и мы уже накопили большую уверенность в схемах с модульными решётками. Гибридные подписи тратят время и повышают сложность5 при том, что их единственное преимущество — защита на случай, если ML-DSA будет взломана классическим образом до появления CRQC; похоже, что на данный момент это ошибочный компромисс.
К счастью, в симметричном шифровании ничего делать не нужно. Многие ошибочно считают, что для защиты от алгоритма Гровера требуются 256-битные ключи, но это мнение основано на крайне упрощённом понимании алгоритма. Более точная характеристика будет звучать так: при глубине цепей в 2⁶⁴ логических вентилей (приблизительное количество вентилей, которое могут последовательно обработать за десяток лет современные классические компьютерные архитектуы) для выполнения алгоритма Гровера над пространством 128-битных ключей потребуется размер цепей 2¹⁰⁶. Насколько я знаю, прогресса в этой сфере нет; кроме того, есть старые доказательства того, что алгоритм Гровера оптимален и его квантовое ускорение не параллелизуется. Необязательные требования 256-битных ключей вредят, учитывая по-настоящему актуальные постквантовые требования, так как запутывают интероперабельность и могут замедлить внедрение асимметричной постквантовой криптографии.
В моей же области работы мне нужно начать думать над последствиями того, что половина криптографических пакетов в стандартной библиотеке Go внезапно окажется небезопасной, и над тем, как сбалансировать риск атак через демодернизацию и обратную совместимость. Мы впервые за всю нашу карьеру столкнулись с подобным: переход от SHA-1 к SHA-256 и близко не был столь разрушительным7, однако даже он занял кучу времени; при этом иногда обнаруживались неожиданные атаки через демодернизацию.
С доверенными средами исполнения (TEE) наподобие как Intel SGX и AMD SEV-SNP и в целом с аппаратной аттестацией ситуация ужасна. Все их ключи и корневые сертификаты непостквантовые, и я слышал, что прогресса во внедрении постквантовых нет; учитывая скорости развития оборудования, мы, вероятно, вынуждены смириться с тем, что их никогда не будет и что надеяться на них не стоит. Из-за этого мне пришлось полностью пересмотреть весь проект, и, скорее всего, я понижу их роль в своём инструментарии почти до уровня дополнительной линии защиты.
Экосистемы с криптографической идентификацией (например, atproto и криптовалюты) должны начать мигрировать как можно раньше, потому что если CRQC появятся до завершения этого процесса, то им придётся принимать крайне сложные решения, выбирая между возможностью компрометации пользователей или их блокировкой.
Шифрование файлов особенно уязвимо к атакам вида «сохраняем сейчас, дешифруем позже», поэтому нам, вероятно, скоро надо начать предупреждать пользователей, а затем возвращать ошибки для непостквантовых типов получателей age. К сожалению, мы лишь несколько месяцев назад добавили постквантовых получателей (в версии 1.3.08).
Наконец, должен сказать, что на этой неделе я начинаю преподавать PhD-курс криптографии в Болонском университете. На нём я буду говорить о RSA, ECDSA и ECDH только как об устаревших алгоритмах, потому что именно в таком качестве студенты будут встречать их в своей карьере. Знаю, это кажется странным, но ситуация именно такова.
Примечания
Научная статья немного дурашливая: в ней есть доказательство для квантовой цепи с нулевым разглашением, которое совершенно точно будет выведено заново и улучшено до того, как появится реальное оборудование для её запуска. Похоже, авторы считают, что это связано с ответственным раскрытием, поэтому я предположу, что физики просто не специалисты в нашей сфере точно так же, как мы — не специалисты в их.
Аудитория этого поста немного необычна для меня: я обращаюсь с своим коллегам и принимающим решения людям, определяющими действия по внедрению постквантовой криптографии.
Рецензент возразил, что вероятность успеха нападающего после работы 2⁶⁴ равна 1/536870912 (0.0000002%, 2⁻²⁹), и это так, потому что в криптографии мы обычно стремимся к 2⁻³².
Но почему стоит доверять новому? Ответ состоит из двух частей: математики и реализации. Математика — тоже не моя сфера, поэтому я снова положусь на специалистов; например, на Софи Шмиег, утверждающую, что она уверена в решётках, и на АНБ, утвердившее ML-KEM и ML-DSA для уровня «совершенно секретно» во всех задачах, связанных с национальной безопасностью. Кроме того, он старше, чем криптография на эллиптических кривых. («А разве АНБ нам уже не лгало, чтобы взломать шифрование?». Нет, АНБ никогда намеренно не подвергало опасности национальную безопасность США посредством бэкдора, работающего не по принципу NOBUS, а ML-KEM и ML-DSA никак не могут скрывать NOBUS-бэкдор.) Что касается реализации, то моё мнение крайне квалифицированное: я создавал реализацию криптографии и тестировал свою нишу. Безопасно реализовать ML-KEM и ML-DSA гораздо проще, чем их классические альтернативы, а благодаря усовершенствованной инфраструктуре тестирования я ожидаю нахождения в их реализациях всё меньшего количества багов.
Есть одно небольшое исключение: если в вашем протоколе уже есть возможность передачи множественных подписей из множественных публичных ключей, то будет разумно реализовать «гибридные подписи для бедных», просто требуя подписей «две из двух» из одного классического публичного ключа и одного чистого постквантового ключа. Часть экосистемы tlog может пойти по этому пути, но только потому, что затраты существенно снижены уже имеющейся поддержкой signing group «n из m».
Почему ML-DSA-44, если вместо ML-KEM-512 мы обычно используем ML-KEM-768? Потому что ML-KEM-512 относится к Level 1, а ML-DSA-44 — к Level 2, а значит, у него уже есть запас защиты против небольших улучшений криптоанализа.
Потому что SHA-256 — это лучшая удобная замена SHA-1, потому что SHA-1 был гораздо меньшей поверхностью, чем все RSA и ECC, и потому что SHA-1 был не настолько поломан: он всё ещё сохраняет устойчивость к атакам нахождения прообраза и всё ещё может использоваться в HMAC и HKDF.
Задержка во многом была связана с моим неудачным решением заблокировать доступность гибридных получателей HPKE, что помешало CFRG, которой понадобилось почти два года для выбора стабильной label string X-Wing (январь 2024 года) и ML-KEM (август 2024 года), хотя в архитектуру не было внесено никаких изменений. IETF стоит провести внутренний разбор произошедшего, но сомневаюсь, что мы его увидим.
