\input zb-basic
\input zb-ioport
\iteman{io-port 05538943}
\itemau{Krause, Matthias; Stegemann, Dirk}
\itemti{Reducing the space complexity of BDD-based attacks on keystream generators.}
\itemso{Robshaw, Matthew (ed.), Fast software encryption. 13th international workshop, FSE 2006, Graz, Austria, March 15--17, 2006. Revised selected papers. Berlin: Springer (ISBN 3-540-36597-4/pbk). Lecture Notes in Computer Science 4047, 163-178 (2006).}
\itemab
Summary: The main application of stream ciphers is online-encryption of arbitrarily long data, for example when transmitting speech data between a Bluetooth headset and a mobile GSM phone or between the phone and a GSM base station. Many practically used and intensively discussed stream ciphers such as the $E_{0}$ generator used in Bluetooth and the GSM cipher A5/1 consist of a small number of linear feedback shift registers (LFSRs) that transform a secret key $x\in \{0,1\}^{n}$ into an output keystream of arbitrary length. In 2002, Krause proposed a Binary Decision Diagram (BDD) based attack on this type of ciphers, which in the case of $E_{0}$ is the best short-keystream attack known so far. However, BDD-attacks generally require a large amount of memory. In this paper, we show how to substantially reduce the memory consumption by divide-and-conquer strategies and present the first comprehensive experimental results for the BDD-attack on reduced versions of $E_{0}$, A5/1 and the self-shrinking generator.
\itemrv{~}
\itemcc{}
\itemut{stream cipher; cryptanalysis; BDD; Bluetooth $E_{0}$; GSM A5/1; self-shrinking generator}
\itemli{doi:10.1007/11799313\_11}
\end