[SC] 8. Stream ciphers: Grain

Introduction

Grain is a stream cipher pruposed and submitted to eSTREAM project by Martin Hell, Thomas Johansson and Willi Meier in 2004.It has been selected for the final eSTREAM portfolio for Profile 2 by the eSTREAM project.

Grain is designed for very restricted hardware environments, such as RFID tags.

The cipher is based on Linear Feedback Shift Register (LFSR) and non-linear feedback shift register (NFSR).

Background

Actually exists a need of cryptographic systems that have a low hardware complexity. Per example, a RFID tag has a very limited amount of resources; it's a microchip capable of transmiting a sequence after a request from the reader.

There are serveral aplications for RFID tags, mostly, card-based authentication systems. The information transmitted between the card and the readers can be hacked easily because there isn't a system that protects the information during its transmission.

Devasting consequences could happen if the RFID tags were implemented, seriously, in electronic payments and hence.

Today, the implementation of AES and DES on an RFID tag is not feasible due to the expensive hardware cost (the large number of logical gates, gate equivalent).

And we can take so much more other examples, such as, bluetooth and NFC modules, microchips, sim cards, memory cards, etc.

Grain is a stream cipher designed to be very simple and small to implement in hardware.

Grain provides a higher security than other ciphers intended to be used in hardware applications, such as 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.

Specification

Grain is based in three main blocks:

• A 80-bit linear feedback shift register
• A 80-bit nonlinear feedback shift register
• A nonlinear filtering function. 

Grain is initialized with the 80-bit key K and the 64-bit initialization value IV . The cipher output is an L-bit keystream sequence (z_t) t = 0,...,L−1.

The current LFSR content is denoted by S_t+80 = (s_t, s_t+1, . . . , s_t+79).

The feedback polynomial of the LFSR, f(x) is a primitive polynomial of degree 80. It is defined as:

f(x) = 1 ⊕ x¹⁸ ⊕ x²⁹ ⊕ x⁴² ⊕ x⁵⁷ ⊕ x⁶⁷ ⊕ x⁸⁰

The update function of LFSR is governed by the linear recurrence:

s_t+80 = s_t+62 ⊕ s_t+51 ⊕ s_t+38 ⊕ s_t+23 ⊕ s_t+13 ⊕ s_t

The current NFSR content is denoted by B_t+80 = (b_t, b_t+1, . . . , b_t+79).
The feedback polynomial of the NFSR, g(x), is defined as:

g(x) = 1 ⊕ x¹⁷ ⊕ x²⁰ ⊕ x²⁸ ⊕ x³⁵ ⊕ x⁴³ ⊕ x⁴⁷ ⊕ x⁵² ⊕ x⁵⁹ ⊕ x⁶⁵ ⊕ x⁷¹ ⊕ x⁸⁰ ⊕ x¹⁷x²⁰ ⊕ x⁴³x⁴⁷ ⊕ x⁶⁵x⁷¹ ⊕ x²⁰x²⁸x³⁵ ⊕ x⁴⁷x⁵²x⁵⁹ ⊕ x¹⁷x³⁵x⁵²x⁷¹ ⊕ x²⁰x²⁸x⁴³x⁴⁷ ⊕ x¹⁷x²⁰x⁵⁹x⁶⁵ ⊕ x¹⁷x²⁰x²⁸x³⁵x⁴³ ⊕ x⁴⁷x⁵²x⁵⁹x⁶⁵x⁷¹ ⊕ x²⁸x³⁵x⁴³x⁴⁷x⁵²x⁵⁹

 The NFSR feedback is disturbed by the output of the LFSR, so that the NFSR content is governed by the recurrence:

b_t+80 = s_t ⊕ g(b_t, b_t+1, . . . , b_t+79)

where:

g(b_t, b_t+1, . . . , b_t+79) = b_t+63 ⊕ b_t+60 ⊕ b_t+52 ⊕ b_t+45 ⊕ b_t+37 ⊕ b_t+33 ⊕ b_t+28⊕ b_t+21 ⊕ b_t+15 ⊕ b_t+9 ⊕ b_t ⊕ b_t+63b_t+60 ⊕ b_t+37b_t+33 ⊕ b_t+15b_t+9 ⊕ b_t+60b_t+52b_t+45 ⊕ b_t+33b_t+28b_t+21 ⊕ b_t+63b_t+45b_t+28b_t+9 ⊕ b_t+60b_t+52b_t+37b_t+33 ⊕ b_t+63b_t+60b_t+21b_t+15 ⊕ b_t+63b_t+60b_t+52b_t+45b_t+37 ⊕ b_t+33b_t+28b_t+21b_t+15b_t+9 ⊕ b_t+52b_t+45b_t+37b_t+33b_t+28b_t+21

