The Grain Stream Cipher Family

The Grain Stream Cipher Family

Introduction

Grain is a family of stream ciphers built for the smallest chips. Each member has two shift registers of the same length. One is a linear feedback shift register, or LFSR, and the other is a nonlinear feedback shift register, or NFSR. A filter function reads a few bits from each and produces one keystream bit per clock.

This guide covers the two classic members. Grain v1 has an 80-bit key and a 64-bit IV. Grain-128 has a 128-bit key and a 96-bit IV. Both have a small hardware footprint, and both can be sped up by running several clocks in parallel.

Table of Contents

• History
• The Two Registers
• Grain v1 in Detail
• Setup
• Grain-128
• Byte Order and Conventions
• A Worked Example
• Python Implementation
• Limitations
• Security Status
• FAQ
• References

History

Martin Hell, Thomas Johansson, and Willi Meier submitted Grain to the eSTREAM project in 2004. The first version, now called version 0, was broken by a key recovery attack, and the designers revised the cipher. The revised Grain v1 was selected for the final eSTREAM portfolio in the hardware category, together with MICKEY 2.0 and Trivium.

A larger variant followed. Grain-128, presented in 2006, raised the key to 128 bits and the IV to 96 bits. It was later broken by dynamic cube attacks. The designers then built Grain-128a in 2011, which became ISO/IEC 29167-13 in 2015, and the authenticated Grain-128AEAD for the NIST lightweight cryptography effort.

The Two Registers

Both registers shift by one bit per clock, and the bit that falls off the end is simply discarded. The LFSR feeds itself through a purely linear function. The NFSR is fed by a nonlinear function of its own bits, plus one bit from the LFSR.

Cipher	Register length	Key	IV	Setup clocks
Grain v1	80 bits each	80 bits	64 bits	160
Grain-128	128 bits each	128 bits	96 bits	256

The linear register is easy to analyze, and it is designed to give a long period. The nonlinear register provides the part that is hard to model. The keystream bit is a filter of both registers together.

Interactive Visualizer

The visualizer above runs this exact algorithm. Choose Grain v1 or Grain-128, enter a key, an IV, and a message in hex, and click Encrypt. The log shows both registers as bytes after loading, after each quarter of the setup clocks, and after each byte of keystream.

Grain v1 in Detail

Let s be the LFSR bits and b the NFSR bits, with i counting clocks. The LFSR feedback is a sum of six taps:

s(i+80) = s(i+62) + s(i+51) + s(i+38) + s(i+23) + s(i+13) + s(i)

The NFSR feedback is the following, where + is XOR and a product is AND:

b(i+80) = s(i) + b(i+62) + b(i+60) + b(i+52) + b(i+45) + b(i+37) + b(i+33)
        + b(i+28) + b(i+21) + b(i+14) + b(i+9) + b(i)
        + b(i+63)b(i+60) + b(i+37)b(i+33) + b(i+15)b(i+9)
        + b(i+60)b(i+52)b(i+45) + b(i+33)b(i+28)b(i+21)
        + b(i+63)b(i+45)b(i+28)b(i+9) + b(i+60)b(i+52)b(i+37)b(i+33)
        + b(i+63)b(i+60)b(i+21)b(i+15)
        + b(i+63)b(i+60)b(i+52)b(i+45)b(i+37)
        + b(i+33)b(i+28)b(i+21)b(i+15)b(i+9)
        + b(i+52)b(i+45)b(i+37)b(i+33)b(i+28)b(i+21)

The output filter combines seven NFSR bits with a small nonlinear function h of five bits:

z(i) = b(i+1) + b(i+2) + b(i+4) + b(i+10) + b(i+31) + b(i+43) + b(i+56)
       + h( s(i+3), s(i+25), s(i+46), s(i+64), b(i+63) )

h(x0, x1, x2, x3, x4) = x1 + x4 + x0x3 + x2x3 + x3x4 + x0x1x2 + x0x2x3
                        + x0x2x4 + x1x2x4 + x2x3x4

