Researchers claim to have solved NSA crypto-breaking mystery

Researchers believe they have worked out how the United States National Security Agency (NSA) is able to break digital encryption used on the internet and intercept potentially trillions of connections.

Ralph Merkle, Martin Hellman and Whitfield Diffie, who developed the first public-key crypto exchange, in 1975. Source: Stanford University.

A team of computer scientists from US and French universities alongside Microsoft looked into rumours that the NSA has in recent years been able to crack present encryption.

They studied the Diffie-Hellman method of exchanging digital keys between internet-connected computers to encrypt virtual private networking, website, email and other traffic.

Diffie-Hellman has until now been thought to be safe against encryption breaking and protect against mass surveillance, if keys larger than 512 bits are used.

The D-H protocol negotiation starts with the client and server agreeing on a large prime number with a particular form, which would require a vast amount of computational effort to calculate.

However, a paper entitled Imperfect Forward Secrecy: How Diffie-Hellman Fails In Practice [pdf] points to an implementation weakness within many clients and servers that means they reuse the same prime numbers.

Two of the researchers, Alex Haldeman and Nadia Heninger, said that for 1024-bit primes, the most common D-H key strength used currently, a special-purpose hardware-equipped computer would cost a few hundred million US dollars to build.

It's a sum well within the NSA's computer network exploitation budget of US$1 billion in 2013.

Such a system would be able to break one Diffie-Hellman prime a year.

Researcher Nicholas Weaver of the International Computer Science Institute in Berkeley, California, analysed the paper, and said the scientists were "almost certainly correct that the technique they describe is used by the NSA, in bulk, to perform a massive amount of decryption of internet traffic."

Weaver noted that while an NSA supercomputer could break 1024-bit Diffie-Hellman, longer keys like 3072-bit, elliptic curve D-H and RSA encryption could not be cracked in the same way.

For the NSA, being able to break commonly used encryption would have an enormous payoff, the researchers said.

"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," they wrote.

"Breaking a second 1024-bit prime would allow passive eavesdropping on connections to nearly 20 percent 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."

While the researchers said they could not prove for certain that the NSA is breaking internet encryption and eavesdropping and intercepting traffic, they believe their analysis of the weaknesses in Diffie-Hellman implementations fits what is known already about the spy agency's decryption abilities better than other explanations.

The NSA working as both the poacher and game keeper when it comes to encryption is problematic, Haldeman and Heninger said. It means the agency could be exploiting weak Diffie-Hellman while only taking small steps to fix the problems.

"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," they wrote.

Weaver said it was critical that users who wish to protect themselves from "Applied Kleptography" or stealing of digital keys for mass surveillance move away from 1024-bit Diffie-Hellman.

Devices deployed today will be in use for a decade, the researchers wrote, which is as long as adverseries can use the above-mentioned techniques for eavesdropping and interception.