Cipher Feedback Mode

Question

I can't understand what CFB really is. It said in Wikipedia that CFB is same as CBC, but I find that CFB is more difficult than CBC.

Can someone explain to me how CFB works. Such as how Initialization Vector(IV) work inside the Encryption Algorithm process together with the Key, and also how does the ciphertext message working to the next block cipher encryption.

And also my other question, is it okay to to use CFB with AES? I am confused because the plaintext message should enter AES algorithm to encrypt the plaintext message, but here in CFB, only Initialization Vector and Secret key will permuted by the block cipher.

Here is my another issue with CFB:

"To use CFB to make a self-synchronizing stream cipher that will synchronize for any multiple of $x$ bits lost, start by initializing a shift register the size of the block size with the initialization vector. This is encrypted with the block cipher, and the highest $x$ bits of the result are XOR'ed with $x$ bits of the plaintext to produce $x$ bits of ciphertext. These $x$ bits of output are shifted into the shift register, and the process repeats with the next $x$ bits of plaintext. Decryption is similar, start with the initialization vector, encrypt, and XOR the high bits of the result with $x$ bits of the ciphertext to produce $x$ bits of plaintext. Then shift the $x$ bits of the ciphertext into the shift register. This way of proceeding is known as CFB-8 or CFB-1 (according to the size of the shifting).

In notation, where $S_i$ is the $i$-th state of the shift register, $a \ll x$ is $a$ shifted up $x$ bits, $\operatorname{head}(a, x)$ is the $x$ highest bits of $a$ and $n$ is number of bits of IV:

$$ \begin{aligned} C_i &= \operatorname{head}(E_K (S_{i-1}), x) \oplus P_i \\ P_i &= \operatorname{head}(E_K (S_{i-1}), x) \oplus C_i \\ S_i &= ((S_{i-1} \ll x) + C_i) \bmod 2^n \\ S_{0} &= \operatorname{IV} \\ \end{aligned} $$

If $x$ bits are lost from the ciphertext, the cipher will output incorrect plaintext until the shift register once again equals a state it held while encrypting, at which point the cipher has resynchronized. This will result in at most one blocksize of output being garbled."

I can't understand the formula and also what is the use of shift register. Can someone help me?

Answer 1

Well, with CFB mode, the encryption process is "take the most recent ciphertext block, pass it through the block cipher, and then exclusive-or that with the plaintext block to generate the next ciphertext block". As for the IV, that's used as "the most recent ciphertext block" when encrypting the first plaintext block (where you don't have a most recent ciphertext block yet).

Now, the advantage that CFB brings to the table is error recovery, including errors that add or delete ciphertext blocks. That is, is a ciphertext block is garbled (or a block is inserted or removed), the corresponding decrypted plaintext block and the one after that is also garbled; however, after that, the decryption process resyncs, and then it decrypts the rest of the text correctly. Now, CBC also has this same property in regards to entire blocks; however, if you take the last 128 bits of ciphertext, encrypt that, and then use (say) only 8 bits of each AES block output, and exclusive-or that is 8 bits of plaintext to form the next 8 bits of ciphertext, well, now you have something that is resilient against changes that inserts or removes individual bytes from the ciphertext (at the cost of having to run the block cipher N times to encrypt N bytes). Nowadays, this is not considered relevent (we generally want to encrypt and MAC entire messages, and if anything was changed, we reject the entire message); historically, this was considered a nice feature if (say) you were encrypting data going over an RS-232 interface (which really could add/drop individual bytes).

The other advantage that CFB mode has (over, say, CBC) is that the decryption process also uses the block cipher in encryption mode; depending on how different the block cipher encryption and decryption is, this can be convienent.

Now, as for your questions:

• As to the relationship between CBC and CFB; well, they both perform the same general process, they both take iteratively exclusive-or in the next block of plaintext, and then run that through the block cipher. How they differ is where they pull the ciphertext from; CBC pulls it after we run the internal state through the block cipher, CFB pulls it after we compute the exclusive-or.

• Is it OK to use with AES? Why, yes, AES works perfectly well with CFB. As for your statement that "the plaintext message should enter AES algorithm to encrypt the plaintext message", why, that's not at all true; in Counter mode, the plaintext message doesn't go through the AES algorithm at all. For CFB mode, for the very first ciphertext, yes, the plaintext doesn't enter the AES algorithm; however, for any other ciphertext block, we send the previous ciphertext block through it, and the previous plaintext blocks were used to compute the previous ciphertext block.

Answer 2

To address the other issue (with the CFB-1, CFB-8, registers, etc.):

Note that in the picture we encrypt whole blocks of the previous ciphertext, and xor the result with the next plaintext block, to get a whole new ciphertext block, to encrypt again, etc. So we process the plaintext in chunks of whole blocks, except maybe the last partial block, where we only xor as many bytes as we need from the last encrypted previous ciphered block.

But traditionally stream cipher systems (as CFB makes a block cipher into a stream cipher, a self-synchronising one) work on bits or bytes, so NIST also standardised a variant of CFB that allows that, and generalises CFB for whole blocks.

Say we want to encrypt single bits at the type. We start with an IV (say we use AES and have 16 random bytes), and we see these as a long shift register of size 128 bits (in the obvious way: the first byte in the block goes left, and within a byte the most significant bit goes left as well). This is the $S_0$.

To encrypt the first plaintext bit, we encrypt $S_0$ with the block cipher, so we get $E_K(S_0)$, and we only use the leftmost bit of the result, and xor it with the first plaintext bit, and we get the first ciphertext bit.

Now the feedback from the ciphertext (where CFB gets its name from) kicks in: we shift $S_0$ left by one bit, so the leftmost bit "falls off" (we already used it to encrypt the first bit), and in the new empty position at the right we put the first ciphertext bit. The result is $S_1$, the next "state" of our stream cipher.

To encrypt the next bit, we repeat this procedure: we encrypt $S_1$ to get $E_K(S_1)$, and only use the highest bit as a key bit: xor it with the second plaintext bit, get the second ciphertext bit. Shift $S_1$ to the left by 1 one bit, and replace the rightmost bit by the new ciphertext bit. This makes $S_2$ (which still has 126 bits of the original IV..)

All the time, of course we collect all the ciphertext bits for sending.

This is the one-bit case (CFB-1), but the byte case (CFB-8) is entirely similar. What is described above is the full generalisation, where we do $x$ bits at the time: we always use the leftmost $x$ bits of the encrypted register to create $x$ new ciphertext bits from $x$ plaintext bits, and then shift the current (unencrypted) state $x$ bits to the left, and put the ciphertext bits (in order) as the rightmost $x$ bits of the updated register. If we take $x=128$, we replace the register completely with the full ciphertext block every time, and we get the variant from the first picture.

These CFB-1, CFB-8 are mostly there for historical reasons, and are not really used anymore; many libraries that do support full-block CFB do not even support the other variants. Note that to encrypt 128 bits in CFB-1 we need 128 block cipher encryption operations, one for each bit. But if we use CFB in full block mode, we only need 1. So it's very inefficient as well.