Cloud of suspicion lifted from NIST curves | Hacker News Reader

Cloud of suspicion lifted from NIST curves

johndcook.com

23 pointsibobev14 comments

Since when has evidence of a plausible innocuous explanation ever been enough to lift suspicion of an espionage intelligence operation?

If I was the NSA, the most efficient use of compute power would be to generate an enormous library of innocuous hashes/seeds, then generate my secret key pairs, then find collisions. Call it the No Cloud Of Suspicion Evil Key Generator.

Depending on the exact rainbow table used they wouldn't necessarily be able to recover the original seed generator (that would require more space, and they're already going to be stretching space limits).

Why would they not have released the timestamp a while back then?

Because they work for a sigint agency. Secrecy is a way of life for them. They probably wouldn’t even tell their own children what they had for breakfast.

As explained on the previous post, when using a method like this there's not enough innocuous seeds to find bad keys. You might semi-plausibly get really lucky and find one but not this many.

As I explained in my reply, you're not limited to just UNIX timestamps. Even the original history was "hash of a passphrase," so there's plenty of entropy available.

You don't care exactly what the innocuous seed is, as long as its innocuous. You can always claim you forgot.

The fact that the "not enough entropy, everything's fine" narrative is being pushed across multiple threads isn't exactly calming down my Spidey-sense...

But all of these numbers are based on timestamps using the same generator, except maybe one. That's too hard of a coincidence for them to have searched all that much bigger of a space. There's an obvious flexibility in the timestamps themselves, but the number of flexibile bits on top of that is limited in reasonable scenarios.

If the finding was a hashed sentence, the analysis would be very different. There's so many sentences you can make. But using an extremely common RNG and seeding it with system time? Except with crazy crazy luck, that means the entropy really is in the same ballpark as what it appears to be. And if they found special weak curves with 25-40 bits of entropy, then they're way too common and we have bigger worries about the entire foundation of ECC collapsing.

The problem is that only part of the generation is done using an arguably-harmless well-known algorithm.

The process is essentially: 1) take the current UNIX time as integer, 2) seed a POSIX drand48 generator with it, 3) draw random numbers and feed it to X9.62-1998 A.3.3.2 - which starts with "choose an arbitrary seed and sha1 it", 4) discard some via an unknown mechanism.

People have made a convincing argument that there isn't enough entropy in 1) and 4) to be malicious. What hasn't been addressed is that 1) and 2) are arbitrary choices, and someone with malicious intent could just as well have chosen "take the current UNIX time as ISO8601", "take the current second of the year", "take the current date as given by `date`", and similarly many variations on the choice of PRNG algorithm to arrive at one of a wide variety of potential harmless-looking algorithms.

Coming up with a few hundred variations of each wouldn't be too difficult - and that's instantly another 20 bits or so of entropy. Add the possibility of doing timestamps in milliseconds and it's 10 more. Now your "you need 70 bits of freedom to select a weak curve, and we've barely got 30" is down to "... and we've barely got 60". Start considering slightly more esoteric things like "use your favorite Bible phrase as initial seed" and I bet you can fill up that gap without too much effort.

Is it far-fetched, and it is far more likely that it was indeed done in good faith? Probably, yeah. Then again, we do have Dual_EC_DRBG as a reminder that this is exactly the sort of stuff that NSA and NIST has a habit of doing...

Given how many results they calculated with the same arbitrary choice of method, there just aren't that many plausible extra bits that they could have gone through that would be in the same simplicity range.

The further up in the complexity tree we think about them looking, the more implausible it is that they needed that many bits but managed to luck into such a simple one.

That's a fair point! On the other hand, perhaps backdooring one curve was already enough for them, as they could suggest that one as the "preferred" option?

Maybe, but the entropy estimates for breaking a curve cited in the other thread are a ton of bits. It would be hard to align even a single one with a simple method.

Is "it would be hard" enough when it comes to security and your opponent is the NSA?

Personally, I'd rather choose the option described at least as "it would be virtually impossible" - but preferably even "it was designed from the start to be completely impossible".

It would be nearly impossible to align it to something simple and straightforward enough.

previously discussed; Claude reveals ECDSA curve origins: https://news.ycombinator.com/item?id=50122800)

If you do a time of day analysis on these timestamp seeds, you'll find most of them generated during plausible business hours in the US eastern region.

I still think the timestamps could have been hand selected. There's no guarantee they confined themselves to actual gps time.

Reply on news.ycombinator.com