Cryptanalysis Of The A5/1 And A5/2 Encryption Algorithms In GSM

With the rapid development of mobile communication technology today, it is a fact that a large of mobile clients have been widely used. Meanwhile, the security of mobile communications has become a hot spot. Compared with emerging 3G and 4G which are widely used, Global System for Mobile Communications(GSM) is still the most popular communication system. Thus, secure encryption algorithm A5 in GSM becomes the most important part of communication security. The algorithm A5 has three versions: A5/1, A5/2 and A5/3, the first two algorithms are stream cipher encryption algorithms based on linear feedback shift register, and the A5/2 is a simplified version of A5/1. The algorithm A5/3 used in the 3G system differs from them, and it adopts a packet encryption system KASUMI.The popular attack methods exist for algorithm A5/1 are Guess method and space-time tradeoff method. The classic Guess method proposed by Andersons was not widely used because of its high time complexity. Space-time tradeoff method was first proposed by Golic. Nohl release a new space-time tradeoff method with rainbow table, and this method reduced the time complexity obviously. This thesis focus on the space-time tradeoff method with thin rainbow table based on the method proposed by Nohl.This thesis analyzes the attack algorithm based on space-time tradeoff for algorithm A5/1 and proposes an improved algorithm about how to obtain initialized state. The proposed algorithm can solve how to complete attack by using subsequent data of key stream, when the first 64 bits key does not work. Due to the reduction of the status register in the key generation phase, the register state can be reversed by introducing the quad-tree structure. This scheme increases the successful probability of attack by making full use of the key stream.This thesis classifies the consequent data with the difference of frame number when attacking the algorithm A5/2. Based on this method, Kc can be obtained by using consequent eight frames of key stream when attacking the chosen-plaintext. Comparedwith the original algorithm proposed by Barkan, this method simplifies the process of building and solving the equations, reduces the computational complexity and time complexity.