Hacker News Reader

Comment by sandyarmstrong | Hacker News Reader

This is pretty fascinating. For easier reading, the Signal blog post [0] they link to is great.

Both Signal and Apple went with CRYSTALS-Kyber [1] as their post-quantum algorithm. If you're interested in the math, and maybe learned at some point about how classic public key cryptography is built on the idea that it's easy to multiply two primes, but hard to factor them, and how this (or other math problems) can be used as a one-way function to make encryption hard to break, the hard math problem that backs Kyber is the "learning-with-errors" [2] problem.

[0] https://signal.org/blog/pqxdh/

[1] https://pq-crystals.org/kyber/

[2] https://en.wikipedia.org/wiki/Learning_with_errors

View on HN

I'm way out of my depth in terms of the math here.

But my 'software engineer brain' likes the ideal of using the prime factoring problem, because it's so simple to understand, and feels like some kind of universal primitive. "It's easy to multiply but hard to factor." It just seems so intuitive.

But I'm reading the 'learning with errors' wiki page and it's beyond my comprehension.

There's a weird fear in my mind that all these "post quantum algorithms" are so complicated, with such a large surface area, that they may hide flaws. While prime factoring, or even the elliptic key stuff, is so simple to comprehend.

that said, obviously the experts know what they're doing, and I'll use what they suggest. just saying that this thought has crossed my mind.

The explanation in this video is what made it click for me: https://www.youtube.com/watch?v=K026C5YaB3A

Same here: this video helped me finally understand the basics concepts underlying LWE

Thank you! This video was GREAT. I was having trouble putting it all together from the wikipedia page alone.

Well, one way to think about this is: how much abstract algebra are you keeping in your head to reassure yourself of the security of classical asymmetric cryptography? It's surprisingly deep. Some programmers are "comfortable" with it because they've been brought up being taught that "factoring" is just the way asymmetric cryptography works, but that has never really been the whole case.

Elliptic curve is not at all simple to comprehend! It's easy to implement, but the motivation for designing systems around them (the effectiveness of the index calculus on elliptic curve groups) and the discoveries made on attacking them (like the MOV attack that transforms ECDLP problems to FFDLP problems) are not at all simple.

Arguably, elliptic curve is an odder corner of mathematics than lattices.

100%. Another underappreciated point is that factoring connection is very misleading. That is, we don't know if factoring is equivalent to breaking RSA (in particular, the algorithms breaking low-exponent RSA (which one shouldn't use for a number of reasons) don't factor the modulus). It might be true that computing e-th roots (i.e. breaking RSA) is tractable while factoring is not.

Similarly, PKCS is complex but every part of PKCS is there because without it there is a concrete attack. Burt Kaliski (former chief scientist of RSA Labs) has an amazing talk which goes into detail about this: https://www.youtube.com/watch?v=sqsDKjPaJVg For example, why does RSA need randomized padding, besides the trivial IND-CPA violation? Because if you encrypt the same message to many recipients, the attacker can use Hastad's attack, which uses lattices in a deep way, to recover the message from non-randomized ciphertexts https://en.wikipedia.org/wiki/Coppersmith%27s_attack?useskin... Very much like an airline checklist in a way :-)

Another nugget in the talk: how RSA embedded a public key in their products and bootstrapped VeriSign! Can't recommend it highly enough.

The LWE problem is one level of abstraction away from the fundamental lattice problems it reduces to. It is somewhat analogous to the Diffie-Hellman problem that many constructions reduce to, which itself is related to the lower-level discrete logarithm problem.

The lattice equivalent of integer factorization is the shortest vector problem: you're given n vectors of length m, and you have to find the sum of integer multiples of those vectors that comes closest to (or a small factor away from the closest) the zero vector. Say you have the 4 vectors

    [ 3 92  4  2]
    [54  0 92 41]
    [19 91 61 48]
    [39 59 40 14].

The shortest vector that you can obtain from adding integer multiples of these vectors is [19 -8 -15 2], which you can obtain by 3*[39 59 40 14] + [19 91 61 48] - 2*[54 0 92 41] - 3*[ 3 92 4 2].

With only 4 vectors it is easy to find the solution here. But the hardness grows exponentially with the dimension, and the dimensions in cryptographically relevant lattices are in the hundreds to thousands.

I know that thinking, but learning more about RSA, I came to realize that there's a flipside of this.

