05289052

a

05289052 Shaked, Yaniv Wool, Avishai Cryptanalysis of the bluetooth $E_{0}$ cipher using OBDD's. Katsikas, Sokratis K. (ed.) et al., Information security. 9th international conference, ISC 2006, Samos Island, Greece, August 30--September 2, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-38341-3/pbk). Lecture Notes in Computer Science 4176, 187-202 (2006). 2006 Berlin: Springer EN Stream cipher Cryptanalysis Bluetooth BDD

doi:10.1007/11836810_14

Summary: In this paper we analyze the $E_{0}$ cipher, which is the cipher used in the Bluetooth specifications. We adapted and optimized the Binary Decision Diagram attack of Krause, for the specific details of $E_{0}$. Our method requires 128 known bits of the keystream in order to recover the initial value of the four LFSR's in the $E_{0}$ system. We describe several variants which we built to lower the complexity of the attack. We evaluated our attack against the real (non-reduced) $E_{0}$ cipher. Our best attack can recover the initial value of the four LFSR's, for the first time, with a realistic space complexity of $2^{23}$ (84MB RAM), and with a time complexity of $2^{87}$. This attack can be massively parallelized to lower the overall time complexity. Beyond the specifics of $E_{0}$, our work describes practical experience with BDD-based cryptanalysis, which so far has mostly been a theoretical concept.