Интернет быстрее и безопаснее: представляем сертификаты на основе деревьев Меркла

Мир участвует в гонке по созданию первого квантового компьютера, способного решать практические задачи, недостижимые даже для самых мощных традиционных суперкомпьютеров. Хотя парадигма квантовых вычислений сулит множество преимуществ, она также угрожает безопасности Интернета, взламывая значительную часть криптографии, на которую мы привыкли полагаться.

Чтобы смягчить эту угрозу, Cloudflare помогает мигрировать Интернет на постквантовую (PQ) криптографию. На сегодняшний день около 50% трафика к периферийной сети Cloudflare защищено от самой насущной угрозы: злоумышленника, который может перехватывать и сохранять зашифрованный трафик сегодня, а затем расшифровать его в будущем с помощью квантового компьютера. Это называется угрозой «собрать сейчас, расшифровать позже» .

Однако это лишь одна из угроз, которые нам необходимо устранить. Квантовый компьютер также можно использовать для взлома TLS-сертификата сервера, что позволит злоумышленнику выдавать себя за сервер для ничего не подозревающих клиентов. Хорошая новость заключается в том, что у нас уже есть PQ-алгоритмы, которые мы можем использовать для квантово-устойчивой аутентификации. Плохая новость в том, что внедрение этих алгоритмов в TLS потребует значительных изменений в одной из самых сложных и критически важных для безопасности систем Интернета: Веб-инфраструктуре открытых ключей (WebPKI).

Основная проблема — огромный размер этих новых алгоритмов: подписи для ML-DSA-44, одного из самых производительных PQ-алгоритмов, стандартизированных NIST, имеют длину 2420 байт, по сравнению с всего 64 байтами для ECDSA-P256, самой популярной не-PQ подписи, используемой сегодня; а его открытые ключи имеют длину 1312 байт по сравнению с всего 64 байтами для ECDSA. Это примерно 20-кратное увеличение размера. Что еще хуже, среднее TLS-рукопожатие включает несколько открытых ключей и подписей, что в сумме составляет десятки килобайт накладных расходов на одно рукопожатие. Этого достаточно, чтобы оказать заметное влияние на производительность TLS.

Это делает прямую замену на PQ-сертификаты сложной задачей для включения уже сегодня: они не приносят никаких преимуществ в безопасности до Q-дня — дня появления криптографически значимого квантового компьютера — но они ухудшают производительность. Мы могли бы сидеть и ждать, пока до Q-дня останется год, но это игра с огнем. Миграции всегда занимают больше времени, чем ожидается, и, ожидая, мы рискуем безопасностью и конфиденциальностью Интернета, которые дороги для нас.

Понятно, что мы должны найти способ сделать постквантовые сертификаты достаточно дешевыми для развертывания сегодня по умолчанию для всех — а не только для тех, кто может себе это позволить. В этом посте мы познакомим вас с планом, который мы разработали вместе с отраслевыми партнерами для IETF, по перепроектированию WebPKI, чтобы обеспечить плавный переход к PQ-аутентификации без потери производительности (и, возможно, с ее улучшением!). Мы предоставим обзор одного конкретного предложения, называемого Merkle Tree Certificates (MTCs), цель которого — сократить количество открытых ключей и подписей в TLS-рукопожатии до абсолютного необходимого минимума.

Но слова — дешевы. Мы знаем по опыту, что, как и при любом изменении в Интернете, крайне важно тестировать рано и часто. Сегодня мы объявляем о нашем намерении развернуть MTCs в экспериментальном порядке в сотрудничестве с Chrome Security. В этом посте мы опишем масштабы этого эксперимента, что мы надеемся из него узнать и как мы обеспечим его безопасное проведение.

Почему в TLS-рукопожатии так много открытых ключей и подписей?

Начнем с основ криптографии. Когда ваш браузер подключается к веб-сайту, он просит сервер аутентифицировать себя, чтобы убедиться, что он общается с настоящим сервером, а не с самозванцем. Обычно это достигается с помощью криптографической примитивы, известной как схема цифровой подписи (например, ECDSA или ML-DSA). В TLS сервер подписывает сообщения, которыми обмениваются клиент и сервер, используя свой секретный ключ, а клиент проверяет подпись с помощью открытого ключа сервера. Таким образом, сервер подтверждает клиенту, что у них был один и тот же разговор, поскольку только сервер мог произвести действительную подпись.

