Fast Correlation Attacks on Grain-like Small State Stream Ciphers

  • 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
Keywords: Cryptanalysis, Stream ciphers, Fast correlation attacks, Linear approximation, Fruit

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.
Published
2017-12-15
How to Cite
Zhang, B., Gong, X., & Meier, W. (2017). Fast Correlation Attacks on Grain-like Small State Stream Ciphers. IACR Transactions on Symmetric Cryptology, 2017(4), 58-81. https://doi.org/10.13154/tosc.v2017.i4.58-81
Section
Articles