Struggling to understand CFB mode (with DES)

Question

I'm really struggling to understand CFB mode (with DES if that matters). I realise after searching around here that these modes are now obsolete but I need to understand them for class. From wikipedia, I see that for encryption: $$C_i = P_i[:s] \oplus E_k(S_i)[:s]$$ $$S_0 = IV$$ $$S_i = (S_{i-1} << s) | C_i$$ (I'm using a python like notation so [:s] means first $s$ bits).

I'm already having trouble understanding this encryption scheme and how error propagates through. Wikipedia says that if an $C_i$ becomes corrupted then the encryption will eventually recover. I tried reading discussions about this here but I'm failing to see this (I am hoping for a more elaborate explanation).

Let's say $s=4$ bits, $IV$ is 64 bits and that $C_2$ becomes corrupted such that we correctly computed $C_1$ and $C_2$ from $P_1$ and $P_2$ but we can not correctly calculate $C_3'$ since $$C_3 = P_3[:4]\oplus E_k((IV << 8) | C_1 | C_2')[:4]$$ and so $E_k((IV << 8) | C_1 | C_2')$ gives an incorrect encryption and therefore an incorrect $C_3$ which I denoted as $C_3'$. If I continue this pattern, it seems that I always get an incorrect $C_i$ since the shift register will always be wrong. e.g consider

$$C_{17}' =^{?} P_{17}[:4]\oplus E_k((IV << 64)|C_1|C_2'|C_3'|...|C_{16'})$$

$$ = P_{17}[:4]\oplus E_k(C_1|C_2'|C_3'|...|C_{16}')[:4]$$

but this still gives the wrong value so I'm not sure why the system recovers. What am I misunderstanding?

Answer 1

and so $E_k((IV << 8) | C_1 | C_2')$ gives an incorrect encryption

That's your issue; CFB isn't designed to correct for errors in the plaintext - after all, if the ciphertext is not modified, then the decryptor will get precisely what the encryptor encrypted and so if the original plaintext had an error, and then was correct, what the decryptor will get will have that exact same error, and then be correct.

Instead, what CFB is concerned about is if the ciphertext is modified. As long as $C_3'$ remains in the shift register, yes, the decryptor will get gibberish. However, after 16 shifts (8 bytes), $C_3'$ will fall out of the shift register. Then, the 8 bytes will be precisely what the encryptor had intended, and so it will start to decrypt properly (and it will stay so as long as long as no further errors in the ciphertext occur).

Of course, CFB's claim to fame is not that it can adjust to bit flips in the ciphertext (after all, CBC has that same property, and OFB is even better); what CFB does in addition is handle it if segments aren't received at all. For example, suppose if $C_3$ wasn't received in error, but not received at all; that is, the decryptor received $C_1, C_2, C_4, C_5, C_6,...$. With CFB, the next 8 bytes will be decrypted incorrectly, however after that, the shift register will resync, and everything later will be decrypted normally. This is in contrast to CBC, where if a 4 bit chunk was dropped, it would never resync (because everything is processed in 64 bit chunks, and those chunks wouldn't line up anymore).

If you're wondering what could cause such an error, well, way back in the day, there really were communication channels (RS-232, for example) where you could add or drop individual bytes. Doing CFB over such a line would give a usable encrypted channel, even when that happened.

Of course, nowadays, we're not concerned about recovering about such add/drop errors, and considerably more concerned about attackers who can intentionally cause such errors (and try to gain an advantage for doing so); hence the fashion today is to place sequences of plaintext bytes into records, and perform an authenticated encryption of those records. Hence, the advantages of CFB aren't seen as an advantage today...