There have been rumors for years that the NSA can decrypt a significant fraction of encrypted Internet traffic. In 2012, James Bamford published an article quoting anonymous former NSA officials stating that the agency had achieved a “computing breakthrough” that gave them “the ability to crack current public encryption.” The Snowden documents also hint at some extraordinary capabilities: they show that NSA has built extensive infrastructure to intercept and decrypt VPN traffic and suggest that the agency can decrypt at least some HTTPS and SSH connections on demand.
However, the documents do not explain how these breakthroughs work, and speculation about possible backdoors or broken algorithms has been rampant in the technical community. Yesterday at ACM CCS, one of the leading security research venues, we and twelve coauthors presented a paper that we think solves this technical mystery.
The key is, somewhat ironically, Diffie-Hellman key exchange, an algorithm that we and many others have advocated as a defense against mass surveillance. Diffie-Hellman is a cornerstone of modern cryptography used for VPNs, HTTPS websites, email, and many other protocols. Our paper shows that, through a confluence of number theory and bad implementation choices, many real-world users of Diffie-Hellman are likely vulnerable to state-level attackers.
For the nerds in the audience, here’s what’s wrong: If a client and server are speaking Diffie-Hellman, they first need to agree on a large prime number with a particular form. There seemed to be no reason why everyone couldn’t just use the same prime, and, in fact, many applications tend to use standardized or hard-coded primes. But there was a very important detail that got lost in translation between the mathematicians and the practitioners: an adversary can perform a single enormous computation to “crack” a particular prime, then easily break any individual connection that uses that prime.
How enormous a computation, you ask? Possibly a technical feat on a scale (relative to the state of computing at the time) not seen since the Enigma cryptanalysis during World War II. Even estimating the difficulty is tricky, due to the complexity of the algorithm involved, but our paper gives some conservative estimates. For the most common strength of Diffie-Hellman (1024 bits), it would cost a few hundred million dollars to build a machine, based on special purpose hardware, that would be able to crack one Diffie-Hellman prime every year.
Would this be worth it for an intelligence agency? Since a handful of primes are so widely reused, the payoff, in terms of connections they could decrypt, would be enormous. Breaking a single, common 1024-bit prime would allow NSA to passively decrypt connections to two-thirds of VPNs and a quarter of all SSH servers globally. Breaking a second 1024-bit prime would allow passive eavesdropping on connections to nearly 20% of the top million HTTPS websites. In other words, a one-time investment in massive computation would make it possible to eavesdrop on trillions of encrypted connections.
NSA could afford such an investment. The 2013 “black budget” request, leaked as part of the Snowden cache, states that NSA has prioritized “investing in groundbreaking cryptanalytic capabilities to defeat adversarial cryptography and exploit internet traffic.” It shows that the agency’s budget is on the order of $10 billion a year, with over $1 billion dedicated to computer network exploitation, and several subprograms in the hundreds of millions a year.
Based on the evidence we have, we can’t prove for certain that NSA is doing this. However, our proposed Diffie-Hellman break fits the known technical details about their large-scale decryption capabilities better than any competing explanation. For instance, the Snowden documents show that NSA’s VPN decryption infrastructure involves intercepting encrypted connections and passing certain data to supercomputers, which return the key. The design of the system goes to great lengths to collect particular data that would be necessary for an attack on Diffie-Hellman but not for alternative explanations, like a break in AES or other symmetric crypto. While the documents make it clear that NSA uses other attack techniques, like software and hardware “implants,” to break crypto on specific targets, these don’t explain the ability to passively eavesdrop on VPN traffic at a large scale.
Since weak use of Diffie-Hellman is widespread in standards and implementations, it will be many years before the problems go away, even given existing security recommendations and our new findings. In the meantime, other large governments potentially can implement similar attacks, if they haven’t already.
Our findings illuminate the tension between NSA’s two missions, gathering intelligence and defending U.S. computer security. If our hypothesis is correct, the agency has been vigorously exploiting weak Diffie-Hellman, while taking only small steps to help fix the problem. On the defensive side, NSA has recommended that implementors should transition to elliptic curve cryptography, which isn’t known to suffer from this loophole, but such recommendations tend to go unheeded absent explicit justifications or demonstrations. This problem is compounded because the security community is hesitant to take NSA recommendations at face value, following apparent efforts to backdoor cryptographic standards.
This state of affairs puts everyone’s security at risk. Vulnerability on this scale is indiscriminate—it impacts everybody’s security, including American citizens and companies—but we hope that a clearer technical understanding of the cryptanalytic machinery behind government surveillance will be an important step towards better security for everyone.
For more details, see our research paper: Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice. (Update: We just received the Best Paper Award at CCS 2015!)
J. Alex Halderman is an associate professor of Computer Science and Engineering at the University of Michigan and director of Michigan’s Center for Computer Security and Society.
Nadia Heninger is an assistant professor of Computer and Information Science at the University of Pennsylvania.
Hi,
If NSA can crack VPN encryption, how come the Dark Markets can still run so easily. They all using VPNs and Tor, or Tails etc?
Second, you may notice that you aren’t being targeted with certain types of
advertising. You just cannot resist preferring SSH VPNover
the others since it opens the door for a plethora of benefits that prove to
be fruitful for you in the long run. SSTP
is a Microsoft VPN with very good encryption but is only available for
Windows 7 an Vista, and is therefore harder to find.
Limit privileges of connections utilising keys lower than 2048-bit. As security demands increase, 2048-bit can also be relegated to legacy connections that are able to run on outdated or antiquated hardware
The only problem is the NSA can ask for your lock, even if stored elsewhere else, steal your lock without notifying anyone, and also abuse access to your lock by using it to gain access to your property or that of any unknown persons living with you.
Limit privileges of connections utilising keys lower than 2048-bit. As security demands increase, 2048-bit can also be relegated to legacy connections that are able to run on outdated or antiquated hardware
Just a few thoughts
– most US people “educated” in recent years cannot write or read in cursive style… This has implications for personal record keeping. Get a book on copperplate…and an ink pen.
– morse in sidelobes as a steganographic strategy.
-noise as psudocrypto
Intent to Deprecate: SHA-1 certificates
https://groups.google.com/a/chromium.org/forum/#!topic/security-dev/2-R4XziFc7A%5B1-25%5D
The key to protecting your data in an age when encryption is useless is to physically split your datagrams into pieces and anonymize them.
The problem here is not so much one of encryption level, or type, or of mathematics, but of TRUST. Public trust in government, TRUSTWORTHINESS of NSA goals and agendae, and exactly WHAT the Director of Central Intelligence (the person that the Director of the NSA is Supposed to report to, below POTUS) and the Secretary of the Department of Homeland Security actually DO with all that information and Intelligence they obtain from cracking all the surveillance and Internet communications they monitor.
I, personally, haven’t transmitted or received anything (other than my banking and bill-paying) that I object to N0 Such Agency having access to over the internet. But then again, I’m 63 years old and happily married. YOUR mileage may vary. The point is that NSA is Supposed to PROTECT and DEFEND the USA, and it’s CITIZENS, from electronic and cybernetic attacks, as part of it’s mission; the rest of it being providing secure communications FOR the U.S. Government in the form of codes and ciphers, and executing electronic espionage services TO the U.S. Government Intelligence community. But There’s where the rub comes in – electronic espionage services against WHOM? Foreign, or domestic subjects? Domestic is supposed to be only with a Federal Court Order, not willy-nilly, blanket eavesdropping. Which is what they can, and do, perform, with the kind of decryption services we’ve been discussing here.
This is why you should use One-Time-Pad if you really want absolute secrecy. OTP, the only encryption technique, that can not be broken, because there is no algorithm there to break.
Sure, with OTP there is the problem of having the need to meet at least once but given that you can change 1 TB key that time and then keep telling the other side in secret where to find more, it really doesn’t matter. 1 TB key you can talk in the phone with the other person for the rest of your life and no one else can ever know what it is about; no matter how powerful computers they have.
People championing modern encryption over OTP are either working for the man or their pets, fools.
You think Amazon is really going to meet with every single customer to exchange a 1TB OTP key? You think every single internet user is going to meet with every single web site owner to exchange a 1TB OTP key? You do realize that none of these trillions of 1TB OTP keys can be shared or re-used?
You do realize how much simpler it is to have one private key which is kept secret from everyone, compared with the nightmarish scenario of thousands of keys for thousands of websites where each key must be shared with exactly one web site but kept secret from all others?
Good luck.
As suggested in the last sentence in the introduction to the paper, the best solution is not to switch to a larger modulus for finite field Diffie Hellman, it is to instead use elliptic curve Diffie Hellman. The group of points on an elliptic curve over a 256-bit finite field provides roughly the same level of security as a 3072-bit RSA key or 3072-bit finite field modulus (assuming the group has prime or near-prime order, which is what one will do in practice). More importantly, the only known algorithms for breaking Diffie Hellman on an elliptic curve actually do have exponential running times versus the subexponential time algorithms that are known for factoring integers and for computing discrete logarithms in the multiplicative group of a finite field. In practical terms: doubling the key size for an elliptic curve from 256 to 512 bits has roughly the same effect as increasing an RSA or Diffie-Hellman finite field modulus from 3072 bits to 15360 bits.
In fact, Google switched to using ECEDH (elliptic curve ephemeral Diffie Hellman) as their default for SSL session key exchange several years ago for precisely this reason (Facebook, Amazon, and several others followed suit shortly thereafter).
Yes to all these points, and in addition elliptic curve DH has lower computational costs and smaller key sizes than RSA/DH, with the cost and size advantage of elliptic curves increasing as key sizes increase. The performance advantage was one of the main motivations for Google to switch to ECEDH. It is important to mention that Google controls a large portion of both the servers (Google services) and the browsers (Google Chrome) on the internet, and for this reason Google is one of the very few companies that is in a position to drive change in deployed crypto unilaterally.
The use of hard-coded primes has been known for over a decade. It was a bad idea then and now it that has propagated for all this time.
Is this a joke? You mention backdoors like they were rumors. Who needs to crack anything when all commercial VPN and firewall software is Federally mandated to have built-in backdoors? The “black hat” industry is simply an outgrowth of the revolving door between the backdoor writers/enforcers and the “Internet Security” industry.
You seem to have forgotten that the rest of the world exists. There are plenty of VPN providers outside of the USA, and there are also plenty of encryption products written by non-Americans.
Um it’s pretty obvious guys, they go in the back door and grab the keys and copy them. If you ever wondered why you can’t view the global hook chain it’s because they don’t want you to see that they can get in and out. You need to encyrpt something – sure – you need the key either typed or in a file, good luck stopping them seeing and copying that.
or they make the company sign a silencing agreement and force them to supply them the keys to copy. Here’s a deal you can’t disagree with – it’s the law, here’s some money for your time, and never speak about it or we will execute you for treason.
I thought generating large prime (or pseudoprime) numbers was relatively easy, computationally-speaking. Why are so many implementations choosing from a fixed set of them?
Because you can’t use an arbitrary prime, it has to have certain properties in order for the key exchange to be secure.
More specifically, it should be a “strong” prime (see Wikipedia).
It’s relatively easy to generate large primes when you only do it occasionally to produce a new RSA key pair. It’s a lot harder when you have to do it on every new SSL connection.
My vpn uses blowfish CBC encryption cipher and SHA1 hash algorithm, how would i tell if this affects me?
SHA1 is thought to be likely to have purposeful collisions within the year.
These are the symmetric ciphers used to encrypt and authenticate the data stream. How does your VPN determine the ephemeral keys used for these ciphers? If it uses a pre-shared key (same long and hard password used on both sides), then you might be safe, depending on how it generates the ephemeral keys from the PSK. Otherwise, you are likely using DH for the key agreement, and possibly even with one of the few primes the NSA has already made insecure.
It would seem that identifying information as encrypted makes you a target, no?
What about steganography? Combining encryption with obfuscation might do the trick for those who wish to avoid NSA scrutiny. My bet is that they don’t spend a lot of effort looking at cute kitten photos. Another obfuscation might be to send your encrypted message in a “spam” payload. Is the NSA really opening all the DHL shipping notices for $1 million money orders, sent as .EXE files?
It seems to me that what the NSA is left with is “routine” encrypted traffic, and that through obfuscation, it should still be possible for moderately sophisticated terrorist groups, etc. to communicate without scrutiny.
The problem identified here is limited to a few of the currently known DH primes. Keys created without DH or with different, maybe even stronger, primes, are not affected by this problem.
So using e.g. RSA (as in PGP or S/MIME) or changing the prime or switching to Elliptic Curves avoids this. No need to switch to Steganography, which makes it hard to talk privately with more than a handful of peers. I guess the latter should be the goal.
Steganography is cute, but has limited applicability because of the enormous overhead it usually entails. And it’s harder to do than you think.
I think it’s much better to strongly encrypt as much of our traffic as we possibly can, including all the unimportant stuff. The bigger the haystack, the harder it is to find the needles. And we already know the NSA simply can’t resist collecting bigger haystacks.
Let me suggest an alternative explanation of human parallel processing. For decades, the NSA has been the largest employer of theoretical mathematicians and promptly has them sign security clearance agreements. They have essentially built a very large mathematics college which is mostly knowledge permeable in a single direction in that it’s mathematicians make use of the discoveries of the world at large but do not quickly share their own.
Given this state of affairs, let’s consider mathematics as a field. Basically there’s known and unknown math given the constraints of today’s information society. However, the knowledge and work of the NSA’s mathematicians represent a body of known math, but only to the NSA. Meanwhile NSA mathematicians are enjoying free rider access to the work of mathematicians around the world.
In this scenario, it is likely that the NSA’s understanding of mathematics as a whole is greater than that of the world at large and that given their focused interest, they may well be able to employ developed knowledge to tackle problems that are unsolvable or at the very least require far more onerous approximations or solutions. The NSA’s encryption and decryption prowess is likely based upon the unique mathematics knowledge advantage it possesses.
It is assumed that the NSA is farther ahead in crypto math than the public, but we don’t have a lot of data points to figure out how far they’re ahead.
I’m a casual follower of crypto, so I personally could have missed a lot of data points here. I’m only aware of one data point to estimate how far ahead the NSA is. It took public mathematicians about 10 years to understand the NSA’s suggestion that changed SHA into SHA1. So we can guess that the NSA is 10 years ahead of the public mathematicians.
This attack gives us another data point. How long has this program been going on? The linked document says this slide is from 2009. So it’s been running at least 6 years. So they’re still 5 to 10 years ahead of the public.
Shouldn’t a state, that has become aware of such a big hole, warn its citizens about it so they can plug the hole rather than leave it open for enemy states to snoop in exactly the same way?
Yes, they get to hear all the juicy gossip about Janice in accounting’s affair with Doug in personnel, but what about all the company secrets that are being taken by nations that could do anything from hurting us financially to losing our technological edge.
The NSA has two missions: to read other people’s mail, and to protect us from the same.
I have been told on several occasions over the years by highly placed NSA people that the first
mission trumps the second.
ches
It isn’t just the choice of prime that is the problem here, it is the construction used to derive keys in TLS.
At the time those 1024 and 512 bit primes were chosen, it was widely believed that DH keys only needed to be half the size of an equivalent RSA key. People wanted short keys because they wanted key setup to fit in a packet.
The way TLS works when doing ephemeral keying is that the RSA keys are used to generate a pre-master secret, call it P and then P is used to authenticate the DH parameters which are used to derive the master secret, call it M. In the current design, M is a feature of the DH parameters alone (M=DH). So the systems do a strong key negotiation, use it to authenticate a weak one and then use the weak one.
This can be fixed using the construction M= SHA2 (DH + P) so the ephemeral is used as a mix in to salt the pre-master secret rather than throwing away that work completely.
When the Internet starts moving to the new CFRG curves for ECC, I expect most people will end up using the 448 bit curve because it offers a huge speed improvement over RSA2048 (for servers) and a comfortable security margin over any public key algorithm that is widely used today (NIST defines a 521 bit curve but I am not aware of anyone issuing certs for it). Using a 448 bit curve in certificates makes perfect sense. But for perfect forward secrecy, it is overkill. I would much rather use the 255 bit curve and rekey more frequently.
Incidentally, BULLRUN tells us that the NSA spends $250 million a year sabotaging efforts to develop security standards. Is this one of the things they bought with that money? I did suggest the salted construction back in the day and was told that it was ‘unnecessary’ and I was ‘troublemaking’. Would it be overly paranoid of me to suggest that maybe this was the work of an NSA mole? After all wouldn’t the way someone like that would ingratiate themselves be to be always willing to volunteer to do lots of scut work?
The most pragmatic solution is adding new pairs (g, p) to your TLS implementation. Precomputing tables for ALL 1024 bit primes is still beyond the NSA’s capabilities. This solution does, for most TLS implementations, not require recompiling any code. And it works even when your TLS impl or that of your peer only handles 1024 bit security. Don’t use primes from the net though, better dust of your algebra books.
agreed
Honestly, if you’re going to do this, you might as well just update to 2048-bit primes. Changing an implementation to support multiple 1024-bit primes is usually harder than changing it to support a single 2048-bit prime, especially if your original implementation assumes a hard-coded prime.
“Precomputing tables for ALL 1024 bit primes is still beyond the NSA’s capabilities.”
And it will be for a very, very long time.
Letting the number of primes less than N be Np = N/ln(N) [approximately]. If N=2^b then Np = (2^b)/b*ln(2), so for N=2^1024 Np = (2^1014)/ln(2). If we eliminate the primes less than 2^1013 [i.e. 1024 bit numbers where the msb is zero] the number of primes is 2^1023/ln(2).
In decimal notation 2^1023/ln(2) = 1.29676 * 10^308.
After computing these primes you still have to store them. Each 1024 bit prime needs 128 Bytes of storage — this works out to 1.66 * 10^310 Bytes.
I recently bought a 1 TB drive for about $50 — you would need 1.66 * 10^298 such drives at a cost of $83 * 10^298 — less any quantity discounts :). Way more than enough to make our national debt look like chump change.
And if you got those drives where would you store them?
So I will admit I am not a cryptography expert and only have an interest in it, but I still have a question I really want to know the answer to.
My question is this: why. Why. WHY ON GOD’S GREEN EARTH would you use *hard freaking coded* prime numbers for a *cryptography* application? What the *christ* were they thinking???
because the software isn’t written by true cryptographers, either, unfortunately
Because finding these massive prime numbers are difficult and time-consuming.
Hard-coded primes are fine as long as the prime is large enough. What happened here is that the prime was large enough by 1990 standards, but is not large enough now.
I agree that if you’re going to use hard-coded primes then you need to plan for future advances in cryptanalysis. At the time these standards were created, people had a 25-year time horizon. Guess what? 1990 + 25 = 2015. The good news is that we won’t have this problem ever again with respect to RSA or DH keys, because the next 25-year time horizon will put us into the quantum computing era, invalidating all of RSA and DH. The bad news is that we’re just as slow as ever when it comes to updating crypto software deployments.
What does this post add to the coverage in May?
http://it.slashdot.org/story/15/05/20/1258251/logjam-vulnerability-threatens-encrypted-connections
The PDF seems to be unchanged.
It gets greater exposure.
One article is lost in the churn of the internet. Two articles (or a repost of the same article) may get notice. Ten thousand copies of the same article ensures people will see it.
Given the dollar amount suggested to build such a computational engine, this attack is not limited to nation state agencies. Very large companies such as Apple, Google, Amazon, Facebook, etc have plenty of money and also spare compute resources to likely carry out the same type of cryptanalysis if so inclined.
indeed, that compute capacity may be available at a negotiated price as part of a nation state’s budget
Thanks for the post. Since this is a passive attack, I assume the servers do not support +1k DHE keys. Can you publish a list of the top million www-sites that use 1024-bit DHE. It would make it easier to vote with one’s feet and it would also put some pressure for the companies to upgrade.
Can’t we use multiple primes? So, exchange multiple keys using different primes over DiffieHellman and then combine them into the actual key? Thus you need to break all primes that are used to decrypt the key exchange. Thats still doable given enough time though 🙁
This would most likely cause too much overhead in the normal use of DH.
You’re better off just using a single much larger prime.
of course, the wikipedia article also tells us this: “RSA claims that 1024-bit keys are likely to become crackable some time between 2006 and 2010” … https://en.wikipedia.org/wiki/Key_size#Asymmetric_algorithm_key_lengths . Yeah they’re different algorithms (and different classes of one too), but I think its kinda clear that 1024bit primes are not providing enough entropy.
No, it’s not clear at all. RSA security does not apply to DH, and vice versa.
For the less-informed of us in the audience, what does it mean to “crack” or “break” a prime? As the article a bove describes the situation, it seems that these primes aren’t secret. That is, they are in use in publicly available software and often the same prime is used by multiple people. And of course, primes aren’t factorable. So what else is there?
And what’s the solution? Does each user of the software have to pick their own 1024 bit prime?
Actually, there are two primes g and p, and the secret shared between the two end-points is is g^(a*b) modulo p, a and b being random numbers choosen each by one end-point, and they are never transmitted. The Diffie-Hellman protocol and mathematics allow the end-points to find this shared secret by exchanging g^a modulop and g^b modulo p. It is assumed that computing g^(a*b) modulo p is very hard when you only know g, p, g^a modulo p and g^b modulo p.
What this paper says, if I’ve understood correctly, is that it possible to pre-compute a function from g and p (even if it takes a lot of time and money), that will let you find g^(a*b) modulo p easily from g^a modulo p and g^b modulo p.
http://mathworld.wolfram.com/Diffie-HellmanProtocol.html
The solution is to increase the size from 1024 bits to 2048. It is believed to be currently infeasible to crack such a long prime, even with a 10 billion dollar budget.
It would be best if each user picked their secret key and switched it often. When you give crackers enough payload generated from a given key you give them a sharper analysis.The Diffie-Hellman.encryption method uses modulus 13 residuals BTW.
pete.d, I had the same question. (and I didn’t know enough math to grasp informatimago’s answer!) But I found this article really helpful, especially the “Two Keys are Better than One” section.
http://blogs.discovermagazine.com/crux/2013/07/31/how-to-create-codes-that-even-the-nsa-cant-break/#.Vh9JHPlVhBc
I might be totally wrong on this, but I think that what is being “cracked/broken” is not actually a prime, but rather the *product* of two primes.