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.

Description

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. 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. 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 Morgari, 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 Lu 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.

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 encryption compare with all existing attacks".

See also

* A5/1
* RC4

References

External links

* Slides.

{{Cryptography navbox , stream

Broken stream ciphers
Bluetooth