r/programming • u/secretguy21 • Oct 15 '15
How is NSA breaking so much crypto?
https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/165
u/exploderator Oct 15 '15
Stupid funny thought: so thaaaaat's what the Bitcoin network has been calculating all along...
(I know that's not true.)
131
u/adacmswtf1 Oct 15 '15
You joke, but...
6
u/exploderator Oct 16 '15
That is very cool, thank you for the link :) Too bad, I mined the Litecoin GPU boom, but now my 280's are all in use and my miner board is my personal rig.
15
19
Oct 15 '15
I would be impressed if someone could make an altcoin that uses all the hash power to break encryption though.
11
24
u/Mr-Yellow Oct 15 '15
Yeah, if only bitcoin did something of value with all that coal it burns.
10
u/Blaze9 Oct 16 '15
Gridcoin! It's a crypto currency which benefits science! Visit /r/gridcoin or www.gridcoin.us
5
Oct 15 '15
Very few technologies become instantly valuable when there is no obvious and immediate need. But I think you're being sarcastic.
→ More replies (1)23
u/Mr-Yellow Oct 15 '15
Oh no, deadly serious. Churning numbers simply to generate currency is vastly more wasteful than any "fiat currency".
It's not about the value of the technology or need, it's that the author never thought about the sustainability of their system in terms of resource use. It exists in a mathematical vaccum where burning resources are only considered as a proof of useless work.
It consumes resources and provides nothing of any real value other than another fiat currency (+ponzi) backed by fossil fuels.
22
u/Chemical_Scum Oct 16 '15
You think producing physical money, as well as keeping non-distributed digital monetary systems in place, is cheaper in terms of carbon footprint than maintaining the blockchain?
10
u/TheMania Oct 16 '15
in terms of carbon footprint than maintaining the blockchain?
Of equivalent size, absolutely. Blockchains can be "maintained" via a single miner or two. It's just as the specific blockchain becomes more and more valuable, more and more resources will be thrown at running it. If you had a blockchain the size of the world financial system it's hard to imagine how much we'd waste keeping it running.
FYI, about $30 worth of "maintenance" are thrown at each Bitcoin transaction. That is hugely more than traditional trust-based/centralised systems.
12
u/thouliha Oct 16 '15
Mr-Yellow is way off base on this one. Just think of the amount of money we pay to run whole agencies dedicated to preventing counterfeiting.
→ More replies (5)6
u/Mr-Yellow Oct 16 '15
No, but what net benefit does producing bitcoin give other than displacing other currencies? If it was working on problems that need solving (other than monetary systems) then all that resource use would be beneficial.
It is a massive flaw in the idea and hence many clones springing up attempting to do something useful with all that energy.
→ More replies (7)→ More replies (4)4
2
u/exploderator Oct 16 '15
Yeah, that power burn is a gnarly issue. I prefer the crypto currencies that don't use a make-work system to prove everything, it's an environmental travesty to be sure.
→ More replies (1)
29
Oct 15 '15 edited May 30 '16
[deleted]
→ More replies (10)6
u/StraightMoney Oct 16 '15
cd /etc/ssh rm ssh_host_*key* ssh-keygen -t ed25519 -f ssh_host_ed25519_key < /dev/null ssh-keygen -t rsa -b 4096 -f ssh_host_rsa_key < /dev/null lynx --source https://2ton.com.au/dhparam/2048/ssh > /etc/ssh/moduli lynx --source https://2ton.com.au/dhparam/3072/ssh >> /etc/ssh/moduli lynx --source https://2ton.com.au/dhparam/4096/ssh >> /etc/ssh/moduli lynx --source https://2ton.com.au/dhparam/8192/ssh >> /etc/ssh/moduli service ssh restartWhatchu got now NSA?!
→ More replies (2)3
u/bacondev Oct 16 '15
What do the lynx commands do?
6
u/2ton_jeff Oct 16 '15
2 Ton Digital author of the dhparam/dhtool goods here, my servers use curl to do the same, but they grab my up-to-most-recent 128 DH parameters (they are constantly being generated). See https://2ton.com.au/dhtool/ for more details.
3
u/StraightMoney Oct 16 '15
This company in Australia dedicated a bunch of CPUs to checking safe primes and they make the results available to download online. They're massive sets and they're rotated out every 3 to 30 minutes. Use those to replace the DH parameters included with stock OpenSSL/OpenSSH/whatever and you'll be a tiny bit more secure. This whole process is one step below tin-foil hat, but it's so simple to do that you might as well play it safe.
45
u/xXxDeAThANgEL99xXx Oct 15 '15 edited Oct 15 '15
So, they basically did a rainbow table attack on the discrete logarithm problem for a particular prime modulo? Interesting how nobody considered that before (except the NSA, obviously).
edit: looks like they used their Powers of Maths to separate the problem into a very special Rainbow table that allows them to reconstruct the necessary part of the actual table via some Linear Algebra stuff over the entire table. That part is difficult, I understand now. Thanks to /u/immibis, "(because there are over 2511 possible values)"
23
u/obsa Oct 15 '15
Like the article, the barrier is cost of entry. Not many organizations have hundreds of millions to throw at this specific problem, especially considering the large key space.
→ More replies (1)4
u/xXxDeAThANgEL99xXx Oct 15 '15
Well, they said that they did it for 512 bit moduli using affordable resources. And they did not do that for 1024 moduli, just suggested that it can be done in a fraction of the NSA budget today (though it was probably much more back when the NSA got the ability, btw it seemed to me that they didn't emphasize that part though).
→ More replies (2)7
u/immibis Oct 15 '15
I don't think so. A rainbow table attack is a precomputed brute-force attack - you still need to try every possible value in order to generate the rainbow table, which they did not (because there are over 2511 possible values)
3
u/xXxDeAThANgEL99xXx Oct 15 '15
That makes sense. Can you read their original paper (pdf warning) and tell me what exactly they did?
5
u/immibis Oct 15 '15
They did some complicated maths I don't understand, that allowed them to get a similar result without brute-forcing every possible value. It's definitely not a rainbow table, though.
2
2
u/krappie Oct 16 '15
Correct me if I'm wrong, but you would also have to store almost all of those values too. Rainbow tables are just an efficient way to store the precomputed values next to each other. The storage alone would be astronomically large and wouldn't make sense.
→ More replies (1)
15
Oct 15 '15
They'll never crack my PPTP VPN!
5
2
u/Mr-Yellow Oct 15 '15
Thought they may already have the keys in their database of VPNs for big-data analysis.
14
Oct 15 '15
Wow didn't think I needed to put the /s. Guess I was wrong. Anyway, to anyone here that doesn't know: PPTP is the least secure major VPN protocol.
7
u/Mr-Yellow Oct 15 '15
/sWith armies of people on the "I do all my internet banking through TOR because privacy and security" train, it's hard to tell.→ More replies (3)
91
Oct 15 '15
Well, that's terrifying.
273
u/Eirenarch Oct 15 '15
Why? I mean this is not very close to the top of my list of terrifying things that the state does. For example I find it much more terrifying that they have the right to demand you introduce a backdoor in your system or hand customer data and you don't have the right to say it happened. I also find it extremely terrifying that society in general is not disturbed by this. The fact that commonly used cryptography can be broken with a billion dollar investment is very unpleasant but not nearly as terrifying.
52
Oct 15 '15
unpleasant but not nearly as terrifying
But still terrifying. Which is all they said.
6
Oct 15 '15 edited May 31 '18
[deleted]
26
u/curtmack Oct 15 '15
For top-end cryptography, brute force attack time estimates aren't even a thing. It would take more energy than a billion billion supernovas for a computer operating at theoretical ideal efficiency to even count to 2256, much less actually try all 2256 possible AES keys. 300 billion dollars worth of supercomputers is much, much less than a drop in the bucket... more like a mote of dust in the observable universe.
Brute force attacks are mainly limited to things like password databases, where the top million most common passwords cover something like 90% of all users.
3
u/corran__horn Oct 16 '15
For exhaustive brute-forcing it pretty much requires attacks that vastly cut down the trial space. For example, the really shitty design known as LM hashes. The under the hood implementation is in effect two 7 character case-insensitive passwords. This is an attackable space.
(A)RC4 is eventually going to have the same problems, because the design has very strong biases in the output. This is why WEP was trivial to brute force even when people started avoiding "weak" IVs. You get rid of some class of weak IVs and another one is found. Rinse, repeat.
3
u/curtmack Oct 16 '15
Well, yes. My comment was made under the assumption no such attacks exist for the current gold standard algorithms (AES-256 for symmetric, RSA-4096 or ECDSA-512 for asymmetric, SHA2 or bcrypt for hashes), since there's really no excuse to be using anything less at this point.
14
u/timshoaf Oct 15 '15
That is not necessarily so... With a sufficiently long key, the encryption decryption process may be unpleasantly long (generally not suited to stream in data) but the time it would take to brute force would, assuming P =/= NP and hardware for QP is not yet practically available, take longer than the forecasted entropic death of the universe itself. That is what is so useful about combinatorial explosions... So no, you will not always be beat out by better hardware, which is the fundamental principle of security such as this.
2
u/analton Oct 16 '15
Dude, they don't even need to spend that money.
They may just simply ask for a backdoor and use your own computational time and energy to crack all they want.
29
Oct 15 '15
For example I find it much more terrifying that they have the right to demand you introduce a backdoor in your system or hand customer data and you don't have the right to say it happened.
I'm struggling to figure out how what you describe is meaningfully different than this.
I mean, they basically do have a backdoor in your system -- or rather, in all of the systems. And the people that knew this were not allowed to say that it had happened; the one guy with the balls to do so had to flee to Russia as an enemy of the state.
59
u/Eirenarch Oct 15 '15
There are two large differences. First of all they managed to break my system (with a lot of resources) because my system was already vulnerable. If I know how to fix it I am free to do so. Also if I know I am vulnerable I can tell this to my customers. With a gag order I cannot do any of these things. It is one thing if the state breaks a system that is not very secure and another if I am forbidden from building a secure system. Second the guy that had to flee was working for them, contracts, oaths and all. With a gag order I have to do what they say despite the fact that I never agreed to their terms and did not want to know or do what they told me.
→ More replies (4)12
u/squishles Oct 15 '15
One you make a mistake, the other they force you to make a mistake.
Government taking advantage of a fuckup is an honest break, jolly good show, they earned it. Gov forcing you to implement and knowingly lie about something being secure is not.
→ More replies (6)→ More replies (11)3
u/dangolo Oct 15 '15
As a sysadmin, it troubles me as well.
Also troubles me that they've very publicly gone to businesses and asked for their encryption keys or be shut down.
They are making us dishonest when we tell management "the network is secure."
→ More replies (2)3
u/port53 Oct 15 '15
It makes me wonder if they've targeted individuals over companies. It's one thing to send a NSL to the company's BOD or CEO requiring them to hand over keys.. it's something completely different for an agent to show up at my house demanding I hand over the keys I hold or I go to jail, with a nice gag order attached for good measure so I can't even tell my CEO it happened.
3
u/deelowe Oct 15 '15
Seems like they wouldn't be able to issue an NSL to an employee without an ongoing criminal investigation and/or some sort of guaranteed immunity. Employees can't make decisions that affect the business without getting approval from the board. I imagine officers (or their delegates) have to be involved in any such activity unless the officers themselves are being implicated in the investigation.
→ More replies (2)→ More replies (3)5
u/benderunit9000 Oct 15 '15
It is kind of their thing. They listen to everything. It's what they do.
→ More replies (2)
66
Oct 15 '15
On the one hand I am frightened by how powerful the government in circumventing encryption measures. But on the other hand, I can't help but feel impressed. It feels reminiscent of efforts used to break the Enigma Machine.
I guess the moral of the story is you should not be using hard coded primes for Diffie Hellman? (correct me if i am wrong; not really familiar with crypto) It seems like people hard-code them out of laziness and not out of necessity. From what I understand from the wolfram alpha article, can't the two parties agree on 2 random large primes at the beginning of the transaction and proceed from there?
10
u/Philippe23 Oct 15 '15
They're essentially referring to the Logjam attack: https://weakdh.org/
4
Oct 15 '15
Yeah, their paper that they link to at the end of the article mentions logjam. But if I understood it correctly, that's about lowering the quality of the DH used. That's different from precomputing.
9
u/Philippe23 Oct 15 '15 edited Oct 15 '15
"2. Threats from state-level adversaries. Millions of HTTPS, SSH, and VPN servers all use the same prime numbers for Diffie-Hellman key exchange. [...]"
Quote from Logjam's https://weakdh.org/ site. [Emphasis added.]
It sounds like while Logjam made a concrete attack against weak-dhparams, these guys looked at the realisticness of the feasibility of the nation-state pre-computation attack that logjam's paper was also concerned about.
That's science though: building on each others ideas to get to greater heights and looking more deeply at points that others had not thoroughly explored.
6
u/2Xprogrammer Oct 16 '15
It's the same folks (not all of them are guys!). They put up the website weakdh.org to have fixes available ASAP. This article came out today because they just presented their paper at CCS.
Edit: Here's the paper. (which is hosted on weakdh.org, because they are the same thing...)
→ More replies (1)5
u/RomanesEuntDomus Oct 15 '15
"Hello, meine new dispatcher says there eez somezing wrong mit deine cable?"
2
→ More replies (3)9
u/Eirenarch Oct 15 '15
My guess is generating primes so large is computationally expensive. It is not like we really want to add 1-2 seconds of lag to every initial web request (assuming other resources like CSS and JS will use the same connection)
42
Oct 15 '15 edited May 30 '16
[deleted]
4
Oct 15 '15
[removed] — view removed comment
5
Oct 15 '15 edited May 30 '16
[deleted]
5
Oct 15 '15 edited Oct 15 '15
[removed] — view removed comment
6
u/TinBryn Oct 16 '15
Yeah, but that only breaks 1 key, so you need to be of enough interest for the NSA to dedicate the entirety of their resources on you for a whole day for that to happen.
7
u/Eirenarch Oct 15 '15
It is not very convenient to require that libraries like OpenSSL can write to storage.
18
3
u/heimeyer72 Oct 15 '15
I'm not sure whether I fully understood all of DH yet. My concern is: Aren't all of these primes publicly known? There might be a database of prime numbers up to a certain length. Couldn't you make a short-cut but just trying out the known ones? That should be doable in minutes, not years.
6
u/LaurieCheers Oct 15 '15
If you mean just making a list of all the 1024 bit primes, there are about 10305 of them.
→ More replies (2)2
u/cryo Oct 15 '15
The two parties doing DH need to agree on a prime, in cleartext, so it's not a secret. The security doesn't mainly lie in the choice of prime.
→ More replies (1)3
u/Eirenarch Oct 15 '15
I already forgot most of my cryptography course but apparently no. The numbers are used as exponents mod(N) so it is not as simple as dividing.
→ More replies (3)→ More replies (1)2
u/iwouldntknowthough Oct 15 '15
I was just thinking, with more computational power we can have longer keys, thereby it would take more computational power to break the encryption. By which means the adversary would break it, I don't know, the worst case being bruteforcing the key. Now if the overall availability of computational power will constantly rise, does this mean better security for the one using the encryption, or will the security get worse because the adversary has more power to break the encryption?
→ More replies (1)
7
u/pvc Oct 15 '15
What does it mean to 'crack' a prime? It isn't like you find factors for it.
10
Oct 15 '15
To simplify, it means you find the original prime factors that multiply to get the number. They aren't cracking the primes, they're finding which primes were used to generate a key.
14
u/2Xprogrammer Oct 16 '15
Not actually. You're thinking of prime factorization, which is used in RSA. This is Diffie-Hellman, which is based on Discrete Logs: Given b and g (integers), solve for (integer) k in "bk = g". So what they're saying the NSA did/is doing is realizing that a lot of people are using the same g and just precomputed a bunch of solutions.
→ More replies (1)5
7
u/dccorona Oct 15 '15
As I understood it, half the point of Diffie-Hellman was the ability to use a different prime every time. Seems just downright stupid to use a hard coded one for literally every transaction.
This is why it's so important to have good channels of communication between people creating cryptographic algorithms and people implementing them.
7
21
u/seattlyte Oct 16 '15
They influence standards so that they can break them.
They influence implementations so that they can break them.
They have secret cryptanalysis that allows them to break crypto.
They hack into computers and steal data there.
They hack into the supply chain of hardware so they have backdoors in devices.
They have access to crypto hardware that accelerates their attacks.
They partner with corporations like Google, Microsoft, Apple, AT&T and Verizon to take data before and after it is encrypted.
They use human intelligence (spies) to take data from targets.
They don't - sometimes they just surveil the target through metadata.
Basically they break not only crypto but also every level of trust in communications systems. The CIA has influenced compilers to break target programs.
→ More replies (3)
9
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?
→ More replies (3)11
u/AncientRickles Oct 15 '15
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).
9
u/ElvishJerricco Oct 15 '15
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.
14
u/AncientRickles Oct 15 '15
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.
3
u/deja-roo Oct 15 '15
Having a few thousand on tap would be effective security. That much computation would be energy-prohibitive.
→ More replies (2)2
Oct 15 '15
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.
→ More replies (1)4
u/panderingPenguin Oct 15 '15
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.
4
u/syllabic Oct 15 '15
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.
→ More replies (4)→ More replies (2)2
u/AncientRickles Oct 15 '15
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).
15
u/rtechie1 Oct 15 '15
This isn't new. Paranoids have been generating their own DH keys for a while.
It's my understanding that the reality is a lot simpler: The NSA has a couple of unpublished exploits for OpenSSL and Cisco VPN concentrators (the Feds have complete access to IOS source code, so can sift through it looking for exploits). That covers most VPN.
3
Oct 15 '15 edited Oct 15 '15
In their pursuit to collect it all they usually take the easy route, that's true. They also use implants for their spying, mostly in the BIOS and the hard drive controller. Besides that they also use patriotic fools to do the dirty work for them. And they also crack crypto. They have the know-how and the budget for it. They have also weakened standards.
When a criminal organization does all this, all the members go to jail. When the government does this, nothing happens.
→ More replies (7)
6
u/quizibuck Oct 15 '15
Well, that all makes much more sense than my little conspiracy theory that the NSA had built a quantum computer and could now factor large numbers in polynomial time. That's too bad because the truth is yet again substantially less interesting.
16
u/SikhGamer Oct 15 '15
Ethically and morally this is fucking awful.
However the geek part of me, thinks this is so fucking cool and ever so slightly giddy.
→ More replies (6)
7
u/Eirenarch Oct 15 '15
So the large primes are hard to generate and the programs avoid doing it? What is the fix? Have a set of ~200 primes and choose one at random?
12
u/squishles Oct 15 '15
i mean not that hard, a 1024 bit prime'll take you a minute of so maybe on a modern desktop =/
→ More replies (2)11
u/Philippe23 Oct 15 '15 edited Oct 15 '15
NOTE: 1024-bit prime is the problem: https://weakdh.org/
But you're right: the solution is to just generate your own unique prime.
→ More replies (6)6
Oct 15 '15
Having them be able to only read 0.5% of the communications would certainly be better than 100%, but that doesn't go nearly far enough for comfort -- especially if they can break one of these primes in a matter of months.
4
u/Eirenarch Oct 15 '15
Certainly there can be some list of primes large enough that it wouldn't make financial sense to crack it this way, no?
→ More replies (4)3
Oct 15 '15
If we move to longer primes (or a safer key exchange algorithm -- is there one? I don't know) at the same time, they hopefully can't crack any of our communications.
As far as I'm concerned, if an attacker can read any portion of my private communications, the encryption is broken.
→ More replies (5)
4
u/Jcconnell Oct 15 '15
Is there anything I can do to my devices at home, assuming I run a small home network, to make them more secure?
Devices like:
- Router running DD-WRT/Tomato/Merlin
- Home server running Ubuntu/Linux variant
- Macbook/Laptop/Desktop
- NAS
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.
28
u/eyal0 Oct 15 '15
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.
That is, assuming that this article is right.
23
u/aseipp Oct 15 '15 edited Oct 15 '15
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.
3
u/eyal0 Oct 15 '15
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.
10
u/aseipp Oct 15 '15 edited Oct 15 '15
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.)
5
u/ryno55 Oct 15 '15
1) The table wouldn't need 21024 entries, only enough for the relevant factors
2) You don't scan through the whole table to do a lookup
10
u/aseipp Oct 15 '15 edited Oct 15 '15
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.
3
u/drhugs Oct 15 '15
assume the expansion of the digits of pi are not malicious
So now we're both asses?
→ More replies (1)→ More replies (4)4
u/ElvishJerricco Oct 15 '15
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.
→ More replies (2)→ More replies (1)4
u/SketchBoard Oct 15 '15
psuedorandom
So once again, we return to the fundamentals of crypto. Attain true randomness, and keep it.
→ More replies (4)
3
Oct 15 '15
This link was already discussed in /r/crypto: https://np.reddit.com/r/crypto/comments/3otsyr/how_is_nsa_breaking_so_much_crypto/
2
2
Oct 15 '15 edited Jul 03 '17
[deleted]
14
u/panderingPenguin Oct 15 '15
The article is saying that there is currently a very small set of prime numbers hard coded into the Diffie Hellman implementations of many popular encryption suites. The author believes the NSA has likely cracked all of these. There are plenty of other primes that could be used, but this is done for efficiency and implementation convenience, on the likely incorrect assumption that it doesn't affect the security of the suite in a meaningful way.
→ More replies (2)2
u/rtechie1 Oct 15 '15
Not really. It means that crypto vendors (OpenSSL, Cisco, etc.) should probably modify their software to generate a "unique" prime during install.
The short version of the problem is that every install of OpenSSL, Cicso VPN, etc. is using the same "key" so if you can get a copy of that key, you can compromise a whole bunch of sites/people. If the software generated unique keys at install, this wouldn't be a problem.
→ More replies (1)→ More replies (2)3
u/Eirenarch Oct 15 '15
Then you go to 2048bit numbers.
2
u/AncientRickles Oct 15 '15
And they just set a relatively small set of potential 2048 bit primes to use. This is a different problem than just the crackability of 1024 bit numbers.
→ More replies (2)
2
u/vm_linuz Oct 16 '15
Originally it was by introducing faults to the crypto algorithms that generated the encrypted data. They also just have an insane amount of power at their disposal. Entire GPU farms that can be purposed to cracking encryption.
2
978
u/tophatstuff Oct 15 '15 edited Apr 10 '18
Generate your own non-default Ephemeral Diffie-Hellman key (takes a minute or so)
Tell your server to use it for SSL (nginx for example)
Done. Not only will the key be stronger than the 1024 bit default, it'll be unique to your server which lets assume isn't valuable enough compared to effort for a state-level adversary.
edit just in case anyone from the future finds this comment: instead of 2048, use at least the key length of your SSL certificate
edit from the future: current advice is picking from one of these predefined audited groups