A lot has been written in the news of late about the NSA, especially now that Snowden is back in the news after joining Twitter just last week. In his revelations in 2013 about surveillance, Snowden revealed that the NSA had gained access to data and metadata on millions of US citizens, and was involved in an illegal data sharing programme with the United Kingdom's Government Communications Headquarters. At the time, there wasn't much information circulating as to how this data and metadata was accessed, although what we did know at the time may in fact not be true at all. So, let's look at what we thought was true at the time the information was first released by Snowden in the summer of 2013, and then at how a research study has changed all that.

What we originally knew

Back in the summer of 2013, Edward Snowden leaked information to various journalists about the surveillance practices of the NSA and GCHQ. As an employee of the NSA at the time, he became uncomfortable with the level of surveillance being carried out on everyday citizens, and the methods being used to do so. So, he leaked as much information as he could to the press using encrypted communication software, and is now hailed as a modern hero in the fight against surveillance.

At the time, it was thought that the NSA had eavesdropped on the conversations of millions of American citizens by cracking the encryption code behind virtual private networks (or VPNs). They did this using a complicated method, whereby first they would intercept the communication unencrypted. This would then be passed to one of the NSA's supercomputers, where complex software and computational methods would be used to determine the encryption key for that VPN. Once the key had been determined, the NSA was able to listen in to the conversation unencrypted. However, this was unprecedented at the time. As they are an extremely complicated and secure form of encryption, cracking a VPN key takes considerable time and effort, sometimes even centuries, even for the most advanced supercomputers at the NSA – so how were they doing it so quickly? At the time, scientists were not able to work this out, and so it was just assumed that the supercomputers contained a new algorithm, capable of working at super-high speeds to make complex calculations. 

However, new research by a team of scientists including computer security experts J. Alex Halderman and Nadia Heninger has found that the key to the NSA's decryption method might not be super-fast supercomputers at all, but could simply be a mistake on the behalf of the encryptors. So what does this mean and how does it work?

The simple mistake

So how can the cracking of millions of mobile phone VPNs be down to just one simple mistake? Let's start at the beginning. When a VPN is created, each should be given its own, unique set of encryption keys. In order to create these keys, there is an algorithm called the Diffie-Hellman key exchange. At the start of the conversation between the two parties, three keys are created for each party: a public key, a private key, and a common public key. The Diffie-Hellman exchange then encrypts the conversation by swapping these keys through its exchange. Once these keys are swapped, the conversation is then encrypted. Then, all future communication between those two parties is encrypted using those keys. In addition, as each key is unique and then swapped through the exchange with the corresponding key for the other person in the conversation, cracking this code is very difficult indeed. As stated above, it would take even the most advanced supercomputers in the world hundreds or thousands of years to guess these keys and decrypt the conversation. So how did they do it?

Herein lies the mistake. Above we told you that before the start of each conversation, three keys are generated for each party: a public key, a private key, and a common public key. The last in that list is the one we want to concentrate on. Common public keys are agreed on at the start of the communication, and are always very large prime numbers. So, as these common public keys are public anyway, many encryption services reuse them to save money – reusing the same keys saves computational time and money for the company involved. It is estimated that one single common public key has been reused to encrypt two-thirds of all VPNs and 25% of all SSH servers worldwide. But reusing these keys, as we shall see, is a big mistake. As they are reused and easily determinable, it is these common public keys that become the target, and an easy one at that.

So how does it work?

The research team involved used a number of complex computational methods to 'attack' the common public keys of a number of encrypted test phone calls. In doing this, they found that a method called 'pre-calculation' could be used to determine the prime number used as the common public key in the communication; from there, the team were able to then crack the rest of the encryption. However, in their studies the team found that this cracking process based on the pre-calculation of prime numbers still takes a fair amount of time. Indeed, for the shortest prime numbers tested (or most intensive, in scientific jargon), cracking the encryption took around a week to complete, and that was with some of the most advanced supercomputers in the world. 

So, the main question here is: is all of this true? Did the NSA manage to hack into the communications of millions of American citizens by figuring out that the companies encrypting the conversations made such a simple mistake as reusing their passwords? Well, the team behind the research say that there is no definitive proof that this is how the NSA hacked VPN encrypted communications, but it is one interesting theory in an ever evolving saga that looks like it won't be ending any time soon. How this discovery plays out in terms of the NSA and GCHQ, we will have to wait and see.