<img height="1" width="1" style="display:none" src="https://www.facebook.com/tr?id=805153362943600&amp;ev=PageView&amp;noscript=1">

Did the NSA really break Diffie-Hellman? Not quite

[fa icon="calendar"] Oct 31, 2016, 9:40:06 AM

If you have any interest in the topics of online privacy, surveillance and encryption, you can’t have missed this month’s big news: a team of scientists simulated how the National Security Agency (NSA) could have broken into trillions of encrypted communications, boiling it down to exploiting backdoors into how the Diffie-Hellman key exchange algorithm is implemented.

The US National Security Agency managed to spy on trillions of encrypted communications.

Which is huge. Diffie-Hellman is the foundation of most public encryption over unsecured channels. It allows protocols like HTTPS, SSH, VPN, and OTR (which we use for Secure Chat) to function by publicly negotiating a secret key with which the correspondence between two parties can be encrypted on the one end and decrypted on the other. Breaking Diffie-Hellman would render most contemporary encryption methods as inefficient as duct-taping a flooding dam.

But did the NSA really break it? Doesn’t seem so. The abovementioned research paper by the University of Pennsylvania, INRIA, CNRS and Université de Lorraine leads us to believe Diffie-Hellman is okay, despite some media outlets’ eagerness to report otherwise. But what exactly did the NSA break then?

How does encryption work?

To understand that we must take a step back and look at the history of cryptography. So, what is encryption? It is the science of securing communication so only those who it is intended for can understand it while making it look like gibberish to everyone else. It has been around for millennia.

One ancient example is the Atbash cipher, used by Hebrew scholars at around 500 or 600 BC. It worked by substituting the first letter of the alphabet with the last one, the second with the second-to-last one and so on. If used with today’s English alphabet it’d mean that a=z, b=y, c=x.... You write “svool” and it means “hello”.

It was probably the cutting-edge encryption tool of its time, but today it seems so simple it can actually be used as an example when explaining what encryption is to children. And this brings us back to the fundamentals of encryption – no encryption technique is theoretically unbreakable, but at a certain point in time an encryption technique could be practically unbreakable with the available technology.

Complexity = more time to solve = security

Contemporary encryption relies on mathematical problems - the more complex, the better.

In more modern times encryption relies on mathematical problems that are easy to solve in one direction, but hard in the other. You know how the cable of your headphones miraculously gets tied into various ridiculous knots really easy by just staying in your pocket? And how it could take you half an hour to unravel it? Encryption and decryption are kind of like that.

The idea is to have an encryption key that is easy to create for you and the person you are having private correspondence with, and hard to solve for eavesdroppers. How secure an encryption method is, boils down to how long it would take supercomputers to solve the problem around which it is built. If the key is so complex that it would take the most powerful computers a thousand years to break, you can be sure your information is pretty safe when encrypted with that key.

For the time being, that is. When decryption technology catches up, it could end up looking as simple as the Atbash cipher does now. By then, however, more sophisticated encryption will be available to make your communications safe. The thing is that encryption and decryption capabilities both evolve at the same time, but encryption is always one step ahead. And the reason is simple – creating complex problems is easier than solving them.

Is Diffie-Hellman obsolete?

Martin Hellman and Whitfield Diffie - inventors of the most commonly used key exchange algorithm.

Well, Diffie-Hellman dates back to the late 1970s (its founders, Martin Hellman and Whitfield Diffie, pictured above, 70s soundtrack not included). Could it be that its time has come then? The study at hand doesn’t suggest so.

What the team of researchers did was to demonstrate how the NSA could’ve decrypted messages by using backdoored prime numbers that were available to no one but those who seeded them in the first place, instead of truly random ones. And the scientists created their own compromised 1024-bit Diffie-Hellman prime so they could show how this works in theory.

And work it did.

As we explained above, the complexity of protection is meassured by the time needed to break it. The time it took the researchers to do this to their own compromised key was two months. Which is not much, given that breaking Diffie-Hellman should theoretically take hundreds of thousands of years. And they used just 3,000 CPUs, which also isn’t a lot – definitely something within the grasp of the NSA and its $10 billion budget.

The implication here is that the agency spied on communications because it had knowledge about the limited number of seed numbers, used to create the primes. Which is not breaking Diffie-Hellman. The algorithm is okay.

More so – while breaking 1024-bit keys is within the reach of well-prepared and well-funded adversaries, 2048-bit ones would take 16 million times longer to crack, the report states. Even if they are trapdoored like in the experiment. Moving to 4096-bit is also on the table. This would defeat the purpose of intentionally weakening encryption standards by once again making the solution to a mathematical problem even harder and computationally impractical.

 

SEE WHAT SOLUTIONS SECURE PACK OFFERS

[fa icon="twitter-square"]

Topics: Encryption, end-to-end encryption, backdoor, NSA

Stefan Topuzov

Written by
Stefan Topuzov

Security Expert