An algebraic attack to the Bluetooth stream cipher \textsc{E0}
From MaRDI portal
Publication:2081340
Abstract: In this paper we study the security of the Bluetooth stream cipher E0 from the viewpoint it is a "difference stream cipher", that is, it is defined by a system of explicit difference equations over the finite field GF(2). This approach highlights some issues of the Bluetooth encryption such as the invertibility of its state transition map, a special set of 14 bits of its 132-bit state which when guessed implies linear equations among the other bits and finally a small number of spurious keys, with 83 guessed bits, which are compatible with a keystream of about 60 bits. Exploiting these issues, we implement an algebraic attack using Gr"obner bases, SAT solvers and Binary Decision Diagrams. Testing activities suggest that the version based on Gr"obner bases is the best one and it is able to attack E0 in about 2^79 seconds on an Intel i9 CPU. To the best of our knowledge, this work improves any previous attack based on a short keystream, hence fitting with Bluetooth specifications.
Recommendations
Cites work
- A note on Nullstellensatz over finite fields
- Advances in Cryptology - CRYPTO 2003
- Algebraic attacks on stream ciphers with Gröbner bases
- Algebraic Cryptanalysis
- Algebraic Cryptanalysis of the Data Encryption Standard
- Attacking Bivium Using SAT Solvers
- Boolean functions and their applications in cryptography
- Cryptanalysis of the Bluetooth E 0 Cipher Using OBDD’s
- Efficient computation of zero-dimensional Gröbner bases by change of ordering
- Gröbner bases and gradings for partial difference ideals
- scientific article; zbMATH DE number 2009966 (Why is no real title available?)
- scientific article; zbMATH DE number 1515218 (Why is no real title available?)
- scientific article; zbMATH DE number 2085193 (Why is no real title available?)
- scientific article; zbMATH DE number 2086709 (Why is no real title available?)
- scientific article; zbMATH DE number 2086710 (Why is no real title available?)
- Hybrid approach for solving multivariate systems over finite fields
- Logical cryptanalysis as a SAT problem: Encoding and analysis of the U. S. Data Encryption Standard
- Noetherian quotients of the algebra of partial difference polynomials and Gröbner bases of symmetric ideals
- Polynomial automorphisms and the Jacobian conjecture
- Reducing the Space Complexity of BDD-Based Attacks on Keystream Generators
- SINGULAR
- Stream Ciphers
- Stream/block ciphers, difference equations and algebraic attacks
- The Conditional Correlation Attack: A Practical Attack on Bluetooth Encryption
Cited in
(9)- Cryptanalysis of the Bluetooth E 0 Cipher Using OBDD’s
- scientific article; zbMATH DE number 2048526 (Why is no real title available?)
- scientific article; zbMATH DE number 2085193 (Why is no real title available?)
- Advances in Cryptology – CRYPTO 2004
- Cryptanalysis of Bluetooth Keystream Generator Two-Level E0
- A multistep strategy for polynomial system solving over finite fields and a new algebraic attack on the stream cipher Trivium
- An algebraic attack on stream ciphers with application to nonlinear filter generators and WG-PRNG
- Algebraic cryptanalysis of symmetric ciphers: modeling and multistep solving strategies
- Oracle-based multistep strategy for solving polynomial systems over finite fields and algebraic cryptanalysis of the Aradi cipher
This page was built for publication: An algebraic attack to the Bluetooth stream cipher \textsc{E0}
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2081340)
