E0 (cipher)

Last updated

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.

Contents

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:

  1. Payload key generation
  2. Keystream generation
  3. 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 264 operations (instead of 2128), if 264 bits of output are known. [1] 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. [2] 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. [3]

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. [4] [5]

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". [6]

See also

Related Research Articles

In cryptography, a block cipher is a deterministic algorithm that operates on fixed-length groups of bits, called blocks. Block ciphers are the elementary building blocks of many cryptographic protocols. They are ubiquitous in the storage and exchange of data, where such data is secured and authenticated via encryption.

<span class="mw-page-title-main">Data Encryption Standard</span> Early unclassified symmetric-key block cipher

The Data Encryption Standard is a symmetric-key algorithm for the encryption of digital data. Although its short key length of 56 bits makes it too insecure for modern applications, it has been highly influential in the advancement of cryptography.

<span class="mw-page-title-main">International Data Encryption Algorithm</span>

In cryptography, the International Data Encryption Algorithm (IDEA), originally called Improved Proposed Encryption Standard (IPES), is a symmetric-key block cipher designed by James Massey of ETH Zurich and Xuejia Lai and was first described in 1991. The algorithm was intended as a replacement for the Data Encryption Standard (DES). IDEA is a minor revision of an earlier cipher Proposed Encryption Standard (PES).

In cryptography, RC4 is a stream cipher. While it is remarkable for its simplicity and speed in software, multiple vulnerabilities have been discovered in RC4, rendering it insecure. It is especially vulnerable when the beginning of the output keystream is not discarded, or when nonrandom or related keys are used. Particularly problematic uses of RC4 have led to very insecure protocols such as WEP.

<span class="mw-page-title-main">Stream cipher</span> Type of symmetric key cipher

A 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, to give a digit of the ciphertext stream. Since encryption of each digit is dependent on the current state of the cipher, it is also known as state cipher. In practice, a digit is typically a bit and the combining operation is an exclusive-or (XOR).

In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state.

Articles related to cryptography include:

A5/1 is a stream cipher used to provide over-the-air communication privacy in the GSM cellular telephone standard. It is one of several implementations of the A5 security protocol. It was initially kept secret, but became public knowledge through leaks and reverse engineering. A number of serious weaknesses in the cipher have been identified.

ISAAC is a cryptographically secure pseudorandom number generator and a stream cipher designed by Robert J. Jenkins Jr. in 1993. The reference implementation source code was dedicated to the public domain.

<span class="mw-page-title-main">XTEA</span> Block cipher

In cryptography, XTEA is a block cipher designed to correct weaknesses in TEA. The cipher's designers were David Wheeler and Roger Needham of the Cambridge Computer Laboratory, and the algorithm was presented in an unpublished technical report in 1997. It is not subject to any patents.

Bart Preneel is a Belgian cryptographer and cryptanalyst. He is a professor at Katholieke Universiteit Leuven, in the COSIC group.

<span class="mw-page-title-main">IDEA NXT</span> Block cipher

In cryptography, the IDEA NXT algorithm is a block cipher designed by Pascal Junod and Serge Vaudenay of EPFL. It was conceived between 2001 and 2003. The project was originally named FOX and was published in 2003. In May 2005, it was announced by MediaCrypt under the name IDEA NXT. IDEA NXT is the successor to the International Data Encryption Algorithm (IDEA) and also uses the Lai–Massey scheme. MediaCrypt AG holds patents on elements of IDEA and IDEA NXT. The cipher is specified in two configurations: NXT64 and NXT128.

<span class="mw-page-title-main">Serge Vaudenay</span> French cryptographer

Serge Vaudenay is a French cryptographer and professor, director of the Communications Systems Section at the École Polytechnique Fédérale de Lausanne

Grain is a stream cipher submitted to eSTREAM in 2004 by Martin Hell, Thomas Johansson and Willi Meier. It has been selected for the final eSTREAM portfolio for Profile 2 by the eSTREAM project. Grain is designed primarily for restricted hardware environments. It accepts an 80-bit key and a 64-bit IV. The specifications do not recommend a maximum length of output per pair. A number of potential weaknesses in the cipher have been identified and corrected in Grain 128a which is now the recommended cipher to use for hardware environments providing both 128bit security and authentication.

In cryptography, Achterbahn is the name of a synchronous stream cipher algorithm submitted to the eSTREAM Project of the eCRYPT network. In the final specification the cipher is called ACHTERBAHN-128/80, because it supports the key lengths of 80 bits and 128 bits, respectively. Achterbahn was developed by Berndt Gammel, Rainer Göttfert and Oliver Kniffler. Achterbahn means rollercoaster, though a literal translation of the term would be eight-track, which indicates that the cipher can encrypt eight bit streams in parallel.

In cryptography, DFC is a symmetric block cipher which was created in 1998 by a group of researchers from École Normale Supérieure, CNRS, and France Télécom and submitted to the AES competition.

In cryptography, COCONUT98 is a block cipher designed by Serge Vaudenay in 1998. It was one of the first concrete applications of Vaudenay's decorrelation theory, designed to be provably secure against differential cryptanalysis, linear cryptanalysis, and even certain types of undiscovered cryptanalytic attacks.

In cryptography, an alternating step generator (ASG) is a cryptographic pseudorandom number generator used in stream ciphers, based on three linear-feedback shift registers. Its output is a combination of two LFSRs which are stepped (clocked) in an alternating fashion, depending on the output of a third LFSR.

In cryptography, partitioning cryptanalysis is a form of cryptanalysis for block ciphers. Developed by Carlo Harpes in 1995, the attack is a generalization of linear cryptanalysis. Harpes originally replaced the bit sums of linear cryptanalysis with more general balanced Boolean functions. He demonstrated a toy cipher that exhibits resistance against ordinary linear cryptanalysis but is susceptible to this sort of partitioning cryptanalysis. In its full generality, partitioning cryptanalysis works by dividing the sets of possible plaintexts and ciphertexts into efficiently-computable partitions such that the distribution of ciphertexts is significantly non-uniform when the plaintexts are chosen uniformly from a given block of the partition. Partitioning cryptanalysis has been shown to be more effective than linear cryptanalysis against variants of DES and CRYPTON. A specific partitioning attack called mod n cryptanalysis uses the congruence classes modulo some integer for partitions.

This article summarizes publicly known attacks against block ciphers and stream ciphers. Note that there are perhaps attacks that are not publicly known, and not all entries may be up to date.

References

  1. ↑ Hermelin, Miia; Kaisa Nyberg (1999). "Correlation Properties of the Bluetooth Combiner". Information Security and Cryptology - ICISC'99 (PDF). Lecture Notes in Computer Science. Vol. 1787. Helsinki, Finland: Nokia Research Centre. pp. 17–29. CiteSeerX   10.1.1.40.9412 . doi:10.1007/10719994_2. ISBN   978-3-540-67380-4.{{cite book}}: |journal= ignored (help)
  2. ↑ Fluhrer, Scott. "Improved key recovery of level 1 of the Bluetooth Encryption" (PostScript). Cisco Systems, Inc.
  3. ↑ Vainio, Juha. "Bluetooth Security" (PDF). Helsinki, Finland: Helsinki University of Technology.{{cite journal}}: Cite journal requires |journal= (help)
  4. ↑ Lu, Yi; Serge Vaudenay (2004). "Cryptanalysis of Bluetooth Keystream Generator Two-Level E0". Advances in Cryptology - ASIACRYPT 2004. Lecture Notes in Computer Science. Vol. 3329. pp. 483–499. doi:10.1007/978-3-540-30539-2_34. ISBN   978-3-540-23975-8.{{cite book}}: |journal= ignored (help)
  5. ↑ Lu, Yi; Serge Vaudenay. "Faster Correlation Attack on Bluetooth Keystream Generator E0" (PDF). Crypto 2004: 407–425.
  6. ↑ Lu, Yi; Meier, Willi; Vaudenay, Serge (2005). "The Conditional Correlation Attack: A Practical Attack on Bluetooth Encryption". Advances in Cryptology – CRYPTO 2005 (PDF). Lecture Notes in Computer Science. Vol. 3621. Santa Barbara, California, USA. pp. 97–117. CiteSeerX   10.1.1.323.9416 . doi:10.1007/11535218_7. ISBN   978-3-540-28114-6.{{cite book}}: |journal= ignored (help)CS1 maint: location missing publisher (link)
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.