Live data from Hacker News

A Post-Quantum Future for Let's Encrypt

letsencrypt.org

81–90 of 175 posts

Re: A Post-Quantum Future for Let's Encrypt

#81
post #73

We are truly living in a science fiction future where quantum code cracking is not a remote possibility but a near term risk we are planning for. In Vernor Vinge's novel "A Fire Upon the Deep" one of the most valuable commodities were one time pads that are physically transported to communication nodes to enable unbreakable communication. The pads are split into three pieces that are XORed to create the actual pad to…

> The pads are split into three pieces that are XORed to create the actual pad to reduce risk of compromise. Thus creating a two-time pad, which is completely insecure…

No, the idea is that the actual key is the XOR of 3 completely independent keys. I think you were thinking of XORing a key with itself 3 times, which would just return the original key.

In the book, there is a cargo ship carrying 1/3 of a OTP. Other two other ships from two other companies are carrying the other thirds. This actually is a fairly decent method of transporting a OTP (I'm assuming there's some kind of physical security preventing tampering).

The book even talks later on about how only using the pad isn't enough, since it provides no proof of authorship or tampering. Vinge did a pretty good job w/compsci in the book.

Re: A Post-Quantum Future for Let's Encrypt

#82
post #59

Earlier quoted context omitted.

"Intuition" about how cryptography works is notoriously bad. Many intuitive things about cryptography are false, and many true things about cryptography are non-intuitive. For this reason it is difficult to seriously discuss cryptography when people are vaguely referring to what they intuitively hope to achieve, framed in terms of concrete constructions that are not secure. This is also completely ignoring that desig…

I don't disagree, but I think the folks who know this ought to remember the lay person perspective and try to address it more concretely. Rather than rejecting the framing because they (we) aren't fluent in your jargon, provide a more constructive hint... E.g. "You may be thinking the symmetric cipher key is simply encrypted with the asymmetric cipher and concatenated to the bulk message. But, to mitigate known crypt…

I'm generally sympathetic to your point, it is just difficult for this particular topic. For example, I mentioned how precision in cryptographic language is important, as there was a discussion about combiners for encryption, when really people should use combiners for KEMs, along with hybrid encryption (here, meaning building public-key encryption from a KEM + symmetric key encryption).

The issue is that none of the above is relevant to the article that we are in the comments of. The article is about signatures. Why are we talking about encryption/KEMs in the first place?

One might hope the story for combiners for KEMs (which people may have intuition for due to combiners for encryption, which you could easily show in an undergraduate cryptography course) is broadly similar to the story for combiners for signatures. Unfortunately, that's not true at all. It would be a very reasonable perspective to have that we should use combiners for KEMs but not combiners for signatures. It would be very difficult to communicate this to a layperson without being very precise about the jargon.

This is especially true as this is a topic where a notable cryptographer has spent the last few years libeling several other cryptographers, and spreading a good deal of misinformation to laypeople. He is also extremely litigious, and has either sued or threatened to sue several cryptographers for what I view to be nonsense reasons. For some (at least myself), this makes precise language all the more important in topics he might have his eyes on.

So I both broadly agree with you for most topics, and also this particular topic requires a good deal more precision than most others in cryptography.

Re: A Post-Quantum Future for Let's Encrypt

#83
post #79
post #43

Earlier quoted context omitted.

There is more certainty about the resilience of lattice cryptography to classical attack than there was about Curve25519's resilience when it was introduced. Lattice schemes weren't invented as PQC schemes; they were invented as faster classical schemes. In the 1990s, there was a live debate about whether lattices might be the successor to RSA, not curves.

With the caveat (for other commenters) that "lattices" means several things that were not viewed with a unified lens in the 90s and 2000s, the main lattice scheme of interest now (LWE) actually was introduced in a quite literal sense as a PQC scheme. In the early 2000s, Oded Regev was looking into quantum computing algorithms for various worst-case lattice problems. He was able to create an efficient quantum algorith…

I didn't say Kyber/MLKEM or even LWE was a contender vs. curves in the 1990s; that wouldn't have made sense. I said lattice cryptography. As I understand it, our formal understanding of LWE is actually better than that of the original NTRU problem.

