Breaking crypto: Not like the movies!

Web encryption is at the top of the discussion list these days in geek circles and with good cause. The revelations over the past few months that many countries are collecting wide swaths of Internet data on their own and foreign citizens has made us all stop and re-think things. We used to think it was fairly near impossible to collect every email and every web session that passes through the Internet but that assumption is now being challenged. Even the security of our encrypted web sessions using the tried and true Secure Sockets Layer (SSL) technology has now been revealed to be orders of magnitude less secure from government prying than we thought. As we work our way through this maelstrom of blows to the head it’s becoming clear that the only answer to true privacy on the Internet is Trust No One (TNO) encryption.

Who uses encryption, anyhow?

The short answer is that we all do, we’re just aware of it in degrees varying from really aware to not a clue it’s happening. Joe netizen who does things like Internet banking uses SSL encryption every session but the browser takes care of it all so Joe has no idea it’s happening. If websites did not use SSL encryption, then Joe would be giving away his username, his password, his bank account numbers, and everything else every time he used his bank’s website. These days many websites other than banks force SSL encryption in order to protect their users because the bad guys have shown that they can wreak havoc with just usernames and passwords, never mind more sensitive data.

What is this encryption you speak of?

I think we all understand that encryption means something is encoded in such a way that only the intended recipient can unscramble it and read it. If I want to send you something encrypted, then I have to scramble it in some way that you will know how to unscramble it. The method that you use to unscramble it is called the “key”. Anyone with the key to the scramble will be able to read the message.

Up until somewhere around the 1970’s all crypto was symmetrical meaning that there was only a single key and it was used to encode as well as decode the message. This symmetrical crypto process was very secure and it still in wide use today in industrial and military grade crypto, but it has one serious drawback. In order for me to encrypt something to send to you, you and I would have had to meet prior in order to share the symmetrical key with each other. That really limits the usefulness of crypto because you can’t go running to your bank to get a crypto key in order to use their website; then run to facebook to get a key to use their site, then run to your employer to get a key to use their web mail, etc, etc. Another problem with symmetrical crypto is that once you have the key to encrypt messages, you can also decrypt all the messages sent to whomever gave you the key. In short, you need to give away the farm with symmetrical crypto. What we really need is a method to share a key without any prior meeting between the two parties. This is called asymmetrical crypto and now forms the basis for what we call the Public Key Infrastructure (PKI).

Steven Levy’s book, Crypto, is a really great book on how public key encryption came about and how the US government tried to stop it.

In PKI, the encryption key and the decryption key are not the same (hence why it is called asymmetrical crypto). The encryption key is called the public key and, as the name suggests, it’s not secret. It can be shared with the public in plain view without degrading the integrity of the encrypted message. The decryption key is called the private key and it is a secret. It must be held in confidence by the person who will need to decrypt the incoming messages. This means that if you want to send me an encrypted message, you simply go get my public key which I can just send you via unsecured means in plain view of everyone, and use it to encrypt the message.

Here’s the critical points of PKI:

  • The public key can be shared with everyone. It is usually uploaded to a public key server and PKI programs used to encrypt messages know this and can find public keys when necessary.
  • When used in web server discussions, the term key is usually replaced with certificate.
  • The private key is the only key that can decrypt a message encrypted with the associated public key
  • Keypairs (meaning the set of public and private keys) usually expire. Once a keypair expires, it is no longer considered valid and usually cannot be used.
    How do web servers use PKI?

As I mentioned above, websites are secured using SSL. SSL is an encrypted socket (meaning an IP address/Port pair, for those of you who care) and it is encrypted with symmetrical encryption. But knowing what we now know about symmetrical crypto, this is not a workable solution because you’d have to have some way to get your hands on the symmetrical key prior to visiting the website. What really happens is that PKI is used to encrypt a symmetrical keypair which is then used for that session. At a very high level, an SSL session is set up like this:
Your web browser connects to the secure web server
The web server sends its public key and a random number to your web browser
Your web browser generates a key with that random secret and encrypts it with the web servers public key and sends it back. Now you’re set up to engage in a secure web session using that (usually smaller) symmetrical key.

This process has been in use for years and works very well. Since PKI is used initially, there is no need for you to have any of the web server’s crypto before your first connection to the site and it is used to generate a nice safe symmetrical key to protect your data. So what’s the problem? Private key expiry is the problem.

Since we now know that many countries are now collecting Internet data and storing it, we can infer that they have a lot of encrypted data stored away that they cannot read. These countries have two choices: either try to break the crypto or get their hands on the decryption key.

