Next week at IETF 124, there's a Birds-of-a-Feather session that will kick off the standardization process here.
I think Merkle Tree Certificates a promising option. I'll be participating in the standardization efforts.
Chrome has signalled in multiple venues that they anticipate this to be their preferred (or only) option for post-quantum certificates, so it seems fairly likely we will deploy this in the coming years
I work for Let's Encrypt, but this is not an official statement or promise to implement anything yet. For that you can subscribe to our newsletter :)
Here’s what I’m not following in general about the Post Quantum encryption studies.
Don’t we already just use the certificates to just negotiate the final encryption keys? Wouldn’t a quantum computer still crack the agreed upon keys without the exchange details?
There's a section missing on the inclusion proof and what exactly the clients will be getting.
If I understand this correctly each CA publishes a signed list of landmarks at some cadence (weekly)
For the certs you get the landmark (a 256-bit hash) and the hashes along the merkle path to the leaf cert's hash. For a landmark that contains N certs, you need to include log2(N) * hash_len bytes and perform log2(N) hash computations.
For a MTC signature that uses a 256bit hash and N=1 million that's about 20*32=620bytes.
Is this the gist of it?
I'm really curious about the math behind deciding the optimal landmark size and publishing cadence
I think MTC is best described as a new signature algorithm for signing certificates where the value is a Merkle tree inclusion proof. This is quite clever. I like it.
> During the TLS handshake, the client tells the server which treeheads it has.
I don’t love the idea of giving every server I connect to via TLS the ability to fingerprint me by how recently (or not) I’ve fetched MTC treeheads. Even worse if this is in client hello, where anyone on the network path can view it either per connection or for my DoH requests to bootstrap encrypted client hello.
If your browser is online on an unrestricted network, then the tree heads will be kept up to date, and this will leak nothing. If you had your laptop closer for a weekend, open it up immediately and visit a website before your browser had a chance to update, well, you leak for maybe a minute or two you had your laptop closed for a weekend. So it's not that much. But we'll want to see how we can reduce this as much as possible.
It can't possibly be updating continuously in real time, can it? Especially for battery devices, a constant background thread polling for updates seems untenable.
Sure, but unlike the CRL checks the server gets to directly know how recently the client fetched the update if my understanding is correct. Knowing which landmarks the client has would likely give you a fairly precise picture of the update time, since more frequent landmarks yields smaller MTC proofs.
Spitballing here, would it still meet the needs of the protocol if the client offered which MTCAs it has (no version information), the server sends back some “typical” depth (say, 3 levels up the tree), then the client can decide to either:
* Accept the MTC
* Request a deeper traversal, following some super linear growth like fib numbers. In that case, they’d communicate “give me up to 5 nodes above your leaf”
* Reject the MTC
* Request the full certificate for “traditional” validation
The server still has a side channel for “how recently updated is this client” by knowing how many levels of inclusion proofs needed to be shared, but this is much less signal than knowing exactly which landmarks a client has.
Regardless of the strengths of this, I can't read this slop. A third of the way in, and:
> Instead of expecting the client to know the server's public key in advance, the server might just send its public key during the TLS handshake. But how does the client know that the public key actually belongs to the server? This is the job of a certificate.
Are you kidding me? You don't know your audience on an article at the nexus of certificate transparency and post-quantum cryptography well-enough to understand that this introduction to PKI isn't required?
Know your audience. Turning over your voice to an AI doesn't do that for you. It will waste everyone's time on thousands of words of vapid nonsense.
> During the TLS handshake, the client tells the server which treeheads it has.
If the first time the client doesn't know what root the server's certificate will chain to, therefore it doesn't tell the server what treeheads it has, and so the client gets a full certificate, and then the client caches this to remember for later connections, then... that could work, though it's a slight metadata leak.
Alternatively the client could send the treeheads for all the roots it trusts. That's going to bloat the ClientHello and... it's going to leak a bit of metadata unless if the client does anything other than claim to trust all roots blessed by the CA/Browser Forum, or the Chrome Root Program.
You only need to send one treehead per MTCA. From that one treehead the server can infer it must also have the previous few. If that's still too much, we can compress it even further by only sending "I trust the standard CAs of Mozilla plus/minus some CAs and the stalest treehead I have has this timestamp". That'll be just a few bytes.
Yes, a timestamp and a code for which set of trust anchors it trusts should be enough. Or even just a timestamp. The server is not going to have lots of certs chaining to many roots, so the client's trust anchor set is really not that relevant. The timestamp can be in coarse increments.
I took some rough notes to whittle down the verbiage.
This proposal is to introduce PQ certificates in WebPKI such as for certificate authorities.
Problem is PQ signatures are large. If certificate chain is small that could be acceptable, but if the chain is large, then it can be expensive in terms of bandwidth and computation during TLS handshake. That is the exchange sends many certificates which embed a signature and a large (PQ) public key.
Merkle Tree Certificates ensures that an up to date client only needs 1 signature, 1 public key, 1 merkle tree witness.
Looking at an MTC generated certificate they've replaced the traditional signing algorithm and signature with a witness.
That means all a client needs is a signed merkle root which comes from an expanding Merkle Tree signed by the MTCA (Merkle Tree CA), which is delivered somehow out of band.
So basically TLS client receives certificate containing new signature algorithm which embeds a witness instead of a signature, a root (not sure if just a hash or a signed hash, I think the former). Client will get the signed roots out of band, which can be pre-verified, which means verifying the witness is simply doing a check on the witness.
Edit: My question: is this really a concern that needs to be addressed? PQ for TLS key exchange addresses a looming threat of HNDL (Harvest Now Decrypt Later). I don't see why we need to address making WebPKI use PQ signatures, at least for awhile now.
There's no good reason to believe that quantum computers will break modern cryptography.
Shor's algorithm requires that a quantum Fourier transform is applied to the integer to be factored. The QFT essentially takes quantum data with a representation that mirrors ordinary binary, and maps it to a representation that encodes information in quantum phase (an angle).
The precision in phase needed to perform an accurate QFT scales EXPONENTIALLY with the number of qubits you're trying to transform. You manage to develop a quantum computer capable of factoring my keys? Fine, I'll add 11 bits to my key length, come back when you've developed a computer with 2000x the phase precision.
> The precision in phase needed to perform an accurate QFT scales EXPONENTIALLY with the number of qubits you're trying to transform.
This is false.
The gates that appear in the textbook QFT circuit (such as the one shown on wikipedia [1]) do mention angles that are exponentially small in N (the number of qubits being operated upon). That may be what's confusing you. But it's well known that the tolerance on those rotations is high, meaning that simply skipping all the exponentially tiny rotations introduces negligible error [2][3].
Here's a simple model. Each time you get a rotation off by an angle of X, add X to the "total algorithm rotation error" R. The chance of an algorithm failing is at most R^2. For example, if R is less than 1 degree then the chance of algorithm failure will be less than 0.03%. That's an acceptable retry chance for Shor's algorithm. The QFT circuit on N qubits performs less than N^2 rotations. So, for R to be less than 1 degree, it's sufficient for each rotation's error X to be less than (1°)/N^2. Therefore the required precision only increases polynomially (like N^2) instead of exponentially (like 2^N). Note the required precision can be improved from O(1/N^2) to O(1/N) using techniques like the qubit recycling QFT [4].
Actually, even if the required precision scaled exponentially, that still wouldn't be an insurmountable problem. Quantum error correction achieves exponentially tighter tolerances from polynomially increasing resources. For example, Ross and Selinger proved that continuous rotations can be approximated to a target error of epsilon using O(log(1/epsilon)) gates from the discrete gate set Clifford+T [4]. And Clifford gates with error below epsilon can be achieved in the surface code using O(log(1/epsilon)^2) noisy qubits for O(log(1/epsilon)) time [5]. And T gates can be achieved by using those reliable Clifford gates to perform magic state distillation of log(1/epsilon)^O(1) T states [6]. Since everything scales polynomially in log(1/epsilon), making epsilon exponentially smaller adds polynomial resources.
There is no part of Shor's algorithm that requires resources growing exponentially in n (the number of digits of the number being factored). The practical scaling is more like n^3: factoring a number that's twice as large can be done with ~two times as many qubits running for ~four times as long. Even if the qubits are noisy [7].
It worries me how we are increasingly making browser vendors a critical part of the TLS ecosystem - first with CRL bloom filters, now with signature Merkle trees. And they of course also manage the root stores.
Sure, it's nice and convenient if you're using an evergreen browser which is constantly getting updates from the mothership, but what is the rest supposed to do? How are we supposed to use this in Curl, or in whatever HTTP library your custom application code is using? How about email clients? Heck, is it even possible with embedded devices?
"The internet" is a hell of a lot bigger than "some website in Google Chrome", and we should be careful to not make all those other use cases impossible.
I agree that there is a big gap between what browsers offer today, and a non-browser client. This is a good moment to improve things. There is no reason that we can't have system service populating /etc/ssl/treeheads, which openssl can read. Or fall back to $USER/.config/treeheads, or per application.
But you still need a public key for TLS? Well, just put it in DNS!
And assuming your DNS responses are validated by DNSSEC, it would be even more secure too.
You'd be closing a whole lot of attack vectors: from IP hijacks and server-side AitM to CA compromises. In fact, you would no longer need to use CA's in the first place. The chain of trust goes directly from your registrar to your webserver with no third party in between anymore. (And if your registrar or webserver is hacked, you'd have bigger problems...)
The biggest blocker for DANE at the moment is that it doesn't have a transparency story. There is no good visibility into whether your TLD advertises a second pair of zone signing keys to few you don't control. We can add some transparency logs as with CT, but then we have a rate-limiting problem. You could have a mix of heavily rate-limited free DNSSEC logs and some paid DNSSEC logs. This is starting to look a lot like the current WebPKI then. I must say that this is an under explored area.
That's a serious blocker, but the biggest blocker for it is that it can't reliably be deployed; too much of the Internet is on links that won't pass the records required to verify DANE, which means that browsers need fallback paths for DANE, which means DANE expands, rather than contracts, the threat surface area of the WebPKI.
But you don't need the transparency!
The whole transparency thing was added because we have hundreds of Certificate Authorities all over the world who would otherwise have the power to secretly sign a cert for your website without anyone ever knowing.
And if you DO need the extra monitoring, all it takes is periodically retrieving the DNS record and send an alert if it changes. (There is no certificate that needs periodical rotation, you only need to renew the keypair if the server is compromised.)
MTC also supports certificates that can be issued immediately and don’t require landmarks to be validated, but these are not as small. A server would provision both types of Merkle tree certificates, so that the common case is fast, and the exceptional case is slow, but at least it’ll work.
I am not so sure about the "exceptional" part
If the landmarks are generated not so often (say, once every couple of days), then the many clients will need to take the slow path
If the landmarks is generated quickly (once per hour ?), then the client will continuously download those landmarks
Landmarks are generated every hour, but I expect clients to pull them perhaps once or twice per day. Servers will keep two signatureless MTCs around a few days apart, so even if your client didn't update in a few days you can still use the small signatureless cert. The biggest reason for needing the big MTCs is for when you need a new certificate quickly. Our intern Lena had a look how common that would be, and she estimates it'd be required for 0.1% at any given time. https://www.youtube.com/watch?si=72ClhykaYDHf0sND&v=f8unMB2Q...
36 comments
[ 12.7 ms ] story [ 1348 ms ] threadI think Merkle Tree Certificates a promising option. I'll be participating in the standardization efforts.
Chrome has signalled in multiple venues that they anticipate this to be their preferred (or only) option for post-quantum certificates, so it seems fairly likely we will deploy this in the coming years
I work for Let's Encrypt, but this is not an official statement or promise to implement anything yet. For that you can subscribe to our newsletter :)
I could see government agencies with a big budget having access to it, but I don't see those computers becoming mainstream
Although I could see China having access to it, which is problem.
Don’t we already just use the certificates to just negotiate the final encryption keys? Wouldn’t a quantum computer still crack the agreed upon keys without the exchange details?
The post didn't discuss it but naively this feels like it becomes a privacy issue?
It's a privacy violating proxy after all.
If I understand this correctly each CA publishes a signed list of landmarks at some cadence (weekly)
For the certs you get the landmark (a 256-bit hash) and the hashes along the merkle path to the leaf cert's hash. For a landmark that contains N certs, you need to include log2(N) * hash_len bytes and perform log2(N) hash computations.
For a MTC signature that uses a 256bit hash and N=1 million that's about 20*32=620bytes.
Is this the gist of it?
I'm really curious about the math behind deciding the optimal landmark size and publishing cadence
I don’t love the idea of giving every server I connect to via TLS the ability to fingerprint me by how recently (or not) I’ve fetched MTC treeheads. Even worse if this is in client hello, where anyone on the network path can view it either per connection or for my DoH requests to bootstrap encrypted client hello.
Spitballing here, would it still meet the needs of the protocol if the client offered which MTCAs it has (no version information), the server sends back some “typical” depth (say, 3 levels up the tree), then the client can decide to either: * Accept the MTC * Request a deeper traversal, following some super linear growth like fib numbers. In that case, they’d communicate “give me up to 5 nodes above your leaf” * Reject the MTC * Request the full certificate for “traditional” validation
The server still has a side channel for “how recently updated is this client” by knowing how many levels of inclusion proofs needed to be shared, but this is much less signal than knowing exactly which landmarks a client has.
> Instead of expecting the client to know the server's public key in advance, the server might just send its public key during the TLS handshake. But how does the client know that the public key actually belongs to the server? This is the job of a certificate.
Are you kidding me? You don't know your audience on an article at the nexus of certificate transparency and post-quantum cryptography well-enough to understand that this introduction to PKI isn't required?
Know your audience. Turning over your voice to an AI doesn't do that for you. It will waste everyone's time on thousands of words of vapid nonsense.
If the first time the client doesn't know what root the server's certificate will chain to, therefore it doesn't tell the server what treeheads it has, and so the client gets a full certificate, and then the client caches this to remember for later connections, then... that could work, though it's a slight metadata leak.
Alternatively the client could send the treeheads for all the roots it trusts. That's going to bloat the ClientHello and... it's going to leak a bit of metadata unless if the client does anything other than claim to trust all roots blessed by the CA/Browser Forum, or the Chrome Root Program.
This proposal is to introduce PQ certificates in WebPKI such as for certificate authorities.
Problem is PQ signatures are large. If certificate chain is small that could be acceptable, but if the chain is large, then it can be expensive in terms of bandwidth and computation during TLS handshake. That is the exchange sends many certificates which embed a signature and a large (PQ) public key.
Merkle Tree Certificates ensures that an up to date client only needs 1 signature, 1 public key, 1 merkle tree witness.
Looking at an MTC generated certificate they've replaced the traditional signing algorithm and signature with a witness.
That means all a client needs is a signed merkle root which comes from an expanding Merkle Tree signed by the MTCA (Merkle Tree CA), which is delivered somehow out of band.
So basically TLS client receives certificate containing new signature algorithm which embeds a witness instead of a signature, a root (not sure if just a hash or a signed hash, I think the former). Client will get the signed roots out of band, which can be pre-verified, which means verifying the witness is simply doing a check on the witness.
Edit: My question: is this really a concern that needs to be addressed? PQ for TLS key exchange addresses a looming threat of HNDL (Harvest Now Decrypt Later). I don't see why we need to address making WebPKI use PQ signatures, at least for awhile now.
Shor's algorithm requires that a quantum Fourier transform is applied to the integer to be factored. The QFT essentially takes quantum data with a representation that mirrors ordinary binary, and maps it to a representation that encodes information in quantum phase (an angle).
The precision in phase needed to perform an accurate QFT scales EXPONENTIALLY with the number of qubits you're trying to transform. You manage to develop a quantum computer capable of factoring my keys? Fine, I'll add 11 bits to my key length, come back when you've developed a computer with 2000x the phase precision.
Nobody needs them The 5 eyes already have access to root certs and internet nodes.
What it _really_ matters is that you are secure, and terrorists and pedofiles stand no chance. At least in theory. /s
This is false.
The gates that appear in the textbook QFT circuit (such as the one shown on wikipedia [1]) do mention angles that are exponentially small in N (the number of qubits being operated upon). That may be what's confusing you. But it's well known that the tolerance on those rotations is high, meaning that simply skipping all the exponentially tiny rotations introduces negligible error [2][3].
Here's a simple model. Each time you get a rotation off by an angle of X, add X to the "total algorithm rotation error" R. The chance of an algorithm failing is at most R^2. For example, if R is less than 1 degree then the chance of algorithm failure will be less than 0.03%. That's an acceptable retry chance for Shor's algorithm. The QFT circuit on N qubits performs less than N^2 rotations. So, for R to be less than 1 degree, it's sufficient for each rotation's error X to be less than (1°)/N^2. Therefore the required precision only increases polynomially (like N^2) instead of exponentially (like 2^N). Note the required precision can be improved from O(1/N^2) to O(1/N) using techniques like the qubit recycling QFT [4].
Actually, even if the required precision scaled exponentially, that still wouldn't be an insurmountable problem. Quantum error correction achieves exponentially tighter tolerances from polynomially increasing resources. For example, Ross and Selinger proved that continuous rotations can be approximated to a target error of epsilon using O(log(1/epsilon)) gates from the discrete gate set Clifford+T [4]. And Clifford gates with error below epsilon can be achieved in the surface code using O(log(1/epsilon)^2) noisy qubits for O(log(1/epsilon)) time [5]. And T gates can be achieved by using those reliable Clifford gates to perform magic state distillation of log(1/epsilon)^O(1) T states [6]. Since everything scales polynomially in log(1/epsilon), making epsilon exponentially smaller adds polynomial resources.
There is no part of Shor's algorithm that requires resources growing exponentially in n (the number of digits of the number being factored). The practical scaling is more like n^3: factoring a number that's twice as large can be done with ~two times as many qubits running for ~four times as long. Even if the qubits are noisy [7].
[1]: https://en.wikipedia.org/wiki/Quantum_Fourier_transform#/med...
[2]: https://arxiv.org/abs/quant-ph/0306018
[3]: https://arxiv.org/abs/quant-ph/9601018
[4]: https://arxiv.org/pdf/quant-ph/9903071#page=12
[5]: https://arxiv.org/abs/1208.0928
[6]: https://arxiv.org/abs/1209.2426
[7]: https://arxiv.org/abs/1905.09749
(I know its controversial what a blockchain even is, but this seems sufficiently close to how cryptocurrencies work to count)
Sure, it's nice and convenient if you're using an evergreen browser which is constantly getting updates from the mothership, but what is the rest supposed to do? How are we supposed to use this in Curl, or in whatever HTTP library your custom application code is using? How about email clients? Heck, is it even possible with embedded devices?
"The internet" is a hell of a lot bigger than "some website in Google Chrome", and we should be careful to not make all those other use cases impossible.
But you still need a public key for TLS? Well, just put it in DNS!
And assuming your DNS responses are validated by DNSSEC, it would be even more secure too. You'd be closing a whole lot of attack vectors: from IP hijacks and server-side AitM to CA compromises. In fact, you would no longer need to use CA's in the first place. The chain of trust goes directly from your registrar to your webserver with no third party in between anymore. (And if your registrar or webserver is hacked, you'd have bigger problems...)
And if you DO need the extra monitoring, all it takes is periodically retrieving the DNS record and send an alert if it changes. (There is no certificate that needs periodical rotation, you only need to renew the keypair if the server is compromised.)
If the landmarks are generated not so often (say, once every couple of days), then the many clients will need to take the slow path
If the landmarks is generated quickly (once per hour ?), then the client will continuously download those landmarks