Cryptanalysis of GSM encryption algorithm A5/1

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 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 2^37.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.