Notice that the NFSR feedback also includes the LFSR bit s(i). That is how the two registers influence each other. The longest product has six factors, b(i+52)b(i+45)b(i+37)b(i+33)b(i+28)b(i+21), so the NFSR feedback has algebraic degree 6.

Setup

Setup loads the registers and then clocks the cipher with the output fed back:

1. Load. The 80 key bits fill the NFSR. The 64 IV bits fill the first 64 bits of the LFSR, and the last 16 bits of the LFSR are set to 1. The ones guarantee that the LFSR never starts as all zeros.
2. Clock 160 times with feedback. On each clock the output bit z is also XORed into the new bit of both registers. During this phase no keystream is released.
3. Produce keystream. After the setup clocks, each clock outputs one bit z, and the feedback of z into the registers stops.

You encrypt by XORing the keystream with the message. Decryption is the same operation. As with every stream cipher, never reuse a key and IV pair, because the keystream would repeat.

Grain-128

Grain-128 follows the same plan with bigger registers and different taps. The LFSR feedback is:

s(i+128) = s(i) + s(i+7) + s(i+38) + s(i+70) + s(i+81) + s(i+96)

The NFSR feedback uses fewer terms than Grain v1, with only quadratic products:

b(i+128) = s(i) + b(i) + b(i+26) + b(i+56) + b(i+91) + b(i+96)
         + b(i+3)b(i+67) + b(i+11)b(i+13) + b(i+17)b(i+18) + b(i+27)b(i+59)
         + b(i+40)b(i+48) + b(i+61)b(i+65) + b(i+68)b(i+84)

The output filter is:

z(i) = b(i+2) + b(i+15) + b(i+36) + b(i+45) + b(i+64) + b(i+73) + b(i+89)
       + s(i+93) + h
h    = x0x1 + x2x3 + x4x5 + x6x7 + x0x4x8

The nine inputs are x0 = b(i+12), x1 = s(i+8), x2 = s(i+13), x3 = s(i+20), x4 = b(i+95), x5 = s(i+42), x6 = s(i+60), x7 = s(i+79), and x8 = s(i+95). Setup loads the key into the NFSR, the 96-bit IV and 32 ones into the LFSR, and runs 256 clocks with feedback. As in Grain v1, the ones keep the LFSR from starting in the all-zero state, which would stay all zero.

Byte Order and Conventions

The specifications work with bits, so implementations must map bytes to bits. This guide follows the eSTREAM reference code. Bit i of the key, the IV, and the keystream is bit i mod 8 of byte i div 8. The lowest bit of byte 0 is bit 0, and the first keystream bit becomes the lowest bit of the first output byte. The visualizer shows each register as bytes in the same layout, so after loading, the NFSR displays the key exactly as you typed it.

The extra linear term s(i+93) is the same in every implementation. Only the cubic term differs. One more detail can confuse readers who compare outputs. The Bouncy Castle library, in its Grain-128 engine, uses s(i+94) instead of s(i+95) for the cubic term in h, and its test vectors reflect that. Its output therefore differs from the eSTREAM test vectors, which this guide matches. Its Grain v1 matches the official vectors.

A Worked Example

Grain v1 setup. The key is 0123456789abcdef1234 and the IV is 0123456789abcdef. After loading, the NFSR is 0123456789abcdef1234, which is the key itself, and the LFSR is 0123456789abcdefffff, which is the IV followed by sixteen ones.

The first clock. The filter inputs are s3 = 0, s25 = 1, s46 = 0, s64 = 1, b63 = 1, so h = 1. The seven linear NFSR taps add up to 0, so the output bit is z = 1. The feedback bits are f = 0 for the LFSR and g = 1 for the NFSR. During setup the output is XORed back in, so the bits that actually enter the registers are 1 and 0.

After setup. Because a register shifts one bit per clock, after 40 clocks the old bits have moved down five bytes. The registers after 40, 80, 120, and 160 clocks are:

