Cloud of suspicion lifted from NIST curves

Posted by ibobev 2 days ago

Counter23Comment14OpenOriginal

Comments

Comment by schiffern 2 days ago

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

Comment by Dylan16807 2 days ago

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.

Comment by crote 2 days ago

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

Comment by Dylan16807 2 days ago

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.

Comment by crote 2 days ago

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?

Comment by Dylan16807 2 days ago

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.

Comment by crote 2 days ago

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

Comment by Dylan16807 2 days ago

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

Comment by schiffern 2 days ago

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

Comment by Dylan16807 2 days ago

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.

Comment by dooglius 2 days ago

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

Comment by seanhunter 2 days ago

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.

Comment by aaron695 2 days ago

[dead]

Comment by Doohickey-d 2 days ago

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

Comment by bob1029 2 days ago

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.