Algebraic Attacks on Combiners with Memory

Recently, algebraic attacks were proposed to attack several cryptosystems, e.g. AES, LILI-128 and Toyocrypt. This paper extends the use of algebraic attacks to combiners with memory. A (k,l)-combiner consists of k parallel linear feedback shift registers (LFSRs), and the nonlinear filtering is done via a finite automaton with k input bits and l memory bits. It is shown that for (k,l)-combiners, nontrivial canceling relations of degree at most ⌈k(l+1)/2⌉ exist. This makes algebraic attacks possible. Also, a general method is presented to check for such relations with an even lower degree. This allows to show the invulnerability of certain (k,l)-combiners against this kind of algebraic attacks. On the other hand, this can also be used as a tool to find improved algebraic attacks.Inspired by this method, the E₀ keystream generator from the Bluetooth standard is analyzed. As it turns out, a secret key can be recovered by solving a system of linear equations with 223.07 unknowns. To our knowledge, this is the best published attack on the E₀ keystream generator yet.