It’s not unusual — one might even say it is fairly common — for me to wander down some rabbit hole on the intertoobz and find myself in way over my head. Such was the case a few years ago when I first read about the Diffie-Hellman Key Exchange. (The name makes it sound like it’s about swingers, but it’s actually an encryption protocol.)
It gets way math-y, but what the protocol does is allow two computers to create a secure connection by first generating a shared private encryption key across a non-secure connection, and then using that key to exchange information. Here’s a very simple example: You and I want to exchange some encrypted data. In order to encrypt the data, and later decrypt it, we both need to have the same key. But we are on different sides of the world, and don’t actually know each other. In order to create the key, we first agree on a “public” number, let’s say we pick the numeral 11. Next, we both choose a “private” number, let’s say I pick 5 and you choose 7. I multiply our public number (11) by my private number (5) for a total of 55, and I send that to you. You multiply our public number (11) by your private number (7) producing 77, and you send that to me. Now we both multiply what the other sent by our respective private numbers. I multiply 77 times 5, you multiply 55 times 7, and we both end up with our secret key of 385 without ever having to exchange it over the non-secure connection.
Of course, since we are using computers, we don’t have to limit ourselves to simple multiplication. We can use logarithmic algorithms and really large prime numbers, making our key impossible to break for anyone without a supercomputer and a whole lot of time and money to waste. Sure, given enough time, any code can be cracked, but why would anyone put so much time and effort into breaking one key when the protocol generates a new key for every transaction, right? Right? Not so much.
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. 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.
Oopsie. Overconfidence and a dash of laziness will burn you every time. But what evil empire would do such a dastardly thing? Say it with me. U-S-A! U-S-A!
There have been rumors for years that the NSA can decrypt a significant fraction of encrypted Internet traffic. In 2012, James Bamford published an article quoting anonymous former NSA officials stating that the agency had achieved a “computing breakthrough” that gave them “the ability to crack current public encryption.” The Snowden documents also hint at some extraordinary capabilities: they show that NSA has built extensive infrastructure to intercept and decrypt VPN traffic and suggest that the agency can decrypt at least some HTTPS and SSH connections on demand.
That’s right. Your government can decrypt HTTPS. Not only did you give your credit card number to that shady website in Thailand, the NSA now knows your tastes in porn. If that doesn’t scare you, consider this: If our government can do it, you can bet your ass China and Russia are doing it too, or will be soon enough.