dxdt.ru: занимательный интернет-журнал

Даниэль Бернштейн (Daniel J. Bernstein) опубликовал большую статью (англ.) с критикой некоторых возражений, относящихся к возможности создания универсальных квантовых компьютеров. Вообще, основной посыл статьи такой: нужно немедленно повсеместно внедрять постквантовую криптографию, потому что, исходя из анализа ситуации, не удаётся найти веских причин для уверенности в том, что АНБ уже не строит активно (или построило) квантовый компьютер, пригодный для практического криптоанализа.

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

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

I’m not saying that computation on qubits is the same as computation on random bits. When you look at the details, you see that quantum computation allows a useful extra trick, setting up interference patterns between positive and negative variables. But an argument saying “quantum computing is impossible because there are so many variables” can’t be right: it also says that your laptop is impossible.
(“Я не утверждаю, что вычисление на кубитах это то же самое, что и вычисление на случайных битах. Если посмотреть детально, то можно увидеть, что квантовое вычисление позволяет провести дополнительный полезный трюк, задав схемы интерференции между положительными и отрицательными переменными. Однако аргумент, говорящий, что “квантовые вычисления невозможны, так как там настолько много переменных”, не может быть верным, поскольку этот же аргумент говорит, что ваш ноутбук невозможен.”)

Вообще, именно возможность “интерференции между переменными”, это не просто трюк, а она таки составляет смысл квантовых вычислений, которые, собственно, вычислениями, в привычном смысле, и не являются. Чтобы интерференция состояний стала возможной, логично допустить, что эти состояния где-то “должны размещаться”. То есть, это не обязательно так, не является необходимым условием. Потому что можно, скажем, посчитать, что соответствующие потоки вероятностей и составляют некоторую над-реальность, а наблюдается только её “срез”, вызванный представлением экспериментатора (возможны ли при этом квантовые вычисления – другой вопрос). Однако, сама идея, что для 2^1000 состояний используемые модели “квантовой механики” не работают, не только не выглядит нелогичной, но уж точно не разрушается возможностью обработать тысячу битов классическим ноутбуком: в классическом ноутбуке другие состояния битовой строки возникают как программное представление после выполнения преобразования, а не являются фундаментом физической реализации алгоритма в некотором аналоговом вычислителе.

А тип криптосистемы ML-KEM (она же – Kyber) на русском лучше писать так: “модуль-решёточная криптография”.

Вообще, определить ML-KEM, как прикладную криптосистему, можно совсем не используя соответствующее понятие решётки. Без модулей и колец – определить не выйдет, поскольку векторы и многочлены непосредственно служат элементами алгоритмических структур (достаточно того, что открытый текст представляется в виде многочлена). Но решётки, как один из мощных инструментов теоретической криптографии, тут возникают при доказательстве предположений о стойкости криптосистемы. Ну, или в другую сторону: выбор базовой задачи данной криптосистемы основан на оценках вычислительной сложности задач “на решётках”.

То есть, как ни крути, а решётки имеют определяющее значение, но с точки зрения базовой задачи, которая напрямую в ML-KEM не используется. Так же, кстати, написано и в стандарте NIST, где термин “решётка”, если не считать употребление его в названии, используется всего пару раз. (При этом, кстати, не совсем корректно писать, что используемая криптография “основана на задачах из теории решёток” – на этих задачах основаны предположения о стойкости, а не криптографические алгоритмы; не то чтобы радикальное изменение смысла, но существенные детали теряются.) И необходимо учитывать, что математический термин “решётка” (русский) и математический термин lattice (английский) – различаются в трактовках, даже если смотреть узкую интерпретацию, поэтому для строгих определений всё равно потребуются уточнения.

“Модулярная решётка” – явно не подходит, поэтому пусть будет “модуль-решёточная”. Ведь главное тут – чтобы криптосистема не оказалась решетчатой, но от слова “решето”.