Если клиент уже знает открытый ключ сервера, то для аутентификации сервера требуется всего 1 подпись. Однако на практике это не совсем вариант. Сегодня веб состоит примерно из миллиарда TLS-серверов, поэтому было бы нереалистично снабжать каждого клиента открытым ключом каждого сервера. Более того, набор открытых ключей будет меняться со временем по мере появления новых серверов и смены ключей существующими, поэтому нам потребуется какой-то способ передавать эти изменения клиентам.

Эта проблема масштабирования лежит в основе проектирования всех PKI.

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

Сертификат связывает открытый ключ с идентификатором сервера — обычно его DNS-именем, например, cloudflareresearch.com. Сертификат подписывается Центром сертификации (CA), открытый ключ которого известен клиенту. Помимо проверки подписи рукопожатия сервера, клиент проверяет подпись этого сертификата. Это устанавливает цепочку доверия: принимая сертификат, клиент доверяет, что CA подтвердил, что открытый ключ действительно принадлежит серверу с этой идентичностью.

Клиенты обычно настроены на доверие многим CA и должны быть снабжены открытым ключом для каждого. Однако все намного проще, поскольку CA всего сотни, а не миллиарды. Кроме того, новые сертификаты можно создавать без необходимости обновлять клиентов.

Эти эффективности достигаются относительно низкой ценой: для тех, кто считает, это +1 подпись и +1 открытый ключ, в сумме 2 подписи и 1 открытый ключ на TLS-рукопожатие.

Однако это еще не конец истории. По мере развития WebPKI эти цепочки доверия стали немного длиннее. В наши дни обычно цепочка состоит из двух или более сертификатов, а не из одного. Это происходит потому, что CA иногда необходимо менять свои ключи, как и серверам. Но прежде чем они смогут начать использовать новый ключ, они должны распространить соответствующий открытый ключ среди клиентов. Это требует времени, поскольку миллиарды клиентов должны обновить свои хранилища доверия. Чтобы заполнить пробел, CA иногда использует старый ключ для выдачи сертификата на новый и добавляет этот сертификат в конец цепочки.

Это +1 подпись и +1 открытый ключ, что доводит нас до 3 подписей и 2 открытых ключей. И нам еще есть куда двигаться.

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

Автоматизация помогает, но атаки все еще возможны, а ошибки почти неизбежны. Ранее в этом году несколько сертификатов для зашифрованного резолвера Cloudflare 1.1.1.1 были выданы без нашего участия или авторизации. По-видимому, это произошло случайно, но, тем не менее, подвергло риску пользователей 1.1.1.1. (Неправомерно выданные сертификаты с тех пор были отозваны.)

Обеспечение возможности обнаружения неправомерной выдачи — задача экосистемы Certificate Transparency (CT). Основная идея заключается в том, что каждый сертификат, выданный CA, добавляется в публичный журнал. Серверы могут проверять эти журналы на наличие сертификатов, выданных на их имя. Если когда-либо будет выдан сертификат, который они сами не запрашивали, оператор сервера может доказать факт выдачи, и экосистема PKI может принять меры, чтобы клиенты не доверяли этому сертификату.

Крупные браузеры, включая Firefox, Chrome и его производные, требуют, чтобы сертификаты были залогированы, прежде чем им можно будет доверять. Например, Chrome, Safari и Firefox будут принимать сертификат сервера только в том случае, если он появляется как минимум в двух журналах, которым браузер настроен доверять. Эту политику легко сформулировать, но сложно реализовать на практике:

1. Исторически эксплуатация CT-журнала была довольно дорогой. Журналы поглощают миллиарды сертификатов за время своего существования: когда происходит инцидент или даже просто при высокой нагрузке, журналу может потребоваться некоторое время, чтобы сделать новую запись доступной для аудиторов.

