Ever since Edward Snowden revealed that the National Security Agency, an intelligence gathering organization of the U.S. government, has achieved unprecedented capabilities to intercept and decrypt digital information, there has been speculation as to the nature and extent of their capabilities. This week at the ACM Conference on Computer and Communications Security, security researchers revealed the probable method the government agency was using to break high-level encryption. While it’s impossible to confirm, many security experts believe the NSA’s methodology to achieve surveillance of highly encrypted internet communication lies in their ability to ‘crack’ an encryption algorithm known as Diffie-Hellman. 

According to the researchers, it is “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 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.” The information is collected in a paper published earlier this year; there’s also a blog post for the TL;DR crowd. 

Note that the researchers make a point of saying the vulnerability in the algorithm can be exploited by state-level attackers, as breaking such an algorithm is prohibitively expensive and time-consuming. To unencrypt a single numerical value used in the algorithm costs a few hundred million dollars and would take approximately one year. The NSA’s annual budget for “groundbreaking cryptanalytic capabilities” has been revealed to be approximately $11 billion. While this cryptographic breakthrough makes it possible for the government of the United States to decrypt online communication on a mass scale, it also reveals the vulnerability to other spy agencies including those of their adversaries. Halderman and Heninger, two of the researchers behind this paper, write:

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