В ML-KEM (ранее – Kyber) возможен вариант, когда корректно полученные сторонами секреты не совпадут. В стандарте NIST это называется Decapsulation failure. То есть, сами криптографические примитивы, составляющие ML-KEM, срабатывают всегда – выводят 256-битное значение. Но с некоторой (чрезвычайно малой) вероятностью принимающая сторона, расшифровывающая секрет, может получить значение, не совпадающее с тем, которое отправлено. “Чрезвычайно малая вероятность” тут означает 2^(-164.8). Выглядит более чем несущественным параметром. Но рассматривать сам факт наличия такой “погрешности” можно с разных сторон.

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

Строго говоря, и в ML-KEM упомянутая “погрешность” оказывается в ряду заданных результатов алгоритма, просто, определяется она на другом уровне. Более того, при практической реализации алгоритмов, не имеющих встроенных “погрешностей”, эти самые погрешности постоянно возникают и из-за ошибок в программах, и даже из-за ошибок в работе оборудования. Особенно, если говорить о вероятностях порядка 2^(-165) – казалось бы, тут и без всяких Rowhammer какой-нибудь залётный нейтрон может вызвать реакцию, которая переключит пару битов в модуле памяти. Нейтрон, конечно, может помешать, но это будет не то же самое, что и внесение обязательного сбоя непосредственно в логику алгоритма.

Пишут, что свежие рекомендации профильного агентства правительства Австралии требуют отказаться от современных распространённых криптосистем (ECDH, ECDSA и др.) и перейти на постквантовые криптосистемы совсем скоро – к 2030 году. Занятно, что в этих рекомендациях запрещают SHA-256 в HMAC, но оставляют AES. Это тем более странно, что отказ от SHA-256 мотивируют традиционным развитием квантовых компьютеров. При этом, конечно, ничего не сказано про алгоритмы, используемые для защиты по высшим категориям (TOP SECRET).

Нетрудно посчитать, что знаменитый 2030 год планируется уже через пять лет. С одной стороны, пять лет это очень мало. С другой стороны – пяти лет может оказаться достаточно для того, чтобы появились квантовые алгоритмы для взлома, скажем, криптосистем на кодах и решётках. (Но и квантовые алгоритмы для AES – тоже нельзя исключать.) Естественно, алгоритмы будут не менее теоретическими, чем алгоритм Шора, и смогут сработать только на “гипотетических квантовых компьютерах”, но это всё равно потребует, как минимум, пересмотра рекомендаций, а как максимум – разработки новых криптосистем. Впрочем, всегда можно просто увеличить длину ключей (как долгие годы и делается с RSA).

Поскольку браузеры, – в том числе, самый свежий Firefox, – перешли с Kyber768 на ML-KEM, я добавил на свой тестовый сервер TLS поддержку X25519MLKEM768 (не удаляя “гибриды” с Kyber768). Проверить можно при помощи новых версий браузеров Chrome и Firefox.

Кстати, немного занимательных элементов. В процессе развития постквантовой криптографии в TLS уже успели поменять “порядок байтов”. Так, в новых версиях представлений гибридных ключей – разная конкатенация массивов: в “старом” X25519Kyber768, если смотреть в сетевом порядке (так сказать, слева направо, что, конечно, математически неверно), сначала идёт ключ X25519, а потом – Kyber768; в “новом” X25519MLKEM – наоборот, сначала данные ML-KEM, а потом – X25519.

