Nearly Setec Astronomy

Holy crap.

I’m still reeling from the latest revelation to come from Edward Snowden:

The files show that the National Security Agency and its UK counterpart GCHQ have broadly compromised the guarantees that internet companies have given consumers to reassure them that their communications, online banking and medical records would be indecipherable to criminals or governments.

This goes far beyond anything I was speculating about a few weeks ago. They don’t mention compromising a CA, but given the scope of the programs revealed yesterday, compromising multiple certificate authorities would be just one small part of the NSA’s assault on privacy. And they really do think of our privacy as the enemy:

The agencies, the documents reveal, have adopted a battery of methods in their systematic and ongoing assault on what they see as one of the biggest threats to their ability to access huge swathes of internet traffic – “the use of ubiquitous encryption across the internet”.

Here’s how the Guardian article describes what the NSA has been doing:

Those methods include covert measures to ensure NSA control over setting of international encryption standards, the use of supercomputers to break encryption with “brute force”, and – the most closely guarded secret of all – collaboration with technology companies and internet service providers themselves.

If I understand the revelations correctly, this doesn’t describe a single program so much as a strategy.

Cryptography is based on math. The broad idea is to find classes of math problems that are that are easy to solve if you have a hint. Encryption then consists of two steps: Generating a random math problem in this class, and then taking plaintext data and transforming it into ciphertext in such a way that the reverse transform back into plaintext will require you to solve the math problem. Since the problem is much easier to solve with the hint, having the hint is like having the key to unlock a door, and this hint becomes the decryption key.

For example, our math problem might involve rotating letters around the alphabet, transforming each letter into, say, the 5th letter after it. A becomes F, B becomes G, Z rotates around to become D, and so on. The decryption is just the reversal: F becomes A, G becomes A, and D rotates back around to become Z. In this example, the class of math problems is rotation around the alphabet, and this particular math problem is based on rotating 5 steps.

Now if I give you a string such as “BNSIDUZSINY” and tell you that it has been rotated by some number of characters, the only way you can decode it is to try all 26 possible rotations and see if any of them make sense. This will take you, on average, 13 tries. Since it is 11 letters long, you will do a total of 143 rotations, on average, to decode it.

On the other hand, if I also tell you that the number of characters it has been rotated is 5, then it will only take you one try — 11 rotations — to decode it to “WINDYPUNDIT”. In other words, by having the hint “5”, you can decrypt it 13 times faster than without the hint. This hint is our decryption key.

Real encryption systems, such as the ones protect your bank’s website, are based on the same principle, but the math problems are much more complicated, and instead of a 13-to-1 advantage to having the decryption key, it’s more like a 13, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000 – to – 1 advantage.

Even if you could convert all the matter in the entire known universe into cloud computing, using any computing technology we know of, you couldn’t try all those keys before the stars burnt out. (Not that there are stars anymore, because you’ve converted them to computers.)

Of course, nobody seriously trying to attack modern public-key encryption will actually try to brute-force it; that would be impossible (unless the key is really tiny). Instead, they try to look for shortcuts that solve the math problem by something other than brute-force guessing. After all, if the problem collapses from impossible to trivial when you have the hint (the decryption key) maybe there are intermediate non-trivial but non-impossible solutions that can be found through analysis of the encrypted data.

Much of internet-based security depends on the RSA algorithm, and there are no known attacks on RSA that improve on brute force enough to make it seriously insecure. On the other hand, nobody has proven that such attacks don’t exist.

Public key encryption algorithms are that complex and that hard to crack because they were designed to be. It’s why they’re secure.

But…

The design process is done by humans, often in the form of standards documents, and this latest document dump from Snowden reveals that some of those humans work for the NSA, and some of them have been secretly making design choices in standards documents that make the encryption weaker.

Some of this may be obvious, in the form of performance trade-offs. Encryption with 2048-bit keys requires more computing power than 1024-bit keys, and since even 1024-bit keys are currently secure, why not use the smaller key and save computing power? Other ways to weaken encryption maybe be a lot less obvious. Cryptography experts have often questioned the reasoning behind some strange decisions by the standards bodies, and subornation by the NSA could explain some of them.

