Одноядерный процессор взломал алгоритм постквантовой криптографии за 1 час

В прошлом месяце Национальный институт стандартов и технологий США (NIST) представил первую в истории группу инструментов шифрования , которые потенциально могут противостоять атаке квантового компьютера. 4 выбранных алгоритма шифрования теперь станут частью стандарта постквантовой криптографии ( post-quantum cryptographic, PQC ) NIST, который будет введен через 2 года.

В то же время NIST предложил четыре дополнительных алгоритма в качестве потенциальных замен, ожидающих дальнейшего тестирования, в надежде, что один или несколько из них также могут быть подходящими альтернативами шифрованию в постквантовом мире. Новая атака взламывает SIKE (Supersingular Isogeny Key Encapsulation) , один из последних четырех дополнительных алгоритмов, разработанный компанией Microsoft. Атака не влияет на четыре алгоритма PQC, выбранных NIST в качестве утвержденных стандартов, которые основаны на совершенно других математических методах, чем SIKE.

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

На выходных группа исследователей компьютерной безопасности и промышленной криптографии в KU Leuven поставила под сомнение работу алгоритма. В документе под названием «Эффективная атака с восстановлением ключа на SIDH » описан метод, использующий сложную математику и один традиционный ПК для восстановления ключей шифрования в транзакциях, защищенных SIKE. Весь процесс требует всего около часа времени. Это исследование дает Воутеру Кастрику и Томасу Декру право на получение награды в размере 50 000 долларов от NIST.

Готовая реализация метода взлома SIKE опубликована в виде сценария для алгебраической системы Magma . Для восстановления закрытого ключа, применяемого для шифрования защищённых сетевых сеансов, при использовании набора параметров SIKEp434 (level 1) на одноядерной системе потребовались 62 минуты, SIKEp503 (level 2) - 2 часа 19 минут, SIKEp610 (level 3) - 8 часов 15 минут, SIKEp751 (level 5) - 20 часов 37 минут. На решение разработанных компанией Microsoft конкурсных заданий $IKEp182 и $IKEp217 было потрачено 4 и 6 минут соответственно.

Для разработчиков SIKE уязвимость алгоритма к атаке GPST оказалась сюрпризом. Это ArsTechnica подтвердил его соавтор Дэвид Джао (David Jao), профессор Университета Ватерлоо. «Атака была неожиданностью», – сказал он.

На вопрос ArsTechnica, почему SIKE уязвим перед математическими теоремами, которым десятки лет, Дэвид Джао ответил: «Это правда, что атака использует математику, которая была опубликована в 1990-х и 2000-х годах. В некотором смысле атака не требует новой математики; это могло быть замечено в любое время. Одним из неожиданных аспектов атаки является то, что она использует кривые второго рода для атаки на эллиптические кривые (которые являются кривыми первого рода)».

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