Почему это занимательно? А вот почему. Те немногие читатели dxdt.ru, которые непосредственно связаны с разработкой и реализацией ГОСТ-криптографии, совершенно точно наслышаны о технической шутке про “вращение байтов”, всплывающей в данной области постоянно и много лет. Суть вот в чём: при записи криптографических представлений, понятно, очень важен порядок байтов; так вот, в реализациях ГОСТ-криптографии, порядок байтов местами “сетевой”, а местами – в другую сторону. “Тупоконечное” и “остроконечное” представление. Так сложилось исторически. И смена направления, хоть и строго определена, но всегда происходит неожиданно. И она вовсе не так тривиальна, как можно подумать: байтовые последовательности попадают в хеш-функции; координаты точек – записываются в файлы; и так далее, и тому подобное. Понятно, что на стойкость и свойства математических операций, как и на описание алгоритмов в спецификациях, это не влияет. Однако если две реализации “байты вертят в разные стороны”, то они между собой несовместимы. На этом направлении даже есть тесты, которые, впрочем, не всегда помогают (как и в других областях, конечно). А самый забавный вариант – это когда значение оказалось “палиндромом”.

Криптосистемы с постквантовой стойкостью предлагается внедрять в составе гибридных схем. Именно так сделано в TLS и в браузерах: широко и давно используемая X25519 + постквантовая криптосистема Kyber, на случай, если последняя окажется нестойкой. Под “гибридной” схемой здесь подразумевается объединение секретов, независимо полученных применением одной и второй криптосистемы: ни о каком “подмешивании” шагов одной криптосистемы в другую речи нет – X25519 не влияет на стойкость Kyber и наоборот (формальная оценка стойкости гибридной схемы в целом и для разных моделей – несколько другая история, но эти детали тут не важны). Подобная “гибридизация” имеет ряд занимательных особенностей: так, постквантовая Kyber должна, очевидно, обладать и стойкостью к классическим атакам, а это означает, что она некоторым образом усиливает защиту сессий с точки зрения переспективных атак “неквантовыми методами”.

То есть, данные криптосистемы достаточно различаются математически, чтобы даже универсальная атака на X25519 не сломала, гарантированно, и Kyber. Так что, если через десять лет вариант протокола Диффи-Хеллмана (ECDH), реализуемый X25519, научатся быстро ломать, – например, для конкретных параметров, – то записанный трафик всё равно будет защищён Kyber. Естественно, это всего лишь обращение мотивации для использования X25519 вместе с Kyber, чтобы подстраховаться на случай внезапного обнаружения неустранимых дефектов в последней. Обратная схема тоже работает, но X25519 используется дольше и, возможно, лучше изучена, так что “поломка” Kyber, конечно, выглядит более вероятным событием.

Вообще, из того, что Kyber признана криптосистемой с постквантовой стойкостью и стандартизована как ML-KEM, вовсе не следует, что доказано отсутствие квантовых алгоритмов взлома Kyber; уж тем более неверно будет утверждать, что эффективность решения базовой задачи для Kyber не отличается на обычных и квантовых компьютерах. Во-первых, квантовых компьютеров пока что нет, и непонятно, как они вообще могли бы быть устроены, чтобы ломать Kyber. Во-вторых, квантовые компьютеры сами ничего “не вычисляют” в том смысле, чтобы сравнивать с “обычными” (но всякий квантовый алгоритм можно запустить и выполнить на “обычном компьютере” – времени потребуется несравнимо больше, чем хотелось бы для достижения практической полезности). В-третьих, доказывать отсутствие алгоритмов вообще непросто. Так что в случае с постквантовой стойкостью слишком многое сводится к алгоритму Шора, в его самой теоретической интерпретации, а для ML-KEM/Kyber резонно ожидать и квантовых улучшений атак тоже.

Более того, поскольку одна задача (Kyber) не переводится быстро в другую (ECDH), то можно предположить не только появление специального квантового алгоритма для эффективного взлома Kyber, но и то, что квантовый компьютер, реализующий этот алгоритм, окажется (согласно некоторой теории) построить проще, чем не менее квантовый компьютер для алгоритма Шора. А что? Теоретические аналоговые вычислители они на то и теоретические, и аналоговые, что это сейчас только различные оценки количества “квантовых элементов” для практической атаки на RSA расходятся на несколько десятичных порядков, а на следующем шаге – могут разойтись и оценки достижимости по новым и старым алгоритмам.

