7 ms·

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 simpl

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.

Retr0id 3y ago
The explanation in this video is what made it click for me: https://www.youtube.com/watch?v=K026C5YaB3A https://www.youtube.com/watch?v=K026C5YaB3A
- kevvok 3y ago
  Same here: this video helped me finally understand the basics concepts underlying LWE
- sandyarmstrong 3y ago
  Thank you! This video was GREAT. I was having trouble putting it all together from the wikipedia page alone.
tptacek 3y ago
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.
- madars 3y ago
  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 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=monobook#H%C3%A5stad's_broadcast_attack 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.
pbsd 3y ago
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.
hannob 3y ago
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/ 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.
- randall 3y ago
  I love that security by difficulty is the new security by obscurity, but actually secure.
  - jmprspret 3y ago
    Is it new? Security by difficulty _is_ security.
  - vmfunction 3y ago
    Yeah talking about difficulty, then you will love this: https://www.science.org/content/article/china-s-quantum-satellite-achieves-spooky-action-record-distance 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.
- pauby 3y ago
  People rolling their own crypto still makes my jaw drop. I get people want something custom but the tradeoffs are just too great.
a1369209993 3y ago
> 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 https://blog.cr.yp.to/20240102-hybrid.html
- tptacek 3y ago
  There are essentially no mainstream systems that don't do this. That's why new systems deploy things like PQ3.
  - a1369209993 3y ago
    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.
    - tptacek 3y ago
      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.
deleted 3y ago
[deleted]
Ar-Curunir 3y ago
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.
orangejake 3y ago
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/ https://mark-schultz.github.io/nist-standard-out/

Retr0id 3y ago

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

kevvok 3y ago
Same here: this video helped me finally understand the basics concepts underlying LWE
sandyarmstrong 3y ago
Thank you! This video was GREAT. I was having trouble putting it all together from the wikipedia page alone.

tptacek 3y ago

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.

madars 3y ago
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 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=monobook#H%C3%A5stad's_broadcast_attack 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.

pbsd 3y ago

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.

hannob 3y ago

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

randall 3y ago
I love that security by difficulty is the new security by obscurity, but actually secure.
- jmprspret 3y ago
  Is it new? Security by difficulty _is_ security.
- vmfunction 3y ago
  Yeah talking about difficulty, then you will love this: https://www.science.org/content/article/china-s-quantum-satellite-achieves-spooky-action-record-distance 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.
pauby 3y ago
People rolling their own crypto still makes my jaw drop. I get people want something custom but the tradeoffs are just too great.

a1369209993 3y ago

> 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 https://blog.cr.yp.to/20240102-hybrid.html

tptacek 3y ago
There are essentially no mainstream systems that don't do this. That's why new systems deploy things like PQ3.
- a1369209993 3y ago
  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.
  - tptacek 3y ago
    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.

deleted 3y ago

[deleted]

Ar-Curunir 3y ago

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.

orangejake 3y ago

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/ https://mark-schultz.github.io/nist-standard-out/