Revisit two memoryless state‐recovery cryptanalysis methods on A5/1

Abstract At ASIACRYPT 2019, Zhang proposed a near collision attack on A5/1 claiming to recover the 64‐bit A5/1 state with a time complexity around 232 cipher ticks with negligible memory requirements. Soon after its proposal, Zhang's near collision attack was severely challenged by Derbez et al. who claimed that Zhang's attack cannot have a time complexity lower than Golic's memoryless guess‐and‐determine attack dating back to EUROCRYPT 1997. In this article, both the guess‐and‐determine and the near collision attacks for recovering A5/1 states with negligible memory complexities are studied. Firstly, a new guessing technique called the move guessing technique that can construct linear equation filters in a more efficient manner is proposed. Such a technique can be applied to both guess‐and‐determine and collision attacks for efficiency improvements. Secondly, the filtering strength of the linear equation systems is taken into account for complexity analysis. Such filtering strength are evaluated with practical experiments making the complexities more convincing. Based on such new techniques, the authors are able to give 2 new guess‐and‐determine attacks on A5/1: the 1st attack recovers the internal state s0 ${oldsymbol{s}}^{0}$ with time complexity 243.92; the 2nd one recovers a different state s1 ${oldsymbol{s}}^{1}$ with complexity 243.25. Golic's guess‐and‐determine attack and Zhang's near collision attacks are revisited. According to our detailed analysis, the complexity of Golic's s1 ${oldsymbol{s}}^{1}$ recovery attack is no lower than 246.04, higher than the previously believed 243. On the other hand, Zhang's near collision attack recovers s0 ${oldsymbol{s}}^{0}$ with the time complexity 253.19: such a complexity can be further lowered to 250.78 with our move guessing technique.