Grain (cipher)

Last updated

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 recommend a maximum length of output per (key, iv) pair. A number of potential weaknesses in the cipher have been identified and corrected in Grain 128a which is now the recommended cipher to use for hardware environments providing both 128bit security and authentication.

Contents

Description

Grain's 160-bit internal state consists of an 80-bit linear feedback shift register (LFSR) and an 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, [1] 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 [2] 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 [3] 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, [4] 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[ sic ] 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[ sic ] 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". [5] 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[ sic ] with a little effort."

Related Research Articles

In cryptography, RC4 is a stream cipher. While it is remarkable for its simplicity and speed in software, multiple vulnerabilities have been discovered in RC4, rendering it insecure. It is especially vulnerable when the beginning of the output keystream is not discarded, or when nonrandom or related keys are used. Particularly problematic uses of RC4 have led to very insecure protocols such as WEP.

<span class="mw-page-title-main">Stream cipher</span> Type of symmetric key cipher

A stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream, to give a digit of the ciphertext stream. Since encryption of each digit is dependent on the current state of the cipher, it is also known as state cipher. In practice, a digit is typically a bit and the combining operation is an exclusive-or (XOR).

In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state.

In cryptography, a block cipher mode of operation is an algorithm that uses a block cipher to provide information security such as confidentiality or authenticity. A block cipher by itself is only suitable for the secure cryptographic transformation of one fixed-length group of bits called a block. A mode of operation describes how to repeatedly apply a cipher's single-block operation to securely transform amounts of data larger than a block.

In cryptography, an S-box (substitution-box) is a basic component of symmetric key algorithms which performs substitution. In block ciphers, they are typically used to obscure the relationship between the key and the ciphertext, thus ensuring Shannon's property of confusion. Mathematically, an S-box is a nonlinear vectorial Boolean function.

In cryptography, MUGI is a pseudorandom number generator (PRNG) designed for use as a stream cipher. It was among the cryptographic techniques recommended for Japanese government use by CRYPTREC in 2003, however, has been dropped to "candidate" by CRYPTREC revision in 2013.

A nonlinear-feedback shift register (NLFSR) is a shift register whose input bit is a non-linear function of its previous state.

<span class="mw-page-title-main">VEST</span> Family of stream ciphers

VEST (Very Efficient Substitution Transposition) ciphers are a set of families of general-purpose hardware-dedicated ciphers that support single pass authenticated encryption and can operate as collision-resistant hash functions designed by Sean O'Neil, Benjamin Gittins and Howard Landman. VEST cannot be implemented efficiently in software.

<span class="mw-page-title-main">Trivium (cipher)</span> Stream cipher

Trivium is a synchronous stream cipher designed to provide a flexible trade-off between speed and gate count in hardware, and reasonably efficient software implementation.

Py is a stream cipher submitted to eSTREAM by Eli Biham and Jennifer Seberry. It is one of the fastest eSTREAM candidates at around 2.6 cycles per byte on some platforms. It has a structure a little like RC4, but adds an array of 260 32-bit words which are indexed using a permutation of bytes, and produces 64 bits in each round.

In cryptography, Achterbahn is the name of a synchronous stream cipher algorithm submitted to the eSTREAM Project of the eCRYPT network. In the final specification the cipher is called ACHTERBAHN-128/80, because it supports the key lengths of 80 bits and 128 bits, respectively. Achterbahn was developed by Berndt Gammel, Rainer Göttfert and Oliver Kniffler. Achterbahn means rollercoaster, though a literal translation of the term would be eight-track, which indicates that the cipher can encrypt eight bit streams in parallel.

In cryptography, SOBER is a family of stream ciphers initially designed by Greg Rose of QUALCOMM Australia starting in 1997. The name is a contrived acronym for Seventeen Octet Byte Enabled Register. Initially the cipher was intended as a replacement for broken ciphers in cellular telephony. The ciphers evolved, and other developers joined the project.

In cryptography, an alternating step generator (ASG) is a cryptographic pseudorandom number generator used in stream ciphers, based on three linear-feedback shift registers. Its output is a combination of two LFSRs which are stepped (clocked) in an alternating fashion, depending on the output of a third LFSR.

In cryptography, the QUAD, cipher is a relatively new stream cipher, which was designed with provable security arguments in mind.

<span class="mw-page-title-main">Crypto-1</span> Stream cipher

Crypto1 is a proprietary encryption algorithm and authentication protocol created by NXP Semiconductors for its MIFARE Classic RFID contactless smart cards launched in 1994. Such cards have been used in many notable systems, including Oyster card, CharlieCard and OV-chipkaart.

The cube attack is a method of cryptanalysis applicable to a wide variety of symmetric-key algorithms, published by Itai Dinur and Adi Shamir in a September 2008 preprint.

Correlation attacks are a class of cryptographic known-plaintext attacks for breaking stream ciphers whose keystream is generated by combining the output of several linear-feedback shift registers (LFSRs) using a boolean function. Correlation attacks exploit a statistical weakness arising from the boolean function chosen for the keystream. While some boolean functions are vulnerable to a correlation attack, not all of them are, and stream ciphers generated using them are not inherently insecure.

<span class="mw-page-title-main">Key feedback mode</span> Mode of operation for cryptographic block ciphers

In cryptography key feedback mode (KFB) is a mode of operation for cryptographic block ciphers. It uses the block cipher output block to form the block cipher key of the next round, thereby creating a keystream generator that can be used as a synchronous stream cipher.

In cryptography, Mutual Irregular Clocking KEYstream generator (MICKEY) is a stream cipher algorithm developed by Steve Babbage and Matthew Dodd. The cipher is designed to be used in hardware platforms with limited resources, and was one of the three ciphers accepted into Profile 2 of the eSTREAM portfolio. The algorithm is not patented and is free for any use.

The Grain 128a stream cipher was first purposed at Symmetric Key Encryption Workshop (SKEW) in 2011 as an improvement of the predecessor Grain 128, which added security enhancements and optional message authentication using the Encrypt & MAC approach. One of the important features of the Grain family is that the throughput can be increased at the expense of additional hardware. Grain 128a is designed by Martin Ågren, Martin Hell, Thomas Johansson and Willi Meier.

References

  1. ↑ Martin Hell, Thomas Johansson, Willi Meier (2005-04-29). "Grain - A Stream Cipher for Constrained Environments" (PDF). eSTREAM.{{cite web}}: CS1 maint: multiple names: authors list (link)
  2. ↑ Yi Lu, http://lasecwww.epfl.ch/~vaudenay/ (2004). "Cryptanalysis of Bluetooth Keystream Generator Two-Level E0" (PDF). Advances in Cryptology - Asiacrypt 2004, LNCS vol. 3329, pp.483-499, Springer, 2004.
  3. ↑ Côme Berbain, Henri Gilbert, Alexander Maximov (2006-01-02). "Cryptanalysis of Grain" (PDF). eSTREAM.{{cite web}}: CS1 maint: multiple names: authors list (link)
  4. ↑ Martin Hell, Thomas Johansson, Willi Meier (2006). "Grain - A Stream Cipher for Constrained Environments" (PDF). eSTREAM.{{cite web}}: CS1 maint: multiple names: authors list (link)
  5. ↑ Ozgul Kucuk (2006-07-16). "Slide Resynchronization Attack on the Initialization of Grain 1.0" (PS). eSTREAM.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.