things.dave.io

This bird is part of the Dawn Chorus in Singapore. I'll leave it up to
you to work out why I call it the Orgasm Bird.

Jelly beans for dessert am BEST.

Everyone knows that when you're encrypting stuff, key length is important. When you choose a key length, and assume no mathematical attacks, you're essentially betting on Moore's Law being upheld and it taking unreasonably long to brute-force the key for your ciphertext.

Fewer people know that the algorithm you use is also very important. Aside from crack speed - my MacBook Pro, running John the Ripper, can test two million single-DES characters a second but only five hundred OpenBSD Blowfish characters a second - you have to beware of using algorithms with mathematical attacks against them which can make brute-force attacks unnecessary.

The real kicker, however, is modes of operation.

Universal Language

Encryption works with numbers. Really big numbers, but fundamentally just numbers. Any data can be expressed as a really big number. If I want to represent the text

LOLDONGS

I can convert this into ASCII (Unicode works fine too, but just ends up with even bigger numbers). This results in

76 79 76 68 79 78 71 83

Computers like binary, and binary reacts well to being concatenated together, so let's convert that to binary and remove the spaces, as we know each character is one byte.

0100110001001111010011000100010001001111010011100100011101010011

This is a number. We like to think in base-10, though, so just to prove a point let's change it back briefly.

5,498,697,526,314,682,195

Big number, right? Trouble is, as plaintext goes, "LOLDONGS" is actually really small. When we start playing with even just a few kilobytes of data to encrypt, this number gets very big very quickly, and doing maths with numbers that big is hard. So, what we do is we break up the message into blocks. Here, let's use the character boundary (one byte) as a block.

01001100 | 01001111 | 01001100 | 01000100 | 01001111 | 01001110 | 01000111 | 01010011

Much easier. Each block can represent a number no bigger than 256 in base-10 (11111111 in binary), which is a lot more manageable. Now it's time to actually encrypt the data.

The Bitgrinder

Since we've decided that we're going to work on 8-bit blocks, for the sake of example, let's choose an 8-bit key. There are all kinds of key derivation algorithms and caveats for keys, but in this case let's keep it simple. Our key is

01010101

And that's the way it is.  We're also going to use a very basic algorithm called XOR, which is a bitwise operation meaning 'exclusive OR'. In binary:

1 XOR 1 = 0
1 XOR 0 = 1
0 XOR 1 = 1
0 XOR 0 = 0

Pretty simple. The result is 1 if the input bits differ and 0 otherwise. But we're not just using XOR for shits and giggles; it's got a really cool feature that makes it perfect as a basis for cryptography: it's reversible.

In the following, x is the plaintext, y is the key and z is the ciphertext:

x XOR y = z

z XOR y = x

How cool is that? Let's look at a real-world example:

10100011 XOR 00101010 = 10001001
10001001 XOR 00101010 = 10100011

We now have the very base case for most symmetric (pre-shared key) encryption, so for simplicity's sake we're going to use just plain vanilla XOR as our algorithm. Don't do this in the real world. Ever.

Now we have to choose how we're going to apply this algorithm. The simplest way is something called ECB ("Electronic Code Book"), but it's discouraged for reasons you're about to discover.  Let's apply ECB with 8-bit blocks, again to make it easy for ourselves.

 Plaintext | 01001100 | 01001111 | 01001100 | 01000100 | 01001111 | 01001110 | 01000111 | 01010011
       Key | 01010101 | 01010101 | 01010101 | 01010101 | 01010101 | 01010101 | 01010101 | 01010101
--------------------------------------------------------------------------------------------------
Ciphertext | 00011001 | 00011010 | 00011001 | 00010001 | 00011010 | 00011011 | 00010010 | 00000110


Brilliant! We can put the ciphertext back together and share it, safe in the knowledge that without the correct key nobody can figure out what it means, right?

Wrong.

Notice that the first and third block, when encrypted, are the same. So are the second and fifth. That's because we operated on each block completely independently, so the same input resulted in the same output. This makes us vulnerable to something called frequency analysis, where we look for repetitions and make educated guesses about the original data. Now, I could go into details about how this works, but the reason I wrote this post in the first place is that I found an even better way to demonstrate why ECB is a bad idea.

The Part With A Penguin

Here is Tux.

Tux is just your everyday penguin. He's sitting down, chilling out, maybe thinking about fish. Now, as we've shown, any data is just a number, and so's this image. If we represent the image as a series of pixels, each pixel having a numerical value describing its colour, we have nice easy blocks to align ECB to.  Let's take each block (pixel), apply our cryptography in ECB mode and see what the image looks like on the other end.

Well now. The image looks very different - strictly speaking, what we have here is a completely different image. Trouble is, humans are exceptionally good at pattern recognition when it comes to images. We recognise similarly coloured areas as shapes - we need to do this to understand and react to our environment.

Because of this, we see Tux anyway, if he does look a bit trippy.  ECB has transformed the image into something completely different numerically, but statistically there's still a pattern that we can use to work out enough about the original image to effectively break the cryptography.

It doesn't always work that way, but the important part is that ECB leaves enough information intact in the seemingly encrypted data to run serious risks of side-channel attacks.

Now You See Him, Now You Don't

So what do we do to get around ECB? Fortunately, cleverer people than I are out there. There are many ways to improve things, but they all started with a mode called CBC - Cipher Block Chaining.

Because we can assume that the person decrypting the message has the key, we can assume that any mathematical operation performed using the ciphertext and the key will always end up with the same result whoever performs it, as long as that operation is known to all parties. So what we do is instead of using discrete blocks, we involve the result from the previous block in the block currently being encrypted.

Here's Tux after a round of CBC.

Brilliant. We have no guarantees that this is completely secure, but the obvious frequency analysis sidechannel has been blocked.

And that's why we don't use ECB.

Johnny Mnemonic

What should you take away from this? A few things.

• Cryptography is hard.
• No, seriously. It's harder than you think.
• If you're using crypto, you are much better off leaving the bit-banging to cleverer people.
• Calling OpenSSL, GnuTLS and/or GnuPG at high levels is almost always a good idea.
• AES is good. If you don't trust the NSA, use Blowfish - Bruce Schneier is cleverer than you.
• If you're implementing your own crypto, you are almost certainly doing it wrong.
• Never use ECB without a form of strengthening unless you have an exceptionally good reason and balls of steel.
• Tux wants fish.

I leave you with a mnemonic.

OPACUE
Only Paedophiles And Communists Use ECB

And you're not a filthy commu-nonce, are you?

Super.

Things have changed a bit now, eh?

From Airplane 2.