International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 30 June 2014

Pratish Datta, Dibyendu Roy, Sourav Mukhopadhyay
ePrint Report ePrint Report
In 2005, Hell, Johansson and Meier submitted a stream cipher proposal named Grain

v1 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.

Expand

Additional news items may be found on the IACR news page.