The NSA may have been able to crack so much encryption thanks to a simple mistake


The NSA may have been able to crack so much encryption thanks to a simple mistake

The NSA could have gained a significant amount of its access to the world’s encrypted communications thanks to the high-tech version of reusing passwords, according to a report from two US academics.

Computer scientists J Alex Halderman and Nadia Heninger argue that a common mistake made with a regularly used encryption protocol leaves much encrypted traffic open to eavesdropping from a well-resourced and determined attacker such as the US national security agency.

The information about the NSA leaked by Edward Snowden in the summer of 2013 revealed that the NSA broke one sort of encrypted communication, virtual private networks (VPN), by intercepting connections and passing some data to the agency’s supercomputers, which would then return the key shortly after. Until now, it was not known what those supercomputers might be doing, or how they could be returning a valid key so quickly, when attacking VPN head-on should take centuries, even with the fastest computers.

The researchers say the flaw exists in the way much encryption software applies an algorithm called Diffie-Hellman key exchange, which lets two parties efficiently communicate through encrypted channels.

A form of public key cryptography, Diffie-Hellman lets users communicate by swapping “keys” and running them through an algorithm which results in a secret key that both users know, but no-one else can guess. All the future communications between the pair are then encrypted using that secret key, and would take hundreds or thousands of years to decrypt directly.

But the researchers say an attacker may not need to target it directly. Instead, the flaw lies in the exchange at the start of the process. Each person generates a public key – which they tell to their interlocutor – and a private key, which they keep secret. But they also generate a common public key, a (very) large prime number which is agreed upon at the start of the process.

The NSA may have been able to crack so much encryption thanks to a simple mistake

Since those prime numbers are public anyway, and since it is computationally expensive to generate new ones, many encryption systems reuse them to save effort. In fact, the researchers note, one single prime is used to encrypt two-thirds of all VPNs and a quarter of SSH servers globally, two major security protocols used by a number of businesses. A second is used to encrypt “nearly 20% of the top million HTTPS websites”.

The problem is that, while there’s no need to keep the chosen prime number secret, once a given proportion of conversations are using it as the basis of their encryption, it becomes an appealing target. And it turns out that, with enough money and time, those commonly used primes can become a weak point through which encrypted communications can be attacked.

In their paper, the two researchers, along with a further 12 co-authors, describe their process: a single, extremely computationally intensive “pre-calculation” which “cracks” the chosen prime, letting them break communications encrypted using it in a matter of minutes.

How intensive? For “shorter” primes (512 bits long, about 150 decimal digits), the precalcuation takes around a week – crippling enough that, after it was disclosed with the catchy name of “Logjam”, major browsers were changed to reject shorter primes in their entirety. But even for the gold standard of the protocol, using a 1024-bit prime, a precalculation is possible, for a price.

The researchers write that “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.”

The NSA may have been able to crack so much encryption thanks to a simple mistake

“Based on the evidence we have, we can’t prove for certain that NSA is doing this. However, our proposed Diffie-Hellman break fits the known technical details about their large-scale decryption capabilities better than any competing explanation.”

There are ways around the problem. Simply using a unique common prime for each connection, or even for each application, would likely reduce the reward for the year-long computation time so that it was uneconomical to do so. Similarly, switching to a newer cryptography standard (“elliptic curve cryptography”, which uses the properties of a particular type of algebraic curve instead of large prime numbers to encrypt connections) would render the attack ineffective.

But that’s unlikely to happen fast. Some occurrences of Diffie-Hellman literally hard-code the prime in, making it difficult to change overnight. As a result, “it will be many years before the problems go away, even given existing security recommendations and our new findings”.

“In the meantime, other large governments potentially can implement similar attacks, if they haven’t already.”

NSA wants encryption that fends off quantum computing hacks


NSA wants encryption that fends off quantum computing hacks

The National Security Agency isn’t just yearning for quantum computers that can break tough encryption — it wants encryption that can protect against quantum computers, too. Officials have begun planning a transition to “quantum resistant” encryption that can’t be cracked as quickly as conventional algorithms. As the NSA explains, even a seemingly exotic technique like elliptic curve cryptography “is not the long term solution” people thought it was. Quantum computing is advancing quickly enough that the NSA and other organizations could find themselves extremely vulnerable if they’re not completely ready when the technology becomes a practical reality.

