Open AccessFast Correlation Attacks on Grain-like Small State Stream Ciphers
Author(s) -
Bin Zhang,
Xinxin Gong,
Willi Meier
Publication year - 2017
Publication title -
iacr transaction on symmetric cryptology
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.715
H-Index - 10
ISSN - 2519-173X
DOI - 10.46586/tosc.v2017.i4.58-81
Subject(s) - keystream , stream cipher , correlation attack , computer science , key (lock) , state (computer science) , algorithm , cryptography , linear feedback shift register , theoretical computer science , arithmetic , mathematics , computer security , shift register , telecommunications , chip
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.