Are all self-synchronizing cryptosystems necessarily self-synchronizing stream ciphers?

Question

I have a noisy communications link between two points that occasionally deletes a byte.

By "self-synchronizing cryptosystem", I mean that the receiver attempting to recover the original plaintext will be mostly successful, with at most a dozen or so corrupted letters of plaintext corresponding to each missing ciphertext byte.

Are all such cryptosystems necessarily self-synchronizing stream ciphers?

In other words:

• Cryptosystems that are some block cipher mode of operation:
  • A few block cipher mode of operation are self-synchronizing, such as the SCFB mode and OCFB mode described by Fang Yang and Howard M. Heys; "Comparison of Two Self-Synchronizing Cipher Modes". Do all such block cipher modes end up producing a stream cipher, i.e., producing a pseudo-random bitstream and then combining that bitstream with the plaintext using XOR (or another stream-cipher operator)?
• Cryptosystems that are not some block cipher mode of operation
  • Do all such cryptosystems end up either being effectively a stream cipher, or are non-self-synchronizing, or both?

I realize this isn't a practical question -- in practice, we MAC the message as a whole, and if anything was changed, added, or deleted, we reject the entire message. (In practice, non-crypto networking techniques handle bit-alignment, byte-alignment, packet-alignment, etc. and then re-send or otherwise correct occasional missing bytes and assemble the complete message long before any crypto algorithms at the receiver ever see that message).

Answer 1

Your best bet is to use an error-correcting code to correct the errors on the ciphertext.

In general, accepting corrupted ciphertexts is a bad idea, because it can allow devastating chosen-ciphertext attacks and because unauthenticated encryption has caused major security holes in practice.

When proper authentication is in use (which should be always), any error will result in the entire message being rejected. There are two solutions:

• Break the message into chunks, such that bad chunks can be detected and retransmitted.
• Use error-correcting codes. These allow for errors to be corrected by introducing redundancy.

These can be combined.