Cryptanalysis of the Bluetooth E0 Cipher using OBDD's

Yaniv Shaked; Avishai Wool

Paper 2006/072

Cryptanalysis of the Bluetooth E0 Cipher using OBDD's

Yaniv Shaked and Avishai Wool

Abstract

In this paper we analyze the E0 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 E0. Our method requires 128 known bits of the keystream in order to recover the initial value of the four LFSR's in the E0 system. We describe several variants which we built to lower the complexity of the attack. We evaluated our attack against the real (non-reduced) E0 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 E0, our work describes practical experience with BDD-based cryptanalysis, which so far has mostly been a theoretical concept.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: Stream cipher Cryptanalysis Bluetooth BDD
Contact author(s): yash @ eng tau ac il
History: 2006-03-27: revised; 2006-02-24: received; See all versions
Short URL: https://ia.cr/2006/072
License: CC BY

BibTeX

@misc{cryptoeprint:2006/072,
      author = {Yaniv Shaked and Avishai Wool},
      title = {Cryptanalysis of the Bluetooth E0 Cipher using {OBDD}'s},
      howpublished = {Cryptology {ePrint} Archive, Paper 2006/072},
      year = {2006},
      url = {https://eprint.iacr.org/2006/072}
}