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

Если (вдруг) появился универсальный “квантовый компьютер” нужной мощности, то как именно будут выглядеть технические шаги по раскрытию ранее записанного 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-трафика, какие-то шифры или, условно, “части ключей”. С тем же успехом секретный параметр Диффи-Хеллмана можно просто угадать: запись трафика позволяет однозначно определить правильность угаданного значения.

Адрес записки: https://dxdt.ru/2024/06/22/13224/