После долгих лет исследования и тестирования, в середине августа 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.