I liken this to the original Certicom proposals from the 1990s versus Curve25519. There's a diversity of curve approaches (binary field Koblitz vs prime-field curves, etc; things were wackier in the early aughts too) just as there is a diversity of implementation strategies for lattice KEMs.

The notion I'm hostile to is the one that poses lattices as moon math.

Re: A Post-Quantum Future for Let's Encrypt

#84

Earlier quoted context omitted.

But that's a miss, it's like one of those Neal Stephenson moments where the creator is using the right language (so it's not like reading William Gibson who clearly has no idea and knows it - he's going for the emotional feel not the technology) but they don't understand what's actually going on. OTP is in theory the correct choice if you don't have working symmetric cryptography but in fact the "Quantum computer" ap…

[Vinge]( https://en.wikipedia.org/wiki/Vernor_Vinge ) was a professor of mathematics and computer science. I'd expect him to get things right. Funny enough I don't remember that bit at all from fire upon the deep.

From Chapter 8, available online at https://deepness.trmm.net/c08b/

"Our main cargo is a one-time cryptographic pad. The source is Commercial Security at Sjandra Kei; the destination is the certificants' High colony. It was the usual arrangement: We're carrying a one-third xor of the pad. Independent shippers are carrying the others. At the destination, the three parts would be xor'd together. The result could supply a dozen worlds' crypto needs on the Net for --"

Re: A Post-Quantum Future for Let's Encrypt

#85

Earlier quoted context omitted.

nsa & eu pushing for something to change proven algorithms makes me personally automatically distrustful as both are highly rotten bad actors. i have no knowledge, nor time to eval. (and probably few people do) all i am saying is there is no good reason to depreciate proven algs, especially not because those two institutions said so.

> nsa & eu pushing for something to change proven algorithms makes me personally automatically distrustful as both are highly rotten bad actors. Who do you trust, then? > i have no knowledge, nor time to eval. (and probably few people do) If you do not have the expertise nor time to evaluate technical claims, how do you hope to arrive at correct technical conclusions? Surely, you'd trust experts in that case? Like th…

> Who do you trust, then? the existing algos

> If you do not have the expertise nor time to evaluate technical claims, how do you hope to arrive at correct technical conclusions? > > Surely, you'd trust experts in that case? Like the experts that were involved in a multi-year international standardization effort? Like the one that produced > ML-KEM and ML-DSA? > > Or do you just balk at experts and "trust no one" even to your own detriment?

what detriment? there is no quantum treat, it is made up. at least not in the discussed timelines.

besides, experts are cheap and compromisable, especially for the nation state level bodies like nsa and eu.

Re: A Post-Quantum Future for Let's Encrypt

#86

We are truly living in a science fiction future where quantum code cracking is not a remote possibility but a near term risk we are planning for. In Vernor Vinge's novel "A Fire Upon the Deep" one of the most valuable commodities were one time pads that are physically transported to communication nodes to enable unbreakable communication. The pads are split into three pieces that are XORed to create the actual pad to…

In terms of actually doing it, it's still very remote, but not as remote as it would have to be for us to completely ignore it. And the NSA has massive data centers full of hard drives storing our encrypted internet traffic.

Re: A Post-Quantum Future for Let's Encrypt

#87

I've been working on a new project using ed25519 signatures and discovered they are not quantum resistant.... I went with ed25519 due to possibility of using openssh keys. Any opinion on this choice at the light of this article and other quantum computing news?

There's an IETF RFC draft for mldsa-44 keys for OpenSSH. https://datatracker.ietf.org/doc/draft-rpe-ssh-mldsa I'm not aware if it has any real traction, but that's what I found with a quick search.

OpenSSH's Damien Miller has https://datatracker.ietf.org/doc/draft-miller-sshm-mldsa44-e... defining ssh-mldsa44-ed25519@openssh.com which seems more likely given the authorship.

Re: A Post-Quantum Future for Let's Encrypt

#88

I've been working on a new project using ed25519 signatures and discovered they are not quantum resistant.... I went with ed25519 due to possibility of using openssh keys. Any opinion on this choice at the light of this article and other quantum computing news?

Signatures aren't as urgent to replace as encryption keys are. You can wait until someone is about to build a quantum computer, then change all your signatures. Encrypted data is more critical because the NSA's going to store all internet traffic for centuries if it thinks it can decrypt it later.

Re: A Post-Quantum Future for Let's Encrypt

#89
post #83
post #79

Earlier quoted context omitted.

With the caveat (for other commenters) that "lattices" means several things that were not viewed with a unified lens in the 90s and 2000s, the main lattice scheme of interest now (LWE) actually was introduced in a quite literal sense as a PQC scheme. In the early 2000s, Oded Regev was looking into quantum computing algorithms for various worst-case lattice problems. He was able to create an efficient quantum algorith…

I didn't say Kyber/MLKEM or even LWE was a contender vs. curves in the 1990s; that wouldn't have made sense. I said lattice cryptography. As I understand it, our formal understanding of LWE is actually better than that of the original NTRU problem. I liken this to the original Certicom proposals from the 1990s versus Curve25519. There's a diversity of curve approaches (binary field Koblitz vs prime-field curves, etc;…

Yes I know. That was what my initial paragraph was about.

And yes, our formal understanding of LWE is much better than the original NTRU problem. NTRU itself

1. admits non-trivial attacks if the ciphertext modulus is too large, as well as

2. had a signature algorithm (NTRU-sign) that was completely broken.

Lattice-based signatures were actually a relatively thorny thing to develop. The first non-broken lattice-based signature was proposed in 2009 iirc. I think this was after Gentry developed fully homomorphic encryption (though his initial scheme is now broken as well). Even in modern treatments, it's a fair statement to say that constructing a secure lattice-based signature is of similar complexity to constructing a secure fully homomorphic encryption scheme (although there are some relatively-simple ones these days).

You can make stronger statements about our understanding of LWE though. I would say that it is relatively uncontentious to state that LWE and elliptic-curve DLOG are the two problems we understand the best theoretically in public-key cryptography, and it is not particularly close. The only remote contenders would be

1. finite-field DH, though arguably our understanding of this is still not great (are CDH and DDH equivalent? well sort of, but the details become quite messy).

2. RSA. There are still many basic questions about it that are wide-open, namely is it equivalent to factoring? There are other questions that are unknown as well, for example how hard it is to attack. "Everyone knows" that you just use GNFS, with L[1/3, c] complexity. But other index calculus attacks were improved to L[1/4, c] complexity in the 2010s. Can those attacks extend to factoring? Things get even worse when you consider the veritable zoo of attacks on RSA when you get a small detail wrong (Coppersmith-style attacks in the presence of some leaked key bits, improved attacks depending on what particular RSA exponents you've chosen, etc).

I think you could even go farther and say that we understand LWE better than elliptic curve DLOG. This would of course be contentious, but is meant to communicate just how good of a (theoretical) understanding we have of the LWE problem.

Of course, the main point in EC DLOG's favor is that, when correctly parameterized (which is a thorny point itself, but mostly fine these days), there are the generic group lower bounds (2^n time, poly space), and attacks have never beaten them. While for LWE attacks have always been of the form (exp time, exp space) (or 2^{n\log n} time, poly space), but the exponent in the "exp"'s doesn't have as clean of a conjectured lower bound, and has been reduced some over time.

Re: A Post-Quantum Future for Let's Encrypt

#90

Earlier quoted context omitted.

> If you encrypt your data twice, and one of them is broken by a quantum computer, the adversary gets the plaintext anyway. Is the idea here that "you broke quantum and quantum breaks classical, therefor layering is pointless"?

If you encrypt your data twice (taken very literally): c1 = E1(p, k1) c2 = E2(p, k2) If we assume E1() is broken by a quantum computer, E2 doesn't matter to protect p. What you do instead is to use multiple KEMs and combine them securely (see the blog post I linked) in such a way that the confidentiality of your shared secret (i.e., the key you actually use for encryption ) is preserved if any of the underlying KEMs…

Why would you take the stupidest possible interpretation of that person's comment?
Post reply on HN