Grain (cipher)


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

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 240 and 235 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 243 computations and 238 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]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Grain (disambiguation) — Grain refers to course particles (e.g. grain of sand , grain of salt ): *Grain is the small, hard, fruits or seeds of arable crops. Commonly grasses (see caryopsis, Cereals). *Film grain, the gritty texture sometimes apparent on images produced… …   Wikipedia

  • Grain — симметричный алгоритм синхронного потокового шифрования, ориентированный, в первую очередь на аппаратную реализацию. Шифр представлен на конкурсе eSTREAM в 2004 году Мартином Хеллом, Томасом Юханссоном и Вилли Мейером. Алгоритм стал одним из… …   Википедия

  • Stream cipher — The operation of the keystream generator in A5/1, a LFSR based stream cipher used to encrypt mobile phone conversations. In cryptography, a stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher… …   Wikipedia

  • Dragon (cipher) — Dragon is a stream cipher developed at the Information Security Institute by Ed Dawson, Kevin Chen, Matt Henricksen, William Millan, Leonie Simpson, HoonJae Lee, and SangJae Moon. The cipher is a Phase 3 Focus candidate for the eSTREAM project.… …   Wikipedia

  • Stream-cipher — Stromverschlüsselung (engl. stream cipher) ist ein kryptographischer Algorithmus, bei dem Zeichen des Klartextes mit den Zeichen eines Schlüsselstroms einzeln (XOR bei nur zwei verschiedenen Zeichen) verknüpft werden. Der Schlüsselstrom ist eine… …   Deutsch Wikipedia

  • NLS (cipher) — In cryptography, NLS is a stream cypher algorithm designed by Gregory Rose, Philip Hawkes, MIchael Paddon, and Miriam Wiggers de Vries. It has been submitted to the eSTREAM Project of the eCRYPT network …   Wikipedia

  • eSTREAM — eSTREAM  проект по выявлению новых поточных шифров, пригодных для широкого применения, организованный ЕС. Был начат после взлома всех 6 шифров, предложенных в проекте NESSIE. Условия приёма алгоритмов впервые были опубликованы в… …   Википедия

  • VEST — High Level Structure of VEST General Designers Sean O Neil First published June 13, 2005 Cipher deta …   Wikipedia

  • Correlation attack — In cryptography, correlation attacks are a class of known plaintext attacks for breaking stream ciphers whose keystream is generated by combining the output of several linear feedback shift registers (called LFSRs for the rest of this article)… …   Wikipedia

  • Bent function — The 2 ary bent functions with Hamming weight 1 Their nonlinearity is …   Wikipedia