International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Fast Correlation Attacks on Grain-like Small State Stream Ciphers

Authors:
Bin Zhang , TCA Laboratory, SKLCS, Institute of Software, Chinese Academy of Sciences; State Key Laboratory of Cryptology, P.O.Box 5159; University of Chinese Academy of Sciences, Beijing
Xinxin Gong , TCA Laboratory, SKLCS, Institute of Software, Chinese Academy of Sciences; State Key Laboratory of Cryptology, P.O.Box 5159, Beijing, 100878
Willi Meier , FH Nordwestschweiz
Download:
DOI: 10.13154/tosc.v2017.i4.58-81
URL: https://tosc.iacr.org/index.php/ToSC/article/view/803
Search ePrint
Search Google
Abstract: In this paper, we study the security of Grain-like small state stream ciphers by fast correlation attacks, which are commonly regarded as classical cryptanalytic methods against LFSR-based stream ciphers. We extend the cascaded structure adopted in such primitives in general and show how to restore the full internal state part-by-part if the non-linear combining function meets some characteristic. As a case study, we present a key recovery attack against Fruit, a tweaked version of Sprout that employs key-dependent state updating in the keystream generation phase. Our attack requires 262.8 Fruit encryptions and 222.3 keystream bits to determine the 80-bit secret key. Practical simulations on a small-scale version confirmed our results.
BibTeX
@article{tosc-2017-28467,
  title={Fast Correlation Attacks on Grain-like Small State Stream Ciphers},
  journal={IACR Trans. Symmetric Cryptol.},
  publisher={Ruhr-Universität Bochum},
  volume={2017, Issue 4},
  pages={58-81},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/803},
  doi={10.13154/tosc.v2017.i4.58-81},
  author={Bin Zhang and Xinxin Gong and Willi Meier},
  year=2017
}