Что там с квантово-устойчивой криптографией

В начале июля институт NIST одобрил четыре защищенных алгоритма. В блоге T1 Cloud ^[1] мы рассказываем про облачные технологии, разработку и информационную безопасность. Поэтому сегодня мы решили подробнее поговорить о новых алгоритмах — обсудить принципы работы, мнение сообщества и перспективы внедрения таких систем на практике.

Заблаговременная подготовка

Как только квантовые компьютеры превзойдут «классические» в решении ряда сложных математических задач, под угрозой окажутся асимметричные криптографические схемы вроде RSA и ECDSA, так как их криптостойкость основана на исключительной трудности разложения больших чисел на множители. Иными словами, определить закрытый ключ на основании открытого невероятно сложно. Однако пока квантовое превосходство остается далекой перспективой.

В этом направлении постепенно двигаются частные компании и исследовательские институты. В начале года группа китайских инженеров представила ^[2] архитектуру квантового компьютера из 10 тыс. кубитов, которая позволит взламывать ключи шифрования. В то же время самый мощный квантовый процессор (разработка также принадлежит китайским инженерам) на сегодняшний день имеет всего 66 кубитов ^[3].

Таким образом, для достижения квантового превосходства необходимы более эффективные аппаратные решения и алгоритмы, подчеркивающие сильные стороны квантовых систем — на это уйдет порядка 10–30 лет. Но криптографы готовятся к будущему уже сейчас. Еще в 2016 году американский институт NIST объявил конкурс ^[4] по разработке алгоритмов шифрования для постквантовой эпохи. В начале июля многолетнее соревнование подошло к концу, и организаторы выделили наиболее многообещающие решения.

Четыре из семидесяти

Исследователи со всего мира предложили ^[5] более семидесяти криптографических механизмов. Их изучали независимые эксперты на предмет уязвимостей. За шесть лет они сократили ^[6] общий список до четырех алгоритмов. Это — универсальный Kyber ^[7], а также Dilithium ^[8], FALCON ^[9], SPHINCS+ ^[10] для работы с цифровыми подписями.

Криптографическую основу первых трех составляют задачи теории решёток — например, NP-задачи поиска кратчайшего вектора или задача обучения с ошибками (LWE). Считается, что их одинаково плохо решают как классические компьютеры, так и квантовые. Для сокрытия информации используют ^[11] многомерные сетки точек, размерность которых позволяет корректировать сложность вычислений. Что касается SPHINCS+ ^[10], то эта криптографическая схема использует хеш-функции и является естественным развитием SPHINCS. Однако в новой версии разработчики сократили ^[12] размер подписи и увеличили надежность алгоритма.

Если говорить об «аутсайдерах», то одним из последних выбыл ^[13] Rainbow. Он основан на криптографической схеме под названием Unbalanced Oil and Vinegar ^[14] (OUV) — «несбалансированная схема масла и уксуса». Её надежность обеспечивает сложная система квадратичных уравнений, а также односторонние функции с потайным входом (trapdoor). Алгоритм не стал финалистом, поскольку ИБ-специалистам удалось реализовать ^[15] серию атак, понижающих его защищенность — в итоге на взлом подписи ушло всего 55 часов ^[16].

Что касается алгоритмов BIKE ^[17], HQC ^[18], Classic McEliece ^[19] и SIKE ^[20], то для них еще не все потеряно. Их ожидает ^[21] еще один раунд оценки — разработчикам дали время на устранение недостатков, так как комиссия столкнулась ^[22] с багами, переполнением буфера и ошибками в работе кода, которые приводили к сбоям. Возможно, после доработки эти криптографические схемы тоже включат в список победителей.

Взгляд на перспективу

В NIST планируют подготовить черновики стандартов к 2023 году и финализировать их к 2024-му. Но бесшовная миграция не пройдет. Необходимо подготовить ИТ-инфраструктуру к работе с более длинными криптографическими ключами. Но несмотря на ограничения, квантово-устойчивые алгоритмы применяют на практике. Крупные облачные провайдеры внедряют их в сервисы управления ключами, включают в открытые криптографические библиотеки ^[23]. Российский стартап, занимающийся вопросами постквантовой криптографии, составил ^[24] собственный SDK с алгоритмами McEliece, SPHINCS+, FALCON и другими. Работу библиотеки проверили ^[25] на устройствах с процессорами Baikal.

Новые алгоритмы также становятся базой для аппаратных платформ. Немецкие инженеры разработали ^[26] чип для квантовой криптографии с Kyber. В микросхему заложены механизмы обнаружения бэкдоров — она анализирует оборудование в дата-центре и пресекает несанкционированную обработку данных.

Однако не все используют стандарты, предложенные NIST. Например, в OpenSSH еще несколько лет назад выбрали ^[27] NTRU-Prime, построенный на работе с NTRU-решетками ^[28]. Но теперь известно, что он менее надежен и уязвим к атакам с использованием подрешеток малого ранга. Возможно, разработчики утилиты для удаленного входа пересмотрят свой выбор — не исключено, что в пользу одного из победителей шестилетнего соревнования.

Хотя здесь стоит заметить, что некоторые участники ИТ-сообщества подходят к вопросам разработки алгоритмов постквантовой криптографии с долей скептицизма. Есть мнение ^[29], что нецелесообразно тратить ресурсы на решение проблемы, которая пока не проявилась. Может получиться так, что предлагаемые сейчас механизмы окажутся совершенно неэффективны в будущем.

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

Обвинения выдвигают и в адрес самой организации NIST. Специалистам до сих пор припоминают историю с бэкдором ^[30] в генераторе псевдослучайных чисел Dual_EC_DRBG. Комитет по стандартизации долгое время игнорировал ^[31] исследования, подтверждающие, что инструмент вырабатывает последовательности, статистически отличимые от истинно случайных.

В любом случае еще предстоит увидеть, получат ли новые криптографические стандарты массовое распространение. Продвижению могут поспособствовать рекомендации государственных регуляторов. В апреле группа американских сенаторов вынесла на обсуждение законопроект — Quantum Computing Cybersecurity Preparedness Act ^[32]. Согласно тексту документа, Национальный институт стандартов и технологий и Административно‑бюджетное управление США займутся ^[33] регулированием и внедрением постквантовой криптографии.

В то же время регуляторы проработают ^[34] дорожную карту по переходу федеральных агентств на квантово-устойчивую инфраструктуру. Аналогичный документ опубликовала ^[35] французская ANSSI. Можно ожидать, что подобных законопроектов и указов будет появляться все больше.

Больше постов про разработку и ИБ в облаке — в нашем блоге на Хабре ^[1]. Подписывайтесь, чтобы не пропустить новые публикации:

• Взлетит или нет — сможет ли новый ЯП Hare стать альтернативой Си ^[36]

• Взять и защитить SDLC — чем поможет облако ^[37]

• Резервное копирование: альтернативы для бизнеса ^[38]