2. Клиенты не могут самостоятельно проводить аудит журналов, поскольку это раскрыло бы историю их просмотров (т.е. серверы, к которым они хотели подключиться) операторам журналов.

Решение обеих проблем заключается в включении подписи от журнала CT вместе с сертификатом. Подпись создается немедленно в ответ на запрос о внесении сертификата в журнал и подтверждает намерение журнала включить сертификат в журнал в течение 24 часов.

Согласно политике браузеров, прозрачность сертификатов добавляет +2 подписи к TLS-рукопожатию, по одной для каждого журнала. В результате в типичном рукопожатии в общедоступной сети у нас оказывается 5 подписей и 2 открытых ключа.

WebPKI — это живая, динамичная и высоко распределенная система. Нам приходилось многократно ее исправлять на протяжении лет, чтобы поддерживать ее работу, но в целом она довольно хорошо удовлетворяла наши потребности — до сих пор.

Ранее, когда нам требовалось обновить что-то в WebPKI, мы просто добавляли еще одну подпись. Эта стратегия работала, потому что традиционная криптография очень дешева. Но 5 подписей и 2 открытых ключа в среднем для каждого TLS-рукопожатия — это уже слишком много для более крупных PQ-подписей, которые скоро появятся.

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

Сертификаты на Дереве Меркла (MTC) — это предложение для следующего поколения WebPKI, которое мы реализуем и планируем развернуть в экспериментальном порядке. Его ключевые особенности следующие:

1. Вся информация, необходимая клиенту для проверки Сертификата на Дереве Меркла, может распространяться внеполосно. Если клиент достаточно обновлен, то для TLS-рукопожатия требуется всего 1 подпись, 1 открытый ключ и 1 доказательство включения в дерево Меркла. Это довольно мало, даже если мы используем постквантовые алгоритмы.

2. Спецификация MTC делает прозрачность сертификатов неотъемлемой функцией PKI, обязывая каждый УЦ вести собственный журнал именно тех сертификатов, которые они выпускают.

Давайте немного заглянем под капот. Ниже представлен MTC, сгенерированный одним из наших внутренних тестов. Он передавался бы с сервера клиенту во время TLS-рукопожатия:

-----BEGIN CERTIFICATE-----
MIICSzCCAUGgAwIBAgICAhMwDAYKKwYBBAGC2ksvADAcMRowGAYKKwYBBAGC2ksv
AQwKNDQzNjMuNDguMzAeFw0yNTEwMjExNTMzMjZaFw0yNTEwMjgxNTMzMjZaMCEx
HzAdBgNVBAMTFmNsb3VkZmxhcmVyZXNlYXJjaC5jb20wWTATBgcqhkjOPQIBBggq
hkjOPQMBBwNCAARw7eGWh7Qi7/vcqc2cXO8enqsbbdcRdHt2yDyhX5Q3RZnYgONc
JE8oRrW/hGDY/OuCWsROM5DHszZRDJJtv4gno2wwajAOBgNVHQ8BAf8EBAMCB4Aw
EwYDVR0lBAwwCgYIKwYBBQUHAwEwQwYDVR0RBDwwOoIWY2xvdWRmbGFyZXJlc2Vh
cmNoLmNvbYIgc3RhdGljLWN0LmNsb3VkZmxhcmVyZXNlYXJjaC5jb20wDAYKKwYB
BAGC2ksvAAOB9QAAAAAAAAACAAAAAAAAAAJYAOBEvgOlvWq38p45d0wWTPgG5eFV
wJMhxnmDPN1b5leJwHWzTOx1igtToMocBwwakt3HfKIjXYMO5CNDOK9DIKhmRDSV
h+or8A8WUrvqZ2ceiTZPkNQFVYlG8be2aITTVzGuK8N5MYaFnSTtzyWkXP2P9nYU
Vd1nLt/WjCUNUkjI4/75fOalMFKltcc6iaXB9ktble9wuJH8YQ9tFt456aBZSSs0
cXwqFtrHr973AZQQxGLR9QCHveii9N87NXknDvzMQ+dgWt/fBujTfuuzv3slQw80
mibA021dDCi8h1hYFQAA
-----END CERTIFICATE-----

