7 ms·

Keeping the Internet fast and secure: introducing Merkle Tree Certificates

215 points by tatersolid 1y ago

rvz 1y ago
[flagged]
- tomrod 1y ago
  ... Why is this the first place to go?
mcpherrinm 1y ago
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 :)
jokoon 1y ago
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.
- mtoner23 1y ago
  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
  - mcpherrinm 1y ago
    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.
- rynn 1y ago
  Seems like you answered your own question
- tptacek 1y ago
  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.
  - phire 1y ago
    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.
    - sunsetonsaturn 1y ago
      > 10 years Moving from SHA-1 to SHA-2 took ~20 years - and that's the "happy path", because SHA-2 is a drop-in replacement. The post-quantum transition is more complex: keys and signatures are larger; KEM is a cryptographic primitive with a different interface; stateful signature algorithms require special treatment for state handling. It can easily take more than 20 years.
- mcpherrinm 1y ago
  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.
  - bwesterb 1y ago
    Yeah, this is going to take time. That is why we're starting now.
- HexDecOctBin 1y ago
  > 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.
- squigz 1y ago
  How is China having access to it any different than, say, America?
  - jokoon 1y ago
    I trust american institutions more than I trust chinese institutions
itopaloglu83 1y ago
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?
- mtoner23 1y ago
  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
  - itopaloglu83 1y ago
    Okay, it makes some sense now. I always assumed that quantum computing would make any encryption scheme less secure, but that’s not the case.
- deleted 1y ago
  [deleted]
- NoahZuniga 1y ago
  While quantum computing weakens AES encyption, AES 256 bit can't be cracked by quantum computers.
  - MangoToupe 1y ago
    Not practically, anyway, and even with absurd advances we can just grow the key sizes.
  - bwesterb 1y ago
    AES-128 also can't be cracked by quantum computers.
- mcpherrinm 1y ago
  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.
tempay 1y ago
> 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?
- megous 1y ago
  It would be ridiculous for cloudflare to discuss privacy issues. ;-)
- cryptonector 1y ago
  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.
  - mcpherrinm 1y ago
    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.
  - vlovich123 1y ago
    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)
megous 1y ago
Ah cloudflare. But who will protect us against cloudflare??? It's a privacy violating proxy after all.
- thhoooowww0101 1y ago
  What's so special about cloudflare? Everyone from AWS to Akamai offers the same "reverse proxy" service.
  - bwesterb 1y ago
    Also MTC is usable for everyone. Perfectly fits an automation-forward webserver like Caddy.
  - layer8 1y ago
    Their market share: https://w3techs.com/technologies/details/cn-cloudflare https://w3techs.com/technologies/details/cn-cloudflare
  - megous 1y ago
    Did I say there's something special about them?
    - thhoooowww0101 1y ago
      Maybe I misunderstood your comment. Traffic wise, I'm not sure if they're ahead of other "privacy violating" proxy services, so I was wondering if there's something special about Cloudflare. They're all MITM traffic after all.
matthewaveryusa 1y ago
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
- mcpherrinm 1y ago
  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-tls-merkle-tree-certs.html#name-size-estimates 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.
- politelemon 1y ago
  Does this mean that some https fetch activities could break if a machine hasn't run sudo apt upgrade in a while?
cryptonector 1y ago
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.
- bwesterb 1y ago
  It indeed is!
mtud 1y ago
> 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.
- deleted 1y ago
  [deleted]
- bwesterb 1y ago
  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.
  - mtud 1y ago
    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.
    - bwesterb 11mo ago
      Client would check perhaps once a day. Similar to how Chrome checks about once a day for urgent revocations.
      - mtud 11mo ago
        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.
oasisbob 1y ago
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.
- jgrahamc 1y ago
  When I was the editor in chief of the Cloudflare blog we had a very, very strong mission to "educate, educate, educate" our readers. That often meant including details that someone versed in the field would skip over or find too basic. After all, we were writing for a general technical audience interested in learning about a topic. So, its natural that some readers would find parts over-explanatory but the hope was that they could read past those bits and the less educated reader would come away having learnt something new.
  - oasisbob 1y ago
    I can understand wanting to give background. There's still a place where it's too long and verbose. The pacing and verbosity makes me really doubt this underwent extensive editing.
- flufluflufluffy 1y ago
  I for one welcomed the refresher as I don’t often deal with the intricacies of the public key infrastructure, even though yes I am a programmer and make websites.
cryptonector 1y ago
> 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.
- bwesterb 1y ago
  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.
  - cryptonector 1y ago
    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.
