Entries Tagged "VPN"

Page 2 of 2

Breaking Diffie-Hellman with Massive Precomputation (Again)

The Internet is abuzz with this blog post and paper, speculating that the NSA is breaking the Diffie-Hellman key-exchange protocol in the wild through massive precomputation.

I wrote about this at length in May when this paper was first made public. (The reason it’s news again is that the paper was just presented at the ACM Computer and Communications Security conference.)

What’s newly being talked about his how this works inside the NSA surveillance architecture. Nicholas Weaver explains:

To decrypt IPsec, a large number of wiretaps monitor for IKE (Internet Key Exchange) handshakes, the protocol that sets up a new IPsec encrypted connection. The handshakes are forwarded to a decryption oracle, a black box system that performs the magic. While this happens, the wiretaps also record all traffic in the associated IPsec connections.

After a period of time, this oracle either returns the private keys or says “i give up”. If the oracle provides the keys, the wiretap decrypts all the stored traffic and continues to decrypt the connection going forward.


This would also better match the security implications: just the fact that the NSA can decrypt a particular flow is a critical secret. Forwarding a small number of potentially-crackable flows to a central point better matches what is needed to maintain such secrecy.

Thus by performing the decryption in bulk at the wiretaps, complete with hardware acceleration to keep up with the number of encrypted streams, this architecture directly implies that the NSA can break a massive amount of IPsec traffic, a degree of success which implies a cryptanalysis breakthrough.

That last paragraph is Weaver explaining how this attack matches the NSA rhetoric about capabilities in some of their secret documents.

Now that this is out, I’m sure there are a lot of really upset people inside the NSA.

EDITED TO ADD (11/15): How to protect yourself.

Posted on October 16, 2015 at 6:19 AMView Comments

The Logjam (and Another) Vulnerability against Diffie-Hellman Key Exchange

Logjam is a new attack against the Diffie-Hellman key-exchange protocol used in TLS. Basically:

The Logjam attack allows a man-in-the-middle attacker to downgrade vulnerable TLS connections to 512-bit export-grade cryptography. This allows the attacker to read and modify any data passed over the connection. The attack is reminiscent of the FREAK attack, but is due to a flaw in the TLS protocol rather than an implementation vulnerability, and attacks a Diffie-Hellman key exchange rather than an RSA key exchange. The attack affects any server that supports DHE_EXPORT ciphers, and affects all modern web browsers. 8.4% of the Top 1 Million domains were initially vulnerable.

Here’s the academic paper.

One of the problems with patching the vulnerability is that it breaks things:

On the plus side, the vulnerability has largely been patched thanks to consultation with tech companies like Google, and updates are available now or coming soon for Chrome, Firefox and other browsers. The bad news is that the fix rendered many sites unreachable, including the main website at the University of Michigan, which is home to many of the researchers that found the security hole.

This is a common problem with version downgrade attacks; patching them makes you incompatible with anyone who hasn’t patched. And it’s the vulnerability the media is focusing on.

Much more interesting is the other vulnerability that the researchers found:

Millions of HTTPS, SSH, and VPN servers all use the same prime numbers for Diffie-Hellman key exchange. Practitioners believed this was safe as long as new key exchange messages were generated for every connection. However, the first step in the number field sieve — the most efficient algorithm for breaking a Diffie-Hellman connection — is dependent only on this prime. After this first step, an attacker can quickly break individual connections.

The researchers believe the NSA has been using this attack:

We carried out this computation against the most common 512-bit prime used for TLS and demonstrate that the Logjam attack can be used to downgrade connections to 80% of TLS servers supporting DHE_EXPORT. We further estimate that an academic team can break a 768-bit prime and that a nation-state can break a 1024-bit prime. Breaking the single, most common 1024-bit prime used by web servers would allow passive eavesdropping on connections to 18% of the Top 1 Million HTTPS domains. A second prime would allow passive decryption of connections to 66% of VPN servers and 26% of SSH servers. A close reading of published NSA leaks shows that the agency’s attacks on VPNs are consistent with having achieved such a break.

Remember James Bamford’s 2012 comment about the NSA’s cryptanalytic capabilities:

According to another top official also involved with the program, the NSA made an enormous breakthrough several years ago in its ability to cryptanalyze, or break, unfathomably complex encryption systems employed by not only governments around the world but also many average computer users in the US. The upshot, according to this official: “Everybody’s a target; everybody with communication is a target.”


The breakthrough was enormous, says the former official, and soon afterward the agency pulled the shade down tight on the project, even within the intelligence community and Congress. “Only the chairman and vice chairman and the two staff directors of each intelligence committee were told about it,” he says. The reason? “They were thinking that this computing breakthrough was going to give them the ability to crack current public encryption.”

And remember Director of National Intelligence James Clapper’s introduction to the 2013 “Black Budget“:

Also, we are investing in groundbreaking cryptanalytic capabilities to defeat adversarial cryptography and exploit internet traffic.