Выглядит как обычный PEM-кодированный сертификат. Давайте декодируем его и посмотрим на параметры:

$ openssl x509 -in merkle-tree-cert.pem -noout -text
Certificate:
    Data:
        Version: 3 (0x2)
        Serial Number: 531 (0x213)
        Signature Algorithm: 1.3.6.1.4.1.44363.47.0
        Issuer: 1.3.6.1.4.1.44363.47.1=44363.48.3
        Validity
            Not Before: Oct 21 15:33:26 2025 GMT
            Not After : Oct 28 15:33:26 2025 GMT
        Subject: CN=cloudflareresearch.com
        Subject Public Key Info:
            Public Key Algorithm: id-ecPublicKey
                Public-Key: (256 bit)
                pub:
                    04:70:ed:e1:96:87:b4:22:ef:fb:dc:a9:cd:9c:5c:
                    ef:1e:9e:ab:1b:6d:d7:11:74:7b:76:c8:3c:a1:5f:
                    94:37:45:99:d8:80:e3:5c:24:4f:28:46:b5:bf:84:
                    60:d8:fc:eb:82:5a:c4:4e:33:90:c7:b3:36:51:0c:
                    92:6d:bf:88:27
                ASN1 OID: prime256v1
                NIST CURVE: P-256
        X509v3 extensions:
            X509v3 Key Usage: critical
                Digital Signature
            X509v3 Extended Key Usage:
                TLS Web Server Authentication
            X509v3 Subject Alternative Name:
                DNS:cloudflareresearch.com, DNS:static-ct.cloudflareresearch.com
    Signature Algorithm: 1.3.6.1.4.1.44363.47.0
    Signature Value:
        00:00:00:00:00:00:02:00:00:00:00:00:00:00:02:58:00:e0:
        44:be:03:a5:bd:6a:b7:f2:9e:39:77:4c:16:4c:f8:06:e5:e1:
        55:c0:93:21:c6:79:83:3c:dd:5b:e6:57:89:c0:75:b3:4c:ec:
        75:8a:0b:53:a0:ca:1c:07:0c:1a:92:dd:c7:7c:a2:23:5d:83:
        0e:e4:23:43:38:af:43:20:a8:66:44:34:95:87:ea:2b:f0:0f:
        16:52:bb:ea:67:67:1e:89:36:4f:90:d4:05:55:89:46:f1:b7:
        b6:68:84:d3:57:31:ae:2b:c3:79:31:86:85:9d:24:ed:cf:25:
        a4:5c:fd:8f:f6:76:14:55:dd:67:2e:df:d6:8c:25:0d:52:48:
        c8:e3:fe:f9:7c:e6:a5:30:52:a5:b5:c7:3a:89:a5:c1:f6:4b:
        5b:95:ef:70:b8:91:fc:61:0f:6d:16:de:39:e9:a0:59:49:2b:
        34:71:7c:2a:16:da:c7:af:de:f7:01:94:10:c4:62:d1:f5:00:
        87:bd:e8:a2:f4:df:3b:35:79:27:0e:fc:cc:43:e7:60:5a:df:
        df:06:e8:d3:7e:eb:b3:bf:7b:25:43:0f:34:9a:26:c0:d3:6d:
        5d:0c:28:bc:87:58:58:15:00:00

Хотя некоторые параметры, вероятно, выглядят знакомо, другие покажутся необычными. С знакомой стороны, субъект и открытый ключ — это именно то, что мы могли бы ожидать: DNS-имя — cloudflareresearch.com, а открытый ключ предназначен для знакомого алгоритма подписи, ECDSA-P256. Конечно, этот алгоритм не является PQ — в будущем мы бы поместили туда ML-DSA-44.

С необычной стороны, OpenSSL, похоже, не распознает алгоритм подписи издателя и просто выводит сырой OID и байты подписи. На это есть веская причина: в MTC вообще нет подписи! Так на что же мы смотрим?

