Why the NSA may not need backdoors

 Image: Declan McCullagh/CNET

James Bamford’s 2012 WIRED article The NSA Is Building the Country’s Biggest Spy Center (Watch What You Say) is a fascinating read about the NSA’s monster data center near Bluffdale, Utah and what it might be used for. Here’s an excerpt:

“Breaking into those complex mathematical shells like the AES is one of the key reasons for the construction going on in Bluffdale,” explains Bamford. “That kind of cryptanalysis requires two major ingredients: super-fast computers to conduct brute-force attacks on encrypted messages and a massive number of those messages for the computers to analyze. The more messages from a given target, the more likely it is for the computers to detect telltale patterns, and Bluffdale will be able to hold a great many messages.”

Bamford then suggests the super-fast computers are part of the High Productivity Computing Systems program located in Oakridge, Tenn. (of Manhattan Project fame), specifically in Building 5300 according to a former senior intelligence official involved in the project interviewed by Bamford.

The official mentions that security intensified in a big way when the Building 5300 team made a huge breakthrough, adding, “They were thinking that this computing breakthrough was going to give them the ability to crack current public encryption.”

Fast forward to 2015 and more evidence

Over the past several months, US law enforcement agencies have been advocating backdoors be added to encryption software, raising the ire of security pundits everywhere. The pundits fought back until finally the federal government cried “uncle.” The battle may have been won, but is the war really over?

Paul Rosenzweig is skeptical. Rosenzweig, founder of Red Branch Consulting PLLC, a Homeland Security consulting company and a senior adviser to The Chertoff Group, wrote an interesting post on the Lawfare Institute’s website. He mentions the whole issue about backdoors is only relevant if current public-key encryption techniques are indeed uncrackable, as per numerous qualified cryptographic sources.

Rosenzweig then speculates, “What if, in fact, certain implementations of public key encryption techniques are not as robust as we think they are?”

Rosenzweig’s theorizing resulted from a Freedom to Tinker article by J. Alex Halderman, associate professor of Computer Science and Engineering at the University of Michigan, and Nadia Heninger, assistant professor of Computer and Information Science at the University of Pennsylvania. In the article How is NSA breaking so much crypto?, the two academics make the case some implementations of the Diffie-Hellman protocol (used by HTTPS and VPN systems) can be cracked.

This is not just idle conjecture. They, along with 12 coauthors, recently presented their paper Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice (PDF) at the Association for Computing Machinery’s 2015 Conference on Computer and Communications Security. Through hard work and serious number-crunching, as evidenced in the paper, the team of authors determined, “Through a confluence of number theory and bad implementation choices, many real-world users of Diffie-Hellman are likely vulnerable to state-level attackers.”

Halderman and Heninger offer the following details:

“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 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.”

Is it worth the NSA’s bother?

The paper’s authors are realistic, saying the computations required would be a technical feat 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,” write Halderman and Heninger. “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.”

As to whether it’s worth it to the NSA, Halderman and Heninger state:

  • Breaking a single, common 1024-bit prime would allow the 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.

The authors put it simpler, “In other words, a one-time investment in massive computation would make it possible to eavesdrop on trillions of encrypted connections.”

The NSA’s dilemma

In conclusion, Halderman and Heninger point out the NSA’s dual-purpose mission of gathering intelligence and defending US computational systems is an unrealistic expectation, adding, “If our hypothesis is correct, the agency has been vigorously exploiting weak Diffie-Hellman, while taking only small steps to help fix the problem.”

In the agency’s defense, the authors admit the NSA recommends transitioning to elliptic curve cryptography, which isn’t known to suffer from this loophole. However, Halderman and Heninger also point out, “The security community is hesitant to take NSA recommendations at face value, following their apparent efforts to backdoor cryptographic standards.”

Also see