# Parallelization of CFB mode encryption and decryption

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.

• With regard to (1), I guess it is a mistake...CFB mode of encryption (when $s=n$) is almost identical to OFB, which is said non parallelizable for encryption. Jul 7 '15 at 9:06
• Maybe this patent gives some insight on how to encrypt in parellel using CFB.
– rob
Jul 9 '15 at 11:52
• @rob, thanks for the link. Looks like what cygnusv describes in the answer, but the patent describes it as a modification of the CFB mode.
– otus
Jul 9 '15 at 12:14

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.

• If that's from ISO 10116, isn't that the "less awkward" generalization?
– otus
Jul 9 '15 at 12:08
• @otus I don't know. IMHO, this version is awkward enough, but maybe there is an ever more awkward version (maybe ANSI X9.52?). Again, I don't have access to the ANSI version either. Jul 9 '15 at 13:31
• @otus Anyway, the term "awkward" used by Rogaway is not very objective, so there is no way to know what he was referring to. Jul 9 '15 at 13:40
• @otus To make things even more confusing, the HAC describes the ISO 10116 variant differently [Section 7.19, 5th edition]. In this version, the feedback block is of the same size than the input block, so this version is not parallelizable. Jul 9 '15 at 14:13
• The definition from HAC is the same as Rogaway shows, so that's the one that the "yes but awkward" claim should apply to.
– otus
Jul 10 '15 at 7:16