Хитрость заключается в том, чтобы опускать подписи: УЦ на Дереве Меркла (MTCA) выпускает свои бесподписные сертификаты пакетами, а не по отдельности. Вместо подписи сертификат содержит доказательство включения сертификата в пакет сертификатов, подписанный MTCA.

Чтобы понять, как работают доказательства включения, давайте рассмотрим слегка упрощенную версию спецификации MTC. Для выпуска пакета MTCA размещает неподписанные сертификаты в структуре данных, называемой деревом Меркла, которая выглядит так:

Каждый лист дерева соответствует сертификату, а каждый внутренний узел равен хешу своих дочерних узлов. Чтобы подписать пакет, MTCA использует свой секретный ключ для подписи корня дерева. Структура дерева гарантирует, что каждый сертификат в пакете был подписан MTCA: если бы мы попытались изменить биты любого из сертификатов, значение корня дерева стало бы другим, что привело бы к неудаче проверки подписи.

Доказательство включения для сертификата состоит из хеша каждого соседнего узла вдоль пути от сертификата к корню дерева:

При наличии проверенного корня дерева этой последовательности хешей достаточно, чтобы доказать включение сертификата в дерево. Это означает, что для проверки MTC клиенту также необходимо получить подписанный корень дерева от MTCA.

В этом заключается ключ к эффективности MTC:

1. Подписанные корни деревьев могут распространяться клиентам внеполосно и проверяться офлайн. Каждый проверенный корень дерева может затем использоваться для проверки любого сертификата в соответствующем пакете, устраняя необходимость получать подпись для каждого серверного сертификата.

2. Во время TLS-рукопожатия клиент сообщает серверу, какие корни деревьев у него есть. Если у сервера есть бесподписный сертификат, покрытый одним из этих корней, то он может использовать этот сертификат для аутентификации. Это 1 подпись, 1 открытый ключ и 1 доказательство включения на рукопожатие, и все они относятся к аутентифицируемому серверу.

Это была упрощенная версия. В полной версии MTC есть еще несколько наворотов. Во-первых, она не создает отдельное дерево Меркла для каждого пакета, а растет одно большое дерево, которое используется для лучшей прозрачности. По мере роста этого дерева периодически выбираются корни (под)деревьев для поставки в браузеры, которые мы называем вехами. В обычном случае браузеры смогут получать самые свежие вехи, а серверы могут ждать выпуска пакетов, но нам нужен запасной вариант: MTC также поддерживает сертификаты, которые могут быть выпущены немедленно и не требуют для проверки наличия вех, но они не такие компактные. Сервер будет предоставлять оба типа сертификатов на дереве Меркла, так что обычный случай будет быстрым, а исключительный — медленным, но, по крайней мере, он будет работать.

С тех пор, как появились ранние проекты MTC, мы с нетерпением ждали возможности поэкспериментировать с этой идеей. В соответствии с принципом IETF «работающий код», зачастую для устранения недочётов в проекте требуется реализация протокола. В то же время мы не можем рисковать безопасностью пользователей. В этом разделе мы описываем наш подход к экспериментированию с аспектами проекта Merkle Tree Certificates без изменения каких-либо отношений доверия.

Начнём с того, что мы надеемся узнать. У нас много вопросов, ответы на которые могут либо подтвердить правильность подхода, либо выявить подводные камни, требующие переработки протокола — фактически, реализация раннего черновика MTC, выполненная Максимилианом Полем и Мией Селестой, сделала именно это. Мы хотим знать:

Что ломается? Окостенение протокола (тенденция, когда ошибки реализаций затрудняют изменение протокола) — это постоянная проблема при развёртывании изменений протокола. Для TLS в частности, несмотря на встроенную гибкость, раз за разом мы обнаруживали, что если этой гибкостью не пользоваться регулярно, то появятся ошибки в реализациях и промежуточные устройства, которые ломаются, сталкиваясь с неизвестными им вещами. Развёртывание TLS 1.3 заняло на годы дольше, чем мы надеялись, именно по этой причине. А совсем недавно внедрение постквантового обмена ключами в TLS привело к разделению Client Hello на несколько TCP-пакетов, к чему многие промежуточные устройства не были готовы.

