Grain (cipher)
Encyclopedia
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.
(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."
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 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 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 with a little effort."
Stream cipher
In cryptography, a stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream . In a stream cipher the plaintext digits are encrypted one at a time, and the transformation of successive digits varies during the encryption...
submitted to eSTREAM
ESTREAM
eSTREAM is a project to "identify new stream ciphers suitable for widespread adoption", organised by the EU ECRYPT network. It was set up as a result of the failure of all six stream ciphers submitted to the NESSIE project. The call for primitives was first issued in November 2004. The project was...
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
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
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 registerLinear feedback shift register
A linear feedback shift register is a shift register whose input bit is a linear function of its previous state.The most commonly used linear function of single bits is XOR...
(LFSR) and a 80-bit non-linear feedback shift register
NLFSR
A NLFSR is a common component in modern stream ciphers, especially in RFID and smartcard applications. NLFSRs are known to be more resistant to cryptanalytic attacks than Linear Feedback Shift Registers , although construction of large NLFSRs with guaranteed long periods remains an open...
(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
Keystream
In cryptography, a keystream is a stream of random or pseudorandom characters that are combined with a plaintext message to produce an encrypted message ....
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, 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
E0 (cipher)
E0 is a stream cipher used in the Bluetooth protocol. It generates a sequence of pseudorandom numbers and combines it with the data using the XOR operator. The key length may vary, but is generally 128 bits.-Description:...
used in Bluetooth
Bluetooth
Bluetooth is a proprietary open wireless technology standard for exchanging data over short distances from fixed and mobile devices, creating personal area networks with high levels of security...
and A5/1
A5/1
A5/1 is a stream cipher used to provide over-the-air communication privacy in the GSM cellular telephone standard. It was initially kept secret, but became public knowledge through leaks and reverse engineering. A number of serious weaknesses in the cipher have been identified.-History and...
used in GSM. These ciphers, while also having a very small hardware implementation, have been proven to be very insecure. Compared to E0
E0 (cipher)
E0 is a stream cipher used in the Bluetooth protocol. It generates a sequence of pseudorandom numbers and combines it with the data using the XOR operator. The key length may vary, but is generally 128 bits.-Description:...
and A5/1
A5/1
A5/1 is a stream cipher used to provide over-the-air communication privacy in the GSM cellular telephone standard. It was initially kept secret, but became public knowledge through leaks and reverse engineering. A number of serious weaknesses in the cipher have been identified.-History and...
, Grain provides higher security while maintaining a small hardware complexity."
The authors quote the attack against E0
E0 (cipher)
E0 is a stream cipher used in the Bluetooth protocol. It generates a sequence of pseudorandom numbers and combines it with the data using the XOR operator. The key length may vary, but is generally 128 bits.-Description:...
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 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 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 with a little effort."