Furthermore, although cryptographic algorithms are math, practical implementations of encryption systems require more than just the encryption algorithm — you have to generate the keys, distribute the public keys, encode the data, and so on — and a lot of that can introduce vulnerabilities. For example, some RSA public keys are inherently weak, so a good implementation has to test each key for these weaknesses and discard keys that don’t pass. Other times, weaknesses in the key generations can produce collections of keys that have mathematical relationships that can be exploited, so that an attacker who collects enough keys from the weak generator can crack all the related keys.

Again, encryption implementations are more than just math, they are code. And the latest Snowden revelations reveal that the NSA has been working with the major technology companies to make sure the code further weakens the security of our encryption systems. There have been convincing allegations of such attacks in the past, and Snowden is claiming that other encryption systems have been compromised as well.

Finally, the Snowden documents mention some sort of breakthrough that makes it easier for the NSA to crack Internet encryption. It’s possible this is some sort of improved attack on the RSA algorithm, or some other part of the encryption process. Bruce Schneier has seen the Snowden documents, and he says the RSA algorithm is still secure, but the NSA has undermined everything around it.

Between these three strategies — undermining standards, undermining code, and some kind of cryptographic breakthrough — it’s possible that the NSA has significantly reduced the practical difficulties of cracking RSA as used in the real world. Even if decryption without the key remains a billion times harder than with the key, those supercomputers mentioned in the quote above could probably crack them in a time frame of seconds to minutes.

In addition, they apparently have built themselves a huge toolkit for compromising computing systems, and people smarter than me say they can probably get into any computer on the internet if they try hard enough. It’s not so easy that they can do it to more than a small fraction of the world’s computers, and it’s risky because they could get caught, but

These are hacker tools designed by hackers with an essentially unlimited budget. What I took away from reading the Snowden documents was that if the NSA wants in to your computer, it’s in. Period.

Then, once the NSA gets into a computer, they can search it for private decryption keys. Lots of good it does to use SSL or PGP if the NSA can copy the keys and certificates off your computer and throw them to a cloud of 100,000 computers to brute-force your password. Or they can compromise your computer’s encryption software to weaken it, then intercept and decrypt the data stream out on the Internet. They may also have broken into the Certificate Authorities’ computers and stolen the signing keys, allowing them to conduct man-in-the-middle attacks.

All of this leaves me feeling somewhat conflicted. On the one hand, I’m a techno-geek, and what the NSA has done is damned impressive. This is as close as we’ve come in the real world to Setec Astronomy, and it’s an awe-inspiring accomplishment of breathtaking scope.

On the other hand — although the major media doesn’t seem worried about it, judging by the lack of coverage — the NSA has essentially destroyed the trusted framework of the internet. Not just the parts of it used by terrorists, cybercriminals, and human traffickers, but all of it, from the secure website where you do your banking, to your medical records, to Gmail, Facebook, and Twitter.

The documents seem to claim that the NSA’s subversions don’t weaken security unless we know what the NSA knows about them:

“These design changes make the systems in question exploitable through Sigint collection … with foreknowledge of the modification. To the consumer and other adversaries, however, the systems’ security remains intact.”

That sounds just like something the NSA would do. They’re trying to balance their espionage role of spying on everyone’s communications with their counter-espionage role of securing American communications. The problem is that we’re all on the same global Internet — everyone uses the same technology and everyone talks to everyone else — so those goals collide head-on: The NSA wants to have back doors through the encryption, but they don’t want anyone else to use them, so they poke holes in the security, and then they make those holes as secure as they can.

There are two problems with that. The first is technological: If the NSA has weakened the security technology of the internet, then we’re all using weaker security technology. We all become more vulnerable because of that.

However, even if the NSA has taken great pains to ensure that other adversaries cannot easily benefit from the backdoors they’ve installed, they’re still going to run into the second problem: People. The people making up the NSA are fallible and flawed, and subject to failure and indiscretions. Some of them probably have evil intentions.

