Paper 2023/1557

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

Yanbin Xu, College of Computer Science, Sichuan University, Chengdu 610065, China
Yonglin Hao, State Key Laboratory of Cryptology, Beijing 100878, China
Mingxing Wang, The 6th Research Institute of China Electronics Corporation, Beijing 100083, China, State Key Laboratory of Cryptology, Beijing 100878, China
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 $2^{32}$ cipher ticks with negligible memory requirements. Soon after its proposal, Zhang's near collision attack was severely challenged by Derbez \etal 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 paper, we study both the guess-and-determine and the near collision attacks for recovering A5/1 states with negligible memory complexities. Firstly, we propose a new guessing technique called the \emph{move guessing technique} that can construct linear equation filters in a more efficient manner. Such a technique can be applied to both guess-and-determine and collision attacks for efficiency improvements. Secondly, we take the filtering strength of the linear equation systems into account for complexity analysis. Such filtering strength are evaluated with practical experiments making the complexities more convincing. Based on such new techniques, we are able to give 2 new guess-and-determine attacks on A5/1: the 1st attack recovers the internal state $\vec{s}^0$ with time complexity $2^{43.92}$; the 2nd one recovers a different state $\vec{s}^1$ with complexity $2^{43.25}$. We also revisit Golic's guess-and-determine attack and Zhang's near collision attacks. According to our detailed analysis, the complexity of Golic's $\vec{s}^1$ recovery attack is no lower than $2^{46.04}$, higher than the previously believed $2^{43}$. On the other hand, Zhang's near collision attack recovers $\vec{s}^0$ with the time complexity $2^{53.19}$: such a complexity can be further lowered to $2^{50.78}$ with our move guessing technique.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Published elsewhere. Minor revision. IET Information Security
DOI
10.1049/ise2.12120
Keywords
stream ciphersA5/1guess-and-determinenear collision attack
Contact author(s)
haoyonglin @ yeah net
History
2023-10-11: approved
2023-10-10: received
See all versions
Short URL
https://ia.cr/2023/1557
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1557,
      author = {Yanbin Xu and Yonglin Hao and Mingxing Wang},
      title = {Revisit Two Memoryless State-Recovery Cryptanalysis Methods on A5/1},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1557},
      year = {2023},
      doi = {10.1049/ise2.12120},
      url = {https://eprint.iacr.org/2023/1557}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.