Memoryless state-recovery cryptanalysis method for lightweight stream cipher – A5/1

Abstract

Cryptology refers to the discipline concerned with securing communication and data in transit by transforming it into an unintelligible form, thereby preventing interpretation by unauthorized entities. Cryptanalysis is the study and practice of analyzing cryptographic systems with the aim of uncovering their weaknesses, finding vulnerabilities and obtaining unauthorized access to encrypted data. A5/1 is a lightweight stream cipher used to protect GSM communications. There are two memoryless cryptanalysis techniques used for this cipher which are Golic’s Guess-and-determine attack and Zhang’s Near Collision attack. In this paper a new guessing technique called move guessing technique used to construct linear equation filter along with Golic’s guess and determine technique is studied. Two modifications in move guessing technique are proposed for recovery of internal states S0 and S1. Further, a novel algorithm is proposed to select the modification to get minimum time complexity for recovery of internal states S0 and S1. The proposed algorithm gives minimum time complexity of 229.3138 at t = 14 for recovery of S0 state and 243.246 for recovery of S1 at t = 22.