Cryptology ePrint Archive: Report 2002/191

A Linearization Attack on the Bluetooth Key Stream Generator

Frederik Armknecht

Abstract: In this paper we propose an attack on the key stream generator underlying the encryption system $E_0$ used in the Bluetooth specification. We show that the initial value can be recovered by solving a system of nonlinear equations of degree 4 over the finite field GF(2). This system of equations can be transformed by linearization into a system of linear equations with at most $2^{24.056}$ unknowns. To our knowledge, this is the best attack on the key stream generator underlying the $\mbox{E}_0$ yet.

Category / Keywords: secret-key cryptography / stream cipher, Bluetooth, linearization attack, XL algorithm, XSL algorithm

Date: received 13 Dec 2002

Contact author: armknecht at th informatik uni-mannheim de

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Version: 20030818:135951 (All versions of this report)

Short URL: ia.cr/2002/191

Discussion forum: Show discussion | Start new discussion