Fast Correlation Attacks on Grain-like Small State Stream Ciphers

Authors

  • Bin Zhang TCA Labaratory, State Key Laboratory of Computer Science (SKLCS), Institute of Software, Chinese Academy of Sciences, Beijing, China; State Key Laboratory of Cryptology, P.O.Box 5159, Beijing, 100878, China;University of Chinese Academy of Sciences, Beijing, 100049, China
  • Xinxin Gong TCA Labaratory, State Key Laboratory of Computer Science (SKLCS), Institute of Software, Chinese Academy of Sciences, Beijing, China;State Key Laboratory of Cryptology, P.O.Box 5159, Beijing, 100878, China
  • Willi Meier University of Applied Sciences and Arts Northwestern Switzerland (FHNW), Windisch, Switzerland

DOI:

https://doi.org/10.13154/tosc.v2017.i4.58-81

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

Issue

Section

Articles

How to Cite

Fast Correlation Attacks on Grain-like Small State Stream Ciphers. (2017). IACR Transactions on Symmetric Cryptology, 2017(4), 58-81. https://doi.org/10.13154/tosc.v2017.i4.58-81