Использование имеющихся сейчас посквантовых криптосистем в TLS существенно увеличивает объём передаваемых данных. Например, ключ Kyber768, используемый в первом же сообщении (ClientHello), требует более килобайта (1184 байта). При этом, в TLS 1.3 есть штатная возможность передать несколько ключей для разных криптосистем в одном сообщении ClientHello, чтобы сервер выбрал подходящее. Эта возможность постоянно используется на практике.

Например, клиент может сразу передать ключи X25519 (32 байта) и P-256 (32+32 == 64 байта). То есть, две криптосистемы – и лишь 96 байтов расходуется на запись ключей (небольшое количество дополнительных байтов нужно для записи тех структур, в которых передаются ключи, но это можно не учитывать). Если передавать ключи двух постквантовых криптосистем, – скажем, с теми же Kyber768 и стандартизованным вариантом ML-KEM, – то получается уже больше двух килобайт. Это много, но если регулярно переходить от одной поствкантовой криптосистемы к другой, то становится необходимым, рутинным элементом TLS-соединений. Заметьте, что сам перечень поддерживаемых клиентом криптосистем для обмена сессионными секретами передаётся в TLS отдельно. Обычно, в этом перечне указано значительно больше криптосистем, чем передано ключей. Так, браузер может передавать семь поддерживаемых вариантов и ключи только для трёх из них (так сейчас делает Firefox). Чтобы сервер мог выбрать криптосистему, ключи от которой отсутствуют в ClientHello, в TLS 1.3 предусмотрен механизм повторного согласования – HelloRetryRequest: сервер, в этом случае, запрашивает повторное ClientHello, где будет только ключ той криптосистемы, которая выбрана (это всё можно самостоятельно увидеть на тестовом сервере TLS 1.3 при помощи современного браузера).

Подобный перебор с постквантовыми криптосистемами ещё больше увеличивает трафик, поэтому уже рассматриваются варианты того, как бы данный момент переложить на DNS. Так, в сообщении Google про ML-KEM в браузере Chrome, на которое я недавно ссылался, упоминается соответствующий черновик RFC – там предлагается публиковать в DNS сведения о предпочитаемых криптосистемах для обмена сеансовыми ключами в TLS. Конечно, тут нужно учитывать возможную защиту DNS-ответов от подмены, то есть, всё это тянет за собой не только и не столько DNSSEC (которая сама не имеет пока что ничего “постквантового”), как DNS-over-TLS/DNS-over-HTTPS.

Развитие постквантового TLS очень бурное. Впрочем, пока что не совсем понятно, для чего вообще такой рост объёмов данных. Сама по себе “постквантовая стойкость” тут ничего не объясняет, как и популярные описания в стиле “зашифруй заранее, пока нет квантового компьютера”. Однако вот уже и DNS охвачена дополнением записей. С одной стороны, размещение предварительных сведений о настройках TLS в DNS выглядит более чем разумно: запрос в систему всё равно необходим для получения IP-адреса; с другой стороны – данное направление развития как-то быстро сводится к надстраиванию новых и новых, всё больших и больших “дополнений”. (Надстраивание происходит в ускоряющемся темпе: не успели год назад внедрить в браузеры Kyber, как его уже переименовали в ML-KEM и переделали.) Эти “дополнения” вытесняют привычную работу с DNS, заменяя её на другой процесс, который следует называть “обнаружением сервисов” (Service Discovery) – дело в том, что с появлением ECH даже и IP-адреса будут извлекаться из доступной сети по-другому.

Постквантовые криптосистемы из рекомендованных NIST используют большие по количеству байтов ключи и значения подписей. Это особенно заметно, если сравнивать с привычными “классическими” криптосистемами на эллиптических кривых: постквантовые схемы требуют в сотню раз больше байтов; требования для разных криптосистем и разных сочетаний параметров различаются, но, тем не менее, это буквально рост на пару десятичных порядков: так, подпись в “минимальном” варианте SLH-DSA записывается в 7856 байтов, сравните с 64 байтами ECDSA/P-256, например; другие наборы параметров SLH-DSA требуют для подписи по 16 килобайтов и более, у ML-DSA – поменьше. Такой рост объёмов передаваемых данных составляет заметную проблему для практики TLS.

