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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Hindawi-IET
2023-07-01
|
| Series: | IET Information Security |
| Subjects: | |
| Online Access: | https://doi.org/10.1049/ise2.12120 |
| _version_ | 1797417894846398464 |
|---|---|
| author | Yanbin Xu Yonglin Hao Mingxing Wang |
| author_facet | Yanbin Xu Yonglin Hao Mingxing Wang |
| author_sort | Yanbin Xu |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-09T06:25:05Z |
| format | Article |
| id | doaj.art-b4e73d152398493facc24a5303a4e5ce |
| institution | Directory Open Access Journal |
| issn | 1751-8709 1751-8717 |
| language | English |
| last_indexed | 2024-03-09T06:25:05Z |
| publishDate | 2023-07-01 |
| publisher | Hindawi-IET |
| record_format | Article |
| series | IET Information Security |
| spelling | doaj.art-b4e73d152398493facc24a5303a4e5ce2023-12-03T11:24:35ZengHindawi-IETIET Information Security1751-87091751-87172023-07-0117462663810.1049/ise2.12120Revisit two memoryless state‐recovery cryptanalysis methods on A5/1Yanbin Xu0Yonglin Hao1Mingxing Wang2College of Computer Science Sichuan University Chengdu ChinaState Key Laboratory of Cryptology Beijing ChinaState Key Laboratory of Cryptology Beijing ChinaAbstract 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.https://doi.org/10.1049/ise2.12120cryptographytelecommunication security |
| spellingShingle | Yanbin Xu Yonglin Hao Mingxing Wang Revisit two memoryless state‐recovery cryptanalysis methods on A5/1 IET Information Security cryptography telecommunication security |
| title | Revisit two memoryless state‐recovery cryptanalysis methods on A5/1 |
| title_full | Revisit two memoryless state‐recovery cryptanalysis methods on A5/1 |
| title_fullStr | Revisit two memoryless state‐recovery cryptanalysis methods on A5/1 |
| title_full_unstemmed | Revisit two memoryless state‐recovery cryptanalysis methods on A5/1 |
| title_short | Revisit two memoryless state‐recovery cryptanalysis methods on A5/1 |
| title_sort | revisit two memoryless state recovery cryptanalysis methods on a5 1 |
| topic | cryptography telecommunication security |
| url | https://doi.org/10.1049/ise2.12120 |
| work_keys_str_mv | AT yanbinxu revisittwomemorylessstaterecoverycryptanalysismethodsona51 AT yonglinhao revisittwomemorylessstaterecoverycryptanalysismethodsona51 AT mingxingwang revisittwomemorylessstaterecoverycryptanalysismethodsona51 |