Cryptology ePrint Archive: Report 2021/021

Fake Near Collisions Attacks

Patrick Derbez and 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

Category / Keywords: secret-key cryptography / Fast near collision technique, Reproducibility, Stream cipher

Original Publication (in the same form): IACR-TOSC ISSUE 4-2020

Date: received 6 Jan 2021

Contact author: patrick derbez at irisa fr

Available format(s): PDF | BibTeX Citation

Version: 20210106:214459 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]