E0 (cipher)
Stream cipher
- 2 min read
- 2 chapters
Related on Lably
Through Bluetooth
Description
A 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 [=e 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.
Sign in to keep reading
One more chapter is free with a Lably account.
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 264 operations (instead of 2128), if 264 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 280 operations precalculation and a key search complexity of about 265 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 270 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 235 Bluetooth frames (a frame is 2745 bits long). The final complexity to retrieve the key is about 240 operations. The attack was improved to 237 operations for precomputation and 239 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 223.8 frames and 238 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".