Why we don’t generate elliptic curves every day • Hacker News Board

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

#21

Post by nmadden » Tue, Oct 24, 2023, 7:58 PM UTC

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;…

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

If I remember correctly, part of the reason for the cofactor in 25519 is because Montgomery curves have to have a cofactor and only those curves have the nice x-only Montgomery Ladder, which basically rules out invalid curve attacks (so long as the curve is twist-secure — not all the NIST curves are IIRC). Do the complete addition formulas for short Weierstrass curves also fix this? Invalid curve attacks are a major danger for NIST curves.

I know you can use compressed point representation to get the same benefit, but that seems very rare in NIST curve implementations (because old now-expired patents). The landscape of NIST prime-order curve implementations is not great. If all those libraries were going to actually switch to complete addition formulas and compressed public keys then I might feel better about them enjoying a renaissance.

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

#22

Post by rainsford » Tue, Oct 24, 2023, 8:02 PM UTC

capitainenemo wrote: post #16

oh_sigh wrote: post #15

Earlier quoted context omitted.

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?

It's an interesting thought experiment, but it feels a little like trying to come up with the best defense against alien invaders. We're already talking about attackers able to craft cryptographic weaknesses decades of peer review can't discover or explain. Trying to figure out how to usefully constrain their algorithm design choices does not seem like a winning strategy.

The bitcoin block hash thing is interesting, but if you're talking about an attacker with that kind of unknown but sophisticated capability, how do you know it actually thwarts their plans? Maybe all they need is any large number with high entropy or maybe the leading zeros characteristic of bitcoin block hashes is actually key to their attack? Once you imbue your adversary with unknown powers, it's by definition difficult to know what helps or hurts them.

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

#23

Post by tptacek » Tue, Oct 24, 2023, 8:38 PM UTC

nmadden wrote: post #21

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;…

> 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). If I remember correctly, part of the reason for the cofactor in 25519 is because Montgomery curves have to have a cofactor and only those curves have the nice x-only Montgomery Ladder, which basically rules…

I agree with you, and am reassured by cryptosystems that use 25519 and put on edge by those that use the P-curves (not because of backdoor conspiracy theories, which are silly, but because the P-curves are easy to mess up). But cryptography engineers increasingly disagree with me.

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

#24

Post by MzxgckZtNqX5i » Tue, Oct 24, 2023, 9:32 PM UTC

cratermoon wrote: post #4

TIL that there are known attacks on primality testing routines, where the test will accept as prime a composite number. Vulnerable libraries at the time of the paper (2018) included OpenSSL, GMP, Apple, JSBN, Cryptlib, LibTomMath, LibTomCrypt, WolfSSL, Bouncy Castle and Botan.

It's a very well made paper, absolutely suggested if you're into cryptography and number theory.

Prime and Prejudice: Primality Testing Under Adversarial Conditions by Martin R. Albrecht, Jake Massimo, Kenneth G. Paterson, and Juraj Somorovsky.

https://eprint.iacr.org/2018/749

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

#25

Post by schoen » Tue, Oct 24, 2023, 9:50 PM UTC

pilif wrote: post #17

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

There can also sometimes be more specialized reasons than the general considerations given in this article. I forgot now whether it was DH or RSA or both, but there was a toy attack where interacting with a peer with super-bad maliciously-chosen parameters can also create an oracle for attacking the same party's simultaneous interactions with a third party, if the same secrets are used in both conversations.

Sorry for the lack of details, I just totally forget them. I know I did something like this in a CTF, though.

A vaguely related example could be that nonce reuse in DSA/ECDSA signatures can leak the signing key, so a DSA signer must not allow the other side to choose the nonce. That isn't conventionally seen as a "parameter", but it's easy to imagine that an implementer wouldn't automatically assume that it's actively dangerous to let the other party choose it.

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

#26

Post by capitainenemo » Tue, Oct 24, 2023, 10:29 PM UTC

rainsford wrote: post #22

capitainenemo wrote: post #16

Earlier quoted context omitted.

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?

It's an interesting thought experiment, but it feels a little like trying to come up with the best defense against alien invaders. We're already talking about attackers able to craft cryptographic weaknesses decades of peer review can't discover or explain. Trying to figure out how to usefully constrain their algorithm design choices does not seem like a winning strategy. The bitcoin block hash thing is interesting,…

heh. well, could drop the leading zeros :)

But, yeah, magic powers, sure, anything goes. I was just thinking there must be something more reliable than NYT headlines.

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

#27

Post by nextaccountic » Tue, Oct 24, 2023, 10:29 PM UTC

capitainenemo wrote: post #16

oh_sigh wrote: post #15

Earlier quoted context omitted.

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?

It's way harder to fake physical measurements (like weather, solar activity, etc) published by international bodies, You could maybeeee influence the least significant digit but even this would be hard without cooking up experimental data.

Maybe get physical measurements, stock exchange data, newspaper headlines, and bitcoin blocks, all in 6 months in the future, and XOR all of them.

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

#28

Post by EGreg » Tue, Oct 24, 2023, 10:34 PM UTC

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.

That's why the Bitcoin and Ethereum crowd trust the Koblitz curves like secp256k1 instead of secp256r1 which is the only curve that is in widespread use in browsers, operating systems, secure enclaves etc.

The k1 curve has parameters like 15, whereas the "standard" one has curves with parameters chosen as an "arbitrary" number in the billions for some reason. People believe the NSA may have iterated through the previous ones until they found a vulnerable curve, and NIST recommended that. Take a look:

https://cointelegraph.com/news/this-researcher-says-bitcoins...

“(1) The Koblitz curve is specially designed for faster scalar multiplications. Hence the (signing, verifying and key generation) operations on Secp256k1 are faster than those on Secp256r1. (2) Although the Secp256r1 curve was announced to be randomly selected, there could still exist some suspicion that some backdoor might be secretly set up in the curve parameters. In contrast, the Koblitz curve parameters are mathematically determined, and there is little possibility for setting such a backdoor.”

However, given the prevalence of the r1 curve, Ethereum devs might want to add a precompiled contract so that people can sign into the blockchain without trusting web sites and wallet software:

https://ethereum-magicians.org/t/eip-7212-precompiled-for-se...

https://security.stackexchange.com/questions/256088/is-the-e...

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

#29

Post by tptacek » Tue, Oct 24, 2023, 10:37 PM UTC

schoen wrote: post #25

pilif wrote: post #17

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

There can also sometimes be more specialized reasons than the general considerations given in this article. I forgot now whether it was DH or RSA or both, but there was a toy attack where interacting with a peer with super-bad maliciously-chosen parameters can also create an oracle for attacking the same party's simultaneous interactions with a third party, if the same secrets are used in both conversations. Sorry fo…

Famously, small subgroup attacks in DH; I can't think of non-silly RSA parameter negotiation bugs (I mean, E=1 with SaltStack, but that doesn't really count). Invalid point bugs in ECDH and zero-mod-p in PAKEs are similar in spirit, but don't really derive from parameter negotiation.

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

#30

Post by euicnon » Tue, Oct 24, 2023, 10:38 PM UTC

Are there cryptographers with dissenting opinions to this article, or is what the author writes about generally recognised best practice?

I ask because I remember an article a while back where this same author had very confidently got some details wrong about CloudFlare and I think the CEO or CTO or someone like that had to step in and correct him.