Rosio Pavoris a blog

The point of these posts on cryptography is mainly to demonstrate that while cryptography may seem like a very arcane field that’s next to impossible for the layperson to get into, it’s actually reasonably straightforward. Still, there are some pitfalls one should watch out for.
A famous one of these involves block ciphers.

Suppose you want to encrypt your data, and you pick a block cipher to do it. Let’s say you pick AES, reasoning that since NIST thinks it’s good enough to encrypt top secret documents, it must be pretty good.
AES has a block size of 128 bits, but the data you want to encrypt is much larger than that. So what happens? You divide the data into 128-bit blocks and encrypt each one separately, right?

Well, yes. This is the way things were done for a long time.¹
The problem, though, is that identical 128-bit segments of plaintext also encrypt to identical segments of ciphertext. For certain datasets this isn’t a huge problem, but for many, it means that a lot of patterns in the plaintext are in fact preserved in the ciphertext, no matter how awesome your cipher is.
By way of illustration, take a look at this illustration I shamelessly stole from Wikipedia:

The picture on the left is our plaintext. The picture on the right is that data encrypted by dividing it into blocks and just using some block cipher on each of those blocks separately.
While the data can’t be extracted completely anymore, it’s still quite obviously Communist propaganda, and no less incriminating than the original.

We’d much rather have something like this:

Which is, on the face of it, purely random noise.
So how do we achieve this?

One way would be to just use a block cipher with a larger block size, but that’s not always possible. Sometimes patterns happen at a much larger scale than in our example. Sometimes you don’t even know what possible patterns may exist in your dataset.
If you had a block cipher with a multi-gigabyte block size, you’d probably be in the clear, but then you’d lose an important advantage of block ciphers: if you just wanted to read a small bit of data, you’d have to decrypt the entire thing, which is a waste of both your time and the CPU’s.²

Output Feedback

Another (more sane) way to do it, of course, would be to just always use stream ciphers, as they don’t suffer from these issues. You can even turn your block cipher into a stream cipher, if you’re so fond of AES:

You start with an initialisation vector. This is just a string of bits the size of your cipher’s block size. It can be anything, but it’s best if it’s random. You’ll want to keep this secret, too, so it kind of acts like a second key.³
You encrypt this vector, and XOR the result with the first block of your plaintext. Then you reencrypt the encrypted vector (not the XORed result, just the encrypted vector), and XOR that with the second block, and so on.

This is known as the output feedback mode, or OFB. It’s essentially a very inefficient stream cipher.

There are three advantages to it. The first is that you can generate the keystream in advance, which is nice if you want to decrypt your data on a computer that’s really too slow to deal with the encryption algorithm on its own, but which can deal with just XORing. In practice, though, this will probably never happen, and it’s a security nightmare in itself.
Another advantage is that the block cipher only ever runs in the encrypting direction, not the decrypting (which can be a completely different-looking algorithm), which means that if you have crypto hardware to go through the motions of the algorithm for you (DES was specifically designed for hardware implementations, for example), it only needs to be half as complex.
The third is that if you transmit your ciphertext over a lossy channel and one of the bits gets flipped by mistake, it only results in a flipped bit in the decrypted plaintext rather than trashing your entire block.

Of course, “real” stream ciphers have most of these advantages as well, and generally run a lot faster than block ciphers in OFB mode.

One problem with stream ciphers, both “real” and OFB block cipher, though, is that decryption is more of a pain. With block ciphers, you can just take a random chunk of the ciphertext and decrypt that, without also having to decrypt the possibly thousands or millions of blocks that precede or follow it. With stream ciphers, to decrypt, you must always generate the key stream from the very beginning, even if the bit you want to decrypt is just near the very end.

Cipher Block Chaining

What if we just encrypted the first block of our ciphertext, though, and XORed the second plaintext block with that first ciphertext block before encrypting it? And then XORed the third plaintext block with that before encrypting that, and so on?

Turns out this works pretty well. If you’re uncomfortable with the fact that your first ciphertext block could still be looked up in some hypothetical codebook, you can XOR your first plaintext block with an initialisation vector before encrypting it.⁴
This mode of operation is the second oldest, and is called cipher block chaining, or just CBC mode for short.

Side note: if you use Linux (or similar) and have OpenSSL installed, you can do openssl list-cipher-commands to (surprisingly) get a list of the cipher commands. You’ll notice that some of those algorithms come in several versions. For instance, AES is available in six flavors:

aes-128-cbc
aes-128-ecb
aes-192-cbc
aes-192-ecb
aes-256-cbc
aes-256-ecb

The number stands for the key size, of course. Now you know what the other part is: the mode of operation.

Now, while CBC mode does destroy the patterns in the plaintext, it does have its drawbacks, the most important of which is that encryption cannot be parallelised; to encrypt a block, you need to encrypt every block before it.
This isn’t a problem for the home user, of course, since he generally has no other options anyway, and OFB (very nearly) shares this same problem.

On the other hand, decryption can be parallelised. To recover a plaintext block, all you need to do is decrypt it and then XOR it with the ciphertext block that preceded it; no need to decrypt the entire thing that came before it. This is a significant advantage over our stream cipher idea.⁵
It also means that, like in ECB mode, you can just decrypt some data at any position in the ciphertext if you like; you don’t have to decrypt everything that came before it, or generate tons of keys first.

Counter

A third mode that’s worth mentioning is the counter mode, or CTR.
What it does is start with an initialisation vector on the one hand, and a counter on the other. This counter is just the block number, and is added to the initialisation vector, or XORed with it, or concatenated to it, or mixed with it in some other way. Then, the result of this is encrypted using the block cipher, and the result of that is XORed with the plaintext. This is done for each block (all with the same initialisation vector; only the counter changes).

CTR mode seems to be the best of both worlds: it has the strengths of OFB (that is, the block cipher is only ever used to encrypt, and a flipped bit in the ciphertext results in only one flipped bit in the plaintext) without any of the weaknesses, and like CBC, decryption can be parallelised (you just need to know the block number).
What’s more, encryption can be parallelised as well (and, in fact, happens in the exact same way as encryption).

Of course, you have to be quite confident in your cipher’s diffusion, but for modern block ciphers, that’s not really a problem.

The only problem is that sometimes, you want a flipped bit in the ciphertext to stand out more in the decrypted data, especially when your communication channels aren’t tamper-proof (and which are, really?). CBC is much better for this, though obviously neither mode is a substitute for a decent checksum.
Which just goes to show you need to understand your tools when you’re working with cryptography, even moreso than in most other fields.

&c.

There are numerous other modes of operation, some more obscure than others. CFB is a popular one that kind of looks like a cross between CBC and OFB. Whole disk encryption schemes tend to use specialised modes, though many of them are based on CBC. I’m sure you can find more information on them on your local internets.

The main thing to keep in mind, though, is that ECB is probably the wrong choice for most applications, and to actually look into what mode of operation you want to use before you use it.
This is the sort of pitfall most people don’t even consider, but it’s very, very important for the security of your data. Cryptography (and security in general) has more of these than you’d expect.

---

¹ This “standard” mode of operation is called the electronic codebook mode, or ECB, since you can pregenerate encrypted blocks and do your encryption or decryption by just looking up the blocks and the corresponding values in that codebook.
Such codebooks are of limited use when trying to crack the encryption, though, since you’d need codebooks for every possible key, and each ciphertext block would correspond to a large number of plaintext blocks anyway.

² Also, multi-gigabyte block sizes are a retarded idea and you should feel bad for even considering it.

³ Technically the pseudo-random number generator’s seed.

⁴ Not doing this is the same as having an initialisation vector that’s just a string of 0s, of course.

⁵ Also note that this means that if the ciphertext block is transmitted over a lossy channel (and in practice it always is) and a bit accidentally gets flipped in transit, only two of the blocks become indecipherable: the one with the flipped bit, and the one coming after it (and even that one will only differ in a single bit). While it’s not as robust as OFB, it’s still an advantage over some fully cascading schemes that have also been suggested, where the entire rest of the datastream would be corrupted.