В начале июля институт NIST одобрил четыре защищенных алгоритма. В блоге T1 Cloud мы рассказываем про облачные технологии, разработку и информационную безопасность. Поэтому сегодня мы решили подробнее поговорить о новых алгоритмах — обсудить принципы работы, мнение сообщества и перспективы внедрения таких систем на практике.
Заблаговременная подготовка
Как только квантовые компьютеры превзойдут «классические» в решении ряда сложных математических задач, под угрозой окажутся асимметричные криптографические схемы вроде RSA и ECDSA, так как их криптостойкость основана на исключительной трудности разложения больших чисел на множители. Иными словами, определить закрытый ключ на основании открытого невероятно сложно. Однако пока квантовое превосходство остается далекой перспективой.
В этом направлении постепенно двигаются частные компании и исследовательские институты. В начале года группа китайских инженеров представила архитектуру квантового компьютера из 10 тыс. кубитов, которая позволит взламывать ключи шифрования. В то же время самый мощный квантовый процессор (разработка также принадлежит китайским инженерам) на сегодняшний день имеет всего 66 кубитов.
Таким образом, для достижения квантового превосходства необходимы более эффективные аппаратные решения и алгоритмы, подчеркивающие сильные стороны квантовых систем — на это уйдет порядка 10–30 лет. Но криптографы готовятся к будущему уже сейчас. Еще в 2016 году американский институт NIST объявил конкурс по разработке алгоритмов шифрования для постквантовой эпохи. В начале июля многолетнее соревнование подошло к концу, и организаторы выделили наиболее многообещающие решения.
Четыре из семидесяти
Исследователи со всего мира предложили более семидесяти криптографических механизмов. Их изучали независимые эксперты на предмет уязвимостей. За шесть лет они сократили общий список до четырех алгоритмов. Это — универсальный Kyber, а также Dilithium, FALCON, SPHINCS+ для работы с цифровыми подписями.
Криптографическую основу первых трех составляют задачи теории решёток — например, NP-задачи поиска кратчайшего вектора или задача обучения с ошибками (LWE). Считается, что их одинаково плохо решают как классические компьютеры, так и квантовые. Для сокрытия информации используют многомерные сетки точек, размерность которых позволяет корректировать сложность вычислений. Что касается SPHINCS+, то эта криптографическая схема использует хеш-функции и является естественным развитием SPHINCS. Однако в новой версии разработчики сократили размер подписи и увеличили надежность алгоритма.
Если говорить об «аутсайдерах», то одним из последних выбыл Rainbow. Он основан на криптографической схеме под названием Unbalanced Oil and Vinegar (OUV) — «несбалансированная схема масла и уксуса». Её надежность обеспечивает сложная система квадратичных уравнений, а также односторонние функции с потайным входом (trapdoor). Алгоритм не стал финалистом, поскольку ИБ-специалистам удалось реализовать серию атак, понижающих его защищенность — в итоге на взлом подписи ушло всего 55 часов.
Что касается алгоритмов BIKE, HQC, Classic McEliece и SIKE, то для них еще не все потеряно. Их ожидает еще один раунд оценки — разработчикам дали время на устранение недостатков, так как комиссия столкнулась с багами, переполнением буфера и ошибками в работе кода, которые приводили к сбоям. Возможно, после доработки эти криптографические схемы тоже включат в список победителей.
Взгляд на перспективу
В NIST планируют подготовить черновики стандартов к 2023 году и финализировать их к 2024-му. Но бесшовная миграция не пройдет. Необходимо подготовить ИТ-инфраструктуру к работе с более длинными криптографическими ключами. Но несмотря на ограничения, квантово-устойчивые алгоритмы применяют на практике. Крупные облачные провайдеры внедряют их в сервисы управления ключами, включают в открытые криптографические библиотеки. Российский стартап, занимающийся вопросами постквантовой криптографии, составил собственный SDK с алгоритмами McEliece, SPHINCS+, FALCON и другими. Работу библиотеки проверили на устройствах с процессорами Baikal.
Новые алгоритмы также становятся базой для аппаратных платформ. Немецкие инженеры разработали чип для квантовой криптографии с Kyber. В микросхему заложены механизмы обнаружения бэкдоров — она анализирует оборудование в дата-центре и пресекает несанкционированную обработку данных.
Однако не все используют стандарты, предложенные NIST. Например, в OpenSSH еще несколько лет назад выбрали NTRU-Prime, построенный на работе с NTRU-решетками. Но теперь известно, что он менее надежен и уязвим к атакам с использованием подрешеток малого ранга. Возможно, разработчики утилиты для удаленного входа пересмотрят свой выбор — не исключено, что в пользу одного из победителей шестилетнего соревнования.
Хотя здесь стоит заметить, что некоторые участники ИТ-сообщества подходят к вопросам разработки алгоритмов постквантовой криптографии с долей скептицизма. Есть мнение, что нецелесообразно тратить ресурсы на решение проблемы, которая пока не проявилась. Может получиться так, что предлагаемые сейчас механизмы окажутся совершенно неэффективны в будущем.
С другой стороны, к массовому распространению квантовых вычислений все же стоит подготовиться, чтобы уязвимость текущих криптографических схем не стала неожиданностью. В то же время новые устойчивые алгоритмы можно применять уже сегодня — многие из них работают быстрее привычного RSA.
Обвинения выдвигают и в адрес самой организации NIST. Специалистам до сих пор припоминают историю с бэкдором в генераторе псевдослучайных чисел Dual_EC_DRBG. Комитет по стандартизации долгое время игнорировал исследования, подтверждающие, что инструмент вырабатывает последовательности, статистически отличимые от истинно случайных.
В любом случае еще предстоит увидеть, получат ли новые криптографические стандарты массовое распространение. Продвижению могут поспособствовать рекомендации государственных регуляторов. В апреле группа американских сенаторов вынесла на обсуждение законопроект — Quantum Computing Cybersecurity Preparedness Act. Согласно тексту документа, Национальный институт стандартов и технологий и Административно‑бюджетное управление США займутся регулированием и внедрением постквантовой криптографии.
В то же время регуляторы проработают дорожную карту по переходу федеральных агентств на квантово-устойчивую инфраструктуру. Аналогичный документ опубликовала французская ANSSI. Можно ожидать, что подобных законопроектов и указов будет появляться все больше.
Больше постов про разработку и ИБ в облаке — в нашем блоге на Хабре. Подписывайтесь, чтобы не пропустить новые публикации:
speshuric
Насколько я в курсе, RSA уязвим к факторизации (разложению больших чисел на множители), а ECDSA всё-таки к задаче дискретного логарифмирования в поле эллиптических кривых, причём важно отметить, что это не простое дискретное логарифмирование в поле вычетов.
Zhuravlev-A-E
speshuric
Да с этим-то я не спорю, может и поломается. Я скорее к тому, что на текущий момент дискретное логарифмирование в поле эллиптических кривых не сведено вроде как к факторизации целых.