I am looking for an easily defined stream cipher to illustrate two basic principles in an undergraduate cryptography course:

  1. not every bit of the internal state should be used in the keystream;
  2. some non-linear operations should be used to step the internal state.

So far, my only candidate is the Geffe generator. But this is a bit too easily broken. My ideal example would be a stream cipher showing (1) and (2) that was a bit stronger than the Geffe generator, but still easily defined, and still breakable by a correlation attack.

If there are no candidates then I'd welcome suggestions for a simple design meeting my requirements.

  • $\begingroup$ have you looked at Simon? $\endgroup$
    – b degnan
    Nov 11 '18 at 7:14
  • $\begingroup$ @bdegnan Simon is lightweight block cipher. $\endgroup$
    – kelalaka
    Nov 11 '18 at 9:19
  • 1
    $\begingroup$ @kelalaka Simon is bitwise or bytewise, and is very simple. It's an excellent choice for a class. Also, I happen to already have the eps generators that I used for my classes (circuits, no crypto): github.com/bpdegnan/simontool/blob/master/simontool/… $\endgroup$
    – b degnan
    Nov 11 '18 at 16:11

The shrinking generator (open to divide and conquer) or self-shrinking generators are possibilities.

If you use a nonlinear combination generator with 3 relatively prime length primitive LFSRs and a nonlinear boolean function $f(x_1,x_2,x_3)$ you can also illustrate the tradeoff between nonlinearity and the degree of the function (Xiao-Massey lemma) as well as have some room for divide and conquer. You can spend 10 minutes on Geffe and show how its weaknesses can be ameliorated with this generator.

It also enables you to explicitly compute the nonlinearity via $f(L_1, L_2, L_3)$ over the integers.

  • $\begingroup$ Bluetooth's $E0$ is also another candidate. $\endgroup$
    – kelalaka
    Nov 11 '18 at 9:26

Here is the baby stream cipher I used for my course. Take linear feedback shift registers of widths $\ell$ and $\ell'$ generating keystreams of maximum period $2^\ell-1$ and $2^{\ell'}-1$, respectively. Let $k_0k_1k_2 \ldots $ and $k'_0k'_1k'_2 \ldots $ be the keystreams for chosen keys $k_0\ldots k_{\ell-1}$ and $k'_0 \ldots k_{\ell'-1}$.

For $m \in \mathbb{N}$, define the $m$-quadratic stream cipher to have keystream $u_0u_1u_2 \ldots$ where

$$ u_i = k_ik'_i \oplus k_{i-1}k'_{i-1} \oplus \cdots \oplus k_{i-(m-1)}k'_{i-(m-1)} \quad\text{for $i \ge m-1$} $$

and $u_0 = \ldots = u_{m-2} = 0$. Thus after the first $m-1$ bits, each bit is defined by adding up the product of $m$ consecutive bits produced by the LFSRs.

The expected correlation between the keystream $u_0u_1u_2 \ldots $ and the LFSR keystream $k_0k_1k_2 \ldots $ is about $1/2^m$. This can be proved as follows: if $X_1, \ldots, X_m$ and $X_1' \ldots, X_m'$ are independent and unbiased bits then the correlation between $X_1X_1' + \cdots + X_mX_m'$ and $X_m$ is

$$\mathbb{E}[(-1)^{X_1X_1' + \cdots + X_mX_m' + X_m}] = \mathbb{E}[(-1)^{X_1X_1'}] \ldots \mathbb{E}[(-1)^{X_{m-1}X_{m-1}'}]\mathbb{E}[X_mX_m'+X_m] = \frac{1}{2^{m}} $$

since each pair $X_iX_i'$ is biased to $0$ with probability $3/4$, and the same holds for $X_mX_m' + X_m$. Therefore an attack using this correlation requires at least $2^{2m}$ bits from $u_0u_1u_2 \ldots $ to distinguish a correct guess for $k_0\ldots k_{\ell-1}$ from an incorrect guess. The graphs below show the correlations for all $31$ non-zero guesses for $k_0k_1k_2k_3k_4$ in a toy example where $\ell = 5$ on $1024$ bits of keystream. The key is $00111_2 = 7$.

Correlations for m-quadratic stream cipher m=1,2,3,4,5

As it stands, the toy $m$-quadratic is easily broken since

$$u_i \oplus u_{i-1} = k_ik_i' \oplus k_{i-m}k_{i-m}'$$

cancels out most of the quadratic terms. This leads to an effective correlation attack for any $m$. As an improvement, I suggest changing the feedback function so that

$$u_i = k_ik_i' \oplus k_{i-1}k'_{i-1} \oplus k_{i-2}k'_{i-2} \oplus k_{i-4}k'_{i-4} \oplus \cdots \oplus k_{i-2^{m-2}}k'_{i-2^{m-2}}. $$

For $m \ge 4$ there is no linear combination of the keystream bits having fewer than $m$ quadratic terms, so the correlation attacks above are ineffective.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.