E0 (cipher)
   HOME

TheInfoList



OR:

E0 is a
stream cipher stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream ...
used in the
Bluetooth Bluetooth is a short-range wireless technology standard that is used for exchanging data between fixed and mobile devices over short distances and building personal area networks (PANs). In the most widely used mode, transmission power is limi ...
protocol. It generates a sequence of
pseudorandom A pseudorandom sequence of numbers is one that appears to be statistically random, despite having been produced by a completely deterministic Determinism is a philosophical view, where all events are determined completely by previously exi ...
numbers and combines it with the data using the
XOR Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false). It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
operator. The
key length In cryptography, key size, key length, or key space refer to the number of bits in a key used by a cryptographic algorithm (such as a cipher). Key length defines the upper-bound on an algorithm's security (i.e. a logarithmic measure of the faste ...
may vary, but is generally 128 bits.


Description

At each iteration, E0 generates a bit using four
shift register A shift register is a type of digital circuit using a cascade of flip-flops where the output of one flip-flop is connected to the input of the next. They share a single clock signal, which causes the data stored in the system to shift from one loc ...
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 #
Keystream In cryptography, a keystream is a stream of random or pseudorandom characters that are combined with a plaintext message to produce an encrypted message (the ciphertext). The "characters" in the keystream can be bits, bytes, numbers or actual chara ...
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 is a Finnish cryptographer and computer security researcher. Contributions Nyberg's research includes the theory of perfect nonlinear S-boxes (now known as Nyberg S-boxes), provably secure block cipher design (resulting in KN-Cipher ...
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, Inc., commonly known as Cisco, is an American-based multinational corporation, multinational digital communications technology conglomerate (company), conglomerate corporation headquartered in San Jose, California. Cisco develo ...
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 Juha Harri "Junnu" Vainio, also known as Juha "Watt" Vainio (10 May 1938 in Kotka, Finland – 29 October 1990, Gryon, Switzerland) was a Finnish lyricist, singer, composer and teacher. With the lyrics or music to over 2,400 songs to his name, ...
showed problems related to misuse of E0 and more generally, possible vulnerabilities in Bluetooth. In 2004, Yi Lu and
Serge Vaudenay Serge Vaudenay (born 5 April 1968) is a French cryptographer and professor, director of the Communications Systems Section at the École Polytechnique Fédérale de Lausanne Serge Vaudenay entered the École Normale Supérieure in Paris as a '' ...
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 The known-plaintext attack (KPA) is an attack model for cryptanalysis where the attacker has access to both the plaintext (called a crib), and its encrypted version (ciphertext). These can be used to reveal further secret information such as secr ...
on Bluetooth encryption compare with all existing attacks".


See also

* A5/1 *
RC4 In cryptography, RC4 (Rivest Cipher 4, also known as ARC4 or ARCFOUR, meaning Alleged RC4, see below) is a stream cipher. While it is remarkable for its simplicity and speed in software, multiple vulnerabilities have been discovered in RC4, ren ...


References


External links

* Slides. {{Cryptography navbox , stream Broken stream ciphers Bluetooth