Grain (cipher) - Security

Security

The key size is 80 bits and the IV size is specified to be 64 bits. The authors claim that the cipher is designed such that no attack faster than exhaustive key search should be possible, hence the best attack should require a computational complexity not significantly lower than 280.

In the original Grain Version 0.0 specifications, the authors claim: "Grain provides a higher security than several other well known ciphers intended to be used in hardware applications. Well known examples of such ciphers are E0 used in Bluetooth and A5/1 used in GSM. These ciphers, while also having a very small hardware implementation, have been proven to be very insecure. Compared to E0 and A5/1, Grain provides higher security while maintaining a small hardware complexity."

The authors quote the attack against E0 requiring a complexity of 240 and 235 frames (a frame is 2745 bits long). The original Grain Version 0.0 cipher was broken by a key recovery attack which required a complexity of 243 computations and 238 keystream bits to determine the 80-bit key.

In the revised Grain Version 1.0 specifications, the cipher has a slightly revised output function and the NLFSR feedback function received a minor change. The specifications claim: "The filter function is quite small, only 5 variables and nonlinearity 12. However, this is partly compensated by the fact that one of the inputs is taken from the NLFSR. The input bit from the NLFSR will depend nonlinearily on other bits in the state, both from the LFSR and from the NLFSR. The small filter function is also compensated by adding 7 bits linearily from the NLFSR at suitable positions to form the output function."

As of October 2006, no key recovery attacks better than brute force attack are known against Grain Version 1.0.

However, a related key attack was published in September 2006 by Ozgul Kucuk in the paper "Slide Resynchronization Attack on the Initialization of Grain 1.0". The paper claims: "we find related keys and initial values of the stream cipher Grain 1.0. For any (K,IV) pair there exist related (K’,IV’) pair with probability 1/22 that generates 1-bit shifted keystream. Although this does not result in an efficient key recovery attack yet, it indicates a weakness in the initialization which could be overcomed with a little effort."