0:02My 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 web PKI. 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 in 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.

0:48And that's what we're going to talk about here. And in particular, we're going to talk about the web. 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. All right. 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.

1:35But 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 saying, signing this handshake with its secret signing key.

2:20So 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 had the same, you've observed the same sequence of messages as I did. And by 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 public 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.

3:05And it's going to do that before verifying the public key, the handshake over the transcript. And this is what we call the web PKI. It's the... of root certificates that are trusted by the majority of clients on the web. So browsers, CLIs, etc. So the threat is that the algorithms we rely on today, ECDSA and NRSA, 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.

3:51And 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 tale 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.

4:38So ECDSA is signatures are a measly 64 bytes and MLDSA signature is 2 .4 kilobytes. And that doesn't might not initially sound like a lot, but we have a lot of signatures in a typical TLS handshake these days. And, um, and, uh, 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. 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. There are, it's just a world of trade -offs.

5:27There are signatures out there with small public keys, but big signatures or big public keys and small signatures. And neither of these trade-offs sense in particular for tls we need something because we have to transmit both in the handshake we need something that it 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 um it's what it does merkle tree certificates is the specification that is re-engineering the web PKI, and TLS in order to make PQ fit. So the main way we're going to do this is through certificate transparency.

6:16So 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 app validation logic out of the TLS handshake that we can 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 logs 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.

7:06So 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.

7:57and 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 a 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 publish signed periodically publish signed tree heads and then i can verify the consistency of the tree uh 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 allows, yeah. Okay. So this is the paradigm shift with MTCs as opposed to the way we thought of certificates.

8:53now. 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 co -signers, 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.

9:28Yeah, so by doing this, in the handshake itself, we no longer need to send these co-signatures, 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 uh this with Chrome.

10:17And 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 authority's log. So this leaves one bit we have to to think about though. So, um, the, the kind of the core problem we have is clients need to periodically validate these signed tree heads that they get, you know, imagine Chrome's infrastructure is pushing out validated tree heads to clients periodically. Uh, let's say you turn off your laptop for a week cause you went on vacation.

11:05Uh, 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.

11:54And 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 the 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 Merpletree 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 web PKI. that's why this matters. Other root programs have followed suit. There are also two MTC CAs in development right now.

12:45One 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 what we're sort of like, 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.

13:35So that's just, you know, 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, you know, 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.

14:22So you need ECDSA, perhaps RSA for legacy clients, but then you need to upgrade to MLDSA for clients that support it. And clients are gonna tell you whether they support it. They're gonna indicate it in the TLS handshake itself. So make sure your system can do this. You might ask yourself, what about, you know, when should I disable classical? Because how, you know, how long are old clients gonna be around? As we all know, the tail, the long tail was long. This is a complicated and hairy problem and it's an ongoing discussion at IETF. IETF-127 has had it. 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.