This doesn’t mean that the NSA is asking the government or security vendors to avoid upgrading their ‘traditional’ encryption. It already has suggestions for cryptographic methods that should make it easier to adopt quantum-proof security. However, the agency doesn’t want others pouring a lot of their time and money into encryption that may well become obsolete in the “not too distant future.” Even though you aren’t likely to see a wave of quantum hacking any time soon, the prospect is real enough that the NSA is treating it as a high priority.

Google is Keeping the NSA Out of Your Data, Eric Schmidt Brags


Google is Keeping the NSA Out of Your Data, Eric Schmidt Brags

Google (GOOGL) Chairman Eric Schmidt boasted on Wednesday about how improving the encryption of Google’s products has successfully shut out warrantless surveillance by the NSA and other law enforcement. Schmidt talked about the encryption advances, and how former NSA contractor Edward Snowden’s leaks prompted them, at BoxDev, a yearly developers conference for Box.

“When the Snowden revelations came out, we were very, very upset,” Schmidt told Aaron Levie, CEO of Box. “They never said anything to us. So we embarked upon a program to fully encrypt the information that our customers entrusted to us.”

Encryption makes it very difficult or impossible for information passed electronically to be deciphered, either by the NSA or even by the company doing the encryption. Snowden’s leaks showed how the NSA uses warrantless mass surveillance of metadata, which Schmidt argued went beyond proper use of the Patriot Act. He and other tech company leaders started boosting their encryption to keep the security agencies from being able to read any email or communication without a warrant. Now encryption is not just a Google project, and it appears to be working.

“Apple and others did the same,” Schmidt said. “And we know our program works, because all the people doing the snooping are complaining about it.”

He’s right about that. FBI Director James Comey told Congress that they should ban phone encryption because of how it helps criminals get away with their crimes. The surveillance is party of what the tech and Internet industry wants to see changed in the Patriot Act and why they are hoping it won’t be renewed in its present form.

The NSA wants a multi-part encryption key for “front door” access to your data


The NSA wants a multi-part encryption key for 'front door' access to your data

The US National Security Agency (NSA) appears to be increasingly concerned about the growing adoption of encryption and its ability to thwart the agency’s surveillance efforts.

Now, after months of debate with tech firms about government access to encrypted data on smartphones and other devices, the NSA has proposed a solution which it hopes will strike a balance between its desire to know everything about everyone and the average law-abiding citizen’s right to privacy.

According to The Washington Post, that solution – put forward by NSA director Michael S. Rogers – lies in a multi-part encryption key, created by various tech companies, which could unlock any device.

Speaking at Princeton University recently, Rogers said the key could be broken into several parts, meaning no one agency or company would be able to use it without the co-operation of the others:

I don't want a back door. I want a front door. And I want the front door to have multiple locks. Big locks.

With the highly contentious Section 215 of the Patriot Act – legislation that has allowed mass eavesdropping from the security services – due to sunset on 1 June 2015, privacy rights groups and concerned members of the public have long been voicing their concerns about bulk data collection.

Add to that the fact that firms such as Apple, Google and Microsoft recently sent a letter to President Barack Obama which demanded an end to data collection, and you can probably see why the NSA is exploring more palatable alternatives.

The debate about encryption and government access comes about as tech companies continue to make customer privacy a key selling point for their products and services.

Companies like Apple – which recently took the decision to enable device encryption by default and made key promises to its customers concerning their privacy – are giving the NSA a real headache as the agency argues the need for government access to data to aid in the battle against crime and terrorism.

Edward Snowden, for his part, continues to lament the level of access the US government still has. At a ecret meeting at this year’s South by Southwest festival he urged tech companies to foil surveillance efforts through the development of better privacy tools.

But Rogers firmly believes that his proposal for a ‘front door’ is both sound and justified, allowing for access as and when required, while keeping data safe from would-be hackers and other forms of attack.

Of course, his view is not universally shared – Donna Dodson, chief cyber­security adviser at the Commerce Department’s National Institute of Standards and Technologies pointed out that a master key still presents a risk, even if it is broken into parts held by different parties:

The basic question is, is it possible to design a completely secure system? There’s no way to do this where you don’t have unintentional vulnerabilities.

Privacy advocates and industry officials alike are not convinced by Rogers’ proposal either. Marc Zwillinger, a former Justice Department official now working as an attorney for tech companies on encryption-related matters, told the Post that law enforcement should not have the undeniable right to access every means of communication between two parties. He added:

I don’t think our Founding Fathers would think so, either.

The fact that the Constitution offers a process for obtaining a search warrant where there is probable cause is not support for the notion that it should be illegal to make an unbreakable lock. These are two distinct concepts.