dur-randir 1y ago
Keeping internet locked, you mean?
commandersaki 1y ago
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.
- rand846633 1y ago
  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?
  - arccy 1y ago
    They're saying WebPKI, which mean basically web browsers can more or less push this through on their evergreen release schedule when it becomes necessary. PKI for everything else can go at their own pace
    - rand846633 1y ago
      But this implies that any small plastic home router using libCurl can fetch its updates via PQ safe https?
dtj1123 1y ago
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.
- jchw 1y ago
  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.
  - Avamander 1y ago
    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.
    - goalieca 1y ago
      Transitions takes decades especially when silicon and networks are involved (eg secure boot and MTU). Most of us would rather just stick with a handful of ciphers than constantly changing (crypto agile has become crypto chaos).
  - hulitu 1y ago
    > We just don't know how quantum computers could feasibly scale. We know. They are not able yet to emulate an i4004, let alone be a treat to "computing".
bawolff 1y ago
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)
- snowwrestler 1y ago
  It’s probably more accurate to say that cryptocurrencies and this approach to TLS certs share common ancestors.
- layer8 1y ago
  Merkle trees have been used in the cryptographic archiving space for a long time (see RFC 4998 for example), they don’t equate to blockchains.
portaouflop 1y ago
Danke Merkle
nacozarina 1y ago
share your design, sure, but there is no reason to suggest Q-day is imminent, the fear-mongering is utterly absurd.
crote 1y ago
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.
- mcpherrinm 1y ago
  On some major OSes (like Windows and Mac), there’s a “platform verifier” which can handle some of this, including the fetching and sharing of out of band data. It doesn’t have to be tied to a browser. Linux should probably get one too, but I don’t know who will lead that effort. In the mean time, browsers aren’t willing to wait on OSes to get their act together, and reasonably so. There’s regulation (and users, especially corporate/government) pushing for post-quantum solutions soon, so folks are trying to find solutions that can actually be deployed. Browsers have always led in this space, all the way back to Netscape introducing SSL in the first place.
- bwesterb 1y ago
  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.
some_bird 1y ago
We could also just get rid of webPKI entirely? 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...)
- bwesterb 1y ago
  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.
  - tptacek 1y ago
    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.
  - some_bird 1y ago
    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.)
JackSlateur 1y ago
Quote: 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
- bwesterb 1y ago
  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=f8unMB2Qjho&feature=youtu.be https://www.youtube.com/watch?si=72ClhykaYDHf0sND&v=f8unMB2Q...

215 points by tatersolid 1y ago

rvz 1y ago

[flagged]

tomrod 1y ago
... Why is this the first place to go?

mcpherrinm 1y ago

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

jokoon 1y ago

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.

mtoner23 1y ago
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
- mcpherrinm 1y ago
  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.
rynn 1y ago
Seems like you answered your own question
tptacek 1y ago
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.
- phire 1y ago
  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.
  - sunsetonsaturn 1y ago
    > 10 years Moving from SHA-1 to SHA-2 took ~20 years - and that's the "happy path", because SHA-2 is a drop-in replacement. The post-quantum transition is more complex: keys and signatures are larger; KEM is a cryptographic primitive with a different interface; stateful signature algorithms require special treatment for state handling. It can easily take more than 20 years.
mcpherrinm 1y ago
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.
- bwesterb 1y ago
  Yeah, this is going to take time. That is why we're starting now.
HexDecOctBin 1y ago
> 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.
squigz 1y ago
How is China having access to it any different than, say, America?
- jokoon 1y ago
  I trust american institutions more than I trust chinese institutions

itopaloglu83 1y ago

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?

mtoner23 1y ago
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
- itopaloglu83 1y ago
  Okay, it makes some sense now. I always assumed that quantum computing would make any encryption scheme less secure, but that’s not the case.
deleted 1y ago
[deleted]
NoahZuniga 1y ago
While quantum computing weakens AES encyption, AES 256 bit can't be cracked by quantum computers.
- MangoToupe 1y ago
  Not practically, anyway, and even with absurd advances we can just grow the key sizes.
- bwesterb 1y ago
  AES-128 also can't be cracked by quantum computers.
mcpherrinm 1y ago
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.

tempay 1y ago

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

megous 1y ago
It would be ridiculous for cloudflare to discuss privacy issues. ;-)
cryptonector 1y ago
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.
- mcpherrinm 1y ago
  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.
- vlovich123 1y ago
  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)

megous 1y ago

Ah cloudflare. But who will protect us against cloudflare??? It's a privacy violating proxy after all.

