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

Постквантовые криптосистемы из рекомендованных 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 килобайт, и даже соответствующие факториалы.

Адрес записки: https://dxdt.ru/2024/08/31/13801/