В TLS указание длины блоков данных встречается на нескольких уровнях, так как запись длины и типа данных перед самими данными – это основа архитектуры данного семейства протоколов (это относится не только к TLS, конечно, но и к другим криптографическим протоколам). Обязательный рост размера полей данных отразится на всех уровнях. Посмотрим на них подробнее, оставив, пока что, за скобками TCP (предполагается, что TLS работает поверх TCP).

Уровни, – начиная с базового, с TLS-записей, – выстраиваются следующим образом:
1) TLS-записи;
2) TLS-сообщения;
3) блоки данных внутри TLS-сообщений.

Блоки данных формируют TLS-сообщения, которые передаются в TLS-записях. Здесь на каждом уровне в заголовке присутствует поле с записью длины, то есть, резкое увеличение длины подействует на всех уровнях. Одно из радикальных проявлений – на уровне TLS-записей. В TLS-записи вкладывается весь TLS-трафик. Заголовок TLS-записи содержит: один байт, обозначающий тип записи; два байта, в которых записывается номер версии протокола; два байта, кодирующих длину данных. При этом максимальная длина ограничена спецификацией отдельно, и для TLS 1.3 составляет 16384 + 256 == 16640 байтов (октетов, в более строгой, “сетевой” терминологии).

Представим, что TLS-сертификаты переведены на посквантовые криптосистемы электронной подписи и на запись только значения подписи и открытого ключа теперь требуется восемь (условно) килобайтов. Даже если прочие необходимые поля сертификата займут только два килобайта (это мало – см. ниже), то получится десять в сумме и уже пара сертификатов – вылезают за максимальный размер одной TLS-записи. Да, спецификация позволяет как угодно нарезать TLS-сообщения по записям, поэтому можно передать одно сообщение в нескольких записях. Однако, так как сервер в ходе установления TLS-соединения присылает в ответе несколько сертификатов, ситуация с постквантовыми криптосистемами прямо потребует такой фрагментации TLS-сообщений. Это хоть и допустимо, но нельзя сказать, что хорошо – в некоторых случаях возможны конфликты.

Занятно, что сейчас TLS-сертификаты для веба, то есть, для использования в распространённых веб-браузерах, требуют наличия так называемых SCT-меток, подтверждающих, что тот или иной доверенный лог Certificate Transparency видел соответствующий (пре)сертификат. Такое подтверждение, как нетрудно догадаться, реализуется с помощью электронной подписи. В случае постквантовых криптосистем, подписи SCT-меток тоже должны разрастись в объёмах. То есть, если оставить архитектуру такой, какая она есть, то TLS-сертификаты станут весить килобайт пятьдесят каждый. Не очень-то удобно.

Более того, значение дополнительной “постквантовой” подписи, при использовании соответствующего TLS-сертификата, передаётся в ходе первоначального установления TLS-соединения, чтобы аутентифицировать параметры соединения и, как минимум, сервер (со стороны клиента). А это ещё несколько килобайт или, скорее, несколько десятков килобайт. Эти многие килобайты должны накапливаться в ходе установления соединения, чтобы вычислить значения хеш-функций, необходимые для аутентификации.

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

Естественно, большое количество дополнительных байтов потребуют и схемы согласования симметричных ключей с постквантовой стойкостью (ML-KEM, в терминах NIST). Из-за этих схем увеличивается объём начальных сообщений TLS. Тут уже можно вспомнить и про TCP, так как влияние TCP-параметров имеет наибольшее значение именно на начальном этапе TLS-соединения: существенное раздутие ClientHello/ServerHello приводит к тому, что сообщения вылезают за привычные границы TCP-сегмента.

