Практика применения постквантовых криптографических алгоритмов

В наших предыдущих постах мы рассказали о возможности взломать современные криптографические алгоритмы с применением квантовых компьютеров — так называемой «квантовой угрозе», а также рассмотрели постквантовые схемы подписи, которые исследуются и стандартизируются Национальным институтом стандартов США (NIST).

Сегодня Александр Сазонов, технический руководитель персонализированных ИИ-сервисов, и Алина Трепачева, разработчик-исследователь во Future Crew, расскажут о практике внедрения постквантовых криптографических алгоритмов известными мировыми компаниями.

В современных системах обмена данными по открытым каналам связи стоит задача обеспечить двум сторонам, имеющим пары из открытого и закрытого ключа, получение общего секретного ключа для шифрования сообщений. Для этой цели повсеместно применяется протокол Диффи-Хеллмана на эллиптических кривых, который хорошо себя зарекомендовал с точки зрения производительности и стойкости. Но этот протокол, использующий «классические» асимметричные криптографические алгоритмы, также подвержен «квантовой угрозе». Поэтому в NIST кроме постквантовых алгоритмов подписи рассматриваются также и постквантовые схемы выработки общего секретного ключа — т.н. key encapsulation mechanism (KEM).

В результате 3-го раунда процесса стандартизации NIST был отобран единственный финалист на роль стандарта схемы KEM  —  CRYSTALS Kyber. В основе Kyber лежит оригинальная схема шифрования на решетках.

Есть три варианта реализации Kyber:

·      Kyber-512 (уровень безопасности 1 по NIST — соответствует уровню стойкости AES-128);

·      Kyber-768 (уровень безопасности 3 по NIST — соответствует уровню стойкости AES-192);

·      Kyber-1024 (уровень безопасности 5 по NIST — соответствует уровню стойкости AES-256).

Оптимальной реализацией считается Kyber-768, которая, согласно очень консервативному анализу, обеспечивает более 128 бит защиты от всех известных классических и квантовых атак.

Авторы протокола рекомендуют использовать Kyber в гибридном режиме (например, в сочетании с протоколом Диффи-Хеллмана на эллиптической кривой). Логика такого подхода состоит в том, чтобы с одной стороны добавить защиту от «квантовой угрозы», а с другой стороны минимизировать риски применения нового, мало исследованного протокола Kyber, и обеспечить стойкость итогового протокола не ниже стойкости, обеспечиваемой проверенным временем протоколом Диффи-Хеллмана. Для того, чтобы взломать гибридную конструкцию, злоумышленнику придется взломать и Kyber и решить задачу дискретного логарифмирования на эллиптической кривой.

Собственно, этот подход был выбран разработчиками следующих решений.

Разработчики мессенджера Signal в мае 2023 года представили протокол PQXDH (Post-Quantum Extended Diffie-Hellman). PQXDH устанавливает общий секретный ключ между двумя сторонами, которые взаимно аутентифицируют друг друга классическим способом, т.е. проверяя подписи открытыми ключами, являющимися точками на эллиптической кривой. PQXDH обеспечивает постквантовую forward secrecy (защиту от атаки «сохрани сейчас, расшифруй потом»), но по-прежнему полагается на сложность вычисления дискретного логарифма на группе точек кривой для взаимной аутентификации. PQXDH протокол является гибридным — для выработки общего секрета используется как криптография на эллиптических кривых (Диффи-Хеллман + XEdDSA), так и постквантовый KEM протокол Crystals Kyber-1024. По сути, в PQXDH вырабатываются два общих секрета — один с помощью Диффи-Хеллмана, другой с помощью Kyber. Из их конкатенации с применением стандартной key derivation function вырабатывается итоговый общий секретный ключ. Злоумышленник должен взломать обе схемы, чтобы вычислить общий секретный ключ.

Разработчики Apple в феврале 2024 года представили протокол PQ3 для защиты сообщений в iMessage. Так же, как PQXDH, протокол PQ3 является гибридным, объединяя протокол Диффи-Хеллмана на эллиптических кривых и Crystals Kyber-1024. Ключевым отличием PQ3 от PQXDH, которое подчеркивают разработчики Apple, является то, что в PQ3 «постквантовая составляющая» протокола применяется не однократно при первоначальной генерации секретного ключа, а регулярно в течение всего обмена сообщениями между пользователями (при смене ключа шифрования).

Внедрением постквантовой криптографии в протокол TLS также занимаются и в AWS в рамках развития своего Сервиса управления ключами; в библиотеке s2n-tls разработчики реализуют гибридный протокол с использованием Kyber-512.

И наконец, все веб-сайты и API, обслуживаемые через Cloudflare, с октября 2022 года в режиме бета сервиса поддерживают постквантовые гибридные протоколы (с использованием Kyber-512 или Kyber-768) для выработки общего секретного ключа.

Еще раз подчеркнем, что во всех вышеупомянутых решениях постквантовая защита была добавлена только к схеме выработки общего ключа шифрования, но аутентификация сторон пока осталась классической. Следующим шагом в развитии постквантовой криптографии должно стать решение, обеспечивающее применение постквантовых криптографических алгоритмов в задаче аутентификации пользователей, которая все еще обеспечивается инфраструктурами открытых ключей (PKI) на классических криптографических алгоритмах. Криптографическим сообществом рассматривается возможность применения постквантовых алгоритмов подписи (таких как Crystals Dilithium) для переработки существующих PKI. Однако существенные размеры подписи и ключевого материала (даже по сравнению с постквантовыми KEM схемами) пока являются препятствием для развития этого направления. Одной из альтернатив является переход на протокол KEMTLS. От стандартного TLS он отличается тем, что для аутентификации сторон вместо алгоритма подписи в нем используется схема KEM Crystals Kyber. В этом направления начали двигаться разработчики Cloudflare, предложившие экспериментальную библиотеку cf-pq-kemtls, реализующую KEMTLS.

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