What’s “breaking crypto” mean?

“Breaking” crypto means, essentially, to guess the key. When dealing with computers we’re necessarily talking about binary so the number of possible keys (called the keyspace) for any given key length is roughly 2^key length (leaving some bits for headers and control data). Therefore, a 2048-bit keyspace has a number of possible keys so large that I can’t find a calculator to give me a result for 2^2048 other than “infinity”. Backing it down a lot by way of example, an easily broken 64-bit keyspace has a mere 10,000,000,000,000,000,000 possible combinations (that’s 19 zeroes). Therefore, “guessing” a key in this arena means powerful computers that are able to try thousands of keys per second. There are some algorithms around that seek to limit the number of guesses required but again “limiting” in this scope means years rather than decades. At this point, there is no practical scenario where breaking a 2048-bit key is useful for anyone on the planet. It would take years, perhaps decades, so whatever data you were trying to get at is likely not useful anymore. Having said that, anyone can get lucky and stumble across the key first try. Also, in time even large keys like will be breakable. There was a time when 56 and 64-bit keyspaces were considered unbreakable but now those small keys are trivial to break because of the increase in computing power available today.

There’s a popular idea floating around that organizations like the NSA can just break the crypto on any message and forcibly decrypt anything they want. This myth stems from the fact that Hollywood knows nothing about crypto and also has exactly zero interest in providing anything even remotely factual if it gets in the way of a plot. The scenes where the hacker-guy or hacker-gurl sits down and ‘cracks the encryption’ in a few minutes is completely, utterly ludicrous. Let’s put this in perspective: a key’s strength (meaning its resistance to being cracked) is based on the length which refers to how many bits the key is comprised of. A 1024-bit key is very common and in many cases web servers are now using 2048-bit keys.

A computer powerful enough to crack a single 1024-bit key would cost $1,000,000 to build and take one full year to crack the key. link

So what does this mean? It means crypto is really, really effective and even the three letter agencies world-wide have virtually no chance of cracking even a single email message in any reasonable time frame. When you take into account that they are collecting literally millions of encrypted messages every day, it’s obvious that they would never be able to catch up. So what’s the solution? Bypass the whole cracking problem by just getting the private key.

Recall that keys expire. When they expire, web server companies generate new ones and discard the old ones. Once a key is expired, there has never really been a lot of concern about what happens to it because it has been used only for transient sessions. All of the traffic that key encrypted is old, it’s gone, that session is over, there’s nothing lying around to decrypt. However, in the new PRISM world, that’s no longer the case. The NSA almost certainly has stockpiles of encrypted data that they’ve collected off the Internet so if it were able to lay its hands on those expired private keys that were used to encrypt that data….well, bingo. That’s a hell of a lot easier than trying to crack millions and millions of keys. It’s not totally clear yet whether the named companies in the PRISM documents are, in fact, handing over expired keys to the NSA, but the possibility certainly exists. Congress in the US has passed a number of laws in the past that unprotect previously protected information after a set period of time. For example, after 6 months, email is not longer considered private therefore the hoops law enforcement agencies have to go through to get old email are significantly less than newer email. I’m not sure how expired SSL keys fit into this framework, but…well….? The NSA may have to wait a year or so for the key to expire, but eventually they may be able to warrant or just talk the big web providers into giving them the expired keys.

So what do we do?

The fundamental weak point in all Internet encryption is that it happens on the Internet. This means that the provider you are using (Gmail, Facebook, Hotmail, etc) has the private key that can be used to decrypt your traffic. You are putting all of your trust in those providers to not allow their private key to be compromised, subpoenaed or other otherwise fall into the wrong hands. The only true way to know for sure that your data cannot be decrypted is to encrypt it yourself before it enters the Internet. This process has the fledgling acronym PIE (Pre-Internet Encryption). PIE is just one practical application of the well established TNO (Trust No-One) approach to security we all learned thanks to Agent Maulder.

There’s not much you can do about your website usage since it’s not possible to encrypt your own traffic and send it to a web server. That part remains vulnerable to examination if the expired private key can be had. However, for email, chat, and cloud storage there are viable solutions out there that provide end-to-end encryption meaning that nobody between the sender and the recipient has the decryption key.

For some starting points and alternative programs that use PIE:

Email: Check out Thunderbird with the Enigmail add-on
Chat: Check out Threema
Dropbox: Check out BitTorrent Sync