thhoooowww0101 1y ago
What's so special about cloudflare? Everyone from AWS to Akamai offers the same "reverse proxy" service.
- bwesterb 1y ago
  Also MTC is usable for everyone. Perfectly fits an automation-forward webserver like Caddy.
- layer8 1y ago
  Their market share: https://w3techs.com/technologies/details/cn-cloudflare https://w3techs.com/technologies/details/cn-cloudflare
- megous 1y ago
  Did I say there's something special about them?
  - thhoooowww0101 1y ago
    Maybe I misunderstood your comment. Traffic wise, I'm not sure if they're ahead of other "privacy violating" proxy services, so I was wondering if there's something special about Cloudflare. They're all MITM traffic after all.

matthewaveryusa 1y ago

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

mcpherrinm 1y ago
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-tls-merkle-tree-certs.html#name-size-estimates 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.
politelemon 1y ago
Does this mean that some https fetch activities could break if a machine hasn't run sudo apt upgrade in a while?

cryptonector 1y ago

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.

bwesterb 1y ago
It indeed is!

mtud 1y ago

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

deleted 1y ago
[deleted]
bwesterb 1y ago
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.
- mtud 1y ago
  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.
  - bwesterb 11mo ago
    Client would check perhaps once a day. Similar to how Chrome checks about once a day for urgent revocations.
    - mtud 11mo ago
      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.

oasisbob 1y ago

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.

jgrahamc 1y ago
When I was the editor in chief of the Cloudflare blog we had a very, very strong mission to "educate, educate, educate" our readers. That often meant including details that someone versed in the field would skip over or find too basic. After all, we were writing for a general technical audience interested in learning about a topic. So, its natural that some readers would find parts over-explanatory but the hope was that they could read past those bits and the less educated reader would come away having learnt something new.
- oasisbob 1y ago
  I can understand wanting to give background. There's still a place where it's too long and verbose. The pacing and verbosity makes me really doubt this underwent extensive editing.
flufluflufluffy 1y ago
I for one welcomed the refresher as I don’t often deal with the intricacies of the public key infrastructure, even though yes I am a programmer and make websites.

cryptonector 1y ago

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

bwesterb 1y ago
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.
- cryptonector 1y ago
  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.

dur-randir 1y ago

Keeping internet locked, you mean?

commandersaki 1y ago

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.

rand846633 1y ago
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?
- arccy 1y ago
  They're saying WebPKI, which mean basically web browsers can more or less push this through on their evergreen release schedule when it becomes necessary. PKI for everything else can go at their own pace
  - rand846633 1y ago
    But this implies that any small plastic home router using libCurl can fetch its updates via PQ safe https?

dtj1123 1y ago

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.

jchw 1y ago
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.
- Avamander 1y ago
  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.
  - goalieca 1y ago
    Transitions takes decades especially when silicon and networks are involved (eg secure boot and MTU). Most of us would rather just stick with a handful of ciphers than constantly changing (crypto agile has become crypto chaos).
- hulitu 1y ago
  > We just don't know how quantum computers could feasibly scale. We know. They are not able yet to emulate an i4004, let alone be a treat to "computing".

bawolff 1y ago

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)

snowwrestler 1y ago
It’s probably more accurate to say that cryptocurrencies and this approach to TLS certs share common ancestors.
layer8 1y ago
Merkle trees have been used in the cryptographic archiving space for a long time (see RFC 4998 for example), they don’t equate to blockchains.

portaouflop 1y ago

Danke Merkle

nacozarina 1y ago

share your design, sure, but there is no reason to suggest Q-day is imminent, the fear-mongering is utterly absurd.

crote 1y ago

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.

mcpherrinm 1y ago
On some major OSes (like Windows and Mac), there’s a “platform verifier” which can handle some of this, including the fetching and sharing of out of band data. It doesn’t have to be tied to a browser. Linux should probably get one too, but I don’t know who will lead that effort. In the mean time, browsers aren’t willing to wait on OSes to get their act together, and reasonably so. There’s regulation (and users, especially corporate/government) pushing for post-quantum solutions soon, so folks are trying to find solutions that can actually be deployed. Browsers have always led in this space, all the way back to Netscape introducing SSL in the first place.
bwesterb 1y ago
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.

some_bird 1y ago

We could also just get rid of webPKI entirely? 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...)

bwesterb 1y ago
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.
- tptacek 1y ago
  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.
- some_bird 1y ago
  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.)

JackSlateur 1y ago

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

bwesterb 1y ago
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=f8unMB2Qjho&feature=youtu.be https://www.youtube.com/watch?si=72ClhykaYDHf0sND&v=f8unMB2Q...