Является ли большой объём данных, требуемый для записи параметров современных постквантовых криптосистем, необходимым условием достижения постквантовой стойкости? Вряд ли. Даже в упомянутых выше криптосистемах использование большого количества байтов диктуется не столько желанием “увеличить пространство перебора”, сколько требованиями по оптимизации вычислений, которые всё же должны выполняться за какое-то разумное время. Текущие параметры нередко всё равно разворачиваются из, например, 256-битного вектора инициализации. С другой стороны, квантовых компьютеров пока нет, а постквантовая стойкость тут всё ещё определяется относительно одного конкретного квантового алгоритма – алгоритма Шора, – так что для взлома предложенных постквантовых криптосистем могут придумать новые, не менее квантовые, алгоритмы, и большое количество байтов, требуемое для записи ключа или значения подписи, не поможет, так или иначе: не факт, что универсальная постквантовая стойкость вообще возможна – в континуум одинаково легко проваливается и 16 килобайт, и 16^16 килобайт, и даже соответствующие факториалы.

Немного технических деталей про протокол Диффи-Хеллмана в практике интернет-коммуникаций, почему ключи остаются в трафике, и немного про симметричные шифры.

Протокол Диффи-Хеллмана (DH) подразумевает, что каждая из сторон вычисляет свой секрет, потом на основе этого секрета вычисляет собственный открытый параметр (назовём пару этих параметров A и B), передаваемый по открытому же каналу. После того, как сторонам удалось обменяться открытыми параметрами, они могут определить уже общий симметричный секрет, на основе которого вычисляется секретный ключ (чаще – ключи) для симметричного шифра. Так вот, каждый из параметров A и B содержит полную информацию, необходимую для вычисления общего секрета (пояснение, 31/08/24: речь тут про вычисление по записи трафика DH). Это так по определению протокола, иначе сторонам не удалось бы получить одинаковый секрет. Другое дело, что извлечь эту информацию, исходя из известных алгоритмов, вычислительно трудно (но возможно). В частности, не было бы предмета для постквантовой криптографии, если бы ключи “классических” реализаций DH не восстанавливались бы полностью из записи трафика. Так что ключ есть в трафике, а не “только на клиенте”. Это всё известно специалистам, а DH в криптографии и не позиционируется как “ключ только на клиенте”, чтобы это ни значило.

Заметьте, что на практике, если конкретная реализация криптосистемы уязвима, то открытые параметры DH (A, B) могут предоставлять информацию о том, как оптимизировать поиск нужного секрета – это обычный приём. “Обратной задачей DH” называют задачу определения исходного секрета по открытому параметру (А или B). Однако вовсе не обязательно уметь решать обратную задачу быстро и универсальным образом. Можно ограничиться прямой задачей: при знании исходного пользовательского секрета решение этой задачи – быстрое по определению, это важный математический момент; специально подобранные параметры и/или дефектный датчик случайных чисел могут свести перебор к минимуму, если атакующей стороне известен другой секрет или параметр, который задаёт бэкдор (намеренно созданную уязвимость). Соответственно, оптимизированный перебор проводится до тех пор, пока подбираемое значение не совпадёт с перехваченным открытым параметром – в этом полезная роль этого параметра, так как подбирать ключ симметричного шифра, обычно, посложнее.

