E0 (cipher)

E0 is a stream cipher used in the Bluetooth protocol. It generates a sequence of pseudorandom numbers and combines it with the data using the XOR operator. The key length may vary, but is generally 128 bits.

At each iteration, E0 generates a bit using four shift registers of differing lengths (25, 31, 33, 39 bits) and two internal states, each 2 bits long. At each clock tick, the registers are shifted and the two states are updated with the current state, the previous state and the values in the shift registers. Four bits are then extracted from the shift registers and added together. The algorithm XORs that sum with the value in the 2-bit register. The first bit of the result is output for the encoding.

E0 is divided in three parts:
# Payload key generation
# Keystream generation
# Encoding

The setup of the initial state in Bluetooth uses the same structure as the random bit stream generator. We are thus dealing with two combined E0 algorithms. An initial 132-bit state is produced at the first stage using four inputs (the 128-bit key, the Bluetooth address on 48 bits and the 26-bit master counter). The output is then processed by a polynomial operation and the resulting key goes through the second stage, which generates the stream used for encoding. The key has a variable length, but is always a multiple of 2 (between 8 and 128 bits). 128 bit keys are generally used. These are stored into the second stage's shift registers. 200 pseudorandom bits are then produced by 200 clock ticks, and the last 128 bits are inserted into the shift registers. It is the stream generator's initial state.

Cryptanalysis

Several attacks and attempts at cryptanalysis of E0 and the Bluetooth protocol have been made, and a number of vulnerabilities have been found.In 1999, Miia Hermelin and Kaisa Nyberg showed that E0 could be broken in 2⁶⁴ operations (instead of 2¹²⁸), if 2⁶⁴ bits of output are known. [ cite journal
url = http://www.esat.kuleuven.ac.be/~jlano/stream/papers/e0hn.ps
title = Correlation properties of the Bluetooth Combiner | location = Helsinki, Findland
first = Miia | last = Hermelin | coauthors Kaisa Nyberg
publisher = Nokia Research Centre | format = PostScript] This type of attack was subsequently improved by Kishan Chand Gupta and Palash Sarkar. Scott Fluhrer, a Cisco Systems employee, found a theoretical attack with a 2⁸⁰ operations precalculation and a key search complexity of about 2⁶⁵ operations. [cite web
url = http://eprint.iacr.org/2002/068.ps | format = PostScript
title = Improved key recovery of level 1 of the Bluetooth Encryption
first = Scott | last = Fluhrer | publisher = Cisco Systems, Inc.] He deduced that the maximal security of E0 is equivalent to that provided by 65-bit keys, and that longer keys do not improve security. Fluhrer's attack is an improvement upon earlier work by Golic, Bagini and Morgani, who devised a 2⁷⁰ operations attack on E0.

In 2000, the Finn Juha Vainio showed problems related to misuse of E0 and more generally, possible vulnerabilities in Bluetooth.

In 2004, Yi Liu and Serge Vaudenay published a statistical attack requiring the 24 first bits of 2³⁵ Bluetooth frames (a frame is 2745 bits long). The final complexity to retrieve the key is about 2⁴⁰ operations. The attack was improved to 2³⁷ operations for precomputation and 2³⁹ for the actual key search. [cite journal
first = Yi | last = Lu | coauthors = Serge Vaudenay
title = Cryptanalysis of Bluetooth Keystream Generator Two-Level E0
journal = ASIACRYPT 2004 | year = 2004 | pages = 483-499.] [cite journal
first = Yi | last = Lu | coauthors = Serge Vaudenay
title = Faster Correlation Attack on Bluetooth Keystream Generator E0
journal = CRYPTO 2004 | pages = 407-425 | url = http://lasecwww.epfl.ch/pub/lasec/doc/YV04a.pdf]

In 2005, Lu, Meier and Vaudenay published a cryptanalysis of E0 based on a conditional correlation attack. Their best result required the first 24 bits of 2^23.8 frames and 2³⁸ computations to recover the key. The authors assert that "this is clearly the fastest and only practical known-plaintext attack on Bluetooth encrytion compare with all existing attacks". [cite journal
first = Yi | last = Lu | coauthors = Willi Meier; Serge Vaudenay
title = The Conditional Correlation Attack: A Practical Attack on Bluetooth Encryption
journal = CRYPTO 2005 | year = 2005 | location = Santa Barbara, California, USA
url = http://www.terminodes.org/micsPublicationsDetail.php?pubno=1216 | volume = 3621 | pages = 97-117 ]

References

ee also

* A5/1
* RC4

External links

* cite web
url = http://www.iris.re.kr/ac04/data/Asiacrypt2004/11%20Symmetric%20Key%20Cryptanalysis/04_Yi%20Lu.pdf
title = Cryptanalysis of E0
first = Serge | last = Vaudenay | coauthors = Yi Lu | publisher = EPFL Slides.