A time memory trade off attack against A5/1 algorithm

摘要

Two types of attacks against the GSM security algorithm, A5/1, are discussed. The A5/1 system consists of three LFSRs (linear feedback shift registers) which have lengths of 19, 22 and 23 bits respectively. So, the total length of the three registers is 64 bits. The purpose of these attacks is to obtain the initial state of the LFSRs just after the encryption key (Kc) and frame number are loaded, in the light of known plaintext. Both attacks depend on the time-memory attack principle. In other words, the solution space of A5/1, as 2/sup 64/, becomes realizable with M /spl ap/ 2/sup 34.955/ as memory and T /spl ap/ 2/sup 28.365/ as time complexity by distributing the solution space between time and memory optimally.