International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Fake Near Collisions Attacks

Authors:
Patrick Derbez , Univ Rennes, Centre National de la Recherche Scientifique (CNRS), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Rennes, France
Pierre-Alain Fouque , Univ Rennes, Centre National de la Recherche Scientifique (CNRS), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Rennes, France
Victor Mollimard , Univ Rennes, Centre National de la Recherche Scientifique (CNRS), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Rennes, France
Download:
DOI: 10.46586/tosc.v2020.i4.88-103
URL: https://tosc.iacr.org/index.php/ToSC/article/view/8749
Search ePrint
Search Google
Abstract: 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.
BibTeX
@article{tosc-2020-30778,
  title={Fake Near Collisions Attacks},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2020, Issue 4},
  pages={88-103},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/8749},
  doi={10.46586/tosc.v2020.i4.88-103},
  author={Patrick Derbez and Pierre-Alain Fouque and Victor Mollimard},
  year=2020
}