One of the NSA slides describes a part of this program as “Extremely fragile.” That may be, but even worse than that, it’s brittle: All it would take is for someone to leak detailed information about the NSA’s subversion of Internet security, and then other intelligence agencies could do it. It’s the cyber equivalent a corporate security officer who puts steel doors with $1000 electronic locks on 100 offices but keeps a copy of the master key locked in his desk. Thieves who want to rob the place blind don’t have to break through 100 locks, they only have to break through one. Anyone who can compromise the NSA can compromise the Internet.

And we know the NSA is compromised. The proof is that we’re reading about this right now. Edward Snowden has taught the NSA a brutal lesson in the hazards of brittle security systems. As the Director of National Intelligence, James R. Clapper, says:

The stories published yesterday, however, reveal specific and classified details about how we conduct this critical intelligence activity. Anything that yesterday’s disclosures add to the ongoing public debate is outweighed by the road map they give to our adversaries about the specific techniques we are using to try to intercept their communications in our attempts to keep America and our allies safe and to provide our leaders with the information they need to make difficult and critical national security decisions.

I think “outweighed” is not his place to decide, but I’m sure he’s right about the damage. Our national enemies have learned of our ability to spy on them, and they will change their behavior to get out from under NSA surveillance. This is a devastating blow.

I actually feel bad for the NSA about this. An awful lot of very smart people with good intentions have done a lot of hard work, and they’ve accomplished something rather amazing: Making most of the internet transparent, at least to the U.S. government. Depending how our adversaries respond, Edward Snowden has destroyed much of their work. Hundreds of millions of dollars worth of effort down the tubes. Maybe more.

But again, the problem is people. Snowden is not the guy who has stolen the NSA’s secrets. He’s just the only guy who has stolen NSA secrets that we know about.

I mean, what are the chances that the only person who has ever walked this information out the door of the NSA is an outside contractor with idealistic tendencies? It’s starting to look like the NSA didn’t even know he took this stuff until he started dumping it to the world media. If somebody else walked out with another thumb drive and sold it to the Russians and the Chinese, is there any way we could even tell? Our nation’s enemies could have had this information for years before we heard about it.

Then there are the internal enemies. We already know from other leaks that NSA personnel spy on their friends and lovers, so why wouldn’t they compromise corporate computing facilities and sell trade secrets to the highest bidders? Why wouldn’t they read an opposing political party’s email? High-security activities are a breeding ground for misbehavior because of the lack of transparency. I’m sure the NSA has its share of the kind of grasping megalomaniacs that seem to populate middle and upper management throughout industry and government, and the NSA provides them with an opportunity to operate with relatively little oversight.

We also have to worry about the kinds of internal enemies that the NSA doesn’t even think of as enemies, such as other government agencies with totalitarian leanings. We already know they share information with the DEA, which then goes on to arrest people based on the information and then lie to everyone about where they got it. The NSA may be a pure intelligence agency, but at this point the DEA is pretty much the American equivalent of the Taliban, invading homes and locking people in cages out of a near-religious conviction that they’re doing something wrong. The United States has the highest percentage of it’s population in prison of any country in the world, and the NSA is helping it jail even more.

I keep coming back to Clapper’s invocation of “terrorists, cybercriminals, human traffickers…” Why is that third item on the list? It seems like a basic appeal to the moral panic of the day. Granted, human trafficking is a real problem, yet when government agencies talk about trafficking, they almost always mean sex trafficking, which they conflate with ordinary prostitution and other sex work. So now I’m imagining an NSA Human Trafficking department that breaks into escort web sites…Polish Princess sure sounds like it’s full of foreign nationals, right? It seems like the NSA are already thinking of themselves as a program in search of a justification.

I guess what I worry about most is that the revelation of this program will severely impair the legitimate activities of the NSA by alerting our nation’s enemies to the NSA’s capabilities, but that nothing else will change. Our enemies will have learned how to hide from the NSA, but the NSA will keep right on spying on the rest of us, using whatever justification seems to work.