Квантовые вычисления начали активно развиваться еще в 1970-х, но до конца прошлого века представляли лишь научный интерес. А в 1994 году математик Питер Шор представил алгоритм факторизации целых чисел и дискретного логарифмирования в конечной группе, и квантовые вычисления превратились в бомбу замедленного действия для решений по защите информации. В этом посте мы расскажем, как обстоят дела в этой сфере и как мы можем защитить блокчейн от этих угроз — с помощью постквантовых алгоритмов, реализованных QApp и интегрированных в нашу блокчейн-платформу «Конфидент».

Большинство существующих решений по информационной безопасности основаны на криптографии с открытым ключом — в том числе вся асимметричная криптография, о которой мы в ракурсе блокчейна рассказывали в одном из предыдущих постов. К ней относится большинство современных криптографических схем — RSA, DSA, EdDSA, ГОСТ Р 34.10-2012. Здесь для шифрования нам достаточно простых математических операций, а для дешифровки требуются колоссальные вычислительные ресурсы. Текущей архитектуры. Но квантовые компьютеры открывают более тревожные перспективы.

Взлом асимметричного шифрования

Алгоритм Шора позволяет квантовым компьютерам взламывать все перечисленные выше асимметричные криптографические схемы за чуть большее время, чем занимает их шифрование. При наличии квантового компьютера мощностью O(log N) кубитов с помощью алгоритма Шора факторизация (в нашем контексте — дешифровка) числа N займет полиномиальное время (O(log3N)).

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

Современные рекомендации по инфобезопасности предполагают использование в криптосистеме RSA чисел размером не менее 2048 бит (рекомендовано 3072). Прогресс классических компьютеров здесь, как видно из таблицы, пока затормозил на 829 битах. Квантовые компьютеры пока находятся в начале пути и демонстрируют впечатляющие темпы роста. Экстраполируя их, мы можем сделать вывод, что используемые сейчас криптосистемы будут взломаны квантовыми компьютерами уже в 2028–2033 гг.

Взлом симметричного шифрования

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

Алгоритм Гровера был представлен чуть позже алгоритма Шора, в 1996 году. По сути, он представляет собой алгоритм обращения функции методом перебора — алгоритм поиска в базе данных. Если мы возьмем блочный шифр с длиной ключа n бит как задачу обращения булевой функции, то алгоритм Гровера способен решить эту задачу за 2n/2 операций, тогда как классический подход потребует 2n операций. Аналогично и с нахождением прообраза хеш-функции. Несколько более совершенен здесь квантовый алгоритм BHT.

В итоге для сохранения заданного уровня стойкости блочного шифра против квантовых атак нам необходимо увеличить длину ключа в 2–3 раза. Современные подходы к обеспечению безопасности при работе в сети/передаче данных практически всегда сочетают симметричные и асимметричные алгоритмы — как, например, в протоколе TLS. Так что обе угрозы здесь следует рассматривать в совокупности.

Harvest now, decrypt later

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

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

Стандартизация алгоритмов

После публикации алгоритма Шора квантовая угроза обеспокоила многих. В 2017 году Национальный институт стандартов и технологий США (National Institute of Standards and Technology, NIST) организовал конкурс с целью стандартизации набора квантово-устойчивых криптографических схем инкапсуляции ключа и цифровой подписи.

Изначально на конкурс было представлено 69 алгоритмов от разработчиков из разных стран. Недавно завершился третий этап конкурса, по итогам которого к дальнейшей стандартизации было принято четыре алгоритма: Dilithium, FALCON и SPHINCS+ для цифровых подписей и KYBER для распределения ключа. Также был объявлен четвертый этап, по итогам которого этот список должен будет расшириться.

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

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

Комитет в рамках трех подгрупп ведет работу по трем направлениям постквантовых алгоритмов — основанных на хеш-функции, кодах, исправляющих ошибки, и теории целочисленных решеток. В рамках работы комитета в апреле 2023 года QApp представила схему подписи «Гиперикум». НПК «Криптонит» представила схему подписи «Шиповник». А БФУ им. И. Канта совместно с QApp — схему подписи «Крыжовник». В активной разработке сейчас находятся и новые механизмы выработки общего ключа. Процессы стандартизации постквантовых алгоритмов механизмов в России организованы не на конкурсной основе, как в США, но также имеют открытый характер, что позволяет привлечь ведущих экспертов отрасли.

