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

Why we don’t generate elliptic curves every day

words.filippo.io

Post reply on HN
Print view View original

11–20 of 54 posts

Re: Why we don’t generate elliptic curves every day

#11

Post by thadt »

ethbr1 wrote: post #2

Curious to hear someone with more expertise than me opine on the validity of brute forcing standardized parameters, which doesn't seem to be discussed in article. Are standardized elliptical curves still susceptible to being "individually" broken in ECDH in practice? Or are there other subsequent randomized mechanisms to accomplish forward secrecy / per session resistance? I understand the article's point against div…

Brute force? I don't think so. Orders of magnitude in brute force are sometimes easier to look at as raw numbers. If we take the sibling comments estimate of the global BitCoin network's total computation of 2^90, multiply it arbitrarily by three orders of magnitude we get:

  2^90        =            1237940039285380000000000000
  2^90 * 1000 =         1237940039285380000000000000000
  2^128       = 340282366920938000000000000000000000000
Even G20 nation states would still be many orders of magnitude short. Much (much, much, much) cheaper to spend your money and energy on an actual Manhattan Project. Then just show up with a nuclear warhead and ask politely for the key.

Re: Why we don’t generate elliptic curves every day

#12

Post by tptacek »

phkahler wrote: post #7

The author never addresses the issue of trusting standard parameters. I agree with them on the rest, but standard parameters need evidence that they were not specially selected for reasons unknown to everyone else.

You're never going to get a satisfactory answer. The world's foremost proponent of not trusting standardized parameters wrote and repeatedly submitted a paper demonstrating a model attack that targeted curves built from mathematical constants; when you've "backdoored pi", there's really no place to go from there.

That author's subtext, as I understood it, was that curves should be selected by functional optimization; pick the curve parameters that best solve the engineering problems. It was a useful argument given their preferred curve, 25519, which does indeed have a lot of attractive engineering features! But it's not hard to see that engineering excellence is a selection principle with even more degrees of freedom than mathematical constants; moreover, you're only ever considering optimality at a fixed point in time, but the optimums change over time --- cofactors might be less important when we lack complete additional formulae for a Weierstrass curves, which makes them hard to implement in constant time, but much more important once we do (as is the case now).

There's really no way around just doing the computer science and cryptological work of working out curve attacks. That's the Menezes and Koblitz argument from the "Enigma" paper: that the reason to trust the NIST P-curves is that we'd know by now if they were weak (not because NSA doesn't have secret attacks, but because the mechanism by which they were generated would result in whole large classes of broken curves that academic cryptography and mathematics would have caught by now).

If you don't find Alfred Menezes and Neil Koblitz persuasive surveyors of elliptic curve security, that's fine, but my response would be that you can't really trust any parameters at all at that point. Certainly, investing trust in the cryptographers best known to the generalist programmer audience seems like a bad alternative strategy.

Re: Why we don’t generate elliptic curves every day

#13

Post by lazide »

adgjlsfhk1 wrote: post #9
wolf550e wrote: post #6

Earlier quoted context omitted.

Every P-256 or X25519 ECDH operation uses a new ephemeral single-use key breaking which is about as hard as brute forcing AES-128. Global bitcoin hash rate is something like 90 bits per year. People think NSA doesn't have more hardware than all the bitcoin miners together. If they can break 128 bit security, they can't break it for every roundtrip in a Signal chat. I don't know what they would even use the capability…

and more importantly, any operation that needs that much compute power can be more efficiently solved by passing around a couple billion dollars of bribes

Or blackmailing the right person.

Re: Why we don’t generate elliptic curves every day

#14

Post by throw0101c »

tptacek wrote: post #12
phkahler wrote: post #7

The author never addresses the issue of trusting standard parameters. I agree with them on the rest, but standard parameters need evidence that they were not specially selected for reasons unknown to everyone else.

