Abstract
In this paper we present a very practical ciphertext-only cryptanalysis of GSM encrypted communication, and various active attacks on the GSM protocols. These attacks can even break into GSM networks that use “unbreakable” ciphers. We describe a ciphertext-only attack on A5/2 that requires a few dozen milliseconds of encrypted off-the-air cellular conversation and finds the correct key in less than a second on a personal computer. We then extend this attack to a (more complex) ciphertext-only attack on A5/1. We describe new attacks on the protocols of networks that use A5/1, A5/3, or even GPRS. These attacks are based on security flaws of the GSM protocols, and work whenever the mobile phone supports A5/2. We emphasize that these attacks are on the protocols, and are thus applicable whenever the cellular phone supports a weak cipher, for instance they are also applicable using the cryptanalysis of A5/1. Unlike previous attacks on GSM that require unrealistic information, like long known plaintext periods, our attacks are very practical and do not require any knowledge of the content of the conversation. These attacks allow attackers to tap conversations and decrypt them either in real-time, or at any later time. We also show active attacks, such as call hijacking, altering of data messages and call theft.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
The 3rd Generation Partnership Project (3GPP), http://www.3gpp.org/
Biham, E., Dunkelman, O.: Cryptanalysis of the A5/1 GSM Stream Cipher. In: Roy, B., Okamoto, E. (eds.) INDOCRYPT 2000. LNCS, vol. 1977, pp. 43–51. Springer, Heidelberg (2000)
Biryukov, A., Shamir, A.: Cryptanalytic Time/Memory/Data Tradeoffs for Stream Ciphers. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 1–13. Springer, Heidelberg (2000)
Biryukov, A., Shamir, A., Wagner, D.: Real Time Cryptanalysis of A5/1 on a PC. In: Schneier, B. (ed.) FSE 2000. LNCS, vol. 1978, pp. 1–18. Springer, Heidelberg (2001)
M. Briceno, I. Goldberg, D. Wagner, A pedagogical implementation of the GSM A5/1 and A5/2 voice privacy encryption algorithms, (1999), http://cryptome.org/gsm-a512.htm , originally on www.scard.org
Briceno, M., Goldberg, I., Wagner, D.: An implementation of the GSM A3A8 algorithm (1998), http://www.iol.ie/~kooltek/a3a8.txt
Briceno, M., Goldberg, I., Wagner, D.: GSM Cloning (1998), http://www.isaac.cs.berkeley.edu/isaac/gsm-faq.html
Courtois, N.: Higher Order Correlation Attacks,XL Algorithm and Cryptanalysis of Toyocrypt. In: Lee, P.J., Lim, C.H. (eds.) ICISC 2002. LNCS, vol. 2587, pp. 182–199. Springer, Heidelberg (2003)
Courtois, N., Klimov, A., Patarin, J., Shamir, A.: Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 392–407. Springer, Heidelberg (2000)
Courtois, N., Pieprzyk, J.: Cryptanalysis of Block Ciphers with Overdefined Systems of Equations. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 267–287. Springer, Heidelberg (2002)
Ekdahl, P., Johansson, T.: Another Attack on A5/1, to be published in IEEE Transactions on Information Theory (2002), http://www.it.lth.se/patrik/publications.html
European Telecommunications Standards Institute (ETSI), Digital cellular telecommunications system (Phase 2+); Security related network functions, TS 100 929 (GSM 03.20), http://www.etsi.org
Goldberg, I., Wagner, D., Green, L.: The (Real-Time) Cryptanalysis of A5/2, presented at the Rump Session of Crypto 1999 (1999)
Golic, J.: Cryptanalysis of Alleged A5 Stream Cipher. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 239–255. Springer, Heidelberg (1997)
Kipnis, A., Shamir, A.: Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 19–30. Springer, Heidelberg (1999)
Security Algorithms Group of Experts (SAGE), Report on the specification and evaluation of the GSM cipher algorithm A5/2 (1996), http://cryptome.org/espy/ETR278e01p.pdf
Petrović, S., Fúster-Sabater, A.: Cryptanalysis of the A5/2 Algorithm, Cryptology ePrint Archive, Report 2000/052 (2000), http://eprint.iacr.org
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Barkan, E., Biham, E., Keller, N. (2003). Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication. In: Boneh, D. (eds) Advances in Cryptology - CRYPTO 2003. CRYPTO 2003. Lecture Notes in Computer Science, vol 2729. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45146-4_35
Download citation
DOI: https://doi.org/10.1007/978-3-540-45146-4_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40674-7
Online ISBN: 978-3-540-45146-4
eBook Packages: Springer Book Archive