Преамбула
Cчитается, что возможно построить физический аналоговый вычислитель, который реализует теоретический алгоритм Шора с "экспоненциальной эффективностью" для чисел большой разрядности - то есть, квантовый компьютер, пригодный для практического взлома весьма распространённых в TLS асимметричных криптосистем (читай: RSA/FFDH, ECDSA/ECDH).
Теория защиты информации учит нас, что важны возможности, а не доказанное наличие материальных средств. До квантовых компьютеров всё ещё далеко, но для прикладной криптографии уже наличие корректного описания быстрого алгоритма взлома достаточно, чтобы возможность квантовых атак признать существующей. Тем более, что трафик, который может быть записан, разумно начать защищать сильно заранее. Поэтому уже давно предложены и недавно реализованы практические криптосистемы, которые, во-первых, алгоритмом Шора разных версий не взламываются; во-вторых, для них не удалось найти другие быстрые алгоритмы взлома методами теоретических квантовых вычислений; и, в-третьих, для этих криптосистем не известно "обычных", - не квантовых, - алгоритмов взлома. Такие криптосистемы, выделяя первые два свойства из перечисленных, принято называть "обладающими постквантовой стойкостью".
По данным Cloudflare на январь-февраль 2025 года больше 30% веб-трафика зашифровано с постквантовой стойкостью. В Рунете, по данным для доменов ТЦИ (сентябрь 2024 года), поддержка постквантовой криптосистемы X25519Kyber768 отмечена, примерно, для 7% имён, адресующих TLS-серверы. Но это уже не трафик, а имена узлов. (X25519Kyber768 - это вариант, который предшествовал стандартизованной ML-KEM.) Так что в современном вебе, работающем через Интернет, постквантовые методы защиты трафика уже получили достаточно большое распространение.
Пререквизиты
Для лучшего понимания этой статьи будет полезным базовое знакомство с принципами устройства TLS, а также с алгеброй в рамках программы средней школы. Если кратко, то в TLS процесс установления соединения оперирует TLS-сообщениями, в составе этих сообщений передаются, кроме прочих параметров, криптографические ключи. Мы посмотрим на соответствующее сообщение клиента и сервера, чтобы определить, как используется постквантовая криптосистема. Что касается алгебры, то в статье используются многочлены, как понятие (но они называются далее "полиномами"), и арифметика остатков. Никакой продвинутой математики, при этом, не используется. (Кто-то скажет, что арифметика остатков - это теория чисел, а мы говорим, что всё - теория чисел, но здесь это алгебра.)
ML-KEM vs Kyber
В TLS криптосистемы с постквантовой стойкостью сейчас используются для защиты трафика, то есть, при вычислении симметричного секрета (обмен ключами), а не в процессе аутентификации сторон сеанса (цифровая подпись). Это объясняется тем, что задача защиты от будущих атак для систем аутентификации здесь лишена технического смысла: сеансовая аутентификация происходит в момент установления соединения, поэтому атаковать завершившуюся аутентификацию из будущего не выйдет. (Практической пользы здесь не найти даже с философской точки зрения: если атакующая сторона умеет обращать направление потока причинности, привычного для протоколов защиты информации, то эта сторона так или иначе уже взломала защиту, если хотела взломать, - это, впрочем, отступление от темы данной статьи.)
Массово (по объёмам трафика) поддерживаемая сейчас криптосистема с постквантовой стойкостью называется ML-KEM. Так её назвали при стандартизации в NIST. На русском криптосистему лучше называть "модуль-решёточная схема инкапсуляции ключа". Регулярно упоминаемые "решётки" (L в ML: Lattice) упоминаются здесь по весьма разумным, но историческим причинам, связанным с синтезом базовой задачи, а вот модули (M в ML: Module), в качестве структурной базы для "операций с матрицами", непосредственно необходимы для определения операций криптосистемы ML-KEM так, как в стандарте. Тем не менее, это всё больше касается названия, чем практики применения.
Исходная криптосистема, предложенная на конкурс, который проводился в процессе стандартизации, называется Kyber. Эти криптосистемы эквивалентны математически. Однако, на уровне операций, ML-KEM не совместима с исходной Kyber, поскольку спецификация стандарта отличается и в нескольких шагах преобразований, и в способах представления параметров. В браузерах изначально поддерживалась именно Kyber, но после принятия стандарта криптосистему Kyber заменили на ML-KEM без сохранения Kyber, ведь обойтись простой заменой идентификатора тут невозможно, а ключи и шифротексты Kyber настолько большие, что передавать параллельно оба варианта слишком накладно.
Гибридизация ключей
В TLS постквантовые криптосистемы используются в составе гибридных схем, совместно с обычными, классическими, криптосистемами. Отсюда и X25519+Kyber768 - то есть, Kyber прикреплен к X25519. Эта последняя криптосистема, реализующая протокол Диффи-Хеллмана, используется давно и повсеместно, поэтому гибридизация позволяет подстраховать новую, постквантовую криптосистему Kyber: если в Kyber обнаружатся уязвимости для классических атак, то X25519 всё ещё будет защищать отправленный трафик, то есть, по крайней мере, схема не ухудшает ситуацию, но добавляет постквантовую стойкость. Ну, как добавляет: предположительно добавляет - нет никаких строгих гарантий, что для Kyber/ML-KEM и других схем невозможно найти квантовые алгоритмы взлома.
В новой версии для TLS вместо X25519+Kyber768 используется X25519+ML-KEM768, несмотря на упомянутую несовместимость, логика применения совпадает полностью, с точностью до перестановки слагаемых - в разных вариантах разный порядок следования ключей и секретов. Однако, как мы увидим ниже, гибридизация здесь состоит только в объединении секретов, сами же криптосистемы работают независимо и никак не пересекаются алгоритмически. Обратите внимание, что сам стандарт ML-KEM никакой гибридизации не предписывает и не подразумевает, а использовать ML-KEM рекомендовано отдельно, поскольку, с точки зрения стандартизации NIST, это самодостаточная и стойкая криптосистема (KEM). Но в TLS всё же используется гибрид. Желание "подложить соломки" - конечно, похвально.
"Закатывайте полиномы бочками"
Итак, в TLS криптосистема ML-KEM используется сторонами для обмена сессионным секретом. Клиент присылает открытый ключ. Сервер отвечает шифротекстом, служащим для получения общего секрета. Сессионный секрет в TLS - это набор байтов, на основе которого вычисляются симметричные ключи для шифров, обеспечивающих фактическую защиту передаваемого между узлами трафика.
ML-KEM, в составе гибрида и в браузерах, сейчас применяется только для TLS версии 1.3. В принципе, алгоритм можно адаптировать для TLS 1.2, но сложно найти причины для этого: все предыдущие версии TLS активно выводятся из оборота, TLS 1.0 и 1.1 уже прямо объявлены нерекомендованными. В TLS версии 1.3 очень много отличий от 1.2. Несмотря на минимальную разность номеров версий, это два протокола с разной архитектурой. И именно потому, что TLS 1.3 устроен лучше, чем предыдущие версии, в протокол удалось прозрачно интегрировать новую криптосистему обмена ключами.
Посмотрим на практический пример. В качестве иллюстрации я использую выдачу экспериментального сервера TLS 1.3, который доступен по HTTP(S) и печатает все параметры и сообщения TLS в браузер (оговорка, на всякий случай: этот сервис разработан автором и запущен ещё в 2018 году, когда TLS 1.3 был в статусе черновика).
Код:
Type: 51 (0x0033); "key_share"
X25519MLKEM768 (0x11EC)
Hybrid: X25519 + ML-KEM-768
Len (octets, dec.): 1216
ML-KEM-768 client public key:
t[1] (packed):
B03142B3793AEE49C50F7C7D35A41F7C4C1AB793C18463B6DBC97A3E3445DE15
52EF3AB8E014808E810D380C63D29CA3775C31AF667AB456721292061BD32699
0052E7F270A766138E81A06DD575DC3AC1A67235D2CB936EAC5B44727EC60C5B
6E360A3B3258E8F7571E857CF8D9247ED57D9B529B4BCC0A2C12CFD2C7A138A7
2939C866CBD93DF8274BC9E78B6EF592591A073719495F18CEF3463BF7A59FB4
26B47F2000BEC706FEA122288367FE5083ED41C621F08D0173CE3646CE17623E
4F2CAE69085C22FBB132EAAFF6E52D26C1CBE6C1992FE83C501A16FB7AAC02EA
9FE1A7C67C8722A5794198F4163EC981CDA2737103C890644D8AF34347D86848
076FDBE68050D1B4C01ACDFAFA615D00C7652A4223653F65C95B76EAC97C2088
77AA64AF7ACBF717A482186E47AB9CFDB041C286CF95178489A24337D0BA9801
708C46914A0C4476B755C9070AFD16125294B55BA54CA6A0643B10109FE582F0
84AAD2BB6185D155BF93B108945CBE3C891E199F70443394892210A43EF6285C
t[2] (packed):
361487A671551F61C3C44A363427AFE57B5D2FA7959C83C3D0C44614A46BB3D6
84D70B660DB816AB980043F07870641C5B9C8FEB98B812173D78D424497055B8
C12E4FEC1BB280183A1048E02BBD4203AA91AC525B0C7ED9D66221B8C0E975BE
CC00463F11B287B89A89815FD94C67EF86275D588A086A1D4BC7ABBF8A6C5AC1
1AE08514091541EEE70B9BA9C3E17CB61CC19B32D61ECBA36CAE92A49E6A08E3
D6C49B81790F820E95716C6206309E2C91E228B5EB597A6871468F8B0450851C
DE4A03D64A641146AC616A589FBAC0D98B734DDC7B3E7C2238E05BA9A521DE83
BE99F14CC8228E0414AA4FAA74E5295DC154C1F603BCE8DB62C6DCCD5F401C69
099FD6865F8259942DC06B8EF481A2C567D0D74FD259792F384AD73C3950A1B8
A3DC4663DB9D55F2A9CA247B68A7A315A4464B196407E9866AF15AE9CA148FF0
08CC141F77819C2769931BF059B8EAB5E8B64ABFFA7E4D826A0967AC26A57D00
BB5BE81535E3634856F00EC63B201C6043009808D098773233CBE87CA5B4359D
t[3] (packed):
B0727DF9348B85763204031C9E223D05472C11C235B2427A8DB53D1389B8761C
1168063ED14287DE9C4060132981DB29C91131BB88023AD271EF099ABC2B947C
AC0E28447E05A8932207BF5E814E4E66358D006401814A71C15E4ED407B45A4F
C4952C027519E0D61C57707E4B02B7AF93860225360E26B4A06B68A4429895D1
C39A40441BAC19C77300EB89A2C355507D630A21A6360D7A5DE99910EDEB8CEE
CC30E355AC5BE57903FA465AAB1F678AA48B46B2FB0BA557735DC28385D901AA
60526BE0B07D74153169261A0756C15C884E050C3590F3A32917A63001C02C74
22E6BB8B1197440D7072F1DA322BDBC03D75C827570AD8A6BE8BBB7E45194045
07387DFA0659977BB9A9503FC12DBF19954F3033CF496D72B43496AB6249B945
BFDBB0A4B4C597F8B746808CC5630F68B7780FC283AB100905B09A330B0F5342
9AD4796F87F91B4EAA67947B004A5899A928780C11444DD67443BC41F87C5643
C7B524B40160E494A0FA249430BA19C59A74E5A23C224D660368360229529C04
Rho (bytes):
E1338433132C0295F0A5A044294DDDD142504D177EC11D6A42F7AD5E971E21DB
X25519:
x = 0x84F13557D2F2C913C242D5D26B61AB775FB5A153DF170838BFD8C449BDB9194D
X25519 (0x001D)
x = 0x84F13557D2F2C913C242D5D26B61AB775FB5A153DF170838BFD8C449BDB9194D
Secp256r1 (0x0017)
x = 0xD6514C4C2C74FC641068B5420FEBB0C35575928BF3664F7DC9C8D622E4387B9E
y = 0x5A87835B6CA70F50487D4661A1BB02381E9618AC8375355A71451DAF888FBF3FДамп содержит фрагмент начального сообщения - ClientHello. Сообщение сгенерировано браузером Firefox 135.0. Используется гибридная криптосистема X25519+ML-KEM. Данные, согласно спецификации TLS 1.3, передаются в составе клиентского TLS-расширения key_share, которое и отображено в дампе. Дамп - это уже результат разбора структуры расширения, где блоки данных обособлены и обозначены текстовыми префиксами. Исходное представление использует вариант "префиксного" кодирования ASN.1, как и почти везде в TLS. Что обозначают детали? Рассмотрим по порядку, сверху вниз.
X25519MLKEM768 (0x11EC)
- идентификатор криптосистемы. В TLS криптосистемы обозначаются двухбайтовыми индексами, а значения присваиваются организацией IANA. 0x11EC - индекс, соответствующий интересующей нас гибридной криптосистеме X25519+ML-KEM768. То есть, это не номер ML-KEM, а именно обозначение для конкретного гибрида. (К цифрам в названиях самих криптосистем мы ещё вернёмся.)
Сейчас в реестре IANA заведены идентификаторы для трёх вариантов гибридов с ML-KEM768: один для варианта с X25519 (0x11EC - X25519MLKEM768) и два - для протокола Диффи-Хеллмана на кривых P-256 и P-384, соответственно (0x11EB - SecP256r1MLKEM768, 0x11ED - SecP384r1MLKEM1024). Здесь мы рассматриваем "в байтах" только X25519+ML-KEM768, а про варианты с P-256 и P-384 будет тоже рассказано ниже, но уже без "байтовых" примеров.
Далее в дампе указан тип гибрида, длина данных, и выведена самая интересная часть - открытый ключ ML-KEM. Запись ключа состоит из четырёх блоков, обозначенных t[1,2,3] и Rho. Открытый ключ в ML-KEM-768 это квадратная матрица 3x3 и вектор из трёх элементов.
ML-KEM работает "на полиномах" (некоторые подробности будут ниже) и матрицах (векторах), элементами которых являются полиномы. Секретный ключ в ML-KEM - это вектор, обозначаемый s. Элементы данного вектора должны выбираться случайным образом по специальному алгоритму. Также конкретный сеанс криптосистемы использует матрицу, которая обозначается A (её размер в ML-KEM768 - 3x3). Открытый ключ получается из секретного по следующей формуле:
t = A∙s + ε
здесь, t - вектор, входящий в состав открытого ключа,
s - секретный ключ,
ε - секретный "маскирующий" вектор, "ошибка", в которой содержится половина криптографической сути ML-KEM и которая делает уравнение трудноразрешимым на практике (если бы не было ε, то получилось бы обычное уравнение, наверняка знакомое по курсу линейной алгебры, а если ε есть, то получается та трудная задача LWE, - Learning With Errors, - которая и даёт "решёточную" часть в названии ML-KEM). Для целей настоящей статьи важны только два объекта из упомянутых: матрица A и вектор t.
Тут необходимо оговорить, что в строгом определении ML-KEM встречается ещё много загадочных аббревиатур, которые раскрываются в ещё более загадочные полные названия. Например, ML-KEM не имела бы практического смысла без NTT для умножения полиномов. NTT здесь - Number-Theoretic Transform (теоретико-числовое преобразование). NTT позволяет умножать полиномы быстро. Но эти моменты остаются за рамками данной статьи.
Итак, в составе открытого ключа ML-KEM768 мы ожидаем матрицу 3x3. Куда делась матрица - сейчас разберёмся. Для начала найдём вектор. Вектор в дампе это t[1,2,3]. Получается, что для каждого элемента использовано 3212==384 байтов. Почему так много байтов требуется для записи элемента вектора? Потому что, как уже отмечалось, в ML-KEM этими элементами являются полиномы. Вектор состоит из трёх полиномов. Это полиномы степени 255, то есть, здесь 256 коэффициентов: a255x255 + a254x254 + ... + a1x1 + a0 (ну или можно записать в другую сторону, тогда a0 будет слева). Букву "икс" следует рассматривать как просто символ. Понятно, что полином полностью определяется перечислением коэффициентов (с сохранением порядка, конечно). Именно значения коэффициентов кодируются в байты, соответствующие записи конкретного полинома в ключе ML-KEM. Возникают новые вопросы: почему и как 256 коэффициентов превращаются в 384 байта? есть ли какие-то ограничения на значение каждого коэффициента?
Да, такие ограничения есть. В ML-KEM коэффициенты полиномов - это вычеты по модулю 3329 (простое число). Другими словами, это остатки от деления на 3329: {0..3328}. Число 3329 является первым чисто математическим параметром данной криптосистемы, который нам встретился. Для записи чисел от 0 до 3328 достаточно 12 битов. Для оптимизации записи значений ключей и шифротекстов в ML-KEM применяется целый ряд алгоритмов разной степени хитрости. Так, коэффициенты многочленов "сжимаются" в байты, которые рассматриваются как битовое поле: и если для записи одного коэффициента достаточно 12 битов, тогда два коэффициента можно уместить в 24 бита или в три байта. Заметная экономия. Особенно, если сравнить с программной реализацией "в лоб", при которой каждый коэффициент записывался бы, предположим, как uint16, то есть, в два байта. Если посчитать 12 битов и 256 коэффициентов, то получатся те самые 384 байта на один полином.
В ML-KEM есть умножение матриц и векторов, при этом элементами матриц и векторов являются полиномы, каждый из которых содержит 256 коэффициентов. Соответствующая математическая структура, если чуть более строго, называется модулем над кольцом, но для целей настоящей статьи это не так важно. Понятно, что за операциями с матрицами стоят операции с полиномами: полиномы здесь нужно складывать и умножать, чтобы получать новые элементы матриц. Арифметические операции с полиномами в ML-KEM проводятся по модулю, но этот модуль - тоже полином: x^256 + 1. Элементы соответствующей структуры (кольца) - полиномы степени не выше 255: степень больше получиться не может, потому что берётся остаток по модулю x^256 + 1. С точки зрения практики записи ключей и шифротекстов в TLS это означает, что полином не будет содержать более 256 коэффициентов, а каждый коэффициент - не потребует более 12 байтов. Но для полиномов шифротекста применяются другие методы кодирования, как мы увидим ниже, битов там расходуется даже меньше, чем при записи ключа.
То, что полиномы 256-разрядные, не является простым совпадением. Верхнеуровневый математический аппарат ML-KEM позволяет передать за одну итерацию протокола только один секретный элемент, один бит, формально. Это очень мало. Но так как практическая реализация ML-KEM оперирует полиномами, то этим передаваемым элементом будет один полином, в котором 256 коэффициентов. Схема использует округление значений, относительно среднего. Это означает, что каждый коэффициент может нести один бит информации (грубо говоря, меньше среднего - больше среднего: бит соответствует уменьшению неопределённости в два раза). Получается, что пусть передаётся один элемент кольца, но это 256 бит. И именно 256 бит составляют полезную разрядность ML-KEM, как схемы передачи ключа.
Что же происходит со вторым заявленным элементом - с матрицей 3x3? Каждый элемент этой матрицы - такой же полином, растянувшийся на 256 коэффициентов. Девять полиномов по 256 коэффициентов в каждом займут много байтов. Поэтому матрица просто не передаётся. Вместо неё передаётся порождающий параметр Rho разрядностью 256 бит, которые соответствуют 32 байтам. Матрица для ключа всё равно должна выбираться случайным образом, поэтому можно эту матрицу "развернуть" при помощи алгоритма, использующего хеш-функции, из начального 256-битного значения. Типовой для криптографии способ. Начальное значение - это и есть Rho. Схема предоставляет 256 бит энтропии, так что является достаточно стойкой.
X25519
- это открытая часть обмена X25519. Фактически, координата точки на эллиптической кривой, полученная по соответствующему X25519 алгоритму. Обратите внимание, что, при всех оптимизациях ML-KEM, запись ключа классической X25519 оказывается короче во много раз. Это особенность всех предлагаемых сейчас криптосистем с постквантовой стойкостью - их ключи/шифротексты очень большие по битовому объёму. Иногда разработчикам криптосистем удаётся уменьшить размер шифротекста, увеличив открытый ключ, или наоборот, но суммарный трафик, нужный для обмена, всё равно гораздо больше, чем у классических криптосистем, особенно, на эллиптических кривых. Свидетельствует ли это о том, что большое количество битов необходимо для обеспечения постквантовой стойкости? Нет, не свидетельствует. Обычно, дополнительные "мегабиты" возникают в результате оптимизации операций криптосистемы по скорости: потому что вторым важнейшим параметром, после стойкости, является количество и сложность вычислительных операций типичного процессора, затрачиваемых на осуществление криптографических преобразований.
После гибридного ключа X25519 и ML-KEM идут параметры "обычных" криптосистем, которые браузер, устанавливающий TLS-соединение, готов использовать немедленно: это простой, - не гибридный, - вариант X25519 и алгоритм Диффи-Хеллмана на кривой P-256 (ECDH/P-256 - Secp256r1).
Мы считаем, что сервер выбрал для согласования X25519+ML-KEM. В сообщении ClientHello сервер получил клиентский открытый ключ ML-KEM и открытую часть X25519. Поэтому сервер выполняет следующие операции: вычисляет свой открытый ключ и секрет X25519 (обычным способом), вычисляет и, используя клиентский открытый ключ ML-KEM, инкапсулирует секрет ML-KEM (можно сказать, что зашифровывает, но конкретный процесс в KEM отличается от обычного зашифрования). Обратите внимание, что обе криптосистемы используются совершенно независимо, ни о каком "переплетении" X25519 c ML-KEM речи не идёт. Теперь сервер получил два секрета - один из X25519, второй - ML-KEM. Эти секреты сервер объединяет в итоговый вывод простой конкатенацией. Также сервер получил открытый параметр X25519 и шифротекст ML-KEM. Эти два параметра сервер отправляет на сторону клиента, чтобы клиент вычислил общий секрет.
Код:
Type: 51 (0x0033); "key_share"
X25519MLKEM768 (0x11EC)
Len (octets, dec.): 1120
ML-KEM-768 cipher text:
U[1] (packed):
906CCA875A6678DE673DEBA64956F18BA1664C7D7C34FD4B47BC297EAE45FCC0
E1F1E1A124077B4814023B667AC2D3E3684637658C022DDB8372C8D3BE1AB0D0
980A6FBBADE50D2E3EF3D9C16662A8FFC60869AAEB2B87F48C21A2635EBF7A84
160AD1EA694D9981F0733BFBBC9A77EC6F2DA651478A2E2F7EFC701FBC83BACD
1F2FEC51D2CEC964C7A87A49B9443E4CABAA96050C9B506D934AA7069E6C3C84
E821516FC74754E5691F397E213D18E467C977CE83FA519135FC1AE86F06593C
A12C8D5F7EC67B46E29102C89E8024ABACA2332628C93718160501C807ACB169
F70B13D62B156622F18592650EABB928E964C79D23800042E12C9328939E2B5C
4EB6FBAD78069543881922B9AF782AF5E33F8DB8D3C20AC7DAA3E2DC83C7FDF4
9E7409D7C363AB65922C7FE1D8A17013DB8B4E8C14C1FDB08AB804B4AE79F38E
U[2] (packed):
ED1C54169D6668340001BD7CF1A5A948D4066C831064C3BA1B239715BAF5058C
06F21C3900FCA2555496EA6C08C267DC2D563D4F3030F86943D9AE0B30CB4717
CF6177457F790E5868288A0C774E5611B3D15534C10DEA58FAC9EA1971D462B8
83D0DE2298B742A1DA17393E1158D4BD84F2A45F488360AFD6AEB3BA8B7DC4B5
E81E547036963F81ABE441487E33B400C7BF0635F5194D5F0E587FE869AE8A44
1B1B0FB2D418D46D6B2326D7339AA81F85D18E1627513E47D4E6C011888B2681
85493DA1C9AF15050C17EDE2AD977535659006E119D9D96BE4813A5795DE7CA4
D31D66B74D1A5347F4E1913C58CD734F64BB8D040C723D7CF27A961DB83D6FFE
4311D27CC5B422BEA07CC0559675F8C55E0F231DED93434F64E24A3D2F1CA270
C00D650F80E2B96543737939D1C6E45FFC64CABFACBEAFCD45AE1F233E939273
U[3] (packed):
BB3E860E4183459EFB3522CBC0646F04A663DFCD413FDC8D36318DFD6CCBACB3
B9A85BAAA7E50660C5AA7D4F6211DD8B60431EA83FE748931EA78249CE5FE146
E3DD0D8025F58F5E8CAD487E7E07DB60D594939A9A7B07F24B446B8A5EA6F873
2C2BEC61E3F5D632AF895380E578C75BDAB13678646FEA4B6FB9AB6BA125E05B
637A83791BC8E9A27B1ECC2B3ED485E6F7DBE7D49DEAE676B2E70AB00048E269
06FE00A7F83C4BD85C901AA028E2E5F0C67F73BD4DCAC32CF5C69EACA91BF896
845C46A5122181C021A1E9E6FECBA1DFFC2F5859571288242DED0FC4A2502A80
1C93D8A2EDEA2C0D395CF5522246EF8D4DB0C3D1A5683FC4DFC1DC4332813BA2
DA55ADA407C76A4727917C972A26160C43F482FABA8B0381978321FEE56798E4
6161E2110318396CFD4DDE81693FA6EB814EAB3BC927F4A1FE4275264FC4116C
V (packed):
BB3E860E4183459EFB3522CBC0646F04A663DFCD413FDC8D36318DFD6CCBACB3
B9A85BAAA7E50660C5AA7D4F6211DD8B60431EA83FE748931EA78249CE5FE146
E3DD0D8025F58F5E8CAD487E7E07DB60D594939A9A7B07F24B446B8A5EA6F873
2C2BEC61E3F5D632AF895380E578C75BDAB13678646FEA4B6FB9AB6BA125E05B
X25519:
x = 0x145891E6697DAA111BD9A43EB39FA860847D09303D603128F82CE7451DAE456BДамп выше - фрагмент сообщения ServerHello, содержащий серверную часть обмена ключами.
В ответном сообщении сервера индекс криптосистемы совпадает - 0x11EC. Отличается размер сообщения: дело в том, что шифротекст ML-KEM имеет другую длину, не совпадающую с длиной представления ключа. При этом длина открытого серверного параметра X25519 такая же, как и в клиентском случае - 32 байта (256 бит). ML-KEM работает по схеме, которая схожа со старинным вариантом "шифрование RSA". Этот вариант довольно широко использовался в TLS долгие годы, пока его не запретили в TLS 1.3. Однако "шифрование RSA" работало в другую сторону: клиент генерировал секретное значение и зашифровывал его, используя открытый RSA-ключ из серверного сертификата. В ML-KEM секрет генерирует сервер, а не клиент, внутренний алгоритм инкапсуляции отличается от "шифрования RSA", но при этом в основе ML-KEM всё так же лежит схема зашифрования с открытым ключом, называемая K-PKE, так что аналогии с использованием RSA тут уместны. Конечно, протокол Диффи-Хеллмана, который выглядит несколько более интерактивным, тоже можно переписать в виде такой же KEM-схемы.
ML-KEM-768 cipher text
- шифротекст ML-KEM. Эта часть серверного key_share состоит из четырёх блоков, которые обозначены U[1,2,3] и V. По аналогии с записью открытого ключа ML-KEM нетрудно догадаться, что U - это вектор, элементами которого являются полиномы. Однако подсчёт количества байтов приводит к расхождению: в случае открытого ключа один полином занимал 384 байта, а здесь на один полином приходится только 320 байтов. Почему? Потому что коэффициенты полиномов шифротекста сжимаются иначе.
Шифротекст ML-KEM вычисляется по следующим двум формулам:
U = AT∙t + ε1
V = tT∙r + ε2 + round(m)
здесь m - это зашифровываемое сообщение, (Τ) обозначает обычное транспонирование (матрицы или вектора), r, ε1, ε2 - векторы (но с малыми коэффициентами полиномов), round() - функция округления, по правилам ML-KEM. То есть, U - это вектор из полиномов, V - это один полином.
Коэффициентов у полиномов шифротекста тоже 256, но в случае вектора U для записи каждого используется 10 битов вместо 12. Это возможно потому, что коэффициенты выбираются из меньшего интервала. Внутри ML-KEM используются представления, вводящие "отрицательные" значения для остатков, это позволяет получить нужные процедуры округления рациональных чисел, но также улучшает "степень упаковывания" полиномов.
Вторая часть шифротекста, обозначаемая V, представляет собой не вектор, а один полином, формирующий полезную нагрузку - именно "вариация", соответствующая данному полиному, позволяет извлечь из шифротекста секрет, который должен совпасть с переданным сервером. Особенности округления и допустимые интервалы погрешности при восстановлении значений позволяют полином V упаковать ещё сильнее, чем прочие полиномы: алгоритм оставляет всего четыре значащих бита. Это, опять же, полезный эффект, обусловленный принципом выбора коэффициентов V.
В составе гибридного обмена мы видим и X25519. Клиент получает оба секрета, - из шифротекста ML-KEM и секрет X25519, - после чего объединяет их простой конкатенацией, чтобы использовать в качестве основы для вычисления симметричных сеансовых ключей. Как и на стороне сервера - криптосистемы используются полностью независимо. В ML-KEM есть вероятность того, что секреты не совпадут. Однако базовые параметры криптосистемы подобраны таким образом, что эта вероятность чрезвычайно мала и составляет около 2-165 (для ML-KEM768).
Интересные особенности браузеров
TLS 1.3 позволяет передать несколько параметров для обмена ключами в составе начального сообщения ClientHello. Пример есть на исходном дампе. Браузер Firefox, как нетрудно заметить, значение X25519 передал одинаковое и для гибрида, и для "обычного" протокола. Это означает, что и секретный ключ X25519 браузером использован одинаковый. Так как криптосистема одна и та же, а отличие касается только "методов гибридизации", то использовать одинаковые значения вполне допустимо. Но при этом, например, браузер Chrome, который тоже присылает "отдельностоящий" ключ X25519 вместе с гибридным, передаёт разные значения. Хорошая демонстрация того, как браузеры можно различать по параметрам TLS.
Ключ и шифротекст ML-KEM потребляют много байтов. Особенно, если сравнивать с классическими эллиптическими криптосистемами. Использованный в качестве источника примеров экспериментальный сервер поддерживает мультипликативный вариант протокола Диффи-Хеллмана, который называется FFDHE3072, а из браузеров работает в Firefox. Число 3072 в названии обозначает битовую разрядность модуля, то есть, это длина записи ключа. Но даже 3072 бита - это всего лишь 384 байта, эквивалент одного полинома из ML-KEM768.
В ML-KEM, цифры, приписываемые к названию справа, тоже обозначают "разрядность", но это не битовая разрядность. Напротив, эти числа из названия следует воспринимать как длину секретного ключа в “базовых элементах”. Например, ML-KEM-768 работает в размерности три, что соответствует трём многочленам или 3*256 == 768 коэффициентам. Откуда и номер. Если бы размерность ключей была бы ровно три коэффициента, то взлом не составил бы труда и без всяких квантовых компьютеров. Для 768 коэффициентов – вычислительная сложность существенно выше.
А номер 25519 в X25519 - это всего лишь 2^255 - 19, простое число, используемое в качестве модуля данной криптосистемы.
Разносортные гибриды
Осталось рассмотреть другие варианты гибридизации ML-KEM с вариантами ECDH, из тех, которые уже получили индексы IANA. Это ML-KEM768(1024) вместе с DH на кривой P-256 и на кривой P-384. В данных схемах секретным параметром DH является X-координата точки на кривой, которая так же, как и в случае X25519, присоединяется к секрету ML-KEM. То есть, базовая схема полностью аналогична, но отличаются детали операций. Кривая P-384 имеет большую разрядность (в полном соответствии с цифрами в обозначении), поэтому соответствующий вариант ECDH позволит получить больше секретных битов именно в части ECDH, на ML-KEM это никак не влияет.