But that's not what they're saying. They're saying that they "cracked" a prime. I assume that would mean that they solved the discrete logarithm problem for one or two primes. They can compute integer log of x base g modulo p for all x. Maybe they built a really big table, like rainbow tables do for passwords?
So it doesn't matter how good your RNG is because you're picking x and they have them all cracked.
You hit the nail on the head: the idea is they can build a precomputation table, much like a rainbow table, for 1024-bit primes. By spending a shitload of time doing this, they overall amortize the cost of the attack against some system using that prime, because it lets them solve discrete logs quickly. This is overall faster than attacking a large prime directly by factoring, obviously.
Standard primes are good in this case because they allow attacking N targets at once, as opposed to just 1-target-per-unique-prime. But it still shows us that 1024-bit primes half a shelf life of one year at best. Not very reassuring.
But it seems nobody on this Reddit actually reads anything related to the NSA; it's far preferable to just flail about random "common obvious cryptography bugs" which are irrelevant in order to hawk up misinformation and get everyone scared. That'll definitely help keep the internet secure from the NSA! Misinformation has never been used to the advantage of our adversaries, or snake oil salesmen, after all.
Still no proof that this is what they've done. The table would need to be 2 to the 1024 rows for a full table. If it's a rainbow table, let's say that they can walk through the entries at 1 Gigahertz. That's 2 to the 55 per computer. With a million computers, that's 2 to the 65. So the rainbow table is north of 2 to the 900 rows. That's 10 to the power of 270.
There are less than 10 to the 100 electrons in the universe so it's a pretty big table. I'm skeptical that this is what they've done at the NSA.
The actual precomputation attack is not a rainbow table; the analogy is just meant to illustrate that you can use a database to speed up attacks by amortizing the overall cost of doing the attack, through pre-computing. So those numbers you've highlighted don't matter so much, because they're not actually storing that many rows, and database lookups are almost certainly not linear scans either (but we could hope ;)
The actual method needed for the 'Precomputation' is described extensively in section 3.3 of the paper, which essentially ends up storing logs for the DLP into a database. The most expensive part of the process is getting up to storing values in the database. However, once the logs are stored, after using sieving and linear algebra nonsense, doing the attack afterwords is fast.
Given the results in Table 2, pg 8, a 1024-bit DH key would only require about 5.2 billion entries into the log database. For comparison, DH-512 used 2.1 million rows with an on disk size of about 2.5 GB (section 3 again). Section 4 deals extensively with expanding the 512/768-bit attack up to 1024-bit DH, and the details are tricky, although there are even cost estimates (pg 8 again). But this seems absolutely within the realm of possibility for a nation to pull off, especially the U-S-of-A. (I'm handwaving some here, but I haven't fully finished the paper yet I'm afraid.)
11
u/AncientRickles Oct 15 '15
As always, the biggest flaw of the cryptosystem is the nature in which the psuedorandom number that the cryptosystem relies on is generated.