You're never going to get a satisfactory answer. The world's foremost proponent of not trusting standardized parameters wrote and repeatedly submitted a paper demonstrating a model attack that targeted curves built from mathematical constants; when you've "backdoored pi", there's really no place to go from there. That author's subtext, as I understood it, was that curves should be selected by functional optimization;…

> That's the Menezes and Koblitz argument from the "Enigma" paper […]

PDF:

> In August 2015 the U.S. National Security Agency (NSA) released a major policy statement on the need for post-quantum cryp- tography (PQC). This announcement will be a great stimulus to the development, standardization, and commercialization of new quantum- safe algorithms. However, certain peculiarities in the wording and tim- ing of the statement have puzzled many people and given rise to much speculation concerning the NSA, elliptic curve cryptography (ECC), and quantum-safe cryptography. Our purpose is to attempt to evaluate some of the theories that have been proposed.

* https://eprint.iacr.org/2015/1018.pdf

Then-coverage:

* https://blog.cryptographyengineering.com/2015/10/22/a-riddle...

Re: Why we don’t generate elliptic curves every day

#15

Post by oh_sigh »

tptacek wrote: post #12
phkahler wrote: post #7

The author never addresses the issue of trusting standard parameters. I agree with them on the rest, but standard parameters need evidence that they were not specially selected for reasons unknown to everyone else.

You're never going to get a satisfactory answer. The world's foremost proponent of not trusting standardized parameters wrote and repeatedly submitted a paper demonstrating a model attack that targeted curves built from mathematical constants; when you've "backdoored pi", there's really no place to go from there. That author's subtext, as I understood it, was that curves should be selected by functional optimization;…

Hell, even picking seeds like "the text of the NYT headline from [future date]", since the FBI or some other shadowy governmental organization could lean on the NYT editor to construct the headline in a manner that is useful to them

Re: Why we don’t generate elliptic curves every day

#16

Post by capitainenemo »

oh_sigh wrote: post #15
tptacek wrote: post #12

Earlier quoted context omitted.

You're never going to get a satisfactory answer. The world's foremost proponent of not trusting standardized parameters wrote and repeatedly submitted a paper demonstrating a model attack that targeted curves built from mathematical constants; when you've "backdoored pi", there's really no place to go from there. That author's subtext, as I understood it, was that curves should be selected by functional optimization;…

Hell, even picking seeds like "the text of the NYT headline from [future date]", since the FBI or some other shadowy governmental organization could lean on the NYT editor to construct the headline in a manner that is useful to them

That seems solvable by picking things about the future that are a lot harder to influence, like the hashes of future bitcoin blocks, or the exact value of all stocks on the NYSE at a given moment in time.

... ok. stock one is probably easier to influence by suborning the exchange :) - all world exchanges?

Re: Why we don’t generate elliptic curves every day

#17

Post by pilif »

This is very timely for me. Only two weeks ago, I learned that the bouncycastle Java FTP client library refuses to talk to servers that run with custom dh_params and I was wondering why because my intuition told me that custom parameters should be better than parameters shared between everyone.

And now only two weeks later, I get a very good explanation as to why, like often in crypto, intuition was wrong

Re: Why we don’t generate elliptic curves every day

#20

Post by PartiallyTyped »

thadt wrote: post #11
ethbr1 wrote: post #2

Curious to hear someone with more expertise than me opine on the validity of brute forcing standardized parameters, which doesn't seem to be discussed in article. Are standardized elliptical curves still susceptible to being "individually" broken in ECDH in practice? Or are there other subsequent randomized mechanisms to accomplish forward secrecy / per session resistance? I understand the article's point against div…

Brute force? I don't think so. Orders of magnitude in brute force are sometimes easier to look at as raw numbers. If we take the sibling comments estimate of the global BitCoin network's total computation of 2^90, multiply it arbitrarily by three orders of magnitude we get: 2^90 = 1237940039285380000000000000 2^90 * 1000 = 1237940039285380000000000000000 2^128 = 340282366920938000000000000000000000000 Even G20 nation…

… or another stuxnet even.
Post reply on HN