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

11–20 of 76 posts

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#11

Post by Y_Y »

mike_hearn wrote: post #7

The naming is unfortunate. Some people (Ubuntu...) have concluded that because some curves are branded "safe" that must mean all the other curves are therefore "unsafe" and must be aggressively phased out as if they were MD5. They're changing apt to refuse to download from repositories signed using NIST curves, for instance. This doesn't make a whole lot of sense unless you think the NSA have an unknown backdoor that…

> unless you think the NSA have an unknown backdoor that nobody was able to find

Your post names sense to me, but I don't think it's too crazy to allow for the possibility that e.g. the NSA has backdoored some of the "recommended" crypto constants in current use.

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#12

Post by ivlad »

bvrmn wrote: post #9
ramchip wrote: post #5

Earlier quoted context omitted.

"Seriously, stop using RSA" https://news.ycombinator.com/item?id=30879442

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 quantum computer would be needed to attack ECC.

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#13

Post by ogogmad »

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

Tl;dr reason: RSA requires larger key sizes, which makes it slower. ECC makes cryptanalysis more complicated, so the keys can be made smaller, which makes it faster.

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#14

Post by mike_hearn »

red_admiral wrote: post #8
mike_hearn wrote: post #7

The naming is unfortunate. Some people (Ubuntu...) have concluded that because some curves are branded "safe" that must mean all the other curves are therefore "unsafe" and must be aggressively phased out as if they were MD5. They're changing apt to refuse to download from repositories signed using NIST curves, for instance. This doesn't make a whole lot of sense unless you think the NSA have an unknown backdoor that…

People migrating to djb's curves, or at least allowing them as a first-class citizen, include - SSH (which includes git over SSH - github suggests djb's Curve 25519 as default: https://docs.github.com/en/authentication/connecting-to-github-with-ssh/generating-a-new-ssh-key-and-adding-it-to-the-ssh-agent) - TLS (recommended in n1.3) - NIST (allows Curve25519, but isn't the default choice) - various cryptocurrency crap…

Yes, but SSH isn't e.g. forbidding you from connecting to servers that use RSA or secp256r1, whereas they want to make apt refuse to access repositories that aren't using djb's curves.

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#15

Post by genewitch »

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…

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?

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#16

Post by red_admiral »

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…

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-quantum crypto", not "go back to RSA" so I infer that they think RSA-4096 might still be vulnerable.

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#17

Post by red_admiral »

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 think it matters not only how many qubits you have, but how they are "connected". As far as I know, it's a far easier problem to put N qubits in a chain with O(N) connections, than it is to have N qubits with O(N^2) connections to form a complete graph. And I believe the second example is what you need to do Shor's algorithm.

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#18

Post by red_admiral »

Y_Y wrote: post #11
mike_hearn wrote: post #7

The naming is unfortunate. Some people (Ubuntu...) have concluded that because some curves are branded "safe" that must mean all the other curves are therefore "unsafe" and must be aggressively phased out as if they were MD5. They're changing apt to refuse to download from repositories signed using NIST curves, for instance. This doesn't make a whole lot of sense unless you think the NSA have an unknown backdoor that…

> unless you think the NSA have an unknown backdoor that nobody was able to find Your post names sense to me, but I don't think it's too crazy to allow for the possibility that e.g. the NSA has backdoored some of the "recommended" crypto constants in current use.

Snowden said that they were doing this, I think?

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#19

Post by red_admiral »

mike_hearn wrote: post #14
red_admiral wrote: post #8

Earlier quoted context omitted.

People migrating to djb's curves, or at least allowing them as a first-class citizen, include - SSH (which includes git over SSH - github suggests djb's Curve 25519 as default: https://docs.github.com/en/authentication/connecting-to-github-with-ssh/generating-a-new-ssh-key-and-adding-it-to-the-ssh-agent) - TLS (recommended in n1.3) - NIST (allows Curve25519, but isn't the default choice) - various cryptocurrency crap…

Yes, but SSH isn't e.g. forbidding you from connecting to servers that use RSA or secp256r1, whereas they want to make apt refuse to access repositories that aren't using djb's curves.

SSH by default isn't, but admins can set up their own list of allowed ciphers in their config file. Github, for example, has banned ssh_dss - I think they still support ECDSA, but they only mention Curve25519 and RSA (with caveats) on their SSH keys page.
Post reply on HN