Cryptanalysis of Grain using Time / Memory / Data Tradeos
T. E. Bjrstad · 2008
Grain is one of the eight nalists in the hardware category of the eSTREAM stream cipher contest, and has shown itself to be one of the fastest and most compact stream ciphers in the competition. Time / memory / data tradeos are a class of generic attacks that modern stream ciphers should resist. We show that Grain has a low resistance to BSW sampling, leading to tradeos that in the active phase recover the internal state of Grain v1 using O(2 71 ) time and memory, and O(2 53:5 ) bits of known keystream. While the practical signicance of these tradeos may be arguable due to the precomputation costs involved, their existence clearly violate stated design assumptions in the Grain specication, and parallels may be drawn to the similar cryptanalytic results on and the subsequent tweak of MICKEY v1.