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].

94A60 Cryptography
Full Text: DOI