Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Safe curves for Elliptic Curve Cryptography [pdf]

eprint.iacr.org

Post reply on HN
Print view View original

51–60 of 76 posts

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#51

Post by less_less »

ivlad wrote: post #12
bvrmn wrote: post #9

Earlier quoted context omitted.

It's hilarious foil-hat level shit here: https://blog.trailofbits.com/2019/07/08/fuck-rsa/#comment-91...

He is not wrong on the main claim, which is “All ECC (X25519-P521) will be broken by private sector quantum chips before RSA-2048 due to the physical limitations of stabilizing qubits.” Shor’s algorithm is polynomial, however the number of qubits required is in order of O(log(n)^2), where n is the length of the key. Because ECC keys are much shorter (e.g., 256 to 521 bits) than RSA (2048 to 4096 bits), a smaller quan…

I'm not sure this is true anymore. There are recent improvements in quantum factoring algorithms, which significantly reduce the number of qubits required. See eg https://eprint.iacr.org/2024/222

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#52

Post by less_less »

madduci wrote: post #20

I would like to see if the authors of this paper have released some kind of benchmark/validation script/tool implementing the maths and checks behind their paper

There's a bunch of validation software at https://safecurves.cr.yp.to/verify.html

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#53

Post by less_less »

tptacek wrote: post #43
fguerraz wrote: post #3

It begs the question: what's wrong with RSA??? I've always heard it's because implementation is hard and ECC magically solves most of these problems, but clearly that's not the case...

Everyone else is talking about key lengths here, but the better reason to avoid RSA is that it's full of footguns that ECC hides from you. ECC constructions don't generally expose a direct encrypt-to-the-public-key operation, which is almost never what you want (unless you're doing RSA-KEM, which nobody does) but frequently what you get. The de facto standard RSA padding --- by the way, another parameter ECC doesn't…

I mostly agree with this, but you could still have advice of like "use only xxx flavor of RSA-KEM for key establishment and yyy flavor of RSA-FDH-SHAKE for sigs" and things would be fine. Those still aren't exactly easy to implement, but they aren't really any harder than ECC. But they do have bigger keys and are slower, especially for keygen.

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#54

Post by less_less »

red_admiral wrote: post #50
less_less wrote: post #39

Earlier quoted context omitted.

> Dual EC DRBG is a bad design and so you shouldn't use it. It is reasonable to believe it's backdoored, but only the same way it would be reasonable to believe David Cameron stuck his dick in a dead pig. Some people say he did, he says he didn't, there's no conclusive proof available - and it's worth noting the "source" is a man who has a grudge against Cameron. Hard disagree. Dual_EC_DRBG more-or-less encrypts the…

Bernstein's argument is that, even if the NIST curves are not backdoored mathematically, they're designed in a way to strongly coerce implementors towards a route which leaves side-channels open, such as non-constant-time implementations or sloppy handling of invalid data such as points that do not lie on the curve, or in a small-order subgroup (all of which has been seen in practice).

Bernstein has multiple arguments. Section 7 is about ways that the NIST curves could hypothetically be backdoored, and about designing curves in a "rigid" way such that they are less likely to be backdoored ... at least assuming that small parameters, or parameters near powers of 2, aren't more likely to be weak.

But yeah, he also argues that Montgomery / Edwards curves are easier to implement securely. IMHO he's right, but he exaggerates the difference. Montgomery and Edwards curves still have plenty of footguns, and some of these are not present in prime-order short Weierstrass curves like the NIST curves. In particular, the fact that Montgomery and Edwards curves must have a cofactor of at least 4 leads to problems: side-channel attacks like "May the 4th be with you", EdDSA signature validity not actually being defined, needing additional complexity (Ristretto/Decaf) to avoid protocol changes, etc.

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#55

Post by ivlad »

tptacek wrote: post #42
ivlad wrote: post #12

Earlier quoted context omitted.

He is not wrong on the main claim, which is “All ECC (X25519-P521) will be broken by private sector quantum chips before RSA-2048 due to the physical limitations of stabilizing qubits.” Shor’s algorithm is polynomial, however the number of qubits required is in order of O(log(n)^2), where n is the length of the key. Because ECC keys are much shorter (e.g., 256 to 521 bits) than RSA (2048 to 4096 bits), a smaller quan…

This is deeply silly.

… because?

Edit: yes, I read it and it is.

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#56

Post by dadrian »

less_less wrote: post #53
tptacek wrote: post #43

Earlier quoted context omitted.

Everyone else is talking about key lengths here, but the better reason to avoid RSA is that it's full of footguns that ECC hides from you. ECC constructions don't generally expose a direct encrypt-to-the-public-key operation, which is almost never what you want (unless you're doing RSA-KEM, which nobody does) but frequently what you get. The de facto standard RSA padding --- by the way, another parameter ECC doesn't…

I mostly agree with this, but you could still have advice of like "use only xxx flavor of RSA-KEM for key establishment and yyy flavor of RSA-FDH-SHAKE for sigs" and things would be fine. Those still aren't exactly easy to implement, but they aren't really any harder than ECC. But they do have bigger keys and are slower, especially for keygen.

They are harder to implement than ECC.

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#57

Post by ivlad »

red_admiral wrote: post #16
ivlad wrote: post #12

Earlier quoted context omitted.

He is not wrong on the main claim, which is “All ECC (X25519-P521) will be broken by private sector quantum chips before RSA-2048 due to the physical limitations of stabilizing qubits.” Shor’s algorithm is polynomial, however the number of qubits required is in order of O(log(n)^2), where n is the length of the key. Because ECC keys are much shorter (e.g., 256 to 521 bits) than RSA (2048 to 4096 bits), a smaller quan…

RSA needs 4k (or 16k) keys because, with index calculus, these sizes reduce to a subproblem where you effectively need only 2^128 (or 2^256) time rather than the 2^{4k} for brute-force. I think, but I may be misremembering, that you could apply Shor's algorithm to speed up index calculus by going for the subproblem directly? In this case RSA would fall too. I note that the NSA recommendations are "move to post-quantu…

I am not NSA, but I think their idea is something along the “once Shor’s algorithm is practical for key sizes of hundreds of bits, it’s only a matter of a few years of engineering effort to make it feasible for thousands bits long keys”. In other words, there is no sufficient safety margin for larger keys.

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#58

Post by ivlad »

genewitch wrote: post #15
ivlad wrote: post #12

Earlier quoted context omitted.

He is not wrong on the main claim, which is “All ECC (X25519-P521) will be broken by private sector quantum chips before RSA-2048 due to the physical limitations of stabilizing qubits.” Shor’s algorithm is polynomial, however the number of qubits required is in order of O(log(n)^2), where n is the length of the key. Because ECC keys are much shorter (e.g., 256 to 521 bits) than RSA (2048 to 4096 bits), a smaller quan…

This is the first time in nearly 30 years I've ever heard the claim that you only need 18-20 qubits for something like a 256 bit key. I've only ever seen the claims of 1:1 key bit to qubits. Aren't there existing claimed quantum computers with 20 qubits? Isn't Canada's machine an order of magnitude more qubits?

I am sorry, I should’ve read it twice before posting. I meant, QC to attack longer keys should be bigger proportionally. Number of operations is logarithmic. Silly me.

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#59

Post by less_less »

dadrian wrote: post #56
less_less wrote: post #53

Earlier quoted context omitted.

I mostly agree with this, but you could still have advice of like "use only xxx flavor of RSA-KEM for key establishment and yyy flavor of RSA-FDH-SHAKE for sigs" and things would be fine. Those still aren't exactly easy to implement, but they aren't really any harder than ECC. But they do have bigger keys and are slower, especially for keygen.

They are harder to implement than ECC.

Really? My experience is that RSA in general is harder because it has so many knobs, but if you just lock it to the easiest-to-implement-securely choices then it's not so bad.

However, for DJB's point there is a major advantage for X25519/X448 specifically: it's hard to get a huge speedup by implementing them insecurely, and the same is not true of RSA.

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#60

Post by upofadown »

adgjlsfhk1 wrote: post #38
upofadown wrote: post #30

Earlier quoted context omitted.

>RSA must use very long keys, ... But probably no longer than 2048 bits: https://articles.59.ca/doku.php?id=em:20482030

imo this article dramatically understates the likelihood that the NSA has unpublished factoring algorithms. it also shows the CPU performance plateau, but GPUs have mostly followed exponential performance scaling

The bottleneck is with a process that can't be parallelized very well. So GPUs are not useful here.

The NSA might have a computer from a crashed alien spacecraft as well but we have to work with what we know. Of course that alien computer is well known to be helpless against RSA and effective against everything else... :)

Post reply on HN