Stream ciphers

So far, we have illustrated cryptosystems that “reuse” the same key to encrypt letters or blocks of the plaintext. This is usually referred to as block ciphers.

\begin{matrix} x_1 & x_2& \ldots ~~~~~~& x_n\\\downarrow& \downarrow&&\downarrow\\k\rightarrow\fbox{E}~~~~~~&k\rightarrow\fbox{E}~~~~~~&\ldots~~~~~~&k\rightarrow\fbox{E}~~~~~~\\\downarrow&\downarrow& &\downarrow\\y_1 & y_2 & \ldots ~~~~~~& y_n\end{matrix}

This scheme can be generalized by considering a stream of keys instead of a fixed one. Let z_1, z_2, \ldots, z_n be such a stream. The idea is to encrypt the first letter of the plaintext with z_1, the second with z_2 and so on. It does not matter much if we encrypt a letter or a block, the important difference is that the used key is always different.

\begin{matrix} x_1 & x_2 & \ldots ~~~~~~~& x_n\\\downarrow&\downarrow& &\downarrow\\z_1\rightarrow\fbox{E}~~~~~~~&z_2\rightarrow\fbox{E}~~~~~~~&\ldots~~~~~~~&z_n\rightarrow\fbox{E}~~~~~~~\\\downarrow&\downarrow& &\downarrow\\y_1 & y_2 & \ldots ~~~~~~~& y_n\end{matrix}

Having a different key for each letter or block of the plaintext is of course appealing but not much practical. The stream of key is thus usually derived starting from an initial key k. To make the stream more complex it can also depend on previous part of the plaintext. In general we say that z_i = f_i(k,x_1,\ldots,x_{i-1}). To understand why a key z_i cannot depend on plaintexts with indexes greater than or equal to i, it is useful to reason on the decryption scheme:

\begin{matrix} y_1 & \ldots ~~~~~~~& y_i & \ldots ~~~~~~~& y_n\\\downarrow&&\downarrow& &\downarrow\\z_1\rightarrow\fbox{D}~~~~~~~&\ldots~~~~~~~&z_i\rightarrow\fbox{D}~~~~~~~&\ldots~~~~~~~&z_n\rightarrow\fbox{D}~~~~~~~\\\downarrow& &\downarrow& &\downarrow\\x_1 & \ldots ~~~~~~~& x_2 & \ldots ~~~~~~~& x_n\end{matrix}

Now, z_1 = f_1(k) meaning that we can compute it with not knowledge of the plaintext. To compute z_2 = f_2(k,x_1), instead, we need to know x_1. As a consequence, we have to decrypt y_1 with z_1 before computing z_2. Once we have this key we can decrypt x_3 and compute z_3, and so on. The values are thus computed in the following sequence: z_1,x_1,z_2,x_2, \ldots, z_n,x_n. It should be evident, now, that we cannot let z_i depend, e.g., on x_i as we would need that plaintext to compute the key.

Notice that block ciphers are, clearly, a simple instance of stream ciphers where z_i = k for all i.It is also useful to classify these ciphers depending on certain properties of the key stream:

Periodic

A stream cipher is periodic its key stream has the following form z_1,z_2,\ldots,z_d,z_{1},z_2,\ldots,z_d,z_1\ldots, i.e., if it repeats after d steps.

Exercise. Vigenére cipher can be seen as a stream cipher acting on single letters and with a periodic key stream. Formalize the cipher giving ({\cal P},{\cal C},{\cal K},E,D)  and defining the key stream z_i.

Synchronous. A stream cipher is synchronous if its key stream does not depend on plaintexts, i.e., z_i = f_i(k) for all i. When this happens, we have that the key stream can be generated starting from k and independently on the plaintext. This is particularly useful to improve efficiency: we do not need to obtain x_{i} to compute z_{i+1}. In fact, the key stream can be generated offline, before the actual ciphertext is received.

Asynchronous. This is the general case where z_i = f_i(k,x_1,\ldots,x_{i-1}). As mentioned above, we need to decrypt and compute the keys stream at the same time, as a key can depend on previous plaintexts. We give a simple example of a cipher of this class, called Autokey. We let {\cal P}={\cal C}={\cal K}=\mathbb{Z}_{26}. E_z(x) = x+z \mod 26 and D_z(y) = y-z \mod 26, i.e., encryption and decryption are exactly as in a shift cipher. The key stream is defined as z_1 = k and z_i = x_{i-1} for i\geq 2, meaning that the first key in the stream is the initial key k while the next keys are the same as the previous plaintext.

\begin{matrix} x_1 & x_2& \ldots ~~~~~~& x_n\\\downarrow& \downarrow&&\downarrow\\k\rightarrow\fbox{E}~~~~~~&x_1\rightarrow\fbox{E}~~~~~~~&\ldots~~~~~~&x_{n-1}\rightarrow\fbox{E}~~~~~~~~~~~\\\downarrow&\downarrow& &\downarrow\\y_1 & y_2 & \ldots ~~~~~~& y_n\end{matrix}

Exercise: try to break the following ciphertext encrypted with the above autokey cipher:

GUAAMLXOOVTMRVTKXOWSSDXNVJSTVTACALTNQFTPNIHUXRPWLV