Постквантовая криптография и практика TLS в браузерах
Аннотация:
Постквантовая криптография является популярным технологическим новшеством. Не так давно [1] о поддержке постквантовой схемы обмена ключами в приложении iMessage заявила компания Apple. Компания Google добавила поддержку аналогичной постквантовой криптосистемы в реализацию TLS браузера Chrome/Chromium [2]. В описании новшества Apple сказано, что постквантовая система должна быть внедрена заблаговременно, чтобы в случае появления квантового компьютера защитить ранее записанный трафик. Такая же причина названа основной и для появления постквантовой криптосистемы в браузере Google. Предполагается, что ранее записанный трафик, защищённый новой криптосистемой, квантовый компьютер раскрыть не сможет, в отличие от используемых сейчас криптосистем – которые, возможно, получится взломать. Такая защита не распространяется на трафик, записанный до добавления новых, стойких криптосистем, однако и подходящего квантового компьютера до сих пор не создано.
Ключевые слова:
«квантовый компьютер», «криптография», «постквантовая криптография», «TLS», «веб-браузер»
Точное значение термина «квантовый компьютер» зависит от той научно-технической области, в которой этот компьютер планируется строить и применять. Можно предложить и универсальное «вычислительное» определение: квантовый компьютер – это такой компьютер, на котором возможно эффективное исполнение квантовых алгоритмов. Ростом своей широкой популярности квантовые компьютеры как социальный феномен всецело обязаны одному вполне конкретному математическому алгоритму – предложенному в 1994 году алгоритму Шора, позволяющему ускорить решение важных для криптографии задач, в частности, задач факторизации целых чисел и дискретного логарифмирования.
Постквантовая криптография обязана своим возникновением тому, что ряд задач, традиционно считающихся вычислительно сложными, гораздо проще решить, если у вас есть квантовый компьютер. Примером является задача факторизации, с которой связана, например, оценка стойкости распространённой криптосистемы RSA. Несмотря на формальную ширину определения, на практике «постквантовыми» можно смело считать такие криптосистемы, для которых не известно методов атаки конкретно с использованием алгоритма Шора – самого знаменитого из квантовых алгоритмов и одного из самых часто упоминаемых в современной популярной литературе алгоритмов вообще (но, конечно, после алгоритма Евклида, с которым механизм применения алгоритма Шора связан математически).
Вычисление невычислимого
Сама концепция квантовых вычислений возникла значительно раньше алгоритма Шора и без всякой привязки к криптологии и взлому криптосистем. Идею использования мощности пространства квантовых состояний для аналоговых вычислений в своей печатной работе одним из первых высказал советский математик Юрий Иванович Манин – речь идет о книге «Вычислимое и невычислимое», 1980 год, «Советское радио». Но представления о «квантовой обработке информации» циркулировали среди физиков и математиков раньше, примерно с конца 60-х годов прошлого века [3]. Реализация квантовых вычислений – это обобщение понятия вычислительной сложности, приводящее к попыткам придумать способ, который позволил бы «вычислить невычислимое» без ограничений классической физики: затрат энергии и пространства.
Интерпретация фундаментальных представлений о возможности вычислить ту или иную функцию имеет большое количество чисто философских воплощений. Современное, популярное состояние данной области в применении к криптосистемам является прикладным преломлением: узкие задачи, стоящие за квантовым криптоанализом асимметричных криптосистем, вполне себе «вычислимы» и на классическом цифровом компьютере, вот только времени на поиск решения «в лоб» потребуется экспоненциально больше. Гипотетический квантовый компьютер мог бы решить эти задачи «в лоб», то есть методом полного перебора, но за обозримое время: алгоритм Шора описывает способ сворачивания «экспоненты сложности» в пространстве состояний квантовых частиц, который позволяет сразу получить полезный результат.
Такая ситуация даёт возможность находить эффективные вероятностные алгоритмы, исполняемые классическим компьютером, для многих задач. Эти алгоритмы, разумеется, эффективно решают только частные случаи сложных задач в некотором приближении к оптимальному решению, но на практике этого достаточно. Так, в случае не абсолютно стойких криптосистем ничто не запрещает успешно угадать любой секретный ключ, скажем, с трёх попыток, поскольку правильность ключа нетрудно точно проверить. При правильно выбранных параметрах криптосистемы вероятность угадать ключ довольно мала, однако и практические алгоритмы криптоанализа не просто оптимизируют полный перебор, а выстраивают именно процесс угадывания, то есть остаются эвристическими, уменьшая количество попыток подбора до практических значений.
Эффективными оказываются как более общие вероятностные алгоритмы с оптимизированным перебором (это, в частности, популярные методы ИИ – искусственного интеллекта), так и алгоритмы, подходящие только для конкретных конфигураций параметров. То есть для задач криптоанализа сейчас предлагаются более эффективные классические – не квантовые – алгоритмы, которые являются практическими. Собственно, даже алгоритм Шора остаётся вероятностным, но его особенность в универсальном методе взлома, подходящего для целого класса криптосистем и параметров.
Факторизация модулей
Традиционный пример для алгоритма Шора — RSA. Стойкость этой криптосистемы основывается на том, что вычислительно сложно находить разложение произвольных больших чисел на простые множители. Задача называется факторизацией. В RSA факторизовать требуется открытый ключ, модуль: большое число, являющееся произведением двух простых. С математическими свойствами таких разложений связаны конкретные периодические структуры, точное знание о которых позволяет быстро вычислить секретное разложение даже для больших чисел. Алгоритм Шора как раз и описывает способ нахождения соответствующего периода методами математического аппарата квантовой механики. Если этот аппарат удастся без существенных изменений перенести на достаточно мощную физическую реализацию, то получится аналоговый квантовый вычислитель, позволяющий выполнять факторизацию больших чисел «быстро». Из этого, впрочем, не следует, что «сломается вся современная криптография».
В чуть более строгой классификации алгоритм Шора относится к квантовым алгоритмам «нахождения периода» (периода функции в данном случае). Именно в этом состоит квантовая часть алгоритма, а само фактическое разложение на множители выполняется классическим компьютером (это и есть связь с алгоритмом Евклида). Другими словами, даже в теории квантового криптоанализа квантовый компьютер без классического бесполезен.
Возможность взломать RSA – в сугубо практических терминах TLS и браузеров – означает, что на основе открытого ключа можно за обозримое время вычислить секретный, нарушив защиту. Конструкция квантового «нахождения периода» переносится и на другие асимметричные криптосистемы, отличающиеся от RSA. Например, на ECDSA.
Асимметричные криптосистемы в TLS непосредственно для защиты трафика не используются, поскольку это слишком накладно в плане вычислительных ресурсов. Для защиты полезных данных в TLS (а также и в большинстве защищённых протоколов мессенджеров) используются симметричные шифры (AES, ChaCha20, «Кузнечик» и др.). Симметричные шифры страдают от известных квантовых атак не столь радикально, но это только если рассматривать симметричные шифры в максимальной общности.
Если направление атаки сузить, то и для симметричных шифров не всё так хорошо. Универсальная оценка эффективности атак на симметричные шифры силами квантовых компьютеров подразумевает полный перебор значений, то есть ситуацию «лобовой атаки», без использования каких-то особенностей конкретного алгоритма: и тут всё неплохо – квантовый алгоритм поиска (алгоритм Гровера) даёт максимально только «квадратичный» прирост, то есть 256-битный ключ как бы превращается в 128-битный, но 128 бит стойкости это всё ещё более чем достаточный уровень.
Однако для конкретных практических шифров могут быть, в теории, предложены специальные квантовые алгоритмы, ускоряющие криптоанализ конкретного шифра, ломающие именно этот шифр. Конечно, тут опять необходим универсальный квантовый компьютер, поскольку схемы, реализующие тот или иной шифр, оказываются весьма сложными. Так что теоретические возможности «квантовых атак» на симметричные шифры всё ещё оказываются весьма скромными: приблизиться к эффективности алгоритма Шора пока не получается.
В порядке очереди
Повышенная квантовая стойкость симметричных шифров делает их защиту «постквантовыми методами» далеко не первоочередной задачей: достаточно длинные ключи позволят защитить сообщения мессенджеров и трафик TLS и после гипотетического появления теоретического квантового компьютера. Однако, чтобы использовать симметричные шифры, сторонам соединения нужны симметричные секретные ключи. В TLS, за исключением редких случаев (PSK – Pre-Shared Key), эти симметричные ключи согласуются сторонами на этапе установления соединения через незащищённый канал. Для этого служит та или иная современная реализация протокола Диффи-Хеллмана (DH), гораздо реже – всё ещё используется RSA. Все эти криптосистемы уязвимы для квантовой атаки по алгоритму Шора. (Кстати, сам протокол DH к подобному взлому устойчив, поэтому применяется в постквантовых схемах, но вот конкретный вариант базовых операций, используемый в TLS, уязвим.)
Это означает, что симметричные ключи можно раскрыть, не прибегая к взлому самих шифров – достаточно атаковать сеанс выработки симметричных ключей, проходящий в открытом виде. Поэтому самый высокий приоритет для защиты постквантовыми методами в TLS имеет именно этап согласования симметричных секретных ключей. Всё это применимо и к защищённым мессенджерам, но далее все примеры в статье будут для случая TLS.
В TLS имеется ещё один непосредственно уязвимый для квантовых атак архитектурный элемент: аутентификация узлов, или TLS-сертификаты. Предполагается, что клиент, выполнив проверку электронных подписей, связанных с сертификатом сервера, определяет, что соединяется именно с той стороной, с которой планировал (при аутентификации клиента сервером процесс аналогичный).
Квантовая атака позволяет взломать криптосистему электронной подписи и выпустить поддельные сертификаты. С точки зрения квантовых атак здесь есть одно важное отличие от описанной в предыдущем абзаце ситуации с согласованием симметричных ключей: взлом электронных подписей, используемых в сертификатах, вообще говоря, не позволяет непосредственно атаковать ранее записанные TLS-сессии, если симметричные ключи в них согласовывались по протоколу Диффи-Хеллмана для конкретного сеанса.
Взлом криптосистемы электронной подписи никак не помогает подставить подменный TLS-сертификат в сессию, которая к моменту взлома давно завершилась. Атаковать «подменным сертификатом» записанные сессии не получится, поскольку симметричные секреты в современных вариантах TLS вырабатываются с учётом так называемой прогрессивной секретности, то есть обеспечивают защиту в случае компрометации долговременного, статического серверного секретного ключа, используемого при аутентификации. Другими словами, для раскрытия записанного трафика корректной TLS-сессии взлом ключа из TLS-сертификата бесполезен, но чтобы защитить процесс обмена ключами, всё равно нужна постквантовая стойкость.
Секретность передаваемых данных желательно сохранять в течение какого-то заметного времени, поэтому и переход на постквантовые криптосистемы для обмена симметричными ключами должен произойти заранее. Тогда «неожиданно появившийся» квантовый компьютер, конечно, позволит подделать аутентификационную информацию во вновь устанавливаемых сессиях и перехватить их, но хотя бы не позволит раскрыть старый, ранее записанный трафик, так как для его защиты уже некоторое время использовались криптосистемы с постквантовой стойкостью.
Оценки стойкости гибридов
Что же подразумевается под термином «постквантовая стойкость»? Подразумевается, что для криптосистемы, обладающей такой стойкостью, не известны квантовые алгоритмы, позволяющие взломать эту криптосистему с использованием некоторого «практического» количества ресурсов. Оценка стойкости криптосистем в теоретической криптографии вообще представляет собой отдельную сложную область, насыщенную эвристическими подходами. Оценки традиционно строятся на подсчёте вычислительных ресурсов, взятых в рамках той или иной модели: количество памяти, количество «битовых операций» и др. – подходы различаются в деталях. То же самое верно и для «постквантовой стойкости»: речь не идёт о том, что для той или иной «постквантовой криптосистемы» эффективные квантовые алгоритмы взлома невозможны в принципе, даётся лишь предположительная оценка квантово-вычислительных затрат, исходя из известных на момент исследования алгоритмов атак и их сравнения с мощностью классических атак, то есть всё это актуально для случая, когда для криптоанализа используется классический компьютер.
Например, оценки сложности квантового алгоритма Шора показывают, что затраты на взлом RSA квантовым компьютером могут находиться в области технологической достижимости. Но не более. Заметьте, это всего лишь предположение, а оценки требуемых ресурсов, если представить их в количестве квантовых элементов (кубитов и «триггеров/гейтов»), различаются буквально в тысячи раз. И тем не менее, эта квантовая сложность для RSA несравнимо меньше классической сложности взлома, отсюда делается вывод, что RSA не обладает постквантовой стойкостью для современной разрядности ключей. То же самое применимо к ECDSA (разрядность даже меньше) и к распространённым вариантам реализации протокола Диффи-Хеллмана. Оговорка про разрядность важна с практической точки зрения, поскольку задаёт нужное количество квантовых элементов. То есть оценки постквантовой стойкости базируются на том, что это именно алгоритм Шора не позволяет сломать данную криптосистему на предложенном количестве «кубитов» и «гейтов».
Наличие «постквантовой уязвимости» ничего не говорит ни о том, что классические методы атак на ту же криптосистему не могут быть улучшены, ни о том, что классический метод атаки обязательно существует. Так, для факторизации RSA-ключей алгоритм Шора работает «в лоб», как работал бы и классический компьютер – никаких алгоритмических «обходных путей» в алгоритме нет, поэтому он и не может сам по себе улучшить классические результаты факторизации. Преимущество алгоритма Шора в том, что он показывает, как перенести вычислительные затраты факторизации на квантовые схемы, где необходимый уровень этих затрат минимизируется.
Постквантовая криптосистема должна обладать и классической стойкостью – иначе смысл её применения теряется. Постквантовая стойкость никак не гарантирует наличие классической. Но у постквантовых криптосистем, несмотря на все трудности, сейчас есть большое, огромное преимущество перед квантовыми компьютерами: универсальных квантовых компьютеров с алгоритмом Шора нет ещё и на горизонте, а постквантовые криптосистемы уже внедряются в качестве элемента гибридной защиты – происходит это из-за предположения, что квантовый компьютер всё же может быть создан и позволит расшифровать ранее записанный трафик.
Гибридная защита тут означает, что криптосистема с постквантовой стойкостью используется в сочетании с классической, хорошо отработанной и изученной, криптосистемой. Это исключает «обратную атаку»: если та или иная постквантовая криптосистема окажется нестойкой к классическим атакам, то защиту обеспечит классическая часть гибридной схемы.
Почему данный подход не применялся к разнотипным криптосистемам в том же TLS ранее, без требований о квантовых компьютерах? Резонный вопрос. Например, можно взять какую-нибудь экзотическую классическую криптосистему и прикрепить её к распространённой реализации классического протокола Диффи-Хеллмана (DH) без оглядки на квантовые компьютеры, чтобы, если через двадцать лет будет найден неквантовый метод эффективного взлома классического DH, записанный трафик всё ещё оказался бы защищён (улучшения вычислительных атак на классический DH за долгие годы достигнуты существенные). Такие гибридные криптосистемы существуют, но почему это не делается повсеместно, в том же TLS? Отчасти положение дел объясняется тем, что задачи, на которых строятся распространённые сейчас асимметричные криптосистемы, нередко имеют математически эквивалентную, с точки зрения сложности, структуру: то есть одну задачу можно перевести в другую «с точностью до некоторой константы» (иногда, впрочем, «константа» получается слишком большой). Навешивание же дополнительных алгоритмов может приводить к росту сложности реализации. Эта точка зрения настолько популярна, что нередко предлагается даже в случае постквантовой стойкости отказываться от гибридных схем и сразу переходить на только постквантовые. В отношении постквантовых схем это выглядит сомнительным, поскольку для новых криптосистем – а также, что важнее, для их реализаций – всё ещё не ясен практический уровень стойкости даже к классическим атакам.
Интересно, что не все криптосистемы, обладающие постквантовой стойкостью, разработаны недавно. Так, исходная асимметричная криптосистема McEliece, практические варианты которой имеют сейчас статус постквантовой стойкости, была предложена ещё в 1978 году. Конечно, в то время постквантовая стойкость не предполагалась, так как алгоритм Шора ещё не был опубликован. В McEliece такая стойкость возникает в качестве побочного эффекта, поскольку сложность обратимости ключей для этой криптосистемы базируется на задаче из теории кодирования («обращение» произвольного линейного кода с исправлением ошибок), которая для алгоритма Шора не подходит.
Собственно, если судить по конкурсным криптосистемам, отбиравшимся NIST [4] по критерию постквантовой стойкости, задачи теории кодирования используются в нескольких современных постквантовых системах. Второй весьма популярный механизм – решётки (алгебраическая структура, простейший пример которой даёт регулярная сетка из точек, расставленных по квадратным клеткам на листочке бумаги). Это, впрочем, достаточно поверхностная и тематическая оценка.
Практика браузеров
Математический аппарат, прямо связанный и с решётками, и с «помехоустойчивыми» кодами, использует постквантовая криптосистема, встроенная в TLS-стек Chrome/Chromium. Эта криптосистема относится к гибридным: классическая часть здесь – X25519, постквантовая – Kyber768.
X25519 [5] это хорошо известный вариант протокола Диффи-Хеллмана на эллиптической кривой (Curve25519, откуда и название). Kyber768 [6] – механизм «инкапсуляции ключа» (KEM – Key Encapsulation Mechanism), или асимметричная криптосистема, предназначенная для передачи общего секрета (формально, протокол Диффи-Хеллмана тоже можно переопределить как KEM-схему). Данная гибридная криптосистема известна под не менее «гибридным» названием: X25519Kyber768 [7], – а так как сейчас используется draft-версия, то полное название – X25519Kyber768draft0. Способ использования данной криптосистемы сейчас совместим только с TLS версии 1.3.
X25519Kyber768 в TLS предоставляет механизм получения общего секрета. Это развитие обязательно для TLS 1.3 протокола DH. Технически, в TLS-стеке браузера происходит следующее. TLS-соединение начинается [8] с сообщения клиента (ClientHello) в сторону сервера. Сообщение содержит параметры соединения, которые готов поддерживать клиент. Штатным ответом сервера на ClientHello является парное к нему сообщение ServerHello. В версии TLS 1.3 стороны уже на раннем этапе установления соединения согласовывают общий секрет. Этот секрет необходим для выработки симметричных ключей защиты трафика.
Используемый для согласования секрета протокол состоит в обмене открытыми частями DH с последующим вычислением секретного значения каждой из сторон.
В постквантовом варианте X25519Kyber768 заменяет для Chrome клиентскую часть ключевого обмена начального этапа TLS-соединения. То есть в ClientHello добавляются данные X25519Kyber768. Если TLS-сервер поддерживает данную криптосистему, то он извлекает клиентскую часть обмена из ClientHello и может вычислить совместимый серверный ответ (см. ниже), который передаёт в ServerHello. Схема архитектурно повторяет существующие варианты, уже используемые в TLS. Внедрение X25519Kyber768 никак не изменяет других аспектов соединения: сохраняются логика и порядок сообщений, не изменяются сертификаты и ключи к ним, используются те же симметричные шифры.
«Гибридизация» криптосистем здесь сводится к конкатенации байтов, составляющих клиентскую часть протокола Диффи-Хеллмана X25519 и открытый ключ клиента Kyber768.
На сервере данные разделяются на относящиеся к разным криптосистемам гибрида и обрабатываются отдельно. А именно: для X25519 сервер вычисляет общий секрет DH и серверный открытый ключ DH точно так же, как это делалось бы в случае «негибридной» X25519; для Kyber768 сервер генерирует общий секрет и «инкапсулирует» его, используя открытый ключ Kyber, присланный клиентом в ClientHello. В результате на сервере формируются два массива байтов, которые можно передать клиенту по открытому каналу, и два секретных массива байтов, которые служат для вычисления набора ключей симметричных шифров; эта секретная часть обмена передаётся на вход внутренней функции генерирования симметричных ключей сервера. Это и есть шаг смешивания секретов, полученный классической и постквантовой криптосистемой.
Чтобы успешно атаковать сессию, атакующему нужно взломать и классическую часть (X25519), и постквантовую (Kyber768). Если у атакующего есть квантовый компьютер, то он определяет 256 бит классической X25519, но остаются неизвестными 256 бит постквантовой Kyber768. Если квантового компьютера нет, но Kyber768 оказалась нестойкой к классическим атакам, то сохраняются 256 бит X25519. А в самом худшем варианте, когда и квантовый компьютер есть, и Kyber768 оказалась нестойкой к классическим атакам, схема скомпрометирована полностью. Однако в случае, когда обе криптосистемы оказались нестойкими к классической атаке, ничего не ухудшилось, поскольку X25519 и так повсеместно используется.
Клиент, получив серверную часть X25519Kyber768, также разделяет данные на открытую часть обмена DH X25519 и шифротекст Kyber768 с «инкапсулированным» секретом, вычисляет общий секрет DH X25519 и, используя клиентский секретный ключ, извлекает секрет Kyber768. Оба полученных значения объединяются, на основе объединённого секрета клиент вычисляет свой набор симметричных ключей. Если всё сработало правильно, то результат должен совпасть с серверным.
Чтобы получить постквантовую стойкость в описанной практической схеме, требуется дополнительно передать примерно килобайт данных для каждой из сторон: основная часть — обмен Kyber768, 1184 и 1088 байтов. По меркам постквантовых криптосистем это весьма и весьма небольшой объём данных, он сравним с типичными сейчас длинами RSA-ключей, но значительно превышает показатели DH на эллиптических кривых.
***
Квантовые вычисления в философском смысле – это попытка получить доступ на самом низком, самом прямом и «железячном» уровне к центральному «процессору» (ЦПУ) вселенных, то есть, к необозримому «чипу», на котором, возможно, окружающая действительность исполняется в режиме виртуализации. Это неплохо соответствует фольклорной интерпретации термина «квантовый» в отношении компьютера: элементы полупроводниковых чипов, находящихся внутри этого ящика, становились всё меньше и меньше, и вот, за гонкой нанометровых технологий, ситуация проваливается в квантовые элементы – получите квантовый компьютер. И действительно, пусть сам предполагаемый принцип квантовых вычислений не имеет ничего общего с уменьшением линейных размеров полупроводниковых вентилей и законами Мура, попытки физической реализации квантовых вычислителей уже сейчас подразумевают управление отдельными атомами. Если квантовый компьютер сделать не получится, эти наработки наверняка пригодятся для дальнейшей миниатюризации компьютеров классических. Что же касается теоретико-информационной криптографии, то она, похоже, выигрывает и тут.
Список литературы:
[1] “iMessage with PQ3: The new state of the art in quantum-secure messaging at scale” https://security.apple.com/blog/imessage-pq3
[2] “Feature: X25519Kyber768 key encapsulation for TLS” https://chromestatus.com/feature/5257822742249472
[3] Cuffaro, Michael and Amit Hagar, “Quantum Computing”, The Stanford Encyclopedia of Philosophy https://plato.stanford.edu/entries/qt-quantcomp/
[4] NIST, https://csrc.nist.gov/projects/post-quantum-cryptography
[5] RFC 7748 https://datatracker.ietf.org/doc/html/rfc7748
[6] Kyber, https://pq-crystals.org/kyber
[7] IETF draft https://www.ietf.org/archive/id/draft-tls-westerbaan-xyber768d00-03.html
[8] RFC 8446 https://datatracker.ietf.org/doc/html/rfc8446