Paper 2022/016

An algebraic attack to the Bluetooth stream cipher E0

Roberto La Scala, Dipartimento di Matematica, Università degli Studi di Bari
Sergio Polese, Dipartimento di Informatica, Università degli Studi di Milano
Sharwan K. Tiwari, Scientific Analysis Group, Defence Research & Development Organization, Metcalfe House
Andrea Visconti, Dipartimento di Informatica, Università degli Studi di Milano
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öbner bases, SAT solvers and Binary Decision Diagrams. Testing activities suggest that the version based on Gröbner 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.

Note: 24 pages, 1 figure. To appear in Finite Fields and Their Applications.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Finite Field and Their Applications
Keywords
stream ciphers cryptanalysis
Contact author(s)
roberto lascala @ uniba it
sergio polese @ unimi it
shrawant @ gmail com
andrea visconti @ unimi it
History
2022-08-08: revised
2022-01-07: received
See all versions
Short URL
https://ia.cr/2022/016
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/016,
      author = {Roberto La Scala and Sergio Polese and Sharwan K.  Tiwari and Andrea Visconti},
      title = {An algebraic attack to the Bluetooth stream cipher E0},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/016},
      year = {2022},
      url = {https://eprint.iacr.org/2022/016}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.