Представлены первые стандарты постквантового шифрования

После долгих лет исследования и тестирования, в середине августа 2023 года Национальный институт стандартов и технологий США (NIST) наконец-то представил полноценные стандарты постквантового шифрования — FIPS 203, FIPS 204 и FIPS 205. Самое время поговорить о том, что они собой представляют и почему внедрять их в идеале нужно было уже вчера.

Зачем нужна постквантовая криптография

Для начала вкратце опишем ту угрозу, которую представляют для криптографии квантовые компьютеры. Состоит она в том, что квантовые вычисления могут успешно применяться для взлома асимметричного шифрования. Почему это важно? Как правило, шифрование современных коммуникаций в наиболее распространенной форме представляет собой двойную систему:

• Все сообщения шифруются симметричным алгоритмом (например, AES) — в нем используется только один ключ, который одинаков у всех участников коммуникации. Симметричные алгоритмы работают хорошо и быстро, но есть проблема: ключ надо как-то так передать от одного собеседника другому, чтобы его невозможно было перехватить в процессе передачи.
• Поэтому для передачи этого ключа используется асимметричное шифрование (например, RSA или ECDH). В нем у каждого собеседника есть пары ключей — закрытый и открытый, — которые связаны математически. Сообщение шифруется открытым ключом, а расшифровывается только закрытым. Асимметричное шифрование более медленное, поэтому использовать его для шифрования всех сообщений было бы непрактично.

Тайну переписки обеспечивает тот факт, что вычислить закрытый ключ, зная соответствующий ему открытый, — задача крайне ресурсоемкая, на ее решение могут уйти десятки, сотни, тысячи, а то и миллионы лет. Но это если мы пытаемся решить ее при помощи классических компьютеров.

Квантовые компьютеры существенно ускоряют вычисления такого рода. В частности, квантовый алгоритм Шора позволяет получать закрытые ключи асимметричного шифрования на многие порядки быстрее, чем рассчитывали создатели соответствующих криптографических схем, — за минуты или часы вместо лет и веков.

В свою очередь, вычислив закрытый ключ асимметричного шифрования, можно узнать ключ симметричного шифрования, которым и зашифрована основная переписка. Таким образом вся переписка может быть прочитана.

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

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

Трио постквантовых криптографических стандартов: FIPS 203, FIPS 204 и FIPS 205

Таким образом, первоочередной задачей для криптографов стало создание устойчивых к взлому с помощью квантовых компьютеров алгоритмов асимметричного шифрования, которые могли бы использоваться в механизмах передачи ключей и цифровых подписей. Собственно, результатом их работы и стали представленные Национальным институтом стандартов и технологий США (NIST) стандарты постквантового шифрования FIPS 203, FIPS 204 и FIPS 205.

FIPS 203

Стандарт FIPS 203 описывает механизм инкапсуляции ключа, основанный на теории решеток — ML-KEM (Module-Lattice-Based Key-Encapsulation Mechanism). Это устойчивая к атакам с помощью квантовых алгоритмов асимметричная криптографическая система, которая служит для передачи ключей шифрования между собеседниками.

Система ML-KEM была разработана в рамках CRYSTALS (Cryptographic Suite for Algebraic Lattices — криптографический комплект на основе алгебраических решеток) и также известна под названием CRYSTALS-Kyber или просто Kyber.

Стандарт FIPS 203 включает три варианта параметров для ML-KEM:

• ML-KEM-512: категория безопасности 1 (эквивалентно AES-128);
• ML-KEM-768: категория безопасности 3 (эквивалентно AES-192);
• ML-KEM-1024: категория безопасности 5 (эквивалентно AES-256).

FIPS 204

В стандарте FIPS 204 описан механизм цифровой подписи, который, как и FIPS 203, основан на алгебраических решетках — ML-DSA (Module-Lattice-Based Digital Signature Algorithm). Ранее известный как CRYSTALS-Dilithium, этот механизм был разработан в рамках того же проекта CRYSTALS, что и вышеописанный Kyber.

В стандарте FIPS 204 зафиксированы три варианта параметров для ML-DSA:

• ML-DSA-44: категория безопасности 2 (эквивалентно SHA3-256);
• ML-DSA-65: категория безопасности 3;
• ML-DSA-87: категория безопасности 5.

FIPS 205

Наконец, третий из представленных NIST стандартов, FIPS 205, описывает альтернативный механизм цифровой подписи — SLH-DSA (Stateless Hash-Based Digital Signature Algorithm). В отличие от двух предыдущих криптосистем, которые используют алгебраические решетки, SLH-DSA основан на хешировании. Также этот механизм известен как SPHINCS+.

Стандарт предполагает использование как хеш-функции SHA2 с фиксированной длиной выходного сообщения, так и функции SHAKE с произвольной длиной. Для каждого базового уровня криптостойкости SLH-DSA предусмотрены наборы параметров, обеспечивающие высокую скорость (f — fast) или более компактный размер сигнатуры (s — small). Таким образом, многообразие здесь самое высокое — всего в стандарте FIPS 205 приведены 12 вариантов параметров:

• SLH-DSA-SHA2-128s, SLH-DSA-SHAKE-128s, SLH-DSA-SHA2-128f, SLH-DSA-SHAKE-128f: категория безопасности 1;
• SLH-DSA-SHA2-192s, SLH-DSA-SHAKE-192s, SLH-DSA-SHA2-192f, SLH-DSA-SHAKE-192f: категория безопасности 3;
• SLH-DSA-SHA2-256s, SLH-DSA-SHAKE-256s, SLH-DSA-SHA2-256f, SLH-DSA-SHAKE-256f: категория безопасности 5.

HNDL, или Почему пора начинать пользоваться постквантовым шифрованием

Пока опасность использования квантовых алгоритмов для взлома асимметричного шифрования в основном теоретическая. Чтобы воплотить его на практике, мощности существующих квантовых компьютеров недостаточно.

До прошлого года считалось, что до появления достаточно больших квантовых систем есть еще лет десять. Однако опубликованная в 2023 году научная работа предложила определенные способы оптимизировать взлом, используя комбинацию классических и квантовых вычислений. Так что сроки достижения квантового превосходства, судя по всему, сдвинулись: RSA-2048, вероятно, все-таки смогут взломать уже в ближайшие годы.

Кроме того, следует помнить о том, что обычно обозначают аббревиатурой HNDL — harvest now, decrypt later (или SNDL — store now, decrypt later). Обладающие серьезными ресурсами атакующие могут уже некоторое время собирать и хранить пока не поддающиеся расшифровке данные. И как только им станут доступны квантовые компьютеры нужной производительности — они немедленно приступят к ретроспективной расшифровке. Смиренно ожидать этого прекрасного момента, конечно же, не стоит, использовать устойчивые для квантовых алгоритмов стандарты шифрования следует уже сейчас.

Судя по уже сложившейся в IT-индустрии практике, идеальный вариант внедрения постквантовой криптографии состоит в гибридном шифровании данных: то есть в шифровании «в два слоя» — сначала классическим алгоритмом, а потом постквантовым. Таким образом атакующему придется иметь дело с обеими криптосистемами, что сильно снижает шансы успешного взлома. Именно такой подход уже используют в Signal, Apple, Google и Zoom.