The NIST Elliptic Curves Seeds Bounty Has Been Claimed
47 points by FiloSottile
47 points by FiloSottile
this nicely completes the “rehabilitation arc” of NIST elliptic curve cryptography, which I would now personally recommend over Curve25519/Ed25519/X25519
What are the benefits of the NIST curves? I know that the curve25519 cofactor caused problems, but I thought that was mitigated by ristretto,
I have a list I should publish at some point of mild advantages of one over the other but really what dominates is that P-256 is everywhere, including in hardware, and once the benefits are so marginal and mixed and context-specific I would rather write one very good implementation of one curve than split my energy across two.
Anyway, it's all moot now: the right choice between ECDSA P-256 and Ed25519 is ML-DSA-44.
My uninformed (likely wrong) intuition is that for an elliptic curve to have a NOBUS vulnerability with N-bit security, it would have to have a property that is true only of 1/(2^N) elliptic curves. Therefore, NIST/NSA/whoever is being accused of putting a backdoor in ECDSA would have to hash 2^(N-1) timestamps before expecting to find one that generates a curve that happens to have that particular NOBUS vulnerability. Does that seem true to people with better understanding than myself?
(I know Filippo's blog post mentions that there are only ~2^30 possible timestamps in the relevant range, but I'm curious about the more general case)
Great news.
I've seen interop issues with people disabling ECDSA for these worries, and I often run into incompatibilities between protocols that only support ed25519, and my hardware tokens/TPMs that only support ECDSA.
I have tried in vain to get projects to allow ECDSA (consistent with prevailing consensus), to address these interop issues.
Hopefully this will persuade https://github.com/jtesta/ssh-audit to not flag ECDSA, also a source of interop issues.
This contributed to enduring conspiracy theories, which had significant appeal among the non-specialist public (although many have since moved on to other, adjacent, conspiracy theories). All this speculation harmed confidence in robust cryptographic systems and was part of my motivation for the bounty.
This week’s findings completely rule out the technique described by Bernstein and Lange.
This feels a bit harsh? If it was only this week's findings that completely ruled this out, was it so irrational to have been sceptical about ECDSA?
After all, as the author persuasively argues in their post on accelerated PQC timelines:
If you are thinking “well, this could be bad, or it could be nothing!” I need you to recognize how immediately dispositive that is. The bet is not “are you 100% sure a CRQC will exist in 2030?”, the bet is “are you 100% sure a CRQC will NOT exist in 2030?” [...] Remember that you are betting with your users’ lives.
I don't know whether this is good news that the curves were not backdoored, or bad news that such a simple linear congruential generator was used to create the seed. Surely as cryptographers they would've known to use a CSPRNG to generate the seed? If they used something so weak for the seed, what else did they get wrong with the curves?
https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number
The interesting and slightly confusing thing was that the way it was derived wasn't documented already. Especially in light of the conspiracy theories.
Those conspiracy theories are a relatively modern phenomenon, so it's not surprising they never expected to be asked about the method, and by the time they were, they had forgotten it.
Those conspiracy theories go back to 1975 when the NSA modified the S-boxes in DES that had been provided by IBM[1]. NIST should have known better.
[1] In that case[2] there was nothing nefarious; a decade later non-NSA cryptographers were able to discover the attack that NSA's modifications had protected against.
[2] In other cases NSA's magic numbers were nefarious: it's all but proven that Dual-EC DRBG has a kleptographic weakness and that the NSA was working to break TLS with it.
Non-cryptographer here. Does it matter? Would the curves have been breakable (or more breakable) if the seeds were 1, 2, 3, 4, 5? (Excluding numbers that didn't generate a valid curve.)
My uninformed (likely wrong) intuition is that for an elliptic curve to have a NOBUS vulnerability with N-bit security, it would have to have a property that is true only of 1/(2^N) elliptic curves. Therefore, NIST/NSA/whoever is being accused of putting a backdoor in ECDSA would have to hash 2^(N-1) timestamps before expecting to find one that happened to have that particular NOBUS vulnerability. Does that seem true to people with better understanding than myself?
(I know Filippo's blog post mentions that there are only ~2^30 possible timestamps in the relevant range, but I'm curious about the more general case)