Cryptanalysis of the Bluetooth E0 Cipher using
Yaniv Shaked and Avishai Wool
School of Electrical Engineering Systems,
Tel Aviv University, Ramat Aviv 69978, ISRAEL
March 18, 2006
Abstract. In this paper we analyze the E0 cipher, which is the cipher
used in the Bluetooth specifications. We adapted and optimized the Bi-
nary Decision Diagram attack of Krause, for the specific details of E0.
Our method requires 128 known bits of the keystream in order to re-
cover 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 223 (84MB RAM), and with
a time complexity of 287. 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.
Keywords: Stream cipher, Cryptanalysis, Bluetooth, BDD
Bluetooth, a technology used for short range fast communications, has quickly
spread worldwide. Bluetooth technology is used in a large set of wired and wire-
less devices: mobile phones, PDA’s, desktop and mobile PC’s, printers, digital
cameras, and dozens of other devices.
Bluetooth employs a stream cipher as the data encryption mechanism. This
stream cipher, E0, is based on 4 LFSR’s (Linear Feedback Shift Registers) of
different lengths, along with a non-linear combiner logic (finite state machine).
The keystream is xor-ed with the plaintext, to create the ciphertext, and de-
cryption is performed in exactly the same way using the same stream used for
1.2 Related work
A number of crypt-analytical results regarding E0 ([JW01], [FL01], [LW05],
[Kra02], [Saa00], [HN99], [EJ00], [GBM02], [LV04], [LMV05], [KS06]) have ap-