after  40:  LFSR = abcdefffffff2ee00851   NFSR = abcdef123438431ee602
after  80:  LFSR = ff2ee00851f608be5901   NFSR = 38431ee602d3939a6bfe
after 120:  LFSR = f608be5901dc6afb529d   NFSR = d3939a6bfe5c8cb0b8d3
after 160:  LFSR = dc6afb529d175f9bf2e5   NFSR = 5c8cb0b8d3b0a8c75aef

Keystream. The first ten keystream bytes are:

7f362bd3f7abae203664

This matches the Bouncy Castle test vector for this key and IV. The message Grain is small. is 477261696e20697320736d616c6c2e in hex, and it encrypts to:

38444aba998bc75316174281d14681

More reference points. With an all-zero key and IV, the first ten bytes are dee931cf1662a72f77d0. The official eSTREAM vector Set 1, vector# 0 uses the key 80000000000000000000 and the IV 0000000000000000, and it begins with ff7710b30f198d75a454ab7a6b92a022.

Grain-128. With the key 0123456789abcdef123456789abcdef0 and the IV 0123456789abcdef12345678, the registers after loading are LFSR = 0123456789abcdef12345678ffffffff and NFSR = 0123456789abcdef123456789abcdef0. After the 256 setup clocks they are LFSR = 5c702ce85e8dc075bb8db61731902638 and NFSR = 31c02fac63ff8e479d1d9ce02ee0a947. The first setup clock works on the registers as loaded. Its filter inputs are b12 = 0, s8 = 1, s13 = 1, s20 = 0, b95 = 0, s42 = 0, s60 = 0, s79 = 0, s95 = 0, so h = 0. The linear terms, including s(i+93), add up to 0, so z = 0. The feedback bits are f = 1 and g = 0, and with the output fed back they become 1 and 0. The first 16 keystream bytes are afb5babfa8de896b4b9c6acaf7c4fbfd. The first byte is af, which is 10101111 in binary, so the first bits generated, lowest bit first, are 1, 1, 1, 1, 0, 1, 0, 1. The same message encrypts to e8c7dbd6c6fee0186bef07ab9ba8d5. For the eSTREAM vector with key 80000000000000000000000000000000 and an all-zero IV, the keystream begins with c9e02c746a64b948e103677385ca0f96.

Python Implementation

This is a complete Grain v1 and Grain-128. The two ciphers share the same code, and a small table of taps describes each one.

# grain.py
#
# The Grain family of stream ciphers (eSTREAM hardware portfolio).
# Each cipher has two shift registers of the same length: a linear feedback
# register (LFSR, bits s) and a nonlinear one (NFSR, bits b). A filter
# function turns a few bits of both registers into one keystream bit.
#
#   Grain v1:   80-bit key, 64-bit IV,  80-bit registers, 160 setup clocks
#   Grain-128: 128-bit key, 96-bit IV, 128-bit registers, 256 setup clocks
#
# Bytes are mapped to bits the way the eSTREAM reference code does it: bit i
# of the key (or IV, or keystream) is bit (i mod 8) of byte (i div 8), so the
# lowest bit of byte 0 is bit 0 and the first keystream bit is the lowest bit
# of the first output byte.

# In the tuples below each number is an NFSR bit position k, meaning b(i+k). A single number is added to the
# feedback, and a tuple is a product (AND) of those bits, which is added as one term.
# Taps of the nonlinear feedback for each variant: a sum of single bits and
# a list of products, all taken from the NFSR.
GRAIN_V1 = {
    "name": "Grain v1",
    "n": 80, "key_bits": 80, "iv_bits": 64, "init_clocks": 160,
    "lfsr_taps": (0, 13, 23, 38, 51, 62),
    "nfsr_single": (0, 9, 14, 21, 28, 33, 37, 45, 52, 60, 62),
    "nfsr_products": ((63, 60), (37, 33), (15, 9), (60, 52, 45), (33, 28, 21),
                      (63, 45, 28, 9), (60, 52, 37, 33), (63, 60, 21, 15),
                      (63, 60, 52, 45, 37), (33, 28, 21, 15, 9),
                      (52, 45, 37, 33, 28, 21)),
    "out_linear": (1, 2, 4, 10, 31, 43, 56),
}

