Self-synchronizing cipher recovery from dropped bits

Question

This cryptography book says:

There are also asynchronous or self-synchronizing stream ciphers, where the previously produced ciphertext bits are used to produce the current keystream bit. This has the interesting consequence that a receiver can eventually recover if some ciphertext bits are dropped.

CFB is an example of a self-synchronizing cipher. What does this mean that it can "eventually recover if some ciphertext bits are dropped"?

This is the equation for CFB:

$$ C_i = E_K (C_{i-1}) \oplus P_i $$

There are 4 variables. I don't see how you eliminate more than two such that the receiver knows all but one and deduce the only unknown variable.

The receiver knows $k$. The receiver knows $C_i$ or $C_{i-1}$, but not both since the situation we're considering is "some ciphertext bits are dropped". The receiver does not know $P_i$ since it's the receiver and it's trying to decipher.

What am I misunderstanding?

Answer 1

"Recovery", in this case, does not mean that the full plaintext can be recovered even if part of the ciphertext is missing.* Instead, the "eventual recovery" property of self-synchronizing stream ciphers simply means that dropping one block from the ciphertext doesn't turn all decrypted plaintext after that block in the same message into garbage, as it would with a synchronous cipher (since the synchronization would be lost).

You'll still get some garbage, and of course you will unavoidably lose the plaintext corresponding to the dropped block. And of course the whole thing only works if the length of the dropped segment is a multiple of the feedback length. (The feedback length $\ell$ of CFB mode can be any number of bits from one up to the block size of the underlying block cipher. However, using a feedback length shorter than the cipher block size makes encryption and decryption slower, since one block cipher encryption operation is required to process every $\ell$ bits of message data.)

If all this seems kind of underwhelming, well, you're not wrong. To quote Squeamish Ossifrage's comment above:

"FYI, essentially nobody cares about self-synchronizing stream ciphers or error propagation or anything like that any more; CFB and OFB are seldom used in practice these days; and the conceptual framework of ‘block cipher modes of operation’ has been largely discarded in favor of authenticated ciphers or AEAD (authenticated encryption with associated data) like AES-GCM or crypto_secretbox_xsalsa20poly1305 on arbitrary-length packets at a time. So don't worry too much about this if you're studying anything other than historical cryptography or horrible legacy cryptography APIs."

Or I could just quote the same text as you did, one sentence later:

"This is generally not considered to be a desirable property anymore in modern cryptosystems, which instead prefer to send complete, authenticated messages."

---

^{If you want to be able to fully decrypt messages even if some of the ciphertext is lost, probably the best way to achieve it is to apply an erasure code to the ciphertext after encryption (and authentication). Basically, don't try to mix crypto and error correction, but rather treat them as separate layers.}

Answer 2

First, when the textbook talks about 'dropped bits', they are not referring to bits that are received incorrectly; instead they are talking about transmission errors where certain bits are deleted.

One example of this would be if the sender sent the pattern:

$$0123456789$$

and the receiver received:

$$012456789$$

That is, the byte containing the value 3 has disappeared, and the 4 immediately follows the 2.

Furthermore, the textbook is referring to a rather older understanding of CFB.

This is the equation for CFB: $$ C_i = E_K (C_{i-1}) \oplus P_i $$

Actually, in the original design of CFB, it was a bit more complex; it was:

$$ C_i = \text{Trunc}_k(E_K (C_{i-1} || C_{i-2} || … || C_{i-n/k})) \oplus P_i $$

where:

• $k$ is a value selected by the designer
• $\text{Trunc}_k$ is a function that returns only the first $k$ bits of its argument
• $P_i, C_i$ are $k$ bit values (rather than the full block size of $n$)

This is equivalent to the modern understanding of CFB if $k=n$; however we can also consider smaller values of $k$.

Now, why would we do that (especially considering that CFB becomes less efficient with smaller $k$; we perform one block encryption for every $k$ bits)?

The answer is because of error recovery; suppose that we have a communication channel that could, by accident, add or delete blocks of $k$ bits (as explained above). If we look at, for example, CBC mode, if we had a long encrypted stream, and deleted 8 bits from the ciphertext, the blocks that the decryptor used to decrypt would not line up with the blocks that the encryptor used, and so the decryptor would get gibberish; and they would never sync up (until a multiple of block size bits were deleted).

In contrast, if we used CFB mode with $k=8$, then deleting 8 bits from the ciphertext is not a major issue; the next 8 bytes (assuming a 64 bit block size; given the historic context we're talking about, this is appropriate) will be gibberish, but after that, things would sync up, and (assuming that the communication channel didn't get more errors) everything would decrypt correctly.

This is what the textbook was referring to; that even after add/delete errors, CFB mode (with an appropriate $k$) will resync.

And, yes, back in those days, we had communication channels that could add or delete blocks of bits as a common error; RS-232 could delete or (more rarely) add bytes (and so $k=8$ would be appropriate in that case); I believe that bisync could add or delete individual bits (and so $k=1$ would work there).

Now, all that is historic; in the modern error, we are rather more sensitive to the issues an attacker could do if he could modify the text. Hence, we are less interested in self-synchronization properties of CFB, and are considerably more concerned about detecting when any error has occurred (either by accident or by maliciousness).