06.08 // Квантовостойкий и практичный TLS на основе R-LWE

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

Одним из перспективных направлений вычислительной постквантовой криптографии являются методы на основе решёток. Исследователи решили проверить практичность одного из таких методов — R-LWE (обучение в кольце с ошибками).

Из кругового поля, заданного круговым полиномом степени m, являющимся степенью числа 2, используя целый модуль q задаётся кольцо R_q. Используя функцию распределения над этим кольцом, описывается алгоритм получения чисел из множества, принадлежащего данному кольцу.

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

На основе более сложной версии этого механизма стороны могут осуществить согласование, аналогичное протоколу Диффи-Хеллмана. Но поскольку стойкость этой проблемы близко связана с нахождением кратчайшего вектора в решётках, то R-LWE протокол считается квантовостойким.

Исследователи Joppe W. Bos (NXP Semiconductors, Лёвен, Бельгия), Craig Costello, Michael Naehrig (Исследовательский центр Майкрософт, Редмонд, Вашингтон, США) и Douglas Stebila (Технологический университет Квинслэнд, Брисбен, Австралия) решили проверить практичность реализации данного протокола на основе библиотеки OpenSSL. Поскольку R-LWE подходит только для анонимного согласования ключа, то он не обеспечивает аутентификацию и, следовательно, защиту от атак человека посредине. Поэтому, было принято решение о гибридном подходе: для аутентифицирующих подписей пока совместно использовать квантовонестойкие RSA или ECDSA. Для этого в OpenSSL были добавлены режимы RLWE-RSA-AES128-GCM-SHA256 и RLWE-ECDSA-AES128-GCM-SHA256. При этом подразумевается, что квантовый компьютер будет создан нескоро и пока никто неспособен проводить атаки подмены трафика с его помощью. А если он когда-то будет создан, то использовать его для подмены аутентификации ранее переданного и перехваченного трафика будет поздно. При этом, само содержимое записанного противником трафика будет защищено от пассивного квантового криптоанализа за счёт ранее произведённого обмена ключами по R-LWE и дешифровать его будет невозможно даже при наличии квантового компьютера.

TLS и HTTPS потоки исследовались в работе на сервере Apache. Ранее считалось, что внедрение квантовостойкой криптографии — крайне ресурсоёмкая задача. Но на практике оказалось, что из-за того, что основная нагрузка в сервере идёт на аутентификацию и другие операции, то при использовании RLWE-RSA сервер обрабатывает практически такое же число запросов, что и обычно, а при использовании RLWE-ECDSA сервер обрабатывает лишь в 1.2 — 1.3 раз меньше запросов в секунду по сравнению с использованием ECDH-ECDSA (т.е., только асимметричной криптографии на эллиптических кривых при сохранении всей остальной части).

Однако, существует опасение, что сами квантовостойкие алгоритмы могут оказаться нестойкими для взлома обычными методами, ещё до изобретения квантовых компьютеров. Но и в этом плане авторы оптимистичны. Помимо достаточно строгого, по их мнению, доказательства стойкости R-LWE, они предложили дважды комбинированный протокол: ECDH-RLWE — в котором обмен материала для совместного выведения ключа производится одновременно и квантовостойким и квантовонестойким способом. Для взлома такого сеансового ключа противнику потребуется взломать и оба протокола — как Диффи-Хеллман в группах на эллиптических кривых, так и в дискретных гауссовых распределениях на круговых кольцах. При этом скорость работы такого протокола также снижается относительно незначительно, по сравнению с одним R-LWE.

Единственным недостатком внедрения R-LWE может являться сложность его правильной реализации, превосходящая сложность реализации протоколов на эллиптических кривых.

Источник: Cryptology ePrint Archive