Why are ECB CBC and CFB parallelizable?

Question

I guess I do not understand the word 'parallelizable'. Why are ECB CBC and CFB parallelizable?

It would be nice if someone could explain it in a short way.

Answer 1

By parallelizable, what we mean is that the encryption/decryption process can be broken down into multiple tasks that can be run at the same time. For block cipher modes, this means that if we have multiple copies of the block cipher, we can use that to go faster.

For example, in CBC decryption mode, the decryption transform of several adjacent blocks is defined as:

$$P_i = C_{i-1} \oplus D_k( C_i )$$ $$P_{i+1} = C_{i} \oplus D_k( C_{i+1} )$$ $$P_{i+2} = C_{i+1} \oplus D_k( C_{i+2} )$$

($C_i$ is the $i$th ciphertext block, $P_i$ is the $i$th plaintext block, and $D_k$ is the block cipher run in decryption mode)

Now, we assume that we see the entire ciphertext, including $C_{i-1}$ through $C_{i+2}$ at the same time. So, if we have three hardware implementations of $D_k$, then we can feed each one with $C_i, C_{i+1}, C_{i+2}$, have them perform the decryption, then do the xor's, and thus produce $P_i, P_{i+1}, P_{i+2}$ all at the same time.

So, by having three hardware implementations, we can decrypt three times as fast.

On the other hand, let us consider CBC mode encryption. Here, the standard definition for this is:

$$C_i = E_k( C_{i-1} \oplus P_i )$$

$$C_{i+1} = E_k( C_i \oplus P_{i+1} )$$

$$C_{i+2} = E_k( C_{i+1} \oplus P_{i+2} )$$

Here, we run into a problem when we try to run it in parallel. To generate $C_{i+1}$, we need to have the value $C_i$ before we can start encrypting. Hence, to generate the next encrypted block, we have to compute the previous one first. Hence, if we have three encryption engines, we can't take advantage of them; we end up only using one at a time.