Zero-knowledge-like Proof of Cryptanalysis of Bluetooth Encryption

Authors: Eric Filiol

Abstract:

This paper presents a protocol aiming at proving that an encryption system contains structural weaknesses without disclosing any information on those weaknesses. A verifier can check in a polynomial time that a given property of the cipher system output has been effectively realized. This property has been chosen by the prover in such a way that it cannot been achieved by known attacks or exhaustive search but only if the prover indeed knows some undisclosed weaknesses that may effectively endanger the cryptosystem security. This protocol has been denoted zero-knowledge-like proof of cryptanalysis. In this paper, we apply this protocol to the Bluetooth core encryption algorithm E0, used in many mobile environments and thus we suggest that its security can seriously be put into question.

Keywords: Bluetooth encryption, Bluetooth security, Bluetoothprotocol, Stream cipher, Zero-knowledge, Cryptanalysis

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1334145

References:

[1] Armknecht, F., Krause, M.: Algebraic Attacks on Combiners with Memory. In Boneh, D. (ed) Advances in Cryptology - CRYPTO-03, LNCS 2729, pp. 162-175, Springer Verlag (2003).
[2] Bleichenbacher, D. (2001), Personal communication in Jakobsson, M., Wetzel S., "Security weaknesses in Bluetooth" in Proc. RSA Security Conf. - Cryptographer-s Track, LNCS 2020, pp. 176-191, Springer- Verlag.
[3] Courtois, N.: Fast Algebraic Attacks on Stream Ciphers with Linear Feedback. In Boneh, D. Advances in Cryptology - CRYPTO-03, LNCS 2729, pp. 176-194, Springer-Verlag, 2003.
[4] Filiol, E.: Computer Viruses: from Theory to Applications. IRIS International Series, Springer Verlag, ISBN 2-287-23939-1, (2005).
[5] Fluhrer, S., Lucks, S.: Analysis of the E0 Encryption System. In Vaudenay, S., Youssef, A. (eds) Selected Areas in Cryptography - SAC 2001, LNCS 2259, pp. 38-48, Springer-Verlag (2001).
[6] Fluhrer, S.: Improved Key Recovery of Level 1 of the Bluetooth Encryption System, available at http://eprint.iacr.org/2002/068, (2002)
[7] Goldreich, O.: Foundations of Cryptography - Basic Tools. Cambridge University Press, Cambridge, (2001).
[8] Goldwasser, S., Micali S., Rackoff C.: The Knowledge-complexity of Interactive Proof Systems. SIAM Journal on Computing, 18, 186-208 (1989).
[9] Golic, J., Bagini, V., Morgani, G.: Linear cryptanalysis of Bluetooth stream cipher. In Knudsen, L. (ed) Advances in Cryptology - EUROCRYPT- 02, LNCS 2332, pp. 238-255, Springer Verlag (2002).
[10] Krause, M.: BDD-based cryptanalysis of keystream generators. In Knudsen, L. (ed) Advances in Cryptology - EUROCRYPT 02, LNCS 2332, pp. 222-237, Springer-Verlag (2002).
[11] Loi pour la confiance en l-'economie num'erique (Law for Confidence in the e-Economy), Journal Officiel, June 22nd, 2004. A detailed presentation of this law as well as comments and legal explanation of this law can be found in English in (4, Chap. 5).
[12] Levy, O., Wool, A.: A Uniform Framework for Cryptanalysis of the Bluetooth E0 Cipher. Available at eprint.iacr.org/2005/107. pdf, (2005).
[13] Lu, Y., Vaudenay, S.: Faster correlation attack on Bluetooth keystream generator E0. In Franklin, M. (ed) Advances in Cryptology - CRYPTO 04, LNCS 3152, pp. 407-425, Springer-Verlag (2004).
[14] Lu, Y., Meier, W., Vaudenay, S.: The Conditional Correlation Attack: A Practical Attack on Bluetooth Encryption. In Shoup, V. (ed) Advances in Cryptology - CRYPTO-05, LNCS 3621, pp. 97-117, Springer Verlag, (2005).
[15] Saarinen, M.-J., "A Software Implementation of the BlueTooth Encryption Algorithm E0". Available at http://www.jyu.fi/˜mjos/ e0.c
[16] Revised NIST Special Publication 88-22: A Statistical Test Suite for the Validation of Ramdom Number Generator and Pseudo-random Number Generator for Cryptographic Applications. National Institute of Standard and Technology, US Commerce Department-s Technology Administration, http://csrc.nist.gov/rng/rng2.html, (2000).
[17] Shaked, Y., Wool, A.: Cracking the Bluetooth PIN. In Proc. 3rd USENIX/ACM Conf. Mobile Systems, Applications, and Services (MobiSys), Seattle, pp. 39-50, ISBN 1-931971-31-5 (2005).
[18] "Specification of the Bluetooth system", v.2.0. Core specification, 2004. Available from http://www.bluetooth.org/foundry/ adopters/document/Core_v2.0_EDR/en/1/Core_v2.0_ EDR.zip
[19] U.S. Copyright Office Summary (1998), "The Digital Millenium Copyright Act of 1998", http://www.copyright.gov/ legislation/dmca.pdf