Some Edward Snowden leaks have revealed that the NSA and other intelligence agencies can break encryption barriers for mass surveillance purposes. It has been theorized that a flaw in encryption used by many Internet services lets the spy agency decrypt HTTPS, SSH, and VPN traffic, and a new paper seems to prove that.
Indeed, a massive effort comparable to the attempts of breaking the German Enigma coding machine during the World War II seems to have given the NSA the tools required to break trillions of secure connections.
DON’T MISS: ‘Netflix for pirates’ now streams movies directly to your web browser
Researchers Alex Halderman, Nadia Heninger and 12 other coauthors won the best paper at the ACM Conference on Computer and Communications Security for the Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice research.
The paper describes the way the NSA – and anyone else with access to similar resources – must have been able to decrypt online secure connections and eavesdrop on communication believed to be protected from prying eyes.
According to the researchers, the NSA didn’t exactly break encryption per se, instead targeting a human flaw: online services tend to reuse the same 1024-bit prime numbers to encrypt services.
“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,” the researchers wrote. “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.”
Cracking those prime numbers, however, is no easy fit, and you wouldn’t be able to do it on your laptop. The computational effort might be on par with the Enigma cryptanalysis during World War II, the researchers speculate, relative to the state of computing at the time.
The complexity of the algorithm involved makes it a tough task that requires a special machine using special-purpose hardware that would cost a few hundred million to build. The machine would crack one Diffie-Hellman prime number each year, which could be used to break encryption.
The NSA certainly can afford it. A 2013 black budget Snowden leak reveals that the agency has prioritized investing in “groundbreaking cryptanalytic capabilities to defeat adversarial cryptography and exploit internet traffic.” In cash, that means the NSA had over $1 billion to spend on computer network exploitations, running additional subprograms that would cost hundreds of millions per year.
“Would this be worth it for an intelligence agency?” researchers rhetorically asked, and the answer seems to be yes.
“Since a handful of primes are so widely reused, the payoff, in terms of connections they could decrypt, would be enormous,” they explain. “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.”
At the same time, the NSA is apparently more than aware that other players with such access to resources would be able to run similar spy programs, which is probably why the agency is encouraging the move to more advanced encryption tools in the future.
