IACR News item: 30 June 2014
Pratish Datta, Dibyendu Roy, Sourav Mukhopadhyay
ePrint Reportv1 to the estream call for stream cipher proposals and it also became one estream nalists in the
hardware category. The output function of Grain v1 connects its 160 bits internal state divided
equally between an LFSR and an NFSR, using a non-linear lter function in a complex way. Over
the last years many cryptanalyst identied several weaknesses in Grain v1. As a result in 2011 the
inventors modied Grain v1 and published a new version of Grain named Grain-128a which has
a similar structure as Grain v1 but with a 256 bits internal state with an optional authentication
is the latest version of Grain family resisting all known attacks on Grain v1. However both these
ciphers are quite resistant against the classical algebraic attack due to the rapid growth of the degree
of the key-stream equations in subsequent clockings caused by the NFSR. This paper presents a
probabilistic algebraic attack on both these Grain versions. The basic idea of our attack is to
develop separate probabilistic equations for the LFSR and the NFSR bits from each key-stream
equations. Surprisingly it turns out that in case of Grain-128a our proposed equations hold with all
most sure probability, which makes the sure retrieval of the LFSR bits. We also outline a technique
to reduce the growth of degree of the equations involving the NFSR bits for Grain v1. Further
we high light that the concept of probabilistic algebraic attack as proposed in this paper can be
considered as a generic attack strategy against any stream cipher having similar structure of the
output function as in case of the Grain family.
Additional news items may be found on the IACR news page.