Cryptanalysis of GSM encryption algorithm A5/1

Document Type: ORIGINAL RESEARCH PAPER

Authors

Abstract

The A5/1 algorithm is one of the most famous stream cipher algorithms used for over-the-air communication privacy in GSM. The purpose of this paper is to analyze several weaknesses of A5/1, including an improvement to an attack and investigation of the A5/1 state transition. Biham and Dunkelman proposed an attack on A5/1 with a time and data complexity of 239.91and 221.1, respectively. In this paper, we propose a method for identification and elimination of useless states from the pre-computed tables and a new approach to access the table in the online phase of the attack which reduces the time complexity to 237.89 and the required memory in half. Furthermore, we discuss another weakness of A5/1 by investigating its internal state transition and its key stream sequence period. Consequently, the internal states are divided into two classes, initially periodic and ultimately periodic. The presented model is verified using a variety of simulations which are consistent with the theoretical results.

Keywords


[1] E. Barkan and E. Biham, "Conditional Estimators: An Effective Attack on A5/1," proceedings of SAC' 05, LNCS 3897, pp. 1-19, Springer-Verlag, 2006.

[2] E. Barkan, E. Biham and N. Keller, "Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication," Journal of Cryptology, Volume 21, Number 3, pp. 392-429, July 2008.

[3] E. Biham and O. Dunkelman, "Cryptanalysis of the A5/1 GSM Stream Cipher," presented by INDOCRYPT 2000, LNCS 1977, pp. 43-51, Springer-Verlag, 2000.

[4] A. Biryukov, A. Shamir and D. Wagner, "Real Time Cryptanalysis of A5/1 on a PC," Advances in Cryptology, proceedings of Fast Software Encryption'00, LNCS 1978, pp. 1-18, Springer-Verlag, 2001.

[5] M. Briceno, I. Goldberg and D. Wagner, "A pedagogical implementation of the GSM A5/1 and A5/2 "voice privacy" encryption algorithms," http://cryptome.org/gsm-a512.htm (originally on www.scard.org), 1999.

[6] P. Ekdahl and T. Johansson, "Another Attack on A5/1," IEEE Transactions on Information Theory, Volume 49, Issue 1, pp. 284-289, 2003.

[7] J. Golić, "Cryptanalysis of Three Mutually Clock-Controlled Stop/Go Shift Registers," Ieee Transactions on Information Theory, VOL. 46, NO. 3, MAY 2000.

[8] J. Keller and Birgit Seitz. "A Hardware-Based Attack on the A5/1 Stream Cipher," In Proceedings of the 2001 Arbeitsplatzcomputer (APC), Munchen, Germany, http://pv.fernunihagen.de/docs/apc2001-final.pdf, 2001.

[9] A. Maximov, Thomas Johansson and Steve Bab-bage, "An improved correlation attack on A5/1," proceedings of SAC'04, LNCS 3357, pp. 1-18, Springer-Verlag, 2005.

[10] T. Pornin and J. Stern, "Software-hardware Trade-offs: Application to A5/1 Cryptanalysis," CHES 2000, LNCS 1965, pp. 318-327, Springer-Verlag, 2000.

[11] E. Zenner, "On the Efficiency of the Clock Control Guessing Attack," ICISC 2002, LNCS 2587, pp. 200-212, Springer-Verlag, 2003.

[12] J. Golić, "Cryptanalysis of Alleged A5 Stream Cipher," Advances in Cryptology, proceedings of Eurocrypt'97, LNCS 1233, pp. 239-255, Springer-Verlag, 1997.

[13] W. G. Chambers, "On random mappings and random permutations," in Fast Software Encryption '94 (Lecture Notes in Computer Science), Berlin, Germany: Springer-Verlag, 1995, vol. 1008, pp. 22-28.