It’s a reasonable guess that this is what both Bamford’s source and Clapper are talking about. It’s an attack that requires a lot of precomputation — just the sort of thing a national intelligence agency would go for.

But that requirement also speaks to its limitations. The NSA isn’t going to put this capability at collection points like Room 641A at AT&T’s San Francisco office: the precomputation table is too big, and the sensitivity of the capability is too high. More likely, an analyst identifies a target through some other means, and then looks for data by that target in databases like XKEYSCORE. Then he sends whatever ciphertext he finds to the Cryptanalysis and Exploitation Services (CES) group, which decrypts it if it can using this and other techniques.

Ross Anderson wrote about this earlier this month, almost certainly quoting Snowden:

As for crypto capabilities, a lot of stuff is decrypted automatically on ingest (e.g. using a “stolen cert”, presumably a private key obtained through hacking). Else the analyst sends the ciphertext to CES and they either decrypt it or say they can’t.

The analysts are instructed not to think about how this all works. This quote also applied to NSA employees:

Strict guidelines were laid down at the GCHQ complex in Cheltenham, Gloucestershire, on how to discuss projects relating to decryption. Analysts were instructed: “Do not ask about or speculate on sources or methods underpinning Bullrun.”

I remember the same instructions in documents I saw about the NSA’s CES.

Again, the NSA has put surveillance ahead of security. It never bothered to tell us that many of the “secure” encryption systems we were using were not secure. And we don’t know what other national intelligence agencies independently discovered and used this attack.

The good news is now that we know reusing prime numbers is a bad idea, we can stop doing it.

EDITED TO ADD: The DH precomputation easily lends itself to custom ASIC design, and is something that pipelines easily. Using BitCoin mining hardware as a rough comparison, this means a couple orders of magnitude speedup.

EDITED TO ADD (5/23): Good analysis of the cryptography.

EDITED TO ADD (5/24): Good explanation by Matthew Green.

Posted on May 21, 2015 at 6:30 AMView Comments

Silk Road Author Arrested Due to Bad Operational Security

Details of how the FBI found the administrator of Silk Road, a popular black market e-commerce site.

Despite the elaborate technical underpinnings, however, the complaint portrays Ulbricht as a drug lord who made rookie mistakes. In an October 11, 2011 posting to a Bitcoin Talk forum, for instance, a user called “altoid” advertised he was looking for an “IT pro in the Bitcoin community” to work in a venture-backed startup. The post directed applicants to send responses to “rossulbricht at gmail dot com.” It came about nine months after two previous posts — also made by a user, “altoid,” to shroomery.org and Bitcoin Talk — were among the first to advertise a hidden Tor service that operated as a kind of “anonymous amazon.com.” Both of the earlier posts referenced silkroad420.wordpress.com.

If altoid’s solicitation for a Bitcoin-conversant IT Pro wasn’t enough to make Ulbricht a person of interest in the FBI’s ongoing probe, other digital bread crumbs were sure to arouse agents’ suspicions. The Google+ profile tied to the rossulbricht@gmail.com address included a list of favorite videos originating from mises.org, a website of the “Mises Institute.” The site billed itself as the “world center of the Austrian School of economics” and contained a user profile for one Ross Ulbricht. Several Dread Pirate Roberts postings on Silk Road cited the “Austrian Economic theory” and the works of Mises Institute economists Ludwig von Mises and Murray Rothbard in providing the guiding principles for the illicit drug market.

The clues didn’t stop there. In early March 2012 someone created an account on StackOverflow with the username Ross Ulbricht and the rossulbricht@gmail.com address, the criminal complaint alleged. On March 16 at 8:39 in the morning, the account was used to post a message titled “How can I connect to a Tor hidden service using curl in php?” Less than one minute later, the account was updated to change the user name from Ross Ulbricht to “frosty.” Several weeks later, the account was again updated, this time to replace the Ulbricht gmail address with frosty@frosty.com. In July 2013, a forensic analysis of the hard drives used to run one of the Silk Road servers revealed a PHP script based on curl that contained code that was identical to that included in the Stack Overflow discussion, the complaint alleged.

We already know that it is next to impossible to maintain privacy and anonymity against a well-funded government adversary.

EDITED TO ADD (10/8): Another article.

Posted on October 7, 2013 at 1:35 PMView Comments

China Now Blocking Encryption

The “Great Firewall of China” is now able to detect and block encryption:

A number of companies providing “virtual private network” (VPN) services to users in China say the new system is able to “learn, discover and block” the encrypted communications methods used by a number of different VPN systems.

China Unicom, one of the biggest telecoms providers in the country, is now killing connections where a VPN is detected, according to one company with a number of users in China.

EDITED TO ADD (1/14): Some interesting blog comments from an American living and working in China.

Posted on December 20, 2012 at 6:32 AMView Comments

Sidebar photo of Bruce Schneier by Joe MacInnis.