Zero-knowledge-like Proof of Cryptanalysis of Bluetooth Encryption
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.
[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
[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
@article{"International Journal of Information, Control and Computer Sciences:56706", author = "Eric Filiol", title = "Zero-knowledge-like Proof of Cryptanalysis of Bluetooth Encryption", 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", volume = "1", number = "8", pages = "2488-9", }
