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.


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.

  • $\begingroup$ thanks. can you tell me why ofb isnt parallelizable? $\endgroup$ – Hans Baum Jun 17 '17 at 15:02
  • $\begingroup$ @HansBaum: in OFB, we have repeated computations of $S_i = E_k(S_{i-1}), C_i = P_i \oplus S_i$; we cannot compute the $S_{i+1}$ value until we have completed the computation of the $S_i$ value $\endgroup$ – poncho Jun 17 '17 at 19:08
  • $\begingroup$ can you explain it in a simpler way without mathematical cover? :) $\endgroup$ – Hans Baum Jun 18 '17 at 12:02
  • $\begingroup$ @HansBaum: 'you can't encrypt (or decrypt) the next block until you've done almost all the work for the previous one' $\endgroup$ – poncho Jun 18 '17 at 12:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.