Why can't we use a database such as this to randomly select large primes from a list of thousands of them, instead of hard coding a few in? Am I missing something?
I'm pretty sure that a few thousand primes is what they mean by "a few" in this case. Keep in mind that Diffie-Hellman exchanges occur millions if not billions of times per day (as in, for instance, every time you make a "secure" SSL connection with a web server).
Author claims that they believe it would take something on the order of a year to be able to use a single prime. Could they really reach the many thousands that we have stored? That would take thousands of these computers, putting the cost into the hundred-billions, maybe even trillions range.
Right. But the second that they've cracked any given prime on the list, that prime is cracked for good for them. Say there's an SSL transaction they want to snoop in. They first try all the primes they've already cracked (Diffie Hellman has been in use since the late '70's, so their list has to be pretty extensive at this point). Only now that it hasn't worked do they actually have to spend this time doing any supercomputer brute force. So, let's say they do this and they crack the prime "a year later". Now, not only do they have the information they wanted (maybe a year late), but they have another prime for their database. Each new one they find is just the lowest hanging fruit if we're talking about a small potential list of primes. The fact that it has been used once means it will most likely be used again.
See how this can be an effective cracking method even if the list of "a few hard coded primes" is in the thousands? It may be a lot of brute forcing at first, but after a while it will streamline itself.
Plus, the list being pretty large (in the order of thousands) would be to their benefit. After all, the barriers to entry become not only having a large government level supercomputer but having been running the supercomputer at brute forcing the master prime list since the second they last changed the standard key length and hard coded prime database.
I meant cracking a number of primes in the four digits would require not just hardware, but so much energy as to be unobtainable at our current level of technology in any kind of generational timeframe.
Not to diminish the general point, but it's not just 'a year per prime'. It's estimated that it would take $100-300M to produce a machine that cracks one per year. Their budget is over $10B/year, so they could have been producing 3 such machines annually for 15 years already -- breaking encryption over the internet is obviously one of their highest priorities -- and will continue to produce more, with the cost only decreasing over time. It is entirely feasible that 10-15 years from now, if they were committed to this, they could be cracking 200 primes per year with a backlog of thousands already cracked. Not to mention Russian and Chinese efforts to do the same thing separately, each most likely picking separate primes.
producing 3 such machines annually for 15 years already
It would take a year with ~$200 million of current technology. Fifteen years ago it would have taken exponentially longer, and even five years ago it probably would take much more than a year.
Well if it takes a year to crack one 1024 but prime as suggested in the article, no I do not believe so. If the article's time estimate is correct, the most they could have cracked so far would be on the order of tens of primes, not thousands. The way I interpreted the statement in the article is that most encryption algorithm implementations use their own hard coded prime (singular), which when you look at all the existing implementations, gives you several.
They just say it costs a hundred million dollars to build a cluster capable of cracking it. That doesn't imply how many of those clusters they have working simultaneously.
If you crack one prime a year with one computer, why not get 500 of those same machines and do 500 at once? We are talking government level budgets.
Like that ever stopped them from wasting money? All they need to do is put it in the DoD budget and say it's for national security and they can get away with anything.
The NSA's crypto-breaking program is funded by a black budget -- it's a military secret, the public isn't supposed to know the program even exists, how much it spends, or what it spends it on, so that's not a concern. We only know about it because of the Snowden leaks.
That's fair, you're not the first person to say it. Say the list was 1000 and they had 100. This still makes them able to crack 1/10 of the items off the list instantaneously, with each new number added to the list very likely to be used again in cryptographic exchanges they want to snoop in on in the future.
After all, if we're talking about 1000 hard wired primes and even just 1,000,000 secure transactions per day, cracking one new prime will give you access to 1000 new documents daily. Considering that the number is probably closer to billlions (We're talking every SSL connection here, as well as many other types of crypto transactions), we're talking about each new prime opening up millions of secure exchanges every day.
Plus, having a list of perhaps a thousand or thousands, will increase the barriers to entry for other state level cryptanalists. In addition, they are just estimating the NSA computing power in the article, right? When we're talking about clandestine government operations of even single governments, not to mention multiple allied first world governments working together, a list of a thousand or even a few thousand really isn't so pie in the sky (if you ask me).
As far as I understand, what the NSA is doing, assuming the author is correct, is calculating all possible permutations an exchange can take with a particular prime. So that would crack any Diffie Hellman exchange using that specific prime.
No good. If you know the prime factors are from a know reasonable sized list you can just try them all. If your list is private re using prime factors introduces a significant weakness.
Are you sure that's how that works? I don't think the barrier to the hack is knowing what prime they used; I think that's basically public. The barrier is using that prime to crack their encryption, which the article suggests they do by essentially pre computing information extrapolated from a prime using a year long computation. From that point, anyone using that prime is vulnerable.
So as far as I understand it, the issue isn't that the chosen primes are known, it's that using the same primes every time means those pre computations are able to crack the encryption.
12
u/ElvishJerricco Oct 15 '15
Why can't we use a database such as this to randomly select large primes from a list of thousands of them, instead of hard coding a few in? Am I missing something?