Debunking ridiculous myths about cryptography

13^th April 2015

I find it bizarre that most people seem to think that encryption is inherently breakable by anyone clever-enough, and are also perfectly happy using things that rely on encryption for security like debit/credit cards and online shopping. Ehem if encryption was so easily breakable then your bank would be emptied every week by people easily stealing your debit card details.

The most common use of cryptography is in civilian applications. It protects the link between our bank's computers and our debit card in the card reader. It protects the link between our laptop and an online shopping website. It protects our mobile phone calls from eavesdropping. Therefore I think it's important that ordinary people have a basic understanding of these things.

Governments like to use cryptography for nasty things like spying, war-fare and hiding information they are ashamed of from taxpayers.

Anyways I'm digressing.

Cryptography breaking is mostly an opportunistic art. To break a cryptosystem you need to exploit a weakness in the cryptosystem or mistake made by the person who implements it. Cryptosystems are usually broken either because they are ill-designed or by user-error.

I will now try to explain three types of strong cryptography and how they might fail.

One-time pad cryptography

One time pad cryptography is the simplest type of cryptography and is impossible to break when used correctly. I use the word "impossible" literally, it actually is impossible to break, when used correctly.

How it works

OK so here is an example of one-time pad encryption:

1. Alice generates a "one time pad". This is a piece of paper with 300 random numbers on it between 0 and 25. These numbers will be between 0 and 25 because she will be using the English alphabet which has 26 letters. She keeps this pad safe.
2. Alice gives Bob an identical copy of the pad. He keeps this safe.
3. Bob travels to some distant place, taking the pad with him.
4. Bob now wants to send an encrypted message to Alice. For each letter, he counts forward in the alphabet by the corresponding number on the pad. So if the letter is "B" and the number is 12 he counts CDEFGHIJKLMN in his head and writes "N" instead of B. Then maybe the next letter is "U" and the next number is 10 so he counts VWXYZABCDE and writes "E". Notice he ran out of letters and went back to the beginning. Annoyingly, he can't write any punctuation characters or even spaces because the numbers only go high-enough to accommodate the 26 letters of the alphabet. If more characters such as space and punctuation were to be included then Alice and Bob need to have established an order for them to go in. Anyways, when he gets to the end of his message he uses up the rest of the numbers on the pad by just encrypting some arbitrary string such as "END" over and over. He then destroys the one-time pad.
5. Bob sends the message using some insecure method such as letter or email.
6. Someone called Eve intercepts the message and tries to read it but can't.
7. When Alice gets the message she de-crypts it by referring to her copy of the pad and counting backwards in the alphabet instead of forwards. She then destroys her pad.

OK. So why is this encryption impossible to break when used correctly? Surely if someone could guess the pad they could de-crypt the message?

OK so imagine you are Eve, trying to read the message. You're guessing trillions of different pads, and they all produce gibberish, then finally you find a pad that produces a grammatically and orthographically correct message in the English language. That means you've found the correct pad right?

Actually it means nothing because there are trillions of pads that would produce a grammatically and orthographically correct message in the English language no more than 300 letters long.

The reason one-time-pad cryptography is unbreakable is because one has no way of knowing when one has guessed the right pad, therefore one gains no information even if one does guess the right pad.

The only piece of information Eve can possibly find out about the message is that it's no more than 300 letters long.

How it can fail

1. If Bob uses same pad twice, the encryption instantly becomes possible to break. This is because Eve can now work out when she has guessed the correct pad. This is because there will only be a very small number (probably 1) of pads which decrypt both encrypted messages into grammatically and orthographically correct messages. Furthermore, Eve does not need to try every possible pad because she can find clues as to what the correct pad might be before she starts. Of course Eve knows that any letters that are the same and in the same positions in both texts must be the same letter. This is usefull because for example if she knows that "E" is the most common letter in the English language she can guess therefore that any matching letters in the two encrypted texts are more likely to be "E" than any other letters, and "E" is more likely to be adjacent to consonants than to other vowels etc etc.
2. Another way it could fail would be if Bob added characters that are not allowed, such as putting spaces and full-stops. This would tell Eve where the words start and end which would again not only allow eve to know when she has guessed the correct pad but give her clues as to what the pad might be in the first place.
3. Another way it could fail would be if Bob or Alice failed to keep their pad safe or failed to destroy it properly after it was used.

However note that all of these failure mechanisms are user error. If used correctly, one-time pad cryptography is impossible to break. So breaking one-time pad cryptography is entirely opportunistic and depends not so much on the competence of the eavesdropper but the competence of Alice and Bob.

P.S. Of course one-time pad cryptography does not have to use letters, it can be done in binary or anything. I explained it using an alphabet to make it easy to explain.

Cipher cryptography

Of course the problem with one-time pad cryptography is that it is inconvenient to use. Alice and Bob must:

1. Meet in person to share pads.
2. Carry numerous-enough and large-enough pads to encrypt every message they want to send one-another.

Cipher cryptography solves the second problem. Instead of a "pad", one uses a "key". The key and a piece of random data called an initialisation vector (IV) modulate the behaviour of an algorithm called a "cipher". The cipher is used to encrypt the message.

This allows a single key to encrypt multiple messages. It also allows encrypting messages that are larger than the key.

The cipher algorithm is normally implemented using a machine or a computer program.

Cipher cryptography is inherently possible to break as long as the eavesdropper (let's call her Eve again) has enough/long-enough messages. This is because it is possible for her to know when she has guessed the right key. This is because only one key will create valid output messages. If the encrypted data is, as in the above example, text, valid can be defined as a "grammatically and orthographically correct".

So, if cipher cryptography is inherently possible to break, why would anybody use it? Because possible and feasible are not the same thing. If the key is long-enough, it may not be feasible to try all, or even a fraction of, the combinations. I believe the most commonly used cipher today is AES-256, which uses a 256-bit long key. This means there are 2^256 combinations which is 115792089237316195423570985008687907853269984665640564039457584007913129639936. I would guess that the maximum number of keys a super-computer can try within a lifetime would be a lot less than 2^100.

So, is AES-256 feasible to break? Only if one can find some clues as to what they key might be without having to try every one. The cipher's job is to make sure that this is not the case. If the cipher is good-enough, and the IVs are truly random, the encryption will be in-feasible to break with modern technology. Unfortunately, modern ciphers are so complex that cryptographers are not able to provide mathematical proof of how good ciphers are. But they can make judgements.

How it can fail

1. Using a weak key is a common problem. For example it's common to use a password or "pass-phrase" as an encryption key. The password goes through a "password key derivation function" to try to make it "stronger" and then goes into the cipher. If the password is, for example, a dictionary word with "o" substituted with "0" and "l" substituted with "1" then it won't be hard to guess. It's easy to write a program that generates billions such passwords and tries them all very fast.
2. Not using initialisation vectors, or re-using initialisation vectors. This is partly how the German "Enigma" encryption cipher was broken in WW2. The operators of the enigma machines were supposed to manually enter initialisation vectors before they sent each message. Unfortunately some of them couldn't be bothered and sent multiple messages using the same IVs. This allowed the British supercomputers to find patterns in the cipher-text and find out the keys.
3. Finally Alice and Bob could be using a weak cipher which can be analysed to gain clues as to what the key might be. Or a cipher that uses too short a key.

Of course failure modes 1 and 2 are user error. In practice failure mode 3 is usually user error also, for using a weak cipher. For example look at the history of the "DES" cipher. Computers became powerful-enough to break DES in the 90s, but cryptographers had been warning it was weak since the 70s, so people still using it in the 90s would have been at fault.

The only way failure mode 3 could not be user error would be if Eve was somehow more insightful than the entire cryptographic community put together and single-handedly found a way to break a cipher that everyone thinks is secure.

Public-key cryptography

Remember I said that the problems with one-time pad cryptography were that Alice and Bob must:

1. Meet in person to share pads.
2. Carry numerous-enough and large-enough pads to encrypt every message they want to send one-another.

So ciphers solve problem 2. But is it possible to also solve 1? Well, in fact it is, and the solution is Public-key cryptography.

Unfortunately public-key cryptography is ridiculously complicated and I can't be bothered to explain how it works so I will simply write some of it's characteristics.

• It is very complicated. This means there are a lot of opportunities for things to go wrong and therefore it is not as strong as simpler types of cryptography.
• It is the cutting edge of modern cryptography.
• It is the most common type of cryptography ordinary people deal with. For example when you see the padlock in your web-browser's address bar it means that the connection is protected with public-key cryptography.

Now since Public-key cryptography is so complicated and there are more things that can go wrong the competence of the eavesdropper does now start to have a bit more relevance relative to the competence of Bob and Alice. Nevertheless, the most common reason public key cryptography fails is still "user error" by Bob and Alice, rather than genius on the part of Eve.

Let's take website encryption as an example. Websites use PKI, which is a super-set of Public-key cryptography. Let's imagine Alice is a sys-admin at a bank's web-server, and Bob is a customer logging into the bank's website using his web-browser.

How it can fail

1. Bob uses an ancient web-browser that does not use up-to date technology. Public-key cryptography is a the cutting edge of modern cryptography and therefore it is crucial to use up-to-date implementations.
2. Someone finds out the server's private key. Alice must keep backups of the server. However the goals of keeping plenty of backups in lots of different places and keeping these backups away from Eve are somewhat conflicting goals.
3. A certificate issuer is corrupt. PKI relies on certificate authorities (CAs) to issue certificates to websites to verify their identity. Web browsers only recognise the website as genuine (and show the padlock) if it has a certificate which is cryptographically linked to the root certificate of a CA that is in the web-browser's built in list of trusted CAs. It was recently all over the news that CNNIC (a big Chinese CA) was making fake certificates for the Chinese government, allowing them to impersonate foreign websites. This means someone could correctly type the address of a website such as mail.google.com, get shown a fake version of the site by a man-in-the-middle attack by the Chinese government, and still see a padlock.
4. The Certificate Authority is incompetent. Actually many of them probably are. If one does not pay an un-affordable cost for an Extended Validation certificate then they usually do very little to verify your identity before issuing you a certificate. Furthermore they sometimes issue certificates that use old technology in order to support old web browsers, which is pretty annoying.
5. A piece of software that implements the encryption has a bug. Of course PKI is, in practice, always implemented with software and there is always the possibility of bugs. Many people use proprietary software with all the code kept secret so the cryptographic community cannot even review it, so there is no assurance of it's quality.
6. A piece of software that implements the encryption has a deliberate security backdoor. According to the snowden leaks the US government forces American software companies such as Microsoft and Apple to put security "back-doors" onto their systems so they can bypass the encryption. http://www.theregister.co.uk/2013/07/11/snowden_leak_shows_microsoft_added_outlookencryption_backdoor_for_feds/
7. An attacker finds a weakness in one of PKI's many cryptosystems. There are many parts to PKI so this may actually be feasible is Eve is a genius. The recently discovered POODLE vulnerability is an example of such.

So as you can see there are a lot of possible ways that a complex system such as PKI can fail. Nevertheless most of these things are still user error. For example let's look at the example of Microsoft deliberately putting security backdoors in outlook.com for the US government. Here Alice is Microsoft and Bob is the person using outlook.com. Alice deliberately sabotages the cryptosystem she's using just because the US Government told her to... so she's misusing the encryption. Even POODLE could be user error if the server admin is slow to update the server config to mitigate it. It's her responsibility to know about security problems and fix them promptly.

I really think that if Alice and Bob are competent and vigilant then they should be OK.

Conclusions

The point of this post is that, if Alice and Bob are competent, choose their encryption carefully and implement it correctly then it is likely to be secure. Especially if they use one of the simpler encryption systems such as one-time pad or cipher.

Of course the James Bond movie "Skyfall" is ridiculous. How could MI6 encryption be broken by just some guy who isn't even a mathematician or a cryptographer? Erm ridiculous. In fact most movies now days seems to feature encryption getting easily broken by some random kid. Haha I don't think so.

If Government encryption is broken by some random guy that means the Gov is incompetent and should be VERY ashamed.

Notes on the author

Why am I qualified to talk about encrypton? Am I a cryptogropher? No I'm not, not at all. I know enough to implement cryptosystems correctly (I hope) but not to make or analyse them. However most people seem to know absolutely nothing whatsoever about cryptography and I hope that this post might provide some enlightenment.

The coolest cryptography thing I ever did was set up the data-at-rest protection system for Taskenizer, with the help of someone more intelligent than myself. It uses a cipher, a password key derivation function, passphrases, salts, keys, initialisation vectors etc.