Постквантовый блокчейн

Наш основной продукт, блокчейн-платформа «Конфидент», способен работать с криптографией на низком уровне. Для интеграции постквантовых алгоритмов у QApp есть набор библиотек и утилит PQLR SDK. Ядро PQLR SDK написано на C, вокруг него построена обвязка из интеграций. Поддерживается OpenSSL, BoringSSL и другие интеграции, необходимые для реализации протоколов верхнего уровня типа TLS и X.509.

Интеграция с «Конфидентом» заняла меньше месяца. Для нее была использована реализация Java JCP. Постквантовые алгоритмы были интегрированы во все связанные процессы. Для нод сети были сгенерированы криптографические ключи — ими ноды подписывают хэндшейки при обмене. Также ключи используются для подписания генезиса и транзакций.

Расскажем чуть подробней о составе PQLR SDK. На сегодняшний день PQLR SDK включает в себя восемь квантово-устойчивых алгоритмов. Реализация всех алгоритмов, входящих в состав PQLR SDK, является отечественной (реализовано QApp), а вот сами алгоритмы (спецификации) разработаны как отечественными, так и иностранными специалистами. Почти все алгоритмы победили или стали финалистами конкурса NIST:

• NewHope — протокол обмена ключами, основанный на обучении с ошибками в кольце (RLWE).

• Saber — алгоритм инкапсуляции ключа, основанный на модульном варианте задачи обучения с ошибками (Module-LWR).

• SPHINCS+ — криптографическая схема, основанная на криптографической стойкости хеш-функции. SPHINCS+ включает алгоритм формирования и проверки электронной цифровой подписи.

• McEliece — алгоритм инкапсуляции ключа, основанный на задаче декодирования случайного линейного кода.

• Falcon — алгоритм цифровой подписи, основанный на задаче поиска кратчайшего целочисленного решения на NTRU-решетках.

• Dilithium — как и Falcon, это алгоритм цифровой подписи, основанный на задаче поиска кратчайшего целочисленного решения на NTRU-решетках.

• «Гиперикум» — схема цифровой подписи, разработанная QApp и предложенная для стандартизации в России в рамках ТК26. Основана на мета-схеме SPHINCS+ и отечественной хеш-функции «Стрибог» (ГОСТ Р 34.11-2018).

• «Крыжовник» — алгоритм электронной подписи, основанный на алгебраических решетках. Схема построена на парадигме Фиата-Шамира, задаче обучения с округлением (LWR) и задаче нахождения короткого целочисленного решения (SIS) в модулях над кольцом целых чисел кругового расширения.

Производительность постквантового шифрования

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

Интересно, что при тестировании «Конфидента» с постквантовыми алгоритмами именно работа алгоритмов оказала сравнительно небольшой эффект на производительность. Больше задержек было связано с вводом-выводом. Что, в принципе, можно объяснить: ведь постквантовые алгоритмы обрабытывают и все сообщения между нодами, начиная с генезиса, и хендшейки, и исполнение смарт-контрактов.

Каких-либо ошибок при тестировании платформы «Конфидент» на постквантовых алгоритмах выявлено не было. Транзакции выполнялись, смарт-контракты исполнялись, блоки добавлялись, и высота сети увеличивалась.

По опыту QApp, в других интеграциях — например, в системах обработки банковских транзакций — падение производительности  из-за постквантовых алгоритмов либо незаметно, либо составляет порядка 30-40%, в зависимости от конкретной подсистемы. Бенчмарки PQLR SDK в разных интеграциях можно посмотреть на сайте QApp.

Итоги и планы развития

«Конфидент» стал первой блокчейн-платформой (как минимум в России) с квантово-устойчивым шифрованием, и в дальнейшем мы продолжим оптимизацию и обкатку этой версии. Наши коллеги из QApp также ведут активную работу по стандартизации криптографических алгоритмов в рамках ТК26.

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