Cryptanalysis of GSM Encryption Algorithm A5/1

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 2^39:91and 2^21: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 keystream 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.