Paper 2021/021

Fake Near Collisions Attacks

Patrick Derbez, Pierre-Alain Fouque, and Victor Mollimard


Fast Near collision attacks on the stream ciphers Grain v1 and A5/1 were presented at Eurocrypt 2018 and Asiacrypt 2019 respectively. They use the fact that the entire internal state can be split into two parts so that the second part can be recovered from the first one which can be found using the keystream prefix and some guesses of the key materials. In this paper we reevaluate the complexity of these attacks and show that actually they are inferior to previously known results. Basically, we show that their complexity is actually much higher and we point out the main problems of these papers based on information theoretic ideas. We also check that some distributions do not have the predicted entropy loss claimed by the authors. Checking cryptographic attacks with galactic complexity is difficult in general. In particular, as these attacks involve many steps it is hard to identify precisely where the attacks are flawed. But for the attack against A5/1, it could have been avoided if the author had provided a full experiment of its attack since the overall claimed complexity was lower than 232 in both time and memory

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. IACR-TOSC ISSUE 4-2020
Fast near collision techniqueReproducibilityStream cipher
Contact author(s)
patrick derbez @ irisa fr
2021-01-06: received
Short URL
Creative Commons Attribution


      author = {Patrick Derbez and Pierre-Alain Fouque and Victor Mollimard},
      title = {Fake Near Collisions Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2021/021},
      year = {2021},
      doi = {10.46586/tosc.v2020.i4.88-103},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.