Какими должны быть стандарты постквантовой криптографии: подход NIST

В обозримом будущем могут быть созданы квантовые компьютеры. Активно ведутся работы по созданию квантово-устойчивых (постквантовых) криптографических алгоритмов. У государственного института стандартов и технологий США (NIST) уже есть проекты нормативных требований по этой части. Что в них содержится?

 

 

 

 

 

1. Введение
2. Состояние работ в области квантово-устойчивой криптографии
3. Категории криптостойкости постквантовых систем
4. Обзор проектов стандартов NIST
   
   1. 4.1. Стандарт для общих целей шифрования FIPS 203
   2. 4.2. Стандарт для защиты цифровых подписей FIPS 204
   3. 4.3. Стандарт для защиты цифровых подписей FIPS 205
5. Выводы

Введение

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

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

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

Целью квантово-устойчивой криптографии (она же — постквантовая криптография) является разработка таких криптографических систем, которые были бы защищены от атак со стороны и квантовых компьютеров, и классических.

Работы в области квантово-устойчивой криптографии ведутся во многих исследовательских центрах и крупных ИТ-компаниях. В частности, Microsoft предложила несколько алгоритмов, Apple показала протокол для защиты переписки в iMessage, NIST разрабатывает проекты стандартов, с которыми уже можно ознакомиться. В России также ведутся исследования в этой области, подготавливаются проекты стандартов, которые мы планируем рассмотреть в последующих публикациях.

Состояние работ в области квантово-устойчивой криптографии

Возможности создания крупномасштабных квантовых компьютеров начали изучаться после открытия Питером Шором в 1994 году квантового алгоритма с полиномиальным временем для факторизации целых чисел. В то время было неясно, станут ли когда-нибудь квантовые вычисления реально используемой технологией. Эксперты указывали, что квантовые состояния подвержены накоплению ошибок, что препятствует крупномасштабным вычислениям. Ситуация изменилась в конце 1990-х годов с развитием квантовых кодов, исправляющих ошибки.

Теоретические исследования показали, что если частоту ошибок на логическую операцию («вентиль») в квантовом компьютере снизить ниже фиксированного порога, то за счёт периодической коррекции могут выполняться сколь угодно длинные квантовые вычисления.

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

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

Исследователи, работающие над созданием квантового компьютера, предсказывают, что в течение следующих десяти лет (или около того) будут построены достаточно большие квантовые компьютеры, способные взломать практически все схемы с открытым ключом, используемые в настоящее время.

Оптимисты считают, что квантовый компьютер, способный взломать 2000-битный RSA за считаные часы, может быть построен к 2030 году.

В России утверждена дорожная карта развития квантовых вычислений, ведётся разработка квантовых компьютеров, построены экспериментальные образцы на несколько десятков кубитов.

Постквантовая криптография в мире и в России интенсивно развивается. Новые криптографические алгоритмы основываются на тех классах математических задач, которые потенциально вычислительно сложны для квантовых компьютеров. Это алгоритмы:

• на основе кодов, исправляющих ошибки;
• на основе алгебраических решёток;
• на основе хеш-функций.

В мире предложены десятки алгоритмов этих классов, ведётся их исследование, некоторые имеют статус кандидатов для принятия в качестве национальных стандартов.

В России исследования по постквантовому шифрованию ведёт ряд компаний с экспертизой в области криптографии и квантовых технологий.

Компания «Криптонит» представила на «РусКрипто 2024» криптографический механизм «Кодиеум» в качестве потенциальной замены протоколу Диффи — Хеллмана.

Постквантовая схема электронной подписи «Шиповник» является кандидатом на новый стандарт взамен алгоритма ГОСТ 3410-2018.

«ЭЛВИС-ПЛЮС» анонсировала возможность использования постквантовой криптографии в своём продукте «ЗАСТАВА» за счёт использования композитных протоколов.

Государственный институт стандартов и технологий США (NIST) опубликовал проекты стандартов нескольких квантово-устойчивых криптографических алгоритмов. Усилия NIST по их разработке начались в 2016 году, когда институт обратился к мировым экспертам по криптографии с просьбой предоставить возможные алгоритмы для проекта по стандартизации постквантового шифрования. Эксперты из десятков стран представили 69 подходящих алгоритмов. К настоящему времени отобраны четыре алгоритма, три из них опубликованы и имеют статус «Draft», четвёртый будет опубликован в 2024 году.

Стандарты определяют схемы создания ключей и цифровой подписи, которые предназначены для противодействия будущим атакам со стороны квантовых компьютеров. FIPS 203 описывает набор алгоритмов для приложений, которым требуется секретный криптографический ключ, используемый двумя сторонами, а FIPS 204 и FIPS 205 — алгоритмы цифровых подписей, созданных с использованием хеш-функций. Их стойкость, даже против квантовых атак, хорошо исследована.

Категории криптостойкости постквантовых систем

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

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

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

Цели введения такой классификации:

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

В качестве криптографических примитивов использовались известные алгоритмы с симметричной криптографией и некоторые из опубликованных постквантовых алгоритмов. Соответственно, в качестве критерия было установлено: любая успешная атака должна требовать таких вычислительных ресурсов, которые сопоставимы с необходимыми, например, для подбора ключа в блочном шифре со 128-битным ключом (таком как AES-128) или превышают их.

 

Таблица 1. Категории криптостойкости NIST

 

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

• количество классических элементарных операций,
• стоимость доступа к большим объёмам памяти,
• размер квантовой схемы,
• максимальная глубина (MAXDEPTH).

