# zbMATH — the first resource for mathematics

Algebraic attacks on combiners with memory. (English) Zbl 1122.94346
Boneh, Dan (ed.), Advances in cryptology – CRYPTO 2003. 23rd annual international cryptology conference, Santa Barbara, California, USA, August 17–21, 2003. Proceedings. Berlin: Springer (ISBN 3-540-40674-3/pbk). Lect. Notes Comput. Sci. 2729, 162-175 (2003).
Summary: Recently, algebraic attacks were proposed to attack several cryptosystems, e.g. AES, LILI-128 and Toyocrypt [see, e.g., N. T. Courtois and W. Meier, Lect. Notes Comput. Sci. 2656, 345–359 (2003; Zbl 1038.94525)]. 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 $$\lceil k(l+1)/2\rceil$$ 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 _{0}$$ 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 $$2^{23.07}$$ unknowns. To our knowledge, this is the best published attack on the $$E _{0}$$ keystream generator yet.
For the entire collection see [Zbl 1027.00041].

##### MSC:
 94A60 Cryptography
Full Text: