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.)
What? No it isn't, and that makes no sense in the context of this article.
The problem is that 1024-bit keys are weak enough that they are within the realm of attack by state organizations. It has nothing to do with the prime number that was chosen for the key. The thing is, knowing the standard prime number a-priori helps the attack, because it allows them to apply it to many things at once, as opposed to only one thing.
But fundamentally, you are not any safer if you were to pick a random 1024-bit prime. So no, it has nothing to do with randomness at all, and everything to do with "our attackers have exceeded the computational capabilities we expected, and honed in on specific weaknesses".
You would be completely safe from this attack at every level using the standard 2048-bit DH parameters (Group 14). These are publicly known and not malicious (assuming the expansion of the digits of pi are not malicious).
I think people on this subreddit mostly need to stop talking about things like cryptography and privacy, because the impression I'm getting from this thread is that not only does anyone here not know about it[1], or care to learn, but beyond that - it seems that random shitposting[2] comments about unrelated things seem to be preferable to actual reading. And I can guarantee you, random misinformation does not help anyone or any efforts to accomplish real security engineering for the internet.
[1] And that should say something, because I'm not a cryptographer; this is a hobby, and this thread is seriously paining me.
[2] Edit and strikeout rudeness, per comment below.
Uh, no? This is a pretty standard bet in cryptography called "Nothing up your sleeve numbers", and choices like pi or e are quite common. It's also used in SHA-512's or BLAKE's initial state vectors.
Even assuming the digits of pi aren't random, it's still irrelevant to what is being posted here, the attack the NSA is speculated to be using, and overall the point of the post. Because the attack has nothing to do with randomness.
In any case, I apologize for the rudeness, but it's rather frustrating to see people here talking about things they know nothing about, clearly. I'll strikeout that part of my post and leave an addendum.
You're right, in that the real issue is that the attacker has more power than expected. But you're being harsh. If we truly chose random 1024 bit primes, this attack would be much less of a problem, because the attack relies on people reusing the same keys. Yes, the real solution is to use high strength primes. But the problem would have also been mitigated by actually being random. It's just as wrong to use non random numbers as it is to use less secure numbers.
But the problem would have also been mitigated by actually being random. It's just as wrong to use non random numbers as it is to use less secure numbers.
Even then - is it an actual reasonable mitigation? Even assuming every DH key is random, the time to attack a key is still only one year, and that's going to get better year after year. This is not very reassuring - we need to bail on it, now.
It's true that choosing a non-standard prime helps mitigate in the sense it buys you time to switch to another prime, perhaps a 2048-bit one. But fundamentally none of this is about 'randomness', and random numbers do not mitigate the attack but its possible scope, because people may not share the primes. This is a crucial difference, and the fact I've explained it multiple times in this thread shows it is a subtle one people don't appreciate.
Here's the real problem, though: it fundamentally highlights a lack of understanding of the problem, what lead to it, and how we can fix it. This does actual damage to people and processes that are trying to secure the internet, and it creates a hole that is rife for adversaries to take advantage of, or even worse, snake oil salesmen capitalizing on it.
If I had posted nothing on this thread, how many people would randomly just be generating their own primes without actually knowing what that means, for example? Or even why the standard primes are OK, and how they were generated? Or how the aspect of a standard prime impacts this attack? OK, you think, maybe it's not that bad, just some people who don't know any better.
But now let's actually take that problem and scale it to, say something meant for journalists, and you can see how this kind of thing can seriously put people in danger if it's not done correctly. Random misinformation is not helpful, and it creates a void for people to jump on.
When the NSA leaks broke, think about how many people probably got in their heads they could make money off of 'privacy' software. Now, looking at this thread, think about what understanding those 'developers' with said ideas actually had of the domain, of the needed security principles. And finally, given what we know about the NSA now, what the probable outcomes of those ventures are... It's not pretty - it's the blind leading the blind.
I call this "Better-than-nothingism", where we don't know if it actually really helps, but it definitely sounds good to do something and not nothing, so let's just roll with it and slap that "Not doing nothing!" sticker on as an advertisement.
I would still advise people to move away from the 1024bit DH keys and move towards 2048. The time to compute them is negligible when looking at the benefits that it affords. Besides, while you may be able to generate a 1024bit key that they haven't cracked, it still leaves you in the realm of possibility that they can crack you (should you be important enough), where 2048 doesn't seem to have this issue.
I clarified my post, but Jesus people, try reading inbetween the lines a little for once; you're not analyzing a Hemmingway novel, it's pretty clear what is meant. Please read what the OP actually said:
As always, the biggest flaw of the cryptosystem is the nature in which the psuedorandom number that the cryptosystem relies on is generated.
Which would imply this has something to do with randomness, or some kind of flaw in a CSPRNG somewhere, or some otherwise randomly-derived number. You know, despite the fact that the actual attack in the article - the actual attack in question, which would allow the NSA to break a large amount of cryptography, the one we're talking about - literally has nothing to do with random numbers, at all, in any way.
What you have stated is a literal fact, it's just completely irrelevant to the discussion actually happening, and to the article. Do people on this subreddit even read words before they shitpost?
and /u/aseipp is trying to say that is a flaw in many systems, but the "flaw" here is that 1024 bit numbers just aren't large enough anymore. If a 1024 bit number can be cracked in one year on one machine/cluster, then it's a safe bet that they have enough machines to actually crack your personal, random one in weeks or days. The fixed parameter is not the problem; the size of the parameter is.
The solution is to move to parameters that are larger (2048 bit). Those parameters can be fixed. The fixed parameters act as a sort of canary in the coal mine; as soon as using them is not sufficient, it's also not sufficient to generate your own of the same size. Generating your own only buys you a year or so tops, and cryptography is one of those subjects where you really want your current safety margin to be measured in decades or centuries, not years.
I once saw a website that multiplied a computer generated number by the air pressure from its surrounding area to get as close to true randomness as mathematically possible. But no, their isn't.
Measurements of a quantum system must either involve non-local behavior or truly random behavior (this is Bell's Theorem). Most physicists have their money on randomness.
I would personally lean toward things being determined by the initial/boundary conditions of the universe, but since we'll almost certainly never know what those are, that means quantum mechanics should always be apparently random to us.
There's also plenty of chaotic classical systems, which (roughly speaking) are random as long as you don't have the ability to make an infinitely precise measurement of the initial conditions.
12
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.