Comment by FiloSottile
1 day ago
Given how expensive this computation would have been in 1997, it makes perfect sense they'd taken months, but even if we assume they tried all timestamps of 1997 and selected arbitrarily among the first 16 viable candidate of any timestamp, that's just ~30 bits of freedom.
Finding out there is a class of weak 256-bit elliptic curves so large that they can be hit randomly with 2^30 tries would be a cryptanalytic breakthrough analogous to discovering all elliptic curve cryptography is broken.
Read section 3.1 of the Koblitz and Menezes paper. It was already implausible with 160 bits of freedom. https://eprint.iacr.org/2015/1018
If you want to believe the NSA knows ECC is broken and chose to risk moving the US government to it and somehow no one figured out the same break in 30 years, you're free to do so. But pretending the seed choice plays any role in that theory is over.
This is unrelated to the above comment, but I figured I'd ask while we're here. You state at the end of your blog post on this topic that you'd now probably recommend the NIST curves over Curve25519. Why is that?
I'm guessing affinity towards prime curves vs cofactor.
As a complete layman, I do wonder why n grows with each subsequent curve, rather than with number of bits. Does this not suggest they were 'searching harder'?
Almost all of the smaller values of n are not valid curve values, so they were searching "harder" but just for valid seeds. If you look at the generator output in [1], you'll see that:
1. Only a very small number of valid seeds were discarded when compared to the number of n values. It seems we don't yet know why about half of the valid seeds were discarded but the explanation of a buggy curve validity checker doesn't seem implausible to me.
2. Directly to your point, most of the prime192 and prime239 curves required larger n values to find a valid seed and they are both smaller and used an earlier timestamp.
[1]: https://words.filippo.io/seeds-solved/
>they can be hit randomly with 2^30 tries
More precisely: not very random tries.
unless your guess is that the hypothetical ECC weakness is somehow correlated with the LCG structure, the draws from the LCG are as good as random.
It is possible such a correlation could occur. but it would be much weirder than this being the result of a random search, which would already be very weird.
I find it slightly less weird because I see potential for indirect attacks on the not-quite-so-ECC parts of actual implementations. Wherever a network client can ask many times for each of the different, but somehow not entirely uncorrelated curves, it might be able to expose previously not deemed critical side channels. Following in the general direction of the discoveries that so far resulted in IV and padding determinism/randomness being considered as important as the "actual crypto" itself. In that case the structures that would need to somehow interact would not be ECC and LCG, but merely LCG and key derivation..
Yeah... It would only be the second time they tried to do exactly that, with elliptic curve related crypto nonetheless
If your comparison here is to Dual EC, the two constructions are utterly unalike; you might as well compare it to the DES S-boxes.
Sure, the construction is different, but for all I know, there is a weakness in some subset of curves, and by not using open "nothing up my sleeve" practices for selecting their curves, they invited speculation. My point is that this is an untrustworthy actor who has shown itself to be untrustworthy on many occasions, and that you could make a similar migration argument about that, since it was pushed through FIPS. The fact that it was also EC based was not very relevant, I just thought that was funny.
4 replies →
Why limit to that? Especially since the official history had it as "hashed passphrase" (which would, of course, provide ample entropy).
A confusing official story doesn't disprove anything. If anything, that would be standard operating procedure for a signals intelligence plant.
NSA is the largest employer of mathematicians in the world.
A breakthrough would indeed be a terrible thing to waste. If I had one, I'd make a good and boring official cover story, and stick to it! Regular old spy-craft stuff, in other words. ;)
"..chose to risk moving the US government to it.."
Oof, about that...
go on...
There is some evidence that they have done it becore.
Specifically, that they had a backdoor for Dual EC DRBG[1], and pushed for a shorter key lenghth for DES, to intentionally weaken it.
It is, obviously, controversial. But I think there is certainly enough there that I wouldn't be confident that the NSA wouldn't recommend something they knew to be weak in some way, even to other government organizations.
[1]: https://en.wikipedia.org/wiki/Dual_EC_DRBG
3DES...
11 replies →
[flagged]
There are plenty of weak curves. See djb's safecurves project. Maybe the NSA found an unknown type of weakness.
There are now multiple cryptographers on this thread (not counting me; I'm not a cryptographer) explaining why this is now utterly implausible.
Unfortunately one of these cryptographers' responses are in a thread that was collapsed for wrongthink.
1 reply →
Where do you get the 2^30 from? drand48 could be f_0, but they could have tried f_1, f_2, ... as well and chosen the f_n that yielded the desired but plausible values.
All we know is that drand48 gave values that the NSA was happy with.
[flagged]