Comment by fidotron
1 day ago
While this confirms the method of production it doesn't say anything about their selection, especially since they were, apparently, generated over a period of months. Specifically you cannot see those candidates that were generated and discarded.
"It is still conceivable that these curves were selected to have a specific property in principle by searching over timestamps to the random number generator."
Yes.
"However, you would only need to do that if you were going to disclose the timestamp as some evidence that the seed was innocuously generated."
Does not logically follow when "doing and saying nothing" will completely suffice.
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.
1 reply →
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.
5 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...
13 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.
2 replies →
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]
> While this confirms the method of production it doesn't say anything about their selection, especially since they were, apparently, generated over a period of months. Specifically you cannot see those candidates that were generated and discarded.
Well, at least now we have a way to perform that analysis! Generate a bunch of curves by varying (along any degree of freedom) the input parameters to the seed generating function and see if there's any difference between the curves that are generated.
I don't think ECDSA itself is a bad idea. You can 10x your signing capacity with the same hardware.
Why couldn't we make a new curve out in the open and then agree to use it? Increment an integer counter until a majority of cryptographers are satisfied.
The fact that the seed is not explained is troubling even if we can figure out how it was derived. We now know it uses a timestamp which means we can probe even deeper and more specifically into potential rigging of the numbers. I don't think we were supposed to figure this one out. I'd be interested in seeing the properties for curves of adjacent timestamps.
We use ed25519 if we care about that.
I think it does rule out any NOBUS vulnerability with these curves, doesn't it? My thinking may be a bit sloppy here, but for a curve to be NOBUS exploitable with N-bit security by its creators, I think it would have to have a property only shared by 1/(2^N) curves. It would be impractical to hash 2^(N-1) timestamps until you find one with the desired property, for any decent size of N--which is how many you'd have to do on average before finding one with that property.
Yeah, there's not nearly enough iterations here for a practical nobus vulnerability.
And here we see demonstrated that nothing can solve paranoia.
God bless you for keeping this alive.
It doesn't prove anything about the core part of the suspicion, which is they were selected using some undisclosed criteria, which may make them weaker or stronger than some other random numbers.
You are entirely familiar with the precedent of the DES s boxes of course, where that is exactly what happened.
> which may make them weaker or stronger than some other random numbers
Are there non-trivial weaker and stronger seeds for this category of elliptic curves?
7 replies →
The sibling subthread by fidotron apparently needed to be flagged, even though (or because?) it contains some of the most concrete information of all comments.
But I guess people are supposed to read Valsorda's reply only ...
If you keep posting like this you're gonna get microwaved from space ;)
I'm only posting like this because they already are.
Check out 133784883 then, it really gets the machine going.
2 replies →
"However, you would only need to do that if you were going to disclose the timestamp as some evidence that the seed was innocuously generated."
And the disclosure happened now through Anthropic that is 100% not going to anger the NSA before the IPO and will have permission.