Каково влияние на производительность? На самом деле, мы ожидаем, что MTC уменьшат размер рукопожатия даже по сравнению с сегодняшними не-PQ сертификатами. Они также снизят нагрузку на ЦП: проверка подписи ML-DSA примерно так же быстра, как ECDSA, и количество подписей, которые нужно проверять, будет гораздо меньше. Следовательно, мы ожидаем снижения задержки. Мы хотим посмотреть, будет ли measurable улучшение производительности.

Какая доля клиентов будет оставаться актуальной? Для получения выгоды в производительности от MTC требуется, чтобы клиенты и серверы были примерно синхронизированы друг с другом. Мы ожидаем, что у MTC будет довольно короткий срок жизни, около недели. Это означает, что если последняя контрольная точка клиента старше недели, серверу придётся откатиться к использованию большего сертификата. Знание того, как часто происходит этот откат, поможет нам настроить параметры протокола так, чтобы сделать откаты менее вероятными.

Чтобы ответить на эти вопросы, мы реализуем поддержку MTC в нашем стеке TLS и в нашей инфраструктуре выпуска сертификатов. Со своей стороны, Chrome реализует поддержку MTC в своём собственном стеке TLS и развернёт инфраструктуру для распространения контрольных точек среди своих пользователей.

Как мы делали в прошлых экспериментах, мы планируем включить MTC для части наших бесплатных клиентов с достаточным трафиком, чтобы мы могли получить полезные измерения. Chrome будет контролировать экспериментальное развёртывание: они могут наращивать темп постепенно, проводя измерения по ходу дела и откатывая изменения, если и когда обнаруживаются ошибки.

Что оставляет нам один последний вопрос: кто будет управлять Merkle Tree CA?

Создание полноценного ЦА — непростая задача: чтобы крупные браузеры начали доверять, требуются годы. Именно поэтому Cloudflare не станет «настоящим» ЦА в этом эксперименте, и Chrome не будет доверять нам напрямую.

Вместо этого, чтобы добиться прогресса в разумные сроки, не жертвуя должной осмотрительностью, мы планируем «имитировать» роль MTCA. Мы будем запускать MTCA (на Workers на основе наших StaticCT-журналов), но для каждого выпущенного MTC мы также публикуем существующий сертификат от доверенного ЦА, который с ним согласуется. Мы называем это сертификатом начальной загрузки. Когда инфраструктура Chrome получает обновления из нашего журнала MTCA, она также загружает эти сертификаты начальной загрузки и проверяет, согласуются ли они. Только в случае согласованности она продолжит передавать соответствующие контрольные точки клиентам Chrome. Другими словами, Cloudflare, по сути, просто «перекодирует» существующий сертификат (с проверкой домена, выполненной доверенным ЦА) в MTC, а Chrome использует прозрачность сертификатов, чтобы удерживать нас в рамках.

Поскольку почти 50% нашего трафика уже защищено постквантовым шифрованием, мы на полпути к полностью постквантово безопасному Интернету. Однако вторая часть нашего пути — постквантовые сертификаты — является самой сложной на сегодняшний день. Простая замена «в лоб» оказывает заметное влияние на производительность и не даёт преимуществ в безопасности до наступления Q-дня. Это означает, что сегодня её сложно продать как решение, включённое по умолчанию. Но здесь мы играем с огнём: миграция всегда занимает больше времени, чем ожидается. Если мы хотим сохранить повсеместно приватный и безопасный Интернет, нам нужно постквантовое решение, которое достаточно производительно, чтобы быть включённым по умолчанию уже сегодня.

Merkle Tree Certificates (MTC) решают эту проблему, сокращая количество подписей и открытых ключей до абсолютного минимума, сохраняя при этом основные свойства WebPKI. Мы планируем развернуть MTC для части бесплатных аккаунтов к началу следующего года. Это не затрагивает ни одного посетителя, который не является частью эксперимента Chrome. Для тех, кто участвует, благодаря сертификатам начальной загрузки, нет никакого влияния на безопасность.