Rendered at 10:57:57 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
schiffern 14 hours 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).
Dylan16807 14 hours 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.
crote 8 hours 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...
Dylan16807 7 hours 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.
crote 7 hours 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?
Dylan16807 7 hours 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.
crote 7 hours 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".
Dylan16807 6 hours ago [-]
It would be nearly impossible to align it to something simple and straightforward enough.
schiffern 8 hours 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...
Dylan16807 8 hours 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.
dooglius 14 hours ago [-]
Why would they not have released the timestamp a while back then?
seanhunter 13 hours 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.
aaron695 7 hours ago [-]
[dead]
bob1029 2 hours 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.
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).
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...
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.
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".
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...
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.
I still think the timestamps could have been hand selected. There's no guarantee they confined themselves to actual gps time.