Revisit Two Memoryless State-Recovery Cryptanalysis Methods on A5/1

At ASIACRYPT 2019, Zhang proposes a near collision attack on A5/1. He claims that such an attack method can recover the 64-bit A5/1 state with a time complexity around \(2^{32}\) cipher ticks and requires negligible memory complexities. Soon after its proposal, Zhang’s near collision attack is severely challenged by Derbez et al. who claim 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 paper, we study both the guess-and-determine and the near collision attacks for recovering A5/1 states with negligible memory complexities. In order to make a fair comparison, we recover the state \(\boldsymbol{s}^0\) using both methods. We propose a new guessing technique that can construct linear equation filters in a more efficient manner. When evaluating time complexities, we take the filtering strength of the linear equation systems into account making the complexities more convincing. According to our detailed analysis, the new guess-and-determine attack can recover the state \(\boldsymbol{s}^0\) with a time complexity of \(2^{43.91}\) simple operations. The time complexity for the near collision attack is \(2^{50.57}\) simple operations.