Ситуация с симметричными шифрами, впрочем, тоже не лишена особенностей. Дело в том, что на практике нетрудно предсказать значение открытого текста, соответствующего перехваченному в трафике зашифрованному сообщению. Это вообще самая старая из минимально содержательных атак на практические криптосистемы, известная задолго до появления интернетов, однако в интернетах обретшая новые черты: нетрудно предсказать, что содержится в начальных байтах HTTP-запроса GET, отправленного браузером через TLS-соединение к веб-серверу под известным именем. (И уж тем более нетрудно определить, для того же TLS, значение индекса в симметричной криптосистеме, работающей в режиме счётчика.) Это означает, что, формально, в трафике есть и следы ключей симметричного шифра. Другое дело, что преобразование, соответствующее зашифрованию симметричным шифром, во-первых, практически одинаково работает в обе стороны (зашифрование/расшифрование), то есть, никто и не полагался на сложность обратного преобразования как элемент обеспечения стойкости; во-вторых, с точки зрения криптоанализа симметричного шифра, секретный ключ входит в состав выполняемого преобразования. Тем не менее, для симметричных шифров тоже известны различные подходы, позволяющие устроить “вычислительный бэкдор“.

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

Да, это возможно. Технически, ключ вовсе не зафиксирован в роли “только для сайта”, так что ничего тут не мешает: достаточно взять какую-нибудь подходящую утилиту, которая может прочитать секретный ключ из файла (OpenSSL или другие варианты), и можно начать подписывать произвольные электронные документы. В процессе подписывания – открытый ключ и сертификат вообще не требуются. Естественно, каждое использование ключа (буквально – каждая операция) несёт с собой дополнительный риск утечки этого ключа. Однако, при штатной работе TLS, ключ “от сертификата” уже постоянно задействован именно для получения электронной подписи, так что тут нет места для каких-нибудь опасений относительно того, что ключ будет “использован не по назначению”. Однако для хитрых ошибок – место, всё же, появляется.

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

Проверка подписи для рассматриваемого способа использования проводится при помощи открытого ключа, опубликованного в TLS-сертификате. Тут возникает административный момент, связанный с политикой управления доверием, используемой приложением на проверяющей стороне. Это приложение может “верить в сертификат”, а может – “верить в сам ключ”.

В первом случае – допустимый контекст использования ключа задаёт сертификат и, так сказать, семантика применения этого сертификата. Например, приложение может в принципе принимать TLS-сертификаты (и ключи из них) только в контексте подписывания TLS-параметров при HTTPS-доступе к веб-серверу, и всё. Естественно, в сертификате предусмотрены дополнительные флаги и параметры, определяющие допустимые способы использования ключа. Их приложение тоже может учитывать каким-то своим способом (но, заметьте, использование ключа для подписи – в сертификате “от сайта” должно быть разрешено и так; см. выше).

Во втором случае, когда приложение “верит в сам ключ”, сертификат служит лишь контейнером для доставки этого ключа. “Верить в сам ключ” – означает, что доверие распространяется прежде всего на конкретное значение ключа, но при этом сам сертификат из рассмотрения может и не исключаться. Например, это обычная практика для корневых ключей в TLS для веб-сайтов и браузеров.

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

Если (вдруг) появился универсальный “квантовый компьютер” нужной мощности, то как именно будут выглядеть технические шаги по раскрытию ранее записанного TLS-трафика? Под “квантовым компьютером” здесь подразумевается аппарат, выполняющий алгоритм Шора. А в роли взламываемой криптосистемы выступает алгоритм Диффи-Хеллмана на эллиптической кривой (ECDH – типовой алгоритм для современного состояния TLS). Шаги потребуются следующие.

1.

В записи трафика присутствуют начальные TLS-сообщения, обеспечивающие распределение общего секрета. Если таких сообщений нет, то раскрыть трафик рассматриваемым способом – не выйдет. Выделить начальные сообщения нетрудно: они начинаются с байтового префикса с зафиксированным значением и имеют строгую структуру. В трафике всегда остаются ключи, согласованные сторонами по протоколу Диффи-Хеллмана (равно как и с использованием RSA или другого метода инкапсуляции). Я писал об этом ранее. Заметьте, что записываются и ключи, согласованные с использованием современных криптосистем, обладающих постквантовой стойкостью. Просто, считается, что их сложнее восстановить даже с использованием гипотетического квантового компьютера.

