Google резко сокращает сроки готовности к приходу Q Day — моменту, когда существующие квантовые компьютеры смогут взломать алгоритмы криптографии открытого ключа, которые защищают секреты военных, банков, правительств и почти каждого человека на Земле.

В посте, опубликованном в среду, Google заявила, что дала себе срок до 2029 года на подготовку к этому событию. В статье компания предупредила остальной мир о необходимости принять аналогичные меры, внедрив алгоритмы PQC (постквантовой криптографии) для дополнения или замены эллиптических кривых и RSA, которые будут взломаны.

Конец близок

«Как пионер в области квантовых вычислений и PQC, мы обязаны показать пример и предложить амбициозный график», — написала Хизер Адкинс, вице-президент по безопасности Google, и Софи Шмиг, старший инженер по криптографии. «Благодаря этому мы надеемся обеспечить ясность и срочность, необходимые для ускорения цифровых переходов не только для Google, но и во всей индустрии».

Отдельно Google подробно описала свой график для обеспечения устойчивости Android к квантовым компьютерам, впервые публично обсудив поддержку PQC на операционной системе. Начиная с бета-версии, Android 17 будет поддерживать ML-DSA, алгоритм цифровой подписи, стандартизированный Национальным институтом стандартов и технологий. ML-DSA будет добавлена в аппаратный корень доверия Android. Этот шаг позволит разработчикам иметь ключи PQC для подписания своих приложений и проверки подписей другого ПО.

Google также заявила, что теперь у неё есть ML-DSA, интегрированная в библиотеку Android verified boot, которая защищает последовательность загрузки от манипуляций. Инженеры Google также начинают переводить удалённое подтверждение личности на PQC. Удалённое подтверждение личности — это функция, позволяющая устройству доказать свое текущее состояние удалённому серверу, например подтвердить серверу корпоративной сети, что на нём работает безопасная версия ОС.

Google также сообщила, что добавляет поддержку ML-DSA в Android Keystore, чтобы разработчики могли генерировать ключи ML-DSA и хранить их непосредственно в защищённом аппаратном обеспечении устройства. Google также планирует перевести Play Store и подписи разработчиков для каждого приложения в нём на PQC.

Эти добавления, вероятно, создадут значительную нагрузку на разработчиков Android.

Что же так напугало Google?

Жёсткий дедлайн в среду стал неожиданностью для многих инженеров в области криптографии, включая тех, кто активно работает над переходом на PQC уже много лет.

«Это, безусловно, значительное ускорение и ужесточение графиков общественного перехода, которые мы видели до сих пор, и это ускорение даже превосходит то, что просил от нас правительство США», — сказал в интервью Брайан ЛаМаккиа, инженер в области криптографии, который контролировал переход Microsoft на постквантовую криптографию с 2015 по 2022 год и теперь работает в Farcaster Consulting Group. «График 2029 года — это агрессивное ускорение, но возникает вопрос, что его мотивирует».

Google не объяснила причины пересмотра ни в одном из своих постов. Представитель компании не сразу предоставил ответы на вопросы, отправленные по электронной почте.

Оценки времени прихода Q Day сильно варьировались с середины 1990-х годов, когда математик Питер Шор впервые показал, что квантовый компьютер достаточной мощности мог бы факторизировать целые числа за полиномиальное время, намного быстрее, чем классические компьютеры. Это предупредило мир о том, что дни RSA сочтены. Дальнейшие исследования показали, что квантовые компьютеры обеспечивают аналогичное ускорение в решении задачи дискретного логарифма, на которой основаны эллиптические кривые.

График прихода этого момента основан на времени, когда существующие квантовые компьютеры будут содержать требуемое количество кубитов, способных исправлять неизбежные ошибки. В 2012 году большинство оценок предполагали, что 2048-битный ключ RSA может быть взломан квантовым компьютером с миллиардом физических кубитов. К 2019 году эта оценка была снижена до 20 миллионов физических кубитов. Среди исследователей ходил анекдот, что Q Day на протяжении последних 30 лет всегда был в 10–20 годах в будущем.

В июне прошлого года Google опубликовала исследование, которое снова резко снизило ожидаемый порог для взлома RSA. В исследовании показано, что 2048-битное целое число RSA может быть факторизировано менее чем за неделю с помощью квантового компьютера с 1 миллионом «шумных кубитов» — кубитов, подверженных ошибкам, возникающим из-за условий окружающей среды, нарушающих квантовое состояние. Исследование возглавлял Крейг Гидни, тот же учёный, стоявший за оценкой 2019 года.

Для подготовки к Q Day криптографы разработали новые алгоритмы шифрования, основанные на проблемах, в решении которых квантовые компьютеры не имеют преимущества перед классическими. Вместо факторизации или решения задачи дискретного логарифма один подход включает математические структуры, известные как решётки. Второй подход включает схему цифровой подписи на основе безгосударственного хеша. Национальный институт стандартов и технологий продвинул несколько алгоритмов, которые до сих пор не были взломаны и считаются безопасными.

В 2022 году АНБ установило дедлайн готовности к PQC в системах национальной безопасности на 2033 год и на 2030 год для нескольких конкретных приложений.

В последнее время дедлайны находятся в движении, так как и администрация Байдена, и администрация Трампа издали указы, приоритизирующие готовность к квантовым вычислениям. В настоящее время АНБ придерживается дедлайна 2031 года.

Алгоритмы PQC нашли свой путь в различные продукты и протоколы, хотя в основном фрагментарно. В прошлом году мессенджер Signal добавил ML-KEM-768, реализацию алгоритма CRYSTALS-Kyber, в свой существующий криптографический механизм. ПО и сервисы от Google, Apple, Cloudflare и десятков других также сделали то же самое.

«Квантовые компьютеры будут представлять значительную угрозу для текущих криптографических стандартов, в частности для шифрования и цифровых подписей», — говорилось в посте Google в среду утром. «Угроза шифрованию актуальна сегодня с атаками "сохрани сейчас — расшифруй позже", в то время как цифровые подписи — это будущая угроза, требующая перехода на PQC до появления криптографически значимого квантового компьютера (CRQC). Вот почему мы скорректировали нашу модель угрозы, чтобы приоритизировать миграцию PQC для сервисов аутентификации — важного компонента онлайн-безопасности и миграции цифровых подписей. Мы рекомендуем другим инженерным командам поступить так же».