Cipher block modes

The block mode of a block cipher determines if and how blocks interact with one another when encrypted/decrypted in sequence. By default, Java Ciphers (at least in Sun's implementations) are constructed in what is called Electronic Codebook (ECB) mode. ECB is basically a fancy way of saying "each block is encrypted separately of other blocks". Although it's the default, ECB is usually not the appropriate block mode unless you're going to hand-code some other processing to remove the information leak we discussed on the previous page.

Remember that we said the essential idea is that we never encrypt the same block twice, even though logically speaking, that's what we want to do if two given blocks of the plaintext we're encoding contain identical bytes. Different block modes get round this in different ways.

Cipher block chaining (CBC)

This is a widely-used block mode. Before encrypting a block, we XOR the data with the encrypted bytes of the previous block. (In a moment, we'll come back to the issue of what happens with the first block, where there's no previous encrypted block.) Notice that in this mode, every block depends on the previous block, so we cannot parallelise the encryption. At present, few people implement multithreaded encryption, but in the future, it is likely to become a more common requirement.

"Stream cipher" modes

Some other common block modes effectively work turning the block cipher into a stream cipher¹. A stream cipher works by generating a sequence of random bytes, and then XORing the message with that random sequence. At first, it sounds surprising that this is secure. But it is completely secure provided that the sequence is "truly" random. (Of course, the output from a block cipher is not "truly" random. But a secure cipher is designed so that its output compared to input appears so random that we can't tell the difference.) So instead of using our block cipher to directly encrypt the data, we actually use it as a random number generator, then simply XOR the plaintext with this random sequence.

The security of stream cipher modes is highly dependent on not ever re-using the same random sequence.

We will call the sequence of random bytes the key stream.

Output feedback mode (OFB)

In this mode, the key stream is created by continually running the last block of key stream through the block cipher. So we start with some initial block (again, we'll come back to that). Then, we encrypt that block to get the first block of key stream. The the first block of plaintext is then XORed with this block of key stream. Then we run the key stream through the encryption routine again to get the next block of key stream, and the whole cycle repeats. In rough Java code, it would look something like this (we'll see that Java actually allows us to specifcy the block mode "properly": this is just to help understand what's going on):

private byte[] encrypt(byte[] data, byte[] key) {
  byte[] tempBlock = new byte[16];
  initialise(tempBlock);

  ByteArrayOutputStream bout = new ByteArrayOutputStream();
  int noBlocks = data.length / 16;
  for (int i = 0; i < noBlocks; i++) {
    byte[] dataSection = section(data, i * 16, i * 16 + 16);
    byte[] buf = xor(tempBlock, dataSection);
    bout.write(buf);
    tempBlock = encryptAES(tempBlock, key);
  }
  return bout.toByteArray();
}

Note that at some point, after encrypting a huge enough amount of data, the output of the encryption will by chance be identical to a previous block of key stream. At that point, we'll hit a "cycle", and the encryption will be insecure for the remainder of the stream. In practice, the amount of data we must encrypt for this to happen is huge by today's standards. With a 128-bit key, then after encrypting 2⁶⁴ blocks, there's a roughly 50% chance that we'll have hit a cycle; after 2⁶³ blocks, a 12.5% chance; after 2⁶² blocks, a 3.1% chance etc (for each power of 2 less, divide the probability by four). With current amounts of data, this is a viable risk in most cases. For example, after encrypting about 17 billion gigabytes (2⁶⁰ blocks), there'll be a roughly 0.2% chance of a cycle.

Counter mode (CTR)

In counter mode, we create the key stream by encrypting a series of incrementing numbers. In common implementations, we pick some starting value, which could be totally random, or could be the number that we got up to after the last set of data we encrypted with this key. Then, we encrypt n + 1 and use the resulting encrypted block as the key stream for XORing the first block of plaintext. The next block of plaintext is then XORed with the encryption of n + 2, etc. Again, it may sound surprising that this is secure, but remember that our block cipher produces an essentially random output: even though the two blocks that we are encrypting differ in a trivial way, the encrypted blocks will be totally, unpredictably different to somebody without the key. (If they're not, our encryption algorithm is not secure.)

Counter mode encryption has the distinct advantage that we can encrypt and decrypt multiple blocks in parallel: since the ith key stream block will be the encryption of n + i, we can calculate the key stream of any future block at any time.

For counter mode to be secure, it is crucially important that we never re-use the same counter value with the same key.

Next: the Initialisation Vector (IV)

We mentioned that these various block modes, we have the the issue of the initial state when there was no previously encrypted block (i.e. when it's the first block we're encrypting in a given conversation). On the next page, we look at how this is resolved with something called the Initialisation Vector or IV.

1. The term synchronous stream cipher is sometimes used for what I simply term "stream ciphers" here. Arguably, any block mode that creates a dependency between blocks, including CBC, is a stream cipher.

comments powered by Disqus