The contents of the two shift registers represent a state of the cipher. The cipher output bit is derived from these states; 5 variables (x0, x1, x2, x3, x4) are taken as input to a boolean function, h(x), the bits are s_t+3, s_t+25, s_t+46, s_t+64 and b_t+63

This filter function is chosen to be balanced, correlation immune of the first order and has algebraic degree 3. The function is defined as:

h(x) = x1 ⊕ x4 ⊕ x0x3 ⊕ x2x3 ⊕ x3x4 ⊕ x0x1x2 ⊕ x0x2x3 ⊕ x0x2x4 ⊕ x1x2x4 ⊕ x2x3x4

Finally, we take take the output of the NFSR and the output of h(x), apply xor with both values to obtain a bit of the keystream.

The  keystream is combined with the plaintext using XOR operation to obtain ciphertext.

Grain, from http://www.ecrypt.eu.org/stream/p3ciphers/grain/Grain_p3.pdf

Key Initialization

Before generate a keystream, the cipher must be initialized with the key and an iniatialization vector (IV), the process as the follows:

• Put the 80-bit length key in the NFSR
• Put the 64-bit length IV in LFSR
• Fill the remaining 16 bits of the LFSR with ones.
• Clock the cipher at 160 cycles.
• Run the cipher.
• The output of the cipher must be xored with the input of both NFSR and LFSR.

Grain, from http://www.ecrypt.eu.org/stream/p3ciphers/grain/Grain_p3.pdf

Vulnerabilities and proposed solutions

From "Grain - A Stream Cipher for Constrained Environments"

There are several vulnerabilities found in Grain cipher, such as:

• "Correlations: Due to the statistical properties of maximum-length LFSR sequences, the bits in the LFSR are (almost) exactly balanced. This may not be the case for a NFSR when it is driven autonomously. However, as the feedback g(x) is xored with a LFSR-state, the bits in the NFSR are balanced. Moreover, recall that g is a balanced function. Therefore, the bits in the NFSR may be assumed to be uncorrelated to the LFSR bits. The function h is chosen to be correlation immune of first order. This does not preclude that there are correlations of the output of h(x) to sums of inputs. As one input comes from the NFSR and as h(x) is xored with a state bit of the NFSR, correlations of the output of the generator to sums of LFSR-bits will be so small that they will not be exploitable by (fast) correlation attacks."




• "Algebraic Attack: A filter generator alone with output function h(x) of degree only three would be very vulnerable to algebraic attacks. On the other hand, algebraic attacks will not work for solving for the initial 160-bit state of the full generator, as the update function of the NFSR is nonlinear, and the later state bits of the NFSR as a function of the inital state bits will have varying but large algebraic degree. Using key initialization, it may be possible to express the output of the generator as a function of state bits of the LFSR alone. As the filter function h(x) has one input coming from the NFSR, and h(x) is xored with a NFSR-state bit, the algebraic degrees of the output bits when expressed as a function of LFSR-bits, are large in general, and varying in time. This will defeat algebraic attacks."




• "Time/Memory/Data Tradeoff Attack: The cost of time/memory/data tradeoff attacks on stream ciphers is O(2^n/2), where n is the number of inner states of the stream cipher. To obey the margins set by this attack, n = 160 has been chosen. It is known that stream ciphers with low sampling resistance have tradeoff attacks with fewer table lookups and a wider choice of parameters. The sampling resistance of h(x) is reasonable:
• This function does not become linear in the remaining variables by fixing less than 3 of its 5 variables. Similarly, the variables occuring in monomials of g(x) are sufficiently disjoint. Hence the resulting sampling resistance is large, and thus time/memory/data tradeoff attacks are expected to have complexity not lower than O(2⁸⁰)."

References

http://events.iaik.tugraz.at/RFIDandLightweightCrypto05/RFID-SlidesandProceedings/Johansson-Grain.pdf

http://edipermadi.wordpress.com/tag/nfsr/

http://edipermadi.files.wordpress.com/2008/06/grain-spec.pdf

http://www.ecrypt.eu.org/stream/e2-grain.html

http://www.iacr.org/cryptodb/archive/2006/FSE/3235/3235.pdf
http://en.wikipedia.org/wiki/Linear_feedback_shift_register
http://cacr.uwaterloo.ca/techreports/2011/cacr2011-08.pdf