Из начального сообщения клиента выделяется блок с открытой частью клиентского обмена ECDH. Например, если используется ECDH на кривой P-256, то в специальном и легко обнаруживаемом блоке данных будет содержаться пара координат точки P на кривой P-256, представляющей собой открытую часть обмена ECDH. Это 64 байта (плюс дополнительные байты с указанием на используемый формат), то есть, два блока по 32 байта: координаты X и Y.

2.

Клиентская часть ECDH представляет собой результат умножения базовой точки на секретный скаляр – значение скаляра и есть секретная часть ECDH клиента: это натуральное число n. Открытая часть ECDH, точка P, это результат [n]G, где G – точка-генератор, заданная в параметрах криптосистемы.

Полученные координаты точки P “загружаются” в квантовый компьютер, который уже должен быть настроен на параметры соответствующей криптосистемы, то есть, содержать схему, реализующую алгоритм Шора (нахождения периода функции) для подгруппы кривой P-256, образованной точкой G. Как именно загружаются значения в квантовый компьютер – пока что не известно, поскольку никаких практических квантовых компьютеров создано пока что не было (ну или, если хотите, не было опубликовано их содержательных описаний). Вероятно, у этого компьютера должен быть некоторый классический интерфейс, воспринимающий значения байтов координат точек, и переходные схемы, которые преобразуют эти значения в коммутацию и состояния квантовых “гейтов/триггеров” и кубитов. Неизвестно даже, сколько этих “кубитов и гейтов” будет нужно: несколько миллионов или несколько триллионов. Что уж там говорить про схемы коммутации.

(Заметьте, впрочем, что так как задействованный математический аппарат квантовой механики манипулирует комплексными числами – или, что эквивалентно, синусами и косинусами, – то все открытые тексты и решения можно уместить в пространстве состояний одного “непрерывного” кубита. Континуум, свернувшийся окружностью за привычным синусом, позволяет это легко проделать. Ещё и места останется, как минимум, в два раза больше, чем займут все решения всех проблем со всеми возможными шифрами в степени всех ключей. Это, впрочем, другая история.)

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

Аналогичная схема сработает и для открытого параметра ECDH, который отправил сервер. Для раскрытия ключей защиты трафика – достаточно знать один из секретов: клиентский или серверный.

3.

Общий секрет в ECDH образуется путём умножения точки-генератора на произведение секретов сторон. В рассмотренном только что случае, достаточно умножить открытый параметр DH сервера Q на секрет клиента, вот так: [n]Q (именно эту операцию проделывает клиент в ходе штатного процесса установления TLS-соединения). Секрет клиента, как мы только что выяснили, был раскрыт при помощи квантового компьютера. Результат умножения даёт точку на кривой, координата X которой используется в качестве задающего значения для генерирования секретных симметричных сеансовых ключей защиты трафика TLS. Функция, генерирующая сеансовые ключи, известна. Так как защищённые записи содержат коды аутентификации, сторона, взломавшая секрет ECDH, может тут же легко проверить, что найденный секрет соответствует записанному трафику. Симметричные ключи позволяют расшифровать трафик сеанса, используя шифр, номер которого тоже записан в начальных сообщениях: эти сообщения как раз и нужны для того, чтобы, кроме прочего, стороны согласовали используемый шифр.

*

Несомненно, прогресс в разработке систем “квантовых вычислений” есть. Однако вот уже несколько лет существенная часть прогресса сосредоточена на генерировании хайпа, поэтому даже до минимально практических схем не только далеко, но даже и не ясно, возможны ли такие схемы в принципе. В описанной выше схеме квантовый компьютер используется в роли “оракула”. Так же будет происходить и на практике: в рассматриваемой схеме для работы квантового компьютера не нужны какие-то дополнительные байты TLS-трафика, какие-то шифры или, условно, “части ключей”. С тем же успехом секретный параметр Диффи-Хеллмана можно просто угадать: запись трафика позволяет однозначно определить правильность угаданного значения.