GRAIN_128 = {
    "name": "Grain-128",
    "n": 128, "key_bits": 128, "iv_bits": 96, "init_clocks": 256,
    "lfsr_taps": (0, 7, 38, 70, 81, 96),
    "nfsr_single": (0, 26, 56, 91, 96),
    "nfsr_products": ((3, 67), (11, 13), (17, 18), (27, 59), (40, 48), (61, 65), (68, 84)),
    "out_linear": (2, 15, 36, 45, 64, 73, 89),
}


def h_v1(s, b):
    """Grain v1 filter: x0..x4 = s[3], s[25], s[46], s[64], b[63]."""
    x0, x1, x2, x3, x4 = s[3], s[25], s[46], s[64], b[63]
    return (x1 ^ x4 ^ (x0 & x3) ^ (x2 & x3) ^ (x3 & x4) ^ (x0 & x1 & x2) ^ (x0 & x2 & x3)
            ^ (x0 & x2 & x4) ^ (x1 & x2 & x4) ^ (x2 & x3 & x4))


def h_128(s, b):
    """Grain-128 filter: x0 .. x8 = b[12], s[8], s[13], s[20], b[95], s[42], s[60], s[79], s[95]."""
    x0, x1, x2, x3 = b[12], s[8], s[13], s[20]
    x4, x5, x6, x7, x8 = b[95], s[42], s[60], s[79], s[95]
    return (x0 & x1) ^ (x2 & x3) ^ (x4 & x5) ^ (x6 & x7) ^ (x0 & x4 & x8)


H = {"Grain v1": h_v1, "Grain-128": h_128}
# Grain-128 also adds the LFSR bit s[93] to the output, a linear term of its specification (Grain v1 has none)
EXTRA_S = {"Grain v1": (), "Grain-128": (93,)}


def output_bit(variant, s, b):
    z = H[variant["name"]](s, b)
    for k in variant["out_linear"]:
        z ^= b[k]
    for k in EXTRA_S[variant["name"]]:
        z ^= s[k]
    return z


def feedbacks(variant, s, b):
    f = 0
    for k in variant["lfsr_taps"]:
        f ^= s[k]
    g = s[0]
    for k in variant["nfsr_single"]:
        g ^= b[k]
    for prod in variant["nfsr_products"]:
        term = 1
        for k in prod:
            term &= b[k]
        g ^= term
    return f, g


def clock(variant, s, b, feed_output):
    """Advance both registers one step and return the output bit of that step."""
    z = output_bit(variant, s, b)
    f, g = feedbacks(variant, s, b)
    if feed_output:
        f ^= z
        g ^= z
    del s[0]
    s.append(f)
    del b[0]
    b.append(g)
    return z


