Why is Vigenère Autokey self-synchronizing?

Question

According to the Wikipedia, and to several of our school study materials, Vigenère autokey ciphers are considered to be self-synchronizing stream ciphers.

If I understand it correctly, the main idea of self-synchronizing ciphers is that they should re-sync in an event of missing characters in the ciphertext because the key only depends on previous N characters.

But, as far as I understand, in Vigenère autokey, every character depends on all the previous characters being in the right order, isn't that so? So, in an event of a character loss, the rest of the ciphertext after the lost character will never be deciphered correctly.

So, what am I missing? Do I misunderstand self-synchronizing ciphers, or am I missing something about the Vigenère autokey cipher?

Answer 1

"Autokey" refers to an encryption method that uses the plaintext itself to generate the ciphertext. "Self-synchronization" of a stream cipher is not an encryption method. It is a modern (from 1946) process for a stream cipher to update its state based on the previous ciphertext.

It is a category mistake to think of Vigenère's Autokey Cipher as an example of a self-synchronizing stream cipher. That said, it could be coded, one supposes, to be self-synchronizing for certain methods of transmission and reception.

Background

Girolamo Cardano (1501-1576), a prolific writer and mathematician from Milan, came up with the first autokey cipher in 1550, but he designed it very poorly. As David Kahn explains in The Codebreakers (Macmillan, 1967), "He employed the plaintext as a key to encipher itself, starting the key over from the beginning with each new plaintext word." (Kahn, p.144).

Blaise de Vigenère improved on Cardano's work when he "did not recommence his key with each plaintext word, which was his [Cardano's] weakness, but kept it running continuously." (Kahn, p. 147). Unfortunately, this innovation was "entirely forgotten" until the latter part of the nineteenth century. Vigenere's autokey is stronger than the famous "Vigenère Cipher" that was later mistakenly attributed to him, but it is a relic of the past like the quill pen and parchment.

However, this idea of an autokey cipher that does not repeat the keyword has been used in some much more modern cryptographic systems--in some rotor machines, for example--and the principle is still relevant.

So, autokey is a symmetric encryption method with a curious history, and it has many variations (see Bellaso's method from 1564; Kahn, p. 144). Self-synchronization is something entirely different and modern, a stream cipher maintaining its correct state.

Answer 2

You're right — the autokey cipher described in the Wikipedia article is not self-synchronizing, since an error in one ciphertext letter will propagate through the decryption process into every $n$-th following plaintext letter, where $n$ is the key length.

There are variants of the autokey cipher sometimes found in crypto puzzles that are self-synchronizing, e.g. where the ciphertext (rather than the plaintext) is used to extend the key, but those variants are trivially insecure (even by the standards of classical ciphers): as long as the encryption method used is known, all but the very beginning of the ciphertext can be straightforwardly decrypted without knowing anything about the key except its length!

Fundamentally, this is because the key in an autokey cipher is only used to start the decryption process, and is not explicitly involved in later stages of the process. If the decryption process did not propagate errors in the key (or in the extended keystream) forward indefinitely, the decrypted plaintext would eventually become entirely independent of the key — and, indeed, would do so at the same time or before it becomes independent of errors in the beginning of the ciphertext, which is what's required for self-synchronization.

The reason why CFB mode decryption can be secure while being self-synchronizing is that each plaintext symbol (bit / byte / etc., depending on the CFB variant used) is calculated based on the corresponding ciphertext symbol, a limited number of previous ciphertext symbols and the secret key. It's this continuous perturbation of the decryption process by the key that prevents an attacker from decrypting any part of the ciphertext without knowing the key, while still allowing the legitimate recipient (who does know the key) to resume decryption after an error in the ciphertext.

---

Anyway, self-synchronization isn't really considered a particularly useful property nowadays. Honestly, I'm not convinced that it ever really was, except as an ad-hoc justification for the existence of CFB mode.

Generally, we do want an encryption scheme to detect errors in the ciphertext (and, in particular, any malicious modifications made by an MITM attacker), which is why one should use an authenticated encryption mode. But recovering partially correct plaintext from corrupted ciphertext, like CFB mode does, is much less useful.

If you do want an encrypted communications protocol that is error-tolerant, it's much better to apply a non-cryptographic error correction scheme on top of the encryption (and authentication) layer, so that you can recover the entire original ciphertext (and thus the plaintext) even from a partially garbled message, and/or to divide long data streams into discrete packets and encrypt and transmit them independently (possibly with some retransmission mechanism in case of packet loss).