Abstract
The Bluetooth standard authorized by IEEE 802.15.1 adopts the two-level E0 stream cipher to protect short range privacy in wireless networks. The best published attack on it at Crypto 2005 requires 238 on-line computations, 238 off-line computations and 233 memory (which amount to about 19-hour, 37-hour and 64GB storage in practice) to restore the original encryption key, given the first 24 bits of 223.8 frames. In this paper, we describe more threatening and real time attacks against two-level E0 based on condition masking, a new cryptanalytic technique that characterizes the conditional correlation attacks on stream ciphers. The idea is to carefully choose the condition to get better tradeoffs on the time/memory/data complexity curve. It is shown that if the first 24 bits of 222.7 frames is available, the secret key can be reliably found with 227 on-line computations, 221.1 off-line computations and 4MB memory. Our attacks have been fully implemented on one core of a single PC. It takes only a few seconds to restore the original encryption key. This is the best known-IV attack on the real Bluetooth encryption scheme so far.
This work was supported by the National Grand Fundamental Research 973 Program of China(Grant No. 2013CB338002), the Strategic Priority Research Program of the Chinese Academy of Sciences (Grant No. XDA06010701), IIE’s Research Project on Cryptography (Grant No. Y3Z0016102) and the programs of the National Natural Science Foundation of China (Grant No. 60833008, 60603018, 61173134, 91118006, 61272476)
Chapter PDF
Similar content being viewed by others
References
Armknecht, F., Krause, M.: Algebraic attacks on combiners with memory. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 162–175. Springer, Heidelberg (2003)
Baignères, T., Junod, P., Vaudenay, S.: How far can we go beyond linear cryptanalysis? In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 432–450. Springer, Heidelberg (2004)
SIG Bluetooth. Specification of the bluetooth system. volume 4.0 (2010)
Canteaut, A., Trabbia, M.: Improved fast correlation attacks using parity-check equations of weight 4 and 5. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 573–588. Springer, Heidelberg (2000)
Chose, P., Joux, A., Mitton, M.: Fast correlation attacks: An algorithmic point of view. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 209–221. Springer, Heidelberg (2002)
Courtois, N.T.: Fast algebraic attacks on stream ciphers with linear feedback. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 176–194. Springer, Heidelberg (2003)
Fluhrer, S.R., Lucks, S.: Analysis of the E0 encryption system. In: Vaudenay, S., Youssef, A.M. (eds.) SAC 2001. LNCS, vol. 2259, pp. 38–48. Springer, Heidelberg (2001)
Fluhrer, S.R., Cisco Systems Inc.: Improved key recovery of level 1 of the bluetooth encryption system. Cambridge University Press (2002), http://eprint.iacr.org/2002/068
Golić, J.: Correlation properties of a general binary combiner with memory. Journal of Cryptology 9, 111–126 (1996)
Golić, J.D., Bagini, V., Morgari, G.: Linear cryptanalysis of bluetooth stream cipher. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 238–255. Springer, Heidelberg (2002)
Hermelin, M., Nyberg, K.: Correlation properties of the bluetooth combiner. In: Song, J.S. (ed.) ICISC 1999. LNCS, vol. 1787, pp. 17–29. Springer, Heidelberg (2000)
Johansson, T., Jönsson, F.: Improved fast correlation attacks on stream ciphers via convolutional codes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 347–362. Springer, Heidelberg (1999)
Johansson, T., Jönsson, F.: Fast correlation attacks through reconstruction of linear polynomials. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 300–315. Springer, Heidelberg (2000)
Krause, M.: BDD-based cryptanalysis of keystream generators. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 222–237. Springer, Heidelberg (2002)
Lee, S., Chee, S., Park, S., Park, S.: Conditional correlation attack on nonlinear filter generators. In: Kim, K.-C., Matsumoto, T. (eds.) ASIACRYPT 1996. LNCS, vol. 1163, pp. 360–367. Springer, Heidelberg (1996)
Löhlein, B.: Attacks based on conditional correlations against the nonlinear filter generator, http://eprint.iacr.org/2003/020
Lu, Y., Meier, W., Vaudenay, S.: The conditional correlation attack: A practical attack on bluetooth encryption. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 97–117. Springer, Heidelberg (2005)
Lu, Y., Vaudenay, S.: Cryptanalysis of bluetooth keystream generator two-level E0. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 483–499. Springer, Heidelberg (2004)
Lu, Y., Vaudenay, S.: Faster correlation attack on bluetooth keystream generator E0. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 407–425. Springer, Heidelberg (2004)
Lu, Y., Vaudenay, S.: Cryptanalysis of an e0-like combiner with memory. Journal of Cryptology 21, 430–457 (2008)
Matsui, M.: Linear cryptanalysis method for DES cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994)
Meier, W., Staffelbach, O.: Fast correlation attacks on certain stream ciphers. Journal of Cryptology 1, 159–176 (1989)
Meier, W., Staffelbach, O.: Correlation properties of combiners with memory in stream ciphers. Journal of Cryptology 5, 67–86 (1992)
Petrakos, N., Dinolt, G.W., Michael, J.B., Stanica, P.: Cube-type algebraic attacks on wireless encryption protocols. Computer 42(10), 103–105 (2009)
Preneel, B.: Stream ciphers: Past, present and future (2010)
Saarinen, M.: Re: Bluetooth and E0. Posting to Sci. Crypt. Research 2(09) (2000)
Shaked, Y., Wool, A.: Cryptanalysis of the bluetooth E0 cipher using oBDD’s. In: Katsikas, S.K., López, J., Backes, M., Gritzalis, S., Preneel, B. (eds.) ISC 2006. LNCS, vol. 4176, pp. 187–202. Springer, Heidelberg (2006)
Siegenthaler, T.: Decrypting a class of stream ciphers using ciphertext only. IEEE Transactions on Computers C-34, 81–85 (1985)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 International Association for Cryptologic Research
About this paper
Cite this paper
Zhang, B., Xu, C., Feng, D. (2013). Real Time Cryptanalysis of Bluetooth Encryption with Condition Masking. In: Canetti, R., Garay, J.A. (eds) Advances in Cryptology – CRYPTO 2013. CRYPTO 2013. Lecture Notes in Computer Science, vol 8042. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40041-4_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-40041-4_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40040-7
Online ISBN: 978-3-642-40041-4
eBook Packages: Computer ScienceComputer Science (R0)