Paper 2018/145

Fast Near Collision Attack on the Grain v1 Stream Cipher

Bin Zhang, Chao Xu, and Willi Meier

Abstract

Modern stream ciphers often adopt a large internal state to resist various attacks, where the cryptanalysts have to deal with a large number of variables when mounting state recovery attacks. In this paper, we propose a general new cryptanalytic method on stream ciphers, called fast near collision attack, to address this situation. It combines a near collision property with the divide-and-conquer strategy so that only subsets of the internal state, associated with different keystream vectors, are recovered first and merged carefully later to retrieve the full large internal state. A self-contained method is introduced and improved to derive the target subset of the internal state from the partial state difference efficiently. As an application, we propose a new key recovery attack on Grain v1, one of the $7$ finalists selected by the eSTREAM project, in the single-key setting. Both the pre-computation and the online phases are tailored according to its internal structure, to provide an attack for any fixed IV in $2^{75.7}$ cipher ticks after the pre-computation of $2^{8.1}$ cipher ticks, given $2^{28}$-bit memory and about $2^{19}$ keystream bits. Practical experiments on Grain v1 itself whenever possible and on a 80-bit reduced version confirmed our results.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in EUROCRYPT 2018
Keywords
CryptanalysisStream ciphersGrainNear collision
Contact author(s)
zhangbin @ tca iscas ac cn
willi meier @ fhnw ch
History
2018-02-08: received
Short URL
https://ia.cr/2018/145
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/145,
      author = {Bin Zhang and Chao Xu and Willi Meier},
      title = {Fast Near Collision Attack on the Grain v1 Stream Cipher},
      howpublished = {Cryptology ePrint Archive, Paper 2018/145},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/145}},
      url = {https://eprint.iacr.org/2018/145}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.