def bits_of(data, count):
    return [(data[i // 8] >> (i % 8)) & 1 for i in range(count)]


def init(variant, key, iv):
    """Load the key and IV and run the setup clocks. Return the registers (s, b)."""
    if len(key) * 8 != variant["key_bits"]:
        raise ValueError("%s keys are %d bytes" % (variant["name"], variant["key_bits"] // 8))
    if len(iv) * 8 != variant["iv_bits"]:
        raise ValueError("%s IVs are %d bytes" % (variant["name"], variant["iv_bits"] // 8))
    b = bits_of(key, variant["key_bits"])
    s = bits_of(iv, variant["iv_bits"]) + [1] * (variant["n"] - variant["iv_bits"])
    for _ in range(variant["init_clocks"]):
        clock(variant, s, b, True)
    return s, b


def keystream(variant, key, iv, length):
    s, b = init(variant, key, iv)
    out = bytearray(length)
    for i in range(8 * length):
        out[i // 8] |= clock(variant, s, b, False) << (i % 8)
    return bytes(out)


def crypt(variant, key, iv, data):
    return bytes(a ^ b for a, b in zip(data, keystream(variant, key, iv, len(data))))


if __name__ == "__main__":
    key = bytes.fromhex("0123456789abcdef1234")
    iv = bytes.fromhex("0123456789abcdef")
    message = b"Grain is small."
    ciphertext = crypt(GRAIN_V1, key, iv, message)
    print("Key:        " + key.hex())
    print("IV:         " + iv.hex())
    print("Keystream:  " + keystream(GRAIN_V1, key, iv, 10).hex())
    print("Plaintext:  " + message.hex())
    print("Ciphertext: " + ciphertext.hex())
    print("Recovered:  " + crypt(GRAIN_V1, key, iv, ciphertext).decode())

Running it produces this output:

Key:        0123456789abcdef1234
IV:         0123456789abcdef
Keystream:  7f362bd3f7abae203664
Plaintext:  477261696e20697320736d616c6c2e
Ciphertext: 38444aba998bc75316174281d14681
Recovered:  Grain is small.

I checked this code against official vectors before writing it up. It reproduces every keystream slice in the eSTREAM test vectors for Grain v1, and for Grain-128. That is 332 slices from 83 vectors for Grain v1, and 368 slices from 92 vectors for Grain-128. It also reproduces the two Bouncy Castle vectors for Grain v1. I also checked the tap positions against the Bouncy Castle source for Grain v1, and against a published description of the Grain-128 filter.

Limitations

This is a faithful teaching version of the ciphers, not a production one:

• Python is slow. Grain is built for one clock per tick in hardware, and this version loops over bits.
• Never reuse a key and IV pair. The code will happily encrypt twice with the same pair, which leaks the XOR of the two messages.
• No authentication. Grain only hides data. Anyone can flip ciphertext bits, which is why Grain-128AEAD adds a tag.
• Grain-128 is not recommended. Cube attacks have broken it faster than brute force, and the later Grain-128a was designed to replace it.

Security Status

Grain v1 has held up well. The published attacks target reduced versions, or they are too expensive to be a threat. One survey reports that the only confirmed attack on the full cipher is a fast correlation attack that needs about 2⁷⁵·¹ bits of keystream from a single key and IV pair, which is not feasible in practice. Version 0 did fall to a key recovery attack, which is why version 1 exists.

Grain-128 is weaker than it looks. In 2011 Dinur and Shamir used dynamic cube attacks to recover the key of the full cipher for a fraction of about 2⁻¹⁰ of all keys, faster than exhaustive search by a factor of about 2¹⁵. A separate experimentally verified attack on the full cipher used dedicated reconfigurable hardware. Grain-128a followed this cryptanalysis, and it adds higher-degree terms to the NFSR feedback.

FAQ

Why does Grain have two registers?

The LFSR provides a long, balanced sequence and is easy to analyze. The NFSR provides nonlinearity, which makes algebraic attacks much harder. Mixing the two through the filter combines the benefits of both.

What does it mean that setup feeds the output back?

During the setup clocks, the output bit is XORed into the new bit of both registers. That makes the key and IV bits affect the whole state quickly, without needing extra rounds.

Is Grain secure?

Grain v1 is not known to be broken in practice, and it is in the eSTREAM portfolio. Grain-128 has been broken faster than brute force for a fraction of the keys. Newer designs such as Grain-128a and Grain-128AEAD are the usual choice.

Can Grain run faster?

The designers allow up to 16 clocks to run in parallel, at the cost of more hardware. The output is the same as in the one-bit version.

What is the difference between Grain v1 and Grain-128?

Grain-128 has a 128-bit key, a 96-bit IV, longer registers, and a different set of taps. The filter function and the setup procedure follow the same idea.

References

1. Hell, M., Johansson, T., and Meier, W. “Grain: A Stream Cipher for Constrained Environments.” International Journal of Wireless and Mobile Computing, 2007.

2. Hell, M., Johansson, T., Maximov, A., and Meier, W. “A Stream Cipher Proposal: Grain-128.” IEEE International Symposium on Information Theory (ISIT), 2006.

3. Dinur, I. and Shamir, A. “Breaking Grain-128 with Dynamic Cube Attacks.” Fast Software Encryption (FSE) 2011.

4. Wikipedia. “Grain (cipher).” Available at: https://en.wikipedia.org/wiki/Grain_(cipher)