E0 (cipher)
Encyclopedia
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.
s 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:
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.
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 Morgani, 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".
Stream cipher
In cryptography, a stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream . In a stream cipher the plaintext digits are encrypted one at a time, and the transformation of successive digits varies during the encryption...
used in the Bluetooth
Bluetooth
Bluetooth is a proprietary open wireless technology standard for exchanging data over short distances from fixed and mobile devices, creating personal area networks with high levels of security...
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 registerShift register
In digital circuits, a shift register is a cascade of flip flops, sharing the same clock, which has the output of any one but the last flip-flop connected to the "data" input of the next one in the chain, resulting in a circuit that shifts by one position the one-dimensional "bit array" stored in...
s 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
- KeystreamKeystreamIn cryptography, a keystream is a stream of random or pseudorandom characters that are combined with a plaintext message to produce an encrypted message ....
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
Kaisa Nyberg
Kaisa Nyberg is a cryptographer and computer security researcher, currently a professor at Helsinki University of Technology. Her notable work includes the theory of perfect nonlinear S-boxes , provably secure block cipher design , and the cryptanalysis of the stream ciphers E0 and SNOW.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
Cisco Systems
Cisco Systems, Inc. is an American multinational corporation headquartered in San Jose, California, United States, that designs and sells consumer electronics, networking, voice, and communications technology and services. Cisco has more than 70,000 employees and annual revenue of US$...
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 Morgani, 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
Serge Vaudenay
Serge Vaudenay is a well-known French cryptographer.Serge Vaudenay entered the École Normale Supérieure in Paris as a normalien student in 1989. In 1992, he passed the agrégation in mathematics. He did his PhD at the computer science laboratory of École Normale Supérieure, and defended it in 1995...
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".