Merkle Tree Certificates and the next phase of the WebPKI

My name is Chris Patton. I work on PQ at Cloudflare. Today I'm going to talk about the post-quantum transition and how it pertains to the WebPKI. So I hope a lot of you attended Sharon Goldberg's talk from earlier in the day. She talked about the big picture of the post-quantum transition and there she sort of described two primary facets. One is encryption. The means by which we protect the confidentiality of packets as they're going over the Internet is of course under threat from quantum computers. Fortunately, the transition to post -quantum encryption has been well underway for a while and we've made very, very good progress there. That leaves authentication, the mechanism by which clients and servers authenticate one another over the Internet. And that's what we're going to talk about here. And in particular, we're going to talk about the WebPKI. That is the set of certificates that clients use to connect to servers securely. We're going to talk about Merkle Tree certificates. This is the technology the IETF is developing in order to make this transition as smooth as possible. And at the end, we'll talk a little bit about what does this mean for you and your organization. Spoiler alert. Unless you're a CA, you can kind of ignore a lot of this presentation. But if you work at a certificate authority, pay attention. Server authentication is the topic here. So TLS certificates. How do I know I'm connecting to Cloudflare.com? There's a whole slew of client authentication mechanisms deployed on the Internet and these matter quite a lot. We don't want to ignore these. But if you're an organization and you are working on a post -quantum transition, you have to make a priority list. And I think it's fair to say any prioritization of PQ transition tasks, the server side is going to float right to the top. And I guess we can argue about this in the Q&A if you disagree. Okay. So just to level set, what is a TLS certificate? Well, when a client wants to connect to a server, they exchange a sequence of messages. We call this a TLS handshake. And at the end of this exchange of messages, both parties derive an encryption key. And this is what they use to start protecting packets. The server authenticates itself by signing this handshake with its secret signing key. So think RSA or ECDSA. And the client has the corresponding public key and that's how it verifies the signature. And what it's doing here is it's asking the server, please confirm to me that you've observed the same sequence of messages as I did. And in so doing, it proves that there's no man in the middle in the connection. So the problem with this picture on this slide is that the client has the server's public key out of band. This is not going to scale. In practice, we have these entities called certificate authorities whose job it is to issue certificates for the server. So the client has the public key of the CA. It uses this to verify a signature over the server's public key. And it's going to do that before verifying the handshake over the transcript. And this is what we call the web PKI. It's the set of root certificates that are trusted by the majority of clients on the web. So browsers, CLIs, et cetera. So the threat is that the algorithms we rely on today, ECDSA and RSA, are vulnerable to quantum computers. And in particular, what we're worried about is in the next few years, perhaps, a quantum computation will be feasible that allows someone to compute the secret key from the public key. And thereafter, impersonate the server to any client that they want. Or even worse, the CA itself. And a lot of experts agree this is likely to be one of the main targets for early quantum computers. If you have a big, expensive quantum computer, you're not going to be targeting the small tail of websites. You're going to target Google .com. That's what we're thinking about here. So what do we do? Well, in theory, it's simple. There is an algorithm called MLDSA. That is post-quantum. We trust this algorithm. And we just need to replace classical algorithms like RSA and ECDSA with MLDSA. In practice, why is this hard? I guess I wouldn't be standing here trying to convince you that it's hard if it weren't hard. The problem is MLDSA is big. So ECDSA signatures are a measly 64 bytes. And MLDSA signature is 2.4 kilobytes. And that might not initially sound like a lot, but we have a lot of signatures in a typical TLS handshake these days. And, yeah. So we did a measurement study a few years ago and where we confirmed that, indeed, when you add 15 kilobytes to every handshake, you end up incurring a lot of latency that clients can notice on their site. So this is what we're trying to avoid. So you might ask yourselves, man, isn't there anything better? Well, cryptographers are looking at this. They continue to look at it. And so far, there is not a lot of great solutions. It's just a world of trade-offs. There are signatures out there with small public keys but big signatures or big public keys and small signatures. And neither of these trade-offs make sense in particular for TLS. Because we have to transmit both in the handshake, we need something that has a nice balance between the both. And right now, MLDSA is what we have. So what are we doing? We turn to protocol engineering. The thing that the IETF does, well, you know, you could argue about how good it does it. But it's what it does. Merkle Tree Certificates is the specification that is reengineering the WebPKI and TLS in order to make PQ fit. So the main way we're going to do this is through certificate transparency. So I'll talk about this on the next slide in detail. But for those who know what CT is, imagine what we're going to do is reuse the infrastructure we've already deployed for this purpose to get as much validation logic out of the TLS handshake that we can and sort of try to amortize it across multiple handshakes. So that's where we're going. So for those who don't know, certificate transparency is the goal of this is a web browser today is only going to accept a server certificate if that certificate appears in at least two locks. So this is Chrome's policy, and this is Firefox's policy, and a lot of other browsers follow suit. And the idea behind this is by making the issuing of certificates transparent, you allow site operators to monitor for misissuance. So misissuance meaning a certificate was issued without my knowledge or approval. And this happens all the time, sometimes by accident. But there are real-world attacks here that go back more than a decade now that motivated this move to CT. So what it is fundamentally is CT logs are append-only data structures that we want to be able to audit for misbehavior. So the log operator is supposed to just append certificates but never change anything in the log that was already logged. So that's the goal. How do we achieve that? Through this beautiful thing called a Merkle tree. So think of the Merkle tree as a binary tree where the leaves of this tree are the certificate entries themselves. In every node in this tree, we're going to compute by hashing everything beneath it. And by doing that, what we end up with is the root of this tree is a hash of everything below it. It sort of represents the state of the log at a point in time. So a log operator can periodically publish signed tree heads. And then I can verify the consistency of the tree between these tree heads. And it also allows this thing called an inclusion proof. So this is the set of nodes that proves that an entry in the log exists at some point in time as represented by the tree head. So this is the paradigm shift with MTCs as opposed to the way we thought of certificates until now. We're issuing by logging. What that means is every Merkle tree certificate CA, that is MTCCA, is going to operate a CT log and periodically publish these signed tree heads that clients will validate out of band. For transparency, we will have multiple cosigners, they're called, sign each tree head. And so this allows auditors to, it allows mirrors to mirror the log so that we can audit it from multiple perspectives. Yeah, so by doing this, in the handshake itself, we no longer need to send these cosignatures, the signatures from the MTCCA and the log mirrors. We just send an inclusion proof up to a verified tree head. And the client is supposed to validate this out of band. So the key takeaway here is basically what we're doing. All we send in the handshake is the server's public key, a signature over the handshake using that public key. And then we have an inclusion proof of that public key in the issuance log. And we somehow need to arrange for the client to verify that tree head out of band. So what does this all look like? So this is a real MTC from an experiment we ran this year with Chrome. And the only thing that is really different here is that the server's signature algorithm, I have a clicker, I have a pointer. This bit here, that's an inclusion proof. So that's not an ECDSA signature or an MLDSA signature. This is an inclusion proof of this whole entry in the certificate authorities log. So this leaves one bit we have to think about, though. So kind of the core problem we have is clients need to periodically validate these signed tree heads that they get. Imagine Chrome's infrastructure is pushing out validated tree heads to clients periodically. Let's say you turn off your laptop for a week because you went on vacation. When you come back online, you need to get everything that's been validated since you were last offline. And in the interim, we have to send you what's called a standalone MTC. And this is basically an inclusion proof plus the co-signatures that we talked about earlier. The signature from the MTCCA and the signature from each of the mirrors. So clients are going to be stale sometimes. That's the key takeaway here. But this system ends up still being pretty efficient as long as falling back to standalone certificates is rare. So how rare? Well, we measured with Chrome's support. We ran an experiment where for a subset of Cloudflare traffic and a subset of Chrome traffic, we deployed a version of MTCs that doesn't involve adding any new trust anchors. And what we saw in this experiment was, yes, clients do fall back about 2% of the time, which is not bad. We think we can do better. But in any case, we're gaining a lot of efficiency by not sending these signatures in every handshake. And that's really the name of the game. So where are we? Where do things stand? So the major root programs have announced intent to support Merple tree certificates. Chrome in particular has said they're not going to support PQ roots in their root store that don't support MTCs, meaning this is going to be required for the WebPKI. So that's why this matters. Other root programs have followed suit. There are also two MTCCAs in development right now. One is Let's Encrypt, of course. And then we announced that we're going to be a public CA at birthday week last year. And where we're sort of heading with all of this, all of these people coordinating to make this happen, we want to start issuing the first production MTCs in Q1 of next year. That's the goal. Okay. What does this all mean for you? If you're a Cloudflare customer, there's two things to think about. Client to edge and then edge to origin. Client to edge, you're good. So if we're going to manage MTC issuance for customers, and we're going to do this transparently without really informing you, at least for some classes of customers, because we believe it's important and it should be free. So that side's good. Client to origin, it depends on how your system's configured. Basically, look out for our software updates. Look out for changes you need to make to your ACME configuration to make this all go. Another option in the future will be Cloudflare Tunnel. You can configure from edge to origin. And we don't have PQ auth here yet, but this is coming very, very soon. So stay tuned. For everything else that's not Cloudflare, well, consider MTCs for your own internal PKIs. There are some advantages to using this regardless for your own internal purposes. The main thing I think I want everyone to know in this room is go make sure your server can support multiple certificates at once. This is very, very, very important. So you need ECDSA, perhaps RSA for legacy clients, but then you need to upgrade to MLDSA for clients that support it. And clients are going to tell you whether they support it. They're going to indicate it in the TLS handshake itself. So make sure your system can do this. You might ask yourself, when should I disable classical? Because how long are old clients going to be around? As we all know, the long tail is long. This is a complicated and hairy problem, and it's an ongoing discussion at IETF. IETF 127 is happening in two weeks here in the city, so come join us if you want to hear more or express an opinion. That's it for me. Thank you very much for your attention.