Parallelization of CFB mode encryption and decryption

Question

While reading Evaluation of Some Blockcipher Modes of Operation by Rogaway (someone just linked it somewhere), I noticed two claims about CFB that I'm not sure I understand:

1. Regarding whether CFB mode encryption is parallelizable the paper says (on page 31):

   Yes, but awkward. See ISO 10116 for less awkward generalization.

2. Regarding whether the decryption is parallelizable it says (same page):

   Yes, but awkward.

---

1. I can't see how this is true at all. To encrypt a block with CFB mode you need the ciphertext of the previous block (or more if $s < n$), so how can you parallelize it?

2. Parallelizing the decryption algorithm, OTOH, seems very simple, especially when $s = n$ (which I suppose is the "common" case?). I'm unsure what is supposed to be awkward about it, unless it's the fact that with $s < n$ you need to look back more than one $s$-bit block of ciphertext? But since you are still just taking the previous $n$ bits of ciphertext, this seems just like CBC, which wasn't considered awkward.

The ISO 10116 reference might be helpful for showing which awkwardness it avoids, but I don't have access to it.

Answer 1

I've been thinking a little bit about it, and now I think it is possible, but you have to consider the generalization of CFB in ISO 10116 (I don't have access to the ISO 10116 standard, so I will assume that the description by Rogaway is correct).

The generalization of CFB from the ISO standard seems to have two main changes:

• The feedback block (FB), of size $r$, can be longer than the input block (IB), of size $n$. The IB is constructed with the left $n$ bits of the FB.
• A new parameter $k$ specifies how much the previous feedback block is shifted to the left on each step.

For each new plaintext block, the feedback block (FB) will be made of three parts:

1. The least significant $r - k$ bits of the previous FB
2. A sequence of one bits, of size $k - s$
3. The previous ciphertext bits, of size $s$

We are used to the case where $r = n$ and $k = s$ (e.g., the NIST 800-38A specification), so there is no sequence of one bits. However, when $r\ge n+s $, the input block for the block cipher will only take bits from the previous FB and one-bits, and not from the previous ciphertext bits since it only takes the left $n$ bits from the FB. This way you could partially parallelize the encryption operation.

A very illustrative way to understand why this allows some parallelization is to imagine a very very long feedback block, much greater than the input block. If you append the previous ciphertext to the right of the FB, shift the FB just a little to the left and take the left part of the resulting FB as your new IB, then the ciphertext will not take part of the new IB, at least for some rounds. These rounds are then parallelizable. Adjusting parameters $k$ and $r$ allow to precisely define the parallelization factor.