Показатель MAXDEPTH предложен NIST. Предполагается, что атаки компьютера ограничиваются временем выполнения и его архитектурой (количеством «вентилей» или элементарных логических операций). Значение показателя варьируется от 2⁴⁰ до 2⁶⁴. Первое значение соответствует современной архитектуре квантовых компьютеров при условии работы в течение года, второе — современным компьютерам классической архитектуры при работе в течение 10 лет.

Максимальное возможное значение показателя — 2⁹⁶ — соответствует гипотетическому квантовому компьютеру с кубитами атомного масштаба, работающему в течение 1000 лет.

Сложность атак можно измерить относительно гипотетического компьютера, содержащего определённое количество логических элементов и решающего задачу за один такт. NIST даёт следующие оценки количества вентилей классических и квантовых компьютеров для выполнения успешной атаки (табл. 2).

 

Таблица 2. Оценка криптостойкости алгоритмов

 

Таким образом, при данном методе оценки исследованные алгоритмы показывают высокую квантовую безопасность.

Обзор проектов стандартов NIST

Стандарт для общих целей шифрования FIPS 203

Полное его название — стандарт механизма инкапсуляции ключей на основе модульной решётки (ML-KEM). Он определяет алгоритмы получения криптографических ключей для шифрования и аутентификации при взаимодействии приложений по открытому каналу. Общий секретный ключ вычисляется совместно обеими сторонами. Может использоваться в криптосистемах с симметричным ключом.

Особенности алгоритма

KEM включает в себя три различных типа ключей: ключи инкапсуляции, ключи декапсуляции и общие секретные ключи. ML-KEM построен на основе компонентной схемы шифрования с открытым ключом K-PKE, а K-PKE имеет два дополнительных типа ключей: ключи шифрования и ключи дешифрования.

В стандарте описаны три алгоритма:

• алгоритм генерации ключа (KeyGen);
• алгоритм инкапсуляции (Encaps);
• алгоритм декапсуляции (Decaps).

Схема механизма инкапсуляции ключей:

• Сторона А генерирует ключи декапсуляции и инкапсуляции. Ключ декапсуляции остаётся конфиденциальным, ключ инкапсуляции пересылается стороне Б.
• Сторона Б использует полученный ключ инкапсуляции для генерации копии общего секретного ключа вместе с соответствующим зашифрованным сообщением. Это сообщение передаётся стороне А.
• Сторона А использует это сообщение и свой ключ декапсуляции для вычисления ещё одной копии общего секретного ключа.

Безопасность механизма обеспечивается вычислительной сложностью решения определённого класса систем линейных уравнений с шумом — в частности, т. н. проблемы модульного обучения с ошибками (MLWE). В настоящее время считается, что этот метод создания общего секретного ключа надёжен даже при использовании квантового компьютера для атак против него.

В стандарте определены три набора параметров для ML-KEM: ML-KEM-512, ML-KEM-768 и ML-KEM-1024 (в порядке повышения уровня безопасности и снижения производительности).

Стандарт для защиты цифровых подписей FIPS 204

Полное название — стандарт цифровой подписи на основе модульной решётки. В стандарте FIPS 204 описан алгоритм создания и проверки цифровых подписей ML-DSA. При генерации подписи используется закрытый ключ, а для её проверки — соответствующий ему открытый.

Цифровую подпись можно использовать для обнаружения несанкционированных изменений данных и для удостоверения личности подписавшего. Кроме того, созданная по этой схеме подпись может использоваться в качестве доказательства того, что её действительно создал именно заявленный подписавший (т. н. неотказуемость).

Особенности алгоритма

Алгоритм цифровой подписи ML-DSA основан на задачах теории решёток.

Безопасность схем цифровой подписи на основе решётки связана с двумя центральными проблемами: обучения с ошибками (LWE) и короткого целочисленного решения (SIS).

Модульный алгоритм позволяет легко изменять параметры и реализовывать криптосистемы с разными размерами ключей, трудоёмкостями расчётов и уровнями безопасности.

Выделяются алгоритмы для генерации ключей (ML-DSA.KeyGen), цифровой подписи (ML-DSA.Sign) и верификации (ML-DSA.Verify).

 

Таблица 3. Размер (в байтах) ключей и подписи для разных вариантов алгоритма ML-DSA

 

Стандарт для защиты цифровых подписей FIPS 205

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

Особенности алгоритма

Представленный в стандарте алгоритм SLH-DSA основан на криптографической схеме SPHINCS+.

Концептуально пара ключей SLH-DSA состоит из очень большого набора пар ключей, которые генерируются псевдослучайным образом.

Схема подписи построена с использованием в качестве компонентов других схем подписи на основе хеша:

• схемы одноразовой подписи,
• схемы с несколькими временными подписями,
• леса случайных подмножеств.

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

В стандарте описаны алгоритмы генерации ключей, подписывания и проверки подписи. Размеры открытого ключа и подписи зависят от 12 параметров, которые можно варьировать. Предложены 6 наборов параметров, которым будут соответствовать разные категории безопасности.

 

Таблица 4. Характеристики алгоритмов SLH-DSA-SHA2

 

Выводы

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

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

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

Одна из проблем, которые придётся преодолеть, состоит в том, что ключи у большинства квантово-устойчивых алгоритмов длиннее, чем у нынешних. Это может потребовать изменения различных интернет-протоколов, таких как TLS или IKE.

Важной задачей будет также обеспечение возможности взаимодействия между пользователями во время перехода к квантово-устойчивым алгоритмам.