People think "RSA is easy", because someone gave them a lecture of a simplified/wrong/insecure version of RSA. Pretty much all "simple introductions to RSA" you can find out there are wrong.

The truth is: RSA isn't that simple. If you want to have RSA, and want to have it secure, there's a whole bunch of things to consider. But RSA looks simple.

So lots of people go ahead and implement their RSA. And then you end up with, hey, I can break almost a third of the top 100 webpage's RSA implementations. (I'm not kidding, I did that -> https://robotattack.org/ .)

I think the fact that crystals-kyber is obviously not that simple may actually protect us. Because hopefully most peopple will end up using some hopefully well audited optimized free implementation, because they won't even have the idea that they could do this on their own.

I love that security by difficulty is the new security by obscurity, but actually secure.

Is it new? Security by difficulty _is_ security.

Yeah talking about difficulty, then you will love this: https://www.science.org/content/article/china-s-quantum-sate...

If we really wanna be security, then entailment is a good bet. I could imagine essential financial clearing, emergency infrastructure could use this level security. Don't know how feasible it is for consumer grade usage yet though.

People rolling their own crypto still makes my jaw drop.

I get people want something custom but the tradeoffs are just too great.

> There's a weird fear in my mind that all these "post quantum algorithms" are so complicated, with such a large surface area, that they may hide flaws.

That's correct (emphasis on "may", of course), and is why it's absolutely imperative to always use PQC/ECC hybrid cryptosystems rather than pure PQC. See eg [0] for a more detailed explanation.

0: https://blog.cr.yp.to/20240102-hybrid.html

There are essentially no mainstream systems that don't do this. That's why new systems deploy things like PQ3.

Do you mean:

> There are essentially no mainstream systems that don't [use PQC/ECC hybrid cryptosystems?].

If so, good. I'll admit my expectations are a bit biased from having to deal with projects that go out of their way to produce defective software (eg DRM, malicious abuse of undefined behaviour by compliers, cloudflare and other captcha-walls, etc) so I tend to assume the worst by default.

Yes. So far as I know, there's no mainstream system that has even proposed to use solely Kyber and not Kyber+ECC. It's been a built-in assumption since the earliest Chrome PQC experiments.

It's not at all clear that factoring is actually hard. I fully expect factoring to be broken classically within my lifetime. FWIW I am a practicing cryptographer.

Curiously, the "large surface area hiding flaws" is actually what happened with RSA. Examples are

1. (large) speedups in solving it in the 90s, 2. issues where if enough of your key leaks, it can all be recovered. This leakage can occur via certain side-channel attacks 3. the "easy RSA" people learn is hard to make secure, which perhaps took a decade of doing very wrong to get right. By this, I mean padding attacks on RSA.

As for understanding LWE, see for example the blog posts

https://mark-schultz.github.io/nist-standard-out/

Was the CRYSTALS-Kyber name intentionally, or accidentally, a reference to Kyber Crystals (I.e. The Lightsaber energy source?)

Absolutely a reference. Dilithium (from Star Trek) is name of their signature algorithm.

The trick to naming things is to first find a cool word/reference, and then 'reverse engineer' it as an acronym second:

* https://en.wikipedia.org/wiki/Backronym

Though you can easily take it too far; I think US legislators have been running out of reasonable backronyms :)

I'm amused by the Padmé reference as well.

I was reading the NIST comments and djb is not very happy with how they present things, and the other commenters seem to think he is a prick.

I want an encryption algorithm composed of 2 parts chained, such that both parts need to be broken for the whole thing to be broken.

And I'd like the US/The west to declare 1 part as secure, and I'd like Russia to declare the other part as secure.

I'm fairly confident that Russia and the US won't collude to push a known-weak algorithm.

They would not have to collude; there is no incentive for either to publicly endorse a secure algorithm. Both Russian and U.S. intelligence services want the ability to break into anything.

They would publicly endorse insecure algorithms, and then employ more secure algorithms in their own classified systems.

I think encryption quality is best evaluated by math and technical testing, not international political triangulation.

Alternatively we could use hash-based signature schemes which have been proven secure under certain assumptions about hash functions, such as SPHINCS, or ZKP based schemes along the lines of Picnic (Picnic in particular uses LowMC which is somewhat new). In that case a backup seems unnecessary.

https://kyberslash.cr.yp.to

Reply on news.ycombinator.com