Paper 2021/021
Fake Near Collisions Attacks
Patrick Derbez, Pierre-Alain Fouque, and Victor Mollimard
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
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Published elsewhere. IACR-TOSC ISSUE 4-2020
- DOI
- 10.46586/tosc.v2020.i4.88-103
- Keywords
- Fast near collision techniqueReproducibilityStream cipher
- Contact author(s)
- patrick derbez @ irisa fr
- History
- 2021-01-06: received
- Short URL
- https://ia.cr/2021/021
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/021,
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},
url = {https://eprint.iacr.org/2021/021}
}
