Постквантовый переход: DH, RSA, ECDSA ->?

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

Google, Amazon, Microsoft и другие крупные игроки активно вкладываются в исследования и пилотные проекты в этой области уже сейчас. Например, тот же Cloudflare уже пилотировал постквантовую криптографию для TLS 1.3 в некоторых зонах. Хотя бы просто потому, что дамп зашифрованного трафика, где для обмена симметричным ключом использовался алгоритм RSA, будет оставаться зашифрованным ровно до того момента, когда у атакующего появится возможность запустить алгоритм Шора на квантовом компьютере с достаточным количеством кубитов. Поэтому, несмотря на то, что подобных квантовых вычислительных комплексов ещё не существует, квантово-устойчивые алгоритмы в критических областях нужно применять уже сейчас. Скорее всего, одними из первых практические атаки смогут осуществить спецслужбы крупных стран. В разработку квантовых компьютеров вкладываются не менее активно.

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

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

Есть ли перспективы у квантовых компьютеров

Ключевое отличие квантовых компьютеров в том, что они оперируют не привычными битами, где каждая ячейка может принимать одно из двух значений, а кубитами, которые находятся в состоянии суперпозиции, принимая одновременно значения 0 и 1. Физически кубит может быть представлен ионами, фотонами или другими частицами, которые находятся в состоянии когерентного взаимодействия с другими кубитами.

IBM Q System One — один из первых коммерческих квантовых компьютеров

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

Прогресс в этой отрасли значительно ускорился в последние несколько лет. Вслед за Google сразу несколько исследовательских групп заявило, что они смогли достичь квантового превосходства, то есть получили квантовый вычислитель, который может выполнить в разумные сроки алгоритм, невыполнимый в разумные сроки классической системой. Так, в декабре 2020 года группа из китайского университета USTC опубликовала работу о создании системы с 76 запутанными фотонами на суперкомпьютере Jiuzhang. В октябре 2021-го та же группа опубликовала работу уже по двум суперкомпьютерам — Jiuzhang 2.0 и Zuchongzhi, где была продемонстрирована система, состоящая из 113 фотонных кубитов. В июне 2022 года канадская Xanadu отчиталась об эксперименте, где было зафиксировано уже среднее значение в 125 когерентных фотонов с максимумом до 219 частиц. А 9 ноября IBM анонсировала выход суперкомпьютера Osprey уже на 433 кубита.

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

Например, обучение классических нейросетей больших размеров — крайне дорогостоящая операция, требующая большого числа GPU или специализированных TPU, как это делает, например, Google. Основная проблема нейросетей в том, что сложность их обучения тоже быстро растёт по мере увеличения числа параметров. Так, например, одна из самых продвинутых языковых моделей в мире — GPT-3 — обучалась уже с использованием 175 миллиардов параметров против 1,5 миллиарда у GPT-2. Рано или поздно комбинаторная сложность таких систем сделает невозможным или крайне дорогостоящим дальнейший прогресс при использовании традиционных вычислительных архитектур. В случае квантовых процессоров эффективность работы с матрицами будет экспоненциально расти по мере увеличения числа когерентных кубитов. Квантовые компьютеры в теории смогут эффективно обрабатывать подобные задачи за очень короткое время.

Не все, впрочем, согласны с тем, что эта технология получит реальное практическое применение в ближайшее время. Так, исследователь Санкар Дас Сарма из Университета Мэриленда в своей публикации высказывает гипотезу о том, что реальное применение квантовых компьютеров для взлома того же RSA может оказаться намного сложнее, чем кажется. Проблема в том, что мало просто получить кубит. 10 отдельных групп по 10 кубитов — это совсем не то же самое, что 100 связанных кубитов, которые работают как единая система. Чем больше элементов, тем больше вероятность, что система потеряет когерентность, и вместо результатов вы получите шум.
Для работающей системы, по его мнению, потребуются миллионы кубитов. Большая их часть будет занята коррекциями ошибок и вспомогательными задачами, а непосредственно в вычислениях будут задействованы только десятки тысяч из них.

Алгоритм Шора и уязвимые алгоритмы

Авторское изображение команды QApp

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

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

Асимметричная криптография используется повсеместно. Например:

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

У этих алгоритмов есть один недостаток — они медленные, и их аппаратное ускорение сложнее реализовать. Поэтому шифрование всего трафика между двумя узлами с использованием только асимметричной криптографии возможно, но бессмысленно из-за низкой производительности и большого оверхеда. Классический подход подразумевает использование «дорогих» асимметричных схем только для проверки подлинности сертификата и согласования общего сессионного ключа. А уже основной объём данных шифруется по симметричной криптосхеме с использованием быстрого AES и CHACHA20. Современные наборы шифрования подразумевают, что в каждой сессии будет новый ключ, что обеспечивает perfect forward secrecy — невозможность вскрыть предыдущие записанные сессии, если когда-то в будущем произойдёт утечка ключа.

Всё это здорово и красиво работает ровно до тех пор, пока не получит практического применения алгоритм, предложенный в 1994 году Питером Шором, учёным и основоположником теории квантовых вычислений. Он состоит из двух ключевых блоков: один выполняется на традиционном железе, а второй реализует квантовые вычисления. Этот алгоритм позволяет факторизовать число N за полиномиальное время (O(log3N)), используя O(log N) кубитов.

На практике открытие Шором алгоритма факторизации больших чисел или целых чисел в простые числа может означать, что при наличии квантового компьютера приблизительно из 3 000 логических кубитов криптографическая система RSA с ключом длиной 2 048 битов может быть эффективно взломана за время, лишь ненамного превосходящее требующееся для зашифрования. Так, чисто академические фундаментальные исследования поставили под угрозу ключевые элементы безопасности для множества систем, включая финансовые.

Таким образом, в горизонте нескольких лет полностью небезопасными становятся многие традиционные алгоритмы криптографии:

1. Распределение ключей (ECDH, DH).
2. Асимметричное шифрование (RSA).
3. Электронная подпись (ECDSA, DSA, ГОСТ Р 34.10-2012).

На стойкость симметричных шифров (AES, Кузнечик и других) и хэш-функций (SHA, Стрибог и других) алгоритм Шора не оказывает влияния, поскольку для их анализа применяются другие, не столь эффективные алгоритмы (метод Гровера, Саймона, BHT и другие), для успешной защиты от которых достаточно увеличить размер параметров алгоритма в два-три раза.

Отложенные атаки

Несмотря на то, что симметричные алгоритмы не являются уязвимыми для атак с применением квантовых компьютеров сами по себе, проблемой будет то, что можно будет извлечь сессионный ключ, зашифрованный уязвимой асимметричной функцией. После этого всю ранее записанную пользовательскую сессию можно будет расшифровать. McKinsey в своём докладе в качестве основной стратегии для критичных систем прогнозирует внедрение постквантовой криптографии уже в ближайшие несколько лет. Затем, после доработки и оптимизации, нужно будет мигрировать на более зрелые решения примерно к 2030 году. В краткосрочном периоде RSA-1024 и RSA-2048 должны давать приемлемый уровень защиты на ближайшие один–три года.

Для противодействия атаке «сохрани сейчас — дешифруй потом» целесообразно применять постквантовую криптографию уже сейчас. Подтверждая эту позицию, в сентябре 2022 года американское Агентство национальной безопасности (NSA) выпустило новые рекомендации по применению постквантовой криптографии в области, связанной с циркулированием информации в государственных органах США и их контрагентах (т. н. шифрнабор АНБ), в которые включены некоторые постквантовые алгоритмы.

Виды постквантовых алгоритмов

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

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

Уже шесть лет NIST (National Institute of Standards and Technology, ведущая организация в США, аналог нашего Росстандарта) проводит конкурс на лучшие варианты реализации, где, помимо криптостойкости, учитывались другие факторы, такие, как минимальный размер ключа и производительность. Рассмотрим основные группы алгоритмов в зависимости от принципов реализации.

На основе многочленов от многих переменных

Стойкость таких квантово-устойчивых криптографических алгоритмов основывается на предположении о вычислительной сложности задачи решения системы нелинейных уравнений от многих переменных над конечным полем. На этой задаче основаны алгоритмы цифровой подписи Rainbow (ныне исключённый финалист) и GeMSS (альтернативный финалист) конкурса NIST. Такие алгоритмы отличаются относительно высокой эффективностью и небольшой длиной подписи при большой длине ключей. В то же время секретные преобразования этого класса алгоритмов имеют особую внутреннюю структуру, которая упрощает их взлом. Например, забавный случай произошёл с криптовалютой ABCMint, создатели которой полагались на стойкость финалиста конкурса NIST — алгоритм Rainbow. Летом 2022 года была продемонстрирована атака, полностью взламывающая этот алгоритм, но разработчики ABCMint яростно настаивали на защищённости своих вкладов до тех пор, пока не был раскрыт секретный ключ самого толстого кошелька этой системы. После этого в публичном поле о ABCMint ничего не слышно.

На основе кодов, исправляющих ошибки

Стойкость таких алгоритмов основывается на предположении о вычислительной сложности задачи декодирования случайного линейного кода. На этой задаче основаны финалист конкурса NIST — алгоритм Classic McEliece — и альтернативные финалисты: BIKE и HQC. Такие алгоритмы отличаются относительно высокой эффективностью, но обладают ключами большой длины. Кроме того, они весьма консервативны в плане безопасности. Усилия криптоаналитиков с 1978 года не смогли значительно уменьшить количества операций, требуемых для взлома криптографических систем на основе кодов, исправляющих ошибки, при условии корректного выбора их параметров.

На основе теории решёток

Стойкость таких алгоритмов основывается на предположении о сложности некоторых математических задач, связанных с теорией целочисленных решёток. На таких задачах основано большинство финалистов конкурса NIST: это алгоритмы CRYSTALS-KYBER, NTRU, SABER, CRYSTALS-DILITHIUM, FALCON и альтернативные финалисты FrodoKEM, NTRUprime, а также подавляющее количество участников конкурса CACR. Такие алгоритмы отличаются относительно высокой эффективностью и обладают ключами умеренной длины. Но некоторые из схем шифрования и выработки общего ключа по построению обладают возможностью ошибки ― некорректного декодирования.

На хэш-функциях

Стойкость таких алгоритмов основывается на свойствах криптографических хэш-функций, например, стойкости к поиску прообраза, коллизий, второго прообраза. На основе криптографических хэш-функций построен алгоритм электронной подписи SPHINCS+ ― альтернативный участник третьего раунда конкурса NIST. В рамках стандартизации постквантовых алгоритмов в России также ведётся разработка электронной подписи на хэш-функциях. Особенности таких алгоритмов: короткие открытые и секретные ключи, а также консервативность с точки зрения безопасности. Хэш-функции — это давно известный и хорошо исследованный инструмент построения криптографических схем.

На изогениях суперсингулярных эллиптических кривых

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

Итоги конкурса NIST

По итогам конкурса, объявленным 5 июля 2022 года, были выбраны следующие реализации.
Для общих задач шифрования, например, используемого при доступе к веб-сайтам, NIST выбрал алгоритм CRYSTALS-Kyber. Среди его преимуществ — сравнительно небольшие ключи шифрования, которыми могут легко обмениваться две стороны, а также скорость работы.

Для цифровых подписей NIST выбрал три алгоритма:

• CRYSTALS-Dilithium;
• FALCON;
• SPHINCS+.

Рецензенты отметили высокую эффективность первых двух, и NIST рекомендует CRYSTALS-Dilithium в качестве основного алгоритма и FALCON — для приложений, которым требуются меньшие сигнатуры, чем может обеспечить Dilithium. Третий, SPHINCS+, несколько медленнее двух других, но он ценен в качестве резервного варианта по одной главной причине — он основан на ином математическом подходе, чем все три других варианта NIST.

Команда QApp тоже принимала участие в конкурсе NIST. QApp — единственная в России и одна из первых команд в мире, сумевшая выявить неточности в доказательстве безопасности одного из перспективных квантово-устойчивых алгоритмов. Естественно, они сразу сообщили в NIST об обнаружении проблем с алгоритмом подписи «SPHINCS+». Ошибку устранили вместе с авторами алгоритма и направили статью с обновлённым доказательством в один из ведущих международных журналов.

Дополнительно NIST объявил четвёртый раунд по расширению набора алгоритмов защищённой передачи ключа. В качестве кандидатов рассматриваются алгоритмы Classic McEliece, BIKE и HQC.

Разработка стандартов в России

В России за этот вопрос взялись в 2019 году. Руководит деятельностью Технический комитет по стандартизации «Криптографическая защита информации» Росстандарта (ТК 26), куда входят представители государственных и коммерческих организаций под общим руководством ФСБ.

ТК 26 разрабатывает нормативные документы в части криптографических механизмов, используемых в России, вплоть до уровня государственных стандартов, а также проводит исследования и экспертизу криптографических механизмов.

Внутри ТК 26 из экспертов компаний-лидеров российского рынка информационной безопасности формируются рабочие группы для решения конкретных задач. Так, рабочая группа «Постквантовые криптографические механизмы» ТК 26, созданная в 2019 году, разрабатывает перспективные квантово-устойчивые криптографические алгоритмы, призванные в будущем дополнить комплекс стандартов серии ГОСТ Р 34.

Существуют следующие подгруппы по направлениям:

1. Подгруппа по постквантовым криптографическим механизмам, построенным на основе хэш-функций. Разрабатывается проект схемы цифровой подписи «Гиперикум».
2. Подгруппа по постквантовым криптографическим механизмам, построенным на основе кодов, исправляющих ошибки. Разрабатывается проект схемы цифровой подписи «Шиповник».
3. Подгруппа по постквантовым криптографическим механизмам, построенным на основе теории целочисленных решёток. Разрабатывается проект схемы цифровой подписи «Крыжовник».

Сотрудники QApp вместе с другими разработчиками из профильных компаний и крупных университетов принимают активное участие в трёх подгруппах из четырёх по постквантовым криптографическим механизмам технического комитета ТК 26.

Что дальше?

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

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

• Государственная и иная охраняемая законом тайна.
• Финансовые данные.
• Персональные данные.
• Медицинские данные.
• Промышленные ноу-хау.

Они чаще подвержены атаке «сохрани сейчас — дешифруй потом». Для других областей этот класс атак менее критичен, так как через условные 10 лет информация потеряет свою актуальность. Но, скорее всего, в течение ближайших пяти–восьми лет мы увидим переход на квантово-устойчивые решения по всему миру для защиты от новых угроз. При этом для обычных пользователей ничего не изменится, всё будет работать так же быстро, как и раньше. А вот тем, кто отвечает за инфраструктуру, стоит внимательно следить за изменениями в этой области. Множество необновлённых систем могут стать уязвимыми уже в ближайшие несколько лет.

Спасибо за помощь при подготовке поста руководителю QApp Антону Гугле.