Paper 2014/971

Key recovery attacks on Grain family using BSW sampling and certain weaknesses of the filtering function

Y. Wei, E. Pasalic, F. Zhang, and W. Wu

Abstract

A novel internal state recovery attack on the whole Grain family of ciphers is proposed in this work. It basically uses the ideas of BSW sampling along with employing a weak placement of the tap positions of the driving LFSRs. The currently best known complexity trade-offs are obtained, and due to the structure of Grain family these attacks are also key recovery attacks. It is shown that the internal state of Grain-v1 can be recovered with the time complexity of about $2^{66}$ operations using a memory of about $2^{58.91}$ bits, assuming availability of $2^{45}$ keystream sequences each of length $2^{49}$ bits generated for different initial values. Moreover, for Grain-128 or Grain-128a, the attack requires about $2^{105}$ operations using a memory of about $2^{82.59}$ bits, assuming availability of $2^{75}$ keystream sequences each of length $2^{76}$ bits generated for different initial values. These results further show that the whole Grain family, due to the choice of tap positions mainly, does not provide enough security margins against internal state recovery attacks. A simple modification of the selection of the tap positions, as a countermeasure against the attacks described here, is given.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint.
Contact author(s)
enes pasalic6 @ gmail com
History
2014-11-28: received
Short URL
https://ia.cr/2014/971
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/971,
      author = {Y.  Wei and E.  Pasalic and F.  Zhang and W.  Wu},
      title = {Key recovery attacks on Grain family using BSW sampling  and certain weaknesses of the filtering function},
      howpublished = {Cryptology ePrint Archive, Paper 2014/971},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/971}},
      url = {https://eprint.iacr.org/2014/971}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.