# How can LCG based stream ciphers be broken?

I'm watching Christoph Paar's Introduction to Cryptography lecture series on youtube. In it he describes an example of an insecure stream cipher which uses XOR as the encryption and decryption functions and a Linear Congruential Generator as the source of the key material. The LCG function is defined as follows:

Given $$A,B,S_0 \in \mathbb{Z}_m$$, successive output symbols can be computed as

$$$$S_{i+1} \equiv A*S_{i}+B \mod m$$$$

He illustrates a situation where an attacker has three consecutive ciphertext symbols $$Y_1,Y_2,Y_3$$ and knows their plaintext values $$X_1,X_2,X_3$$. Using that information they can easily recover the the corresponding key symbols $$S_1, S_2, S_3$$. From there they can compute $$A$$ and $$B$$ using a simple system of linear equations.

\begin{align*} S_2 \equiv A*S_1 + B \mod m\\ S_3 \equiv A*S_2 + B \mod m \end{align*}

after rearranging and substituting we get:

\begin{align*} A = (S_2-S_3)(S_1-S_2)^{-1} \mod m\\ B = S_2 - S_1(S_2-S_3)(S_1-S_2)^{-1} \mod m \end{align*}

However, it is my understanding that for an arbitrary element $$a \in \mathbb{Z}_m$$, the existence of a multiplicative inverse $$a^{-1} \in \mathbb{Z}_m$$ is not guaranteed. So how can this attack work if $$(S_1-S_2)^{-1}$$ may not even exist?

For the cipher formula to work, $$A$$ must be coprime to $$m$$ and exists, which means $${(S_2 - S_3)}\over{(S_1 - S_2)}$$ must also be coprime to $$m$$ and also exists.

After excluding duplicate factors of both numerator and denominator, the denominator must be coprime to $$m$$, otherwise the division will not work (Extended Euclidean algorithm would return error), and the fraction will not have valid value, and thus not exist.

• My must A be coprime to m for the cipher to work? Would an LCD using a non-coprime A be insufficiently random?
– Nick
Commented Apr 18 at 18:53
• Let's suppose $m$ is 26 and $A$ is 13, all letters end up either 13 or 0 after multiplication. In this case, how are you suppose to decrypt if you can't deduce what other possible value the input may take? Try other $m$ and non-coprime $A$ and you'll see something similar. Commented Apr 18 at 23:49
• It sounds like you are talking about an affine cipher (i.e $e(x_i) \equiv a*x_i + b \mod m$), where decryption is indeed impossible if $gcd(a,m) \neq 1$. But while the formula for the LCG is similar it is only used for generating key material, not encryption. For a stream cipher, the encryption function itself is $e(x_i) = x_i \oplus s_i$, so all that is needed for decryption is $y_i$ and $s_i$. In other words it is not necessary to compute $S_i$ from $S_{i+1}$ in order to decrypt, therefore even if $A^{-1}$ does not exist decryption is still possible.
– Nick
Commented Apr 20 at 20:18
• But regardless thank you for taking the time to respond, and your comment does illustrate that, at least for certain choices of ($A, m$) the LCG's output has an extremely short period and is therefore decidedly not random.
– Nick
Commented Apr 20 at 21:25

I just received my copy of Paar's Understanding Cryptography and was happy to find that this question is addressed there:

In case $$gcd((S_1 - S_2), m) \neq 1$$ we get multiple solutions since this is an equation system over $$\mathbb{Z}_m$$. However, with a fourth piece of known plaintext the key can uniquely be detected in almost all cases. Alternatively, Oscar simply tries to encrypt[sic: decrypt?] the message with each of the multiple solutions found

• I think Oscar is right to say "encrypt", because I think he's trying to see if the encrypted ciphertext matches the ones captured. Commented Apr 21 at 9:00
• Ahhh, that makes sense. Thanks!
– Nick
Commented Apr 21 at 14:47