Modes of Operation in Block Cryptography

Sorry for the slow pace of the blog lately. I've been sick with a horrible
sinus infection for the last month, and I've also been particularly busy with work, which have left me with neither the time nor the energy to do the research necessary to put together a decent blog post. After seeing an ENT a couple of days ago, I'm on a batch of new antibiotics plus some steroids, and together, those should knock the infection out.

With that out of the way: we're going to look at how to get from simple block ciphers to stream ciphers, using the oh-so-imaginatively named modes of operation!

As a quick refresher, block encryption specifies an encryption scheme that operates on fixed-size blocks of bits. In the case of DES, that's 64 bits. In the
real world, that's not terribly useful on its own. What we want is something called
a stream cipher: a cipher that's usable for messages with arbitrary lengths. The way to get from a block cipher to a stream cipher is by defining
some mechanism for taking an arbitrary-sized message, and describing how to break it into blocks, and how to connect those blocks together.

Modes of operation are formal descriptions of the way that you
use block encryption on a message that's larger than a single block. Modes of operation (MOOs) are critical in making effective use of a block cipher. Of course, there's always a tradeoff in things like this: you have to choose what properties of your encrypted communication you want to protect. Particularly for DES encryption, the standard MOOs can provide confidentiality (making sure that no one can read your encrypted communication), or integrity (making sure that your communication isn't altered during transmission), but not both.

To give you a quick and foolishly simple example of that tradeoff, we can consider a real-life example of a simple mode of operation, called the electronic codebook (ECB). In the ECB MoM, you encrypt each block separately, and then just concatenate the results together. Everyone who does crypto knows that ECB is incredibly stupid; no one seriously uses it. The only case I recall hearing of anyone actually using ECB was a multiplayer online role-playing game,
where they encrypted the traffic between players and the game server using ECB.
So every time the player did something, it sent a message to the server, and the server sent back a message telling it how to respond.

For performance reasons, games like this tend to do a lot of stuff on the
player's computer. So, for example, when a player gets into a fight with a monster,
the fight was mostly handled on the players computer, and when it was over, it sent
a message to the server, either saying "player died", or "player killed
monster". Since they were using ECB, a player watching network traffic
could easily notice that whenever he killed a type-A monster, his would sent a particular bag-o-bits to the server. That b-o-b was always exactly the same - so while they didn't know exactly what was in the message, they were able to
tell that the way the game told the server that the player killed a monster was
to send those bits.

This was, naturally, exploited by clever players, who wrote programs sending
thousands of copies of that b-o-b to the server, racking up credits for killing thousands of monsters. Since it was a message that was set up to be one block long, and it was using ECB, that block always encrypted to the same ciphertext block - so they knew how to tell the server that they killed another monster. They
had no idea of what was actually inside the block - no idea of what data specifically was being transmitted to say "Player A killed an Orc". But because
of the combination of ECB with the way in which the cipher was being used, they
formed a very effective exploit.

That's an example of something called a replay attack, where you try
to violate the integrity of the message. Encryption isn't only about hiding the
message plaintext from prying eyes, but about protecting a communication
channel from interference by intruders. In the case of this MMORPG, the
attackers compromised the communication channel without decrypting the
message. They had no idea exactly what the batch-o-bits that they were transmitting
said, but they had a good idea of what they meant, and they were able to
intrude on the communication channel, adding messages that the receiver assumed
were legitimate, because they matched the expected encryption. This kind of attack
is called a replay attack. For this application, the ECB did a decent job
of protecting confidentiality (no one figured out what the specific contents of the
message were, but they were able to figure out what it meant, so it didn't even do
that terribly well), but it did a lousy job with integrity (it was easy to
introduce spurious content to the communication channel without being detectable by
the sender or receiver.)

So, moving on, the way to improve the performance of the block cipher is
to use a mode of operation that doesn't just blindly concatenate things.

The Counter (CTR) MoO

(I've been alerted by a reader that I made a major mistake in my description of the CTR mode of operation. Since I don't have time to correct it while I'm at work, I'm posting this warning: the information about CTR is incorrect. I'll fix it this evening.)

The simplest MoO beyond ECB is to just add a counter to the process. So, you
XOR your plaintext block with a counter value, and then send it through the
encryption. For a sequence of blocks, you increment the counter for each block. So
a single block encoded multiple times will encode once exclusive-OR'ed with
"1", once with "2", etc. Repeated blocks won't look repeated in the ciphertext.

Below is a very simple fragment of pseudo-python that demonstrates
the basic idea of this; next to it is a data-flow diagram illustrating
the same thing. For each of the modes of operation I describe below, I'll provide similar pseudo-code and diagrams.

def EncryptWithCTR(blocks, ctr, key):
  for b in blocks:
    encrypted = encrypt(key, b ^ ctr)
    ctr = ctr + 1
    output(encrypted)

Of course, just using integers that way isn't ideal. It's hard to detect,
but it's a natural thing to try. What's better is to use a counter function. A counter function is a function F from the natural numbers
to a stream of bits the size of one block. So instead of exclusive-ORing
cleartext block #I with "I", you XOR it with F(I). If your counter function
is pseudo-random, this can be very effective. Despite the fact that this is
potentially a significant benefit, most implementations that I've seen using
CTR just use a plain counter - the only variation is that it often doesn't start the counter at 0 or 1.

Consider how the replay attack would play out with CTR (or any of the others
below). People monitoring the network would be able to detect that a single encoded block would be sent each time a player killed a monster. But they wouldn't know what the specific payload of the message was, and they wouldn't be able to guess how to encode a copy of the block in a way that would work.

One of the nice properties of CTR is that it's easy to parallelize: if you know the counter function, then you can encrypt/decrypt blocks in isolation without
needing any information from a previous block. So you can encrypt/decrypt blocks
3, 4, 5, and 6 at the same time: you know that the key for block 5 is just the
basic key XOR counter(5).

Of course, that parallelization is a curse as well as a blessing. Someone
trying to crack your system can also parallelize, and try decrypting multiple blocks at the same time. Once you've got a few blocks broken, getting the rest
becomes relatively easy, and you've got lots of different blocks, some of which may (by chance) be easy to break by brute-force methods.

Feedback Modes of Operation

Most of the common modes of operation are based on some form of feedback. You
start with an initial block of random bits called an initialization vector
(IV), and you encrypt the block XORing the IV somewhere in the process of
generating the ciphertext of the first block. Then for each successive block, you
replace the IV with some kind of output from the previous block.

Cipher-block chaining is a simple feedback-based MoO. Basically, you start
with your agreed-upon block of bits in the initialization vector (IV). For the
first block, you exclusive-OR the plaintext with the IV, and then perform the
block encryption. The output ciphertext of the first block is then used as the
IV for the second block; the IV of the third block is the output ciphertext of the second, and so on. So each block is scrambled by mixing it with the ciphertext of the previous blocks. This also avoids the problem of the game, because the same plain text message encrypts to different ciphertext each time.

def EncryptWithCBC(blocks, iv, key):
  feedback = iv
  for b in blocks:
    inblock = b ^ feedback
    encrypted = encrypt(key, inblock)
    feedback = encrypted
    output(encrypted)

The big problem with CBC is that it's weak against many kinds of brute-force
attacks. You can't parallelize encryption using CBC: you need to finish encrypting each block before you can encrypt the next; but for decrypting, you can
try to decrypt multiple blocks; and once you've broken two adjacent blocks,
you're pretty much wide-open.

A slight variation is CFB; it's just a minor reshuffle of the
order of things. In CBC, we XORed the plaintext of the message with an IV,
and then did block encryption on that to produce the ciphertext. In CFB,
to produce the ciphertext, we do the block encryption on the IV, and then XOR the result with the plaintext. The ciphertext of block N is then exclusive-or'ed
with the previous IV to create the IV for block 5.

def EncryptWithCFB(blocks, iv, key):
  feedback = iv
  for b in blocks:
    encrypted = encrypt(key, feedback)
    out = encrypted ^ b
    feedback = out
    output(out)

CFB has pretty much the same vulnerabilities as CBC.

Output feedback (OFB) is yet another variation on the same theme. The only difference is that the input to block N+1 is the output of the block cipher
from step N, before it's exclusive-OR'ed with the plaintext for step N.
The interesting thing about OFB is that the plaintext doesn't affect the output of the block cipher itself: the block cipher encrypts the combination of the key and
some feedback from the previous block - the plaintext gets exclusive-OR'ed afterwards.

def EncryptWithCFB(blocks, iv, key):
  feedback = iv
  for b in blocks:
    encrypted = encrypt(key, feedback)
    feedback = encrypted
    out = encrypted ^ b
    output(out)

These are all modes that focus on confidentiality rather than integrity. Integrity protection is more recent innovation, and it's more complicated. In
later posts, I'm going to talk a bit about the cryptanalysis and attacks that are used against block ciphers, and how they interact with different modes of operation. From there, we'll be able to see why these modes don't protect integrity, and show how we can build modes that focus on integrity.