Grain (cipher)

Grain is a stream cipher submitted to eSTREAM in 2004 by Martin Hell, Thomas Johansson and Willi Meier. It has been selected for the final eSTREAM portfolio for Profile 2 by the eSTREAM project. Grain is designed primarily for restricted hardware environments. It accepts an 80-bit key and a 64-bit IV. The specifications do not recommended a maximum length of output per (key, iv) pair. A number of potential weaknesses in the cipher have been identified.

Description

Grains' 160-bit internal state consists of an 80-bit linear feedback shift register (LFSR) and a 80-bit non-linear feedback shift register (NLFSR). Grain updates one bit of LFSR and one bit of NLFSR state for every bit of ciphertext released by a nonlinear filter function. The 80-bit NLFSR is updated with a nonlinear 5-to-1 Boolean function and a 1 bit linear input selected from the LFSR. The nonlinear 5-to-1 function takes as input 5 bits of the NLFSR state. The 80-bit LFSR is updated with a 6-to-1 linear function. During keying operations the output of the cipher is additionally fed-back as linear inputs into both the NLFSR and LFSR update functions. In the original Grain Version 0.0 submission of Grain, one bit of the 80-bit NLFSR and four bits of the 80-bit LFSR are supplied to a nonlinear 5-to-1 Boolean function (that is chosen to be balanced, correlation immune of the first order and has algebraic degree 3) and the output is linearly combined with 1 bit of the 80-bit NLFSR and released as output.

In the updated Grain Version 1.0 submission of Grain, one bit of the 80-bit NLFSR and four bits of the 80-bit LFSR are supplied to a (slightly revised) nonlinear 5-to-1 Boolean function and the output is linearly combined with 7 bits of the 80-bit NLFSR and released as output.

To initialize the cipher, the 80-bit key is loaded directly into the 80-bits NLFSR and the 64-bit IV is loaded into the low 64-bits of the LFSR and the remaining 16 high bits of the LFSR are filled with ones. The cipher is sealed for 160 rounds where the 160 bits of keystream generated are fed-back linearly into both the LFSR and NLFSR update functions. The cipher releases no keystream output during the initialization process. Grain's authors discuss the complete diffusion rates of Grain initialization process in the Grain Version 1.0 specifications: "For initialization with two different IVs, differing by only one bit, the probability that a shift register bit is the same for both initializations should be close to 0.5. Simulations show that this is achieved after 160 clockings."

Performance

The cipher is designed to allow up to 16 rounds to be carried out in parallel, allowing faster implementations at the cost of greater hardware use.

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 2⁸⁰.

In the original Grain Version 0.0 specifications [cite paper
author = Martin Hell, Thomas Johansson, Willi Meier
title = Grain - A Stream Cipher for Constrained Environments
publisher = eSTREAM
date = 2005-04-29
url = http://www.ecrypt.eu.org/stream/ciphers/grain/grain.pdf
format = PDF] 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 [cite paper
author = Yi Lu, http://lasecwww.epfl.ch/~vaudenay/
title = Cryptanalysis of Bluetooth Keystream Generator Two-Level E0
publisher = Advances in Cryptology - Asiacrypt 2004, LNCS vol. 3329, pp.483-499, Springer, 2004
date = 2004
url = http://lasecwww.epfl.ch/pub/lasec/doc/YV04b.pdf
format = PDF] requiring a complexity of 2⁴⁰ and 2³⁵ frames (a frame is 2745 bits long). The original Grain Version 0.0 cipher was broken by a key recovery attack [cite paper
author = Côme Berbain, Henri Gilbert, Alexander Maximov
title = Cryptanalysis of Grain
publisher = eSTREAM
date = 2006-01-02
url = http://www.ecrypt.eu.org/stream/papersdir/2006/019.pdf
format = PDF] which required a complexity of 2⁴³ computations and 2^{38 keystream bits to determine the 80-bit key.}

In the revised Grain Version 1.0 specifications [cite paper
author = Martin Hell, Thomas Johansson, Willi Meier
title = Grain - A Stream Cipher for Constrained Environments
publisher = eSTREAM
date = 2006
url = http://www.ecrypt.eu.org/stream/p2ciphers/grain/Grain_p2.pdf
format = PDF] , 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" [cite paper
author = Ozgul Kucuk
title = Slide Resynchronization Attack on the Initialization of Grain 1.0
publisher = eSTREAM
date = 2006-07-16
url = http://www.ecrypt.eu.org/stream/papersdir/2006/044.ps
format = PS] . 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."

References

External links

* [http://www.ecrypt.eu.org/stream/grainp2.html eSTREAM page on Grain]