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 279 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.

An algebraic attack to the Bluetooth stream cipher E0 / R. La Scala, S. Polese, S.K. Tiwari, A. Visconti. - In: FINITE FIELDS AND THEIR APPLICATIONS. - ISSN 1071-5797. - 84:(2022 Dec), pp. 102102.1-102102.29. [10.1016/j.ffa.2022.102102]

An algebraic attack to the Bluetooth stream cipher E0

S. Polese;A. Visconti
Ultimo
2022

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 279 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.
stream ciphers; algebraic difference equations; Gröbner bases
Settore INF/01 - Informatica
Settore MAT/02 - Algebra
   Piano di Sostegno alla Ricerca 2015-2017 - Linea 2 "Dotazione annuale per attività istituzionali" (anno 2020)
   UNIVERSITA' DEGLI STUDI DI MILANO
dic-2022
23-ago-2022
Article (author)
File in questo prodotto:
File Dimensione Formato  
IACR_2022-016.pdf

accesso aperto

Tipologia: Pre-print (manoscritto inviato all'editore)
Dimensione 402.66 kB
Formato Adobe PDF
402.66 kB Adobe PDF Visualizza/Apri
1-s2.0-S1071579722001113-main.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 430.6 kB
Formato Adobe PDF
430.6 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/937526
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 3
social impact