hckrnws

> 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.

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 :)

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.

Even though I agree with you, I totally understand why the push for at least hybrid algorithms. We just don't know how quantum computers could feasibly scale. Until we know for sure that cracking existing crypto systems really is infeasible for physical reasons, using hybrid systems that provide an extra layer of security just seems like obvious good practice.

At the same time it's very suspicious how a few three-letter agencies are pushing for total deprecation of non-PQ algorithms, even in hybrids.

> 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.

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.

Could take ipv6 ages to have this standardised and rolled out the most parts of the internet and IOT. Might make sense to do now if you want to be able to shut down that last non PQ safe tls device in the year 2050?

> All the information a client needs to validate a Merkle Tree Certificate can be disseminated out-of-band.

The post didn't discuss it but naively this feels like it becomes a privacy issue?

Using The Approved Set™ from your browser or OS carries no privacy issues: it's just another little bit of data your machine pulls down from some mothership periodically, along with everyone else. There's nothing distinguishing you from anyone else there.

You may want to pull landmarks from CAs outside of The Approved Set™ for inclusion in what your machine trusts, and this means you'll need data from somewhere else periodically. All the usual privacy concerns over how you get what from where apply; if you're doing a web transaction a third party may be able to see your DNS lookup, your connection to port 443, and the amount of traffic you exchange, but they shouldn't be able to see what you asked for or what you go. Your OS or browser can snitch on you as normal, though.

I don't personally see any new privacy threats, but I may not have considered all angles.

Different machines will need to have variations in when they grab updates to avoid thundering herd problems.

I could see the list of client-supplied available roots being added to client fingerprinting code for passive monitoring (e.g. JA4) if it’s in the client hello, or for the benefit of just the server if it’s encrypted in transit.

Vaguely. Basically each CA will run one of these. Relying parties (browsers) will need to fetch the Merkle tree heads periodically for at least the CAs that sign certificates for the sites the users browse, or maybe all of the WebPKI CAs rather than just those that sign certs for the visited sites. There's on the order of 100 CAs for the whole web though, so knowledge that your browser fetched the MT heads for, say, 5 CAs, or even 1 CA, wouldn't leak much of anything about what specific sites the user is visiting. Though if the user is visiting, say, China sites only, then you might see them only fetch the MT heads for CN, and then you might say "aha! it's a Chinese user", or something, but... that's not a lot of information leaked, nor terribly useful.

I think most folks involved are assuming the landmarks will be distributed by the browser/OS vendor, at least for end-user devices where privacy matters the most - Similar to how CRLSets/CRLite/etc are pushed today.

There's "full certificates" defined in the draft which include signatures for clients who don't have landmarks pre-distributed, too.

The privacy aspect isn’t that you fetched the heads. It’s that you are sending data that is likely usable (in combination with other data being leaked) that websites can use to fingerprint you and track you across websites (since these heads are sent by the client in TLS hello)

The heads don't change often. I think we should list all the metadata that gets leaked to see just how many bits of fingerprint we might get. Naively I think it's rather few bits.

Sure, but every few bits is enough to disambiguate just a little bit more. Then each little trickle is combined to create a waterfall to completely deanonymize you.

For example, your IP + screen resolution + the TLS handshake head might be enough of a fingerprint to disambiguate your specific device among the general population.

It would be ridiculous for cloudflare to discuss privacy issues. ;-)

Has the day finally arrived where "blockchain technology" is actually useful for something?

(I know its controversial what a blockchain even is, but this seems sufficiently close to how cryptocurrencies work to count)

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

Yeah. From the RFC draft:

> If a new landmark is allocated every hour, signatureless certificate subtrees will span around 4,400,000 certificates, leading to 23 hashes in the inclusion proof, giving an inclusion proof size of 736 bytes, with no signatures.

https://davidben.github.io/merkle-tree-certs/draft-davidben-...

That's assuming 4.4 million certs per landmark, a bit bigger than your estimate.

There's also a "full certificate" which includes signatures, for clients who don't have up-to-date landmarks. Those are big still, but if it's just for the occasional "curl" command, that's not the end of the world for many clients.

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?

Yes, the rest of the cryptography needs to be PQ-secure as well.

But that's largely already true:

The key exchange is now typically done with X25519MLKEM768, a hybrid of the traditional x25519 and ML-KEM-768, which is post-quantum secure.

The exchanged keys typically AES-128 or AES-256 or ChaCha20. These are likely to be much more secure against quantum computers as well (while they may be weakened, it is likely we have plenty of security margin left).

Changing the key exchange or transport encryption protocols however is much, much easier, as it's negotiated and we can add new options right away.

Certificates are the trickiest piece to change and upgrade, so even though Q-day is likely years away still, we need to start working on this now.

Upgrading the key exchange has already happened because of the risk of capture-now, decrypt-later attacks, where you sniff traffic now and break it in the future.

No the agreed upon keys are symmetric encryption keys with like an AES cipher and we don't have any reason to believe the current encryption there is easier to calculate with a quantum computer

> Don’t we already just use the certificates to just negotiate the final encryption keys?

No, since forward secret key agreement the certificate private key isn't involved at all in the secrecy of the session keys; the private key only proves the authenticity of the connection / the session keys.

While quantum computing weakens AES encyption, AES 256 bit can't be cracked by quantum computers.

Not practically, anyway, and even with absurd advances we can just grow the key sizes.

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.

Are we already talking about attackers having access to quantum computers?

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.

The migration here is going to be long.

Chrome and Cloudflare are doing a MTC experiment this year. We'll work on standardizing over the next year. Let's Encrypt may start adding support the year after that. Downstream software might start deploying support MTCs the year after that. People using LTS Linux distros might not upgrade software for another 5 years after that. People run out-of-date client devices for another 5 years too.

So even in that timeline, which is about as fast as any internet-scale migration goes, it may be 10-15 years from today for MTC support to be fully widespread.

The fear is attackers are recording conversations today in the hopes that they can crack the encryption when we do have quantum computers in a few years

Capture-now Decrypt-later isn't really relevant to certificates, who mostly exist to defend against active MITM. The key exchange algorithms need to be PQ-secure for CN-DL, but that has already happened if you have an up-to-date client and server.

No. Nobody serious that I know of thinks Q-day has occurred or will occur in 2025. The more typical question is whether we're 10, 50, or 100 years away from it.

I’m of the opinion that it’s unlikely to happen within 50 years.

But I still think it’s a good idea to start switching over to post-quantum encryption, because the lead time is so high. It could easily take a full 10 years to fully implement the transition and we don’t want to be scrambling to start after Q-day.

> Although I could see China having access to it, which is problem.

I can see USA having access to it, which is also a problem. Or any other government.

Seems like you answered your own question

How is China having access to it any different than, say, America?

Keeping internet locked, you mean?

Ah cloudflare. But who will protect us against cloudflare???

It's a privacy violating proxy after all.

What's so special about cloudflare? Everyone from AWS to Akamai offers the same "reverse proxy" service.

[flagged]

... Why is this the first place to go?

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.