The Rabbit Stream Cipher

The Rabbit Stream Cipher

Introduction

Rabbit is a stream cipher built for speed in software. It takes a 128-bit key and an optional 64-bit initialization vector, and it produces 128 bits of keystream per round. You encrypt by XORing that keystream with your message. Decryption is the very same operation.

Most fast stream ciphers get their nonlinearity from S-boxes or from long registers. Rabbit takes a different route. It squares a 32-bit number and keeps the XOR of the high and low halves of the 64-bit result. That one cheap trick is the heart of the cipher.

Table of Contents

• History
• The Inner State
• Key Setup
• The Counter System
• The Next-State Function
• IV Setup and Output
• Byte Order
• A Worked Example
• Python Implementation
• Limitations
• Security Status
• FAQ
• References

History

Martin Boesgaard, Mette Vesterager, Thomas Pedersen, Jesper Christiansen, and Ove Scavenius designed Rabbit at the Danish company Cryptico. They presented it at the 10th Fast Software Encryption workshop in February 2003. Cryptico later submitted it to the eSTREAM project run by the ECRYPT network.

The IETF published the algorithm as RFC 4503 in May 2006. Rabbit became part of the final eSTREAM portfolio in the software category. The portfolio’s other software ciphers were HC-128, Salsa20/12, and SOSEMANUK.

Rabbit started out as a patented, licensed algorithm. According to Wikipedia, it was made free for any use on October 6, 2008, and the reference source code is now public domain.

The Inner State

The state of Rabbit is 513 bits. Eight 32-bit state words X0 to X7 hold the main state. Eight 32-bit counter words C0 to C7 hold a counter system that runs alongside the state. One more bit, the carry bit b, links the counters together.

The counters have two jobs. They are designed to keep the state from falling into a short cycle, because they count up with a very long period. They also feed fresh values into the nonlinear part of the cipher every round.

Interactive Visualizer

The visualizer above runs this exact algorithm. Choose Rabbit with or without an IV, enter a key and a message in hex, and click Encrypt. Each row of the log shows the full state after one 16-byte block, with the keystream block and the message block that it was XORed with. Click Decrypt on the output to get the message back.

Key Setup

The 128-bit key is read as one big-endian integer and split into eight 16-bit subkeys. The last two bytes of the key form K0, and the first two bytes form K7, because the key is read as a big-endian integer. The state and counter words are then filled from the subkeys in a crossed pattern:

for j = 0 to 7:
  if j is even:
    Xj = K(j+1 mod 8) || Kj
    Cj = K(j+4 mod 8) || K(j+5 mod 8)
  else:
    Xj = K(j+5 mod 8) || K(j+4 mod 8)
    Cj = Kj || K(j+1 mod 8)

Here || means concatenation. The carry bit starts at zero. The system is then iterated four times, where one iteration is a counter update followed by the next-state function. Finally, each counter word is XORed with another state word: Cj = Cj ^ X(j+4 mod 8). That last step stops anyone from reading the key straight out of the counters.

The Counter System

Before each next-state step, the counters are updated with eight fixed constants:

A0 = 0x4D34D34D   A1 = 0xD34D34D3   A2 = 0x34D34D34   A3 = 0x4D34D34D
A4 = 0xD34D34D3   A5 = 0x34D34D34   A6 = 0x4D34D34D   A7 = 0xD34D34D3

The update is a chain of additions with carry:

for j = 0 to 7:
  temp = Cj + Aj + b
  b    = temp div 2^32
  Cj   = temp mod 2^32

The carry out of one counter word becomes the carry into the next, and the last carry stays in b for the next round. In effect the eight counters form one 256-bit counter. The constants have a repeating bit pattern, and together with the carry chain they make the counter run for a very long time before it repeats.

The Next-State Function

The nonlinear step uses a function g that takes two 32-bit words and returns one:

g(u, v) = LSW(square(u + v)) ^ MSW(square(u + v))

Here u + v is taken modulo 2³², and square multiplies that 32-bit result by itself to give a 64-bit number. LSW and MSW are its low and high 32 bits. Squaring mixes every input bit into many output bits, and it needs no table at all.

The function g is applied to each pair Xj and Cj. The eight results G0 to G7 are then combined with rotations and additions to give the new state:

X0 = G0 + (G7 <<< 16) + (G6 <<< 16)
X1 = G1 + (G0 <<<  8) +  G7
X2 = G2 + (G1 <<< 16) + (G0 <<< 16)
X3 = G3 + (G2 <<<  8) +  G1
X4 = G4 + (G3 <<< 16) + (G2 <<< 16)
X5 = G5 + (G4 <<<  8) +  G3
X6 = G6 + (G5 <<< 16) + (G4 <<< 16)
X7 = G7 + (G6 <<<  8) +  G5

All additions are modulo 2³², and the indices of the words wrap around, so the word before X0 is X7. The pattern alternates between two rotation amounts, 16 and 8, and every new word depends on two or three of the G values.

IV Setup and Output

If you use an IV, it is mixed in after the key setup. The 64-bit IV is XORed into the counters in a fixed pattern, and then the system runs four more iterations. The key setup result is saved as a master state. A new IV only needs the cheap IV setup on that master state, which makes switching IVs fast.

C0 = C0 ^ IV[31..0]        C1 = C1 ^ (IV[63..48] || IV[31..16])
C2 = C2 ^ IV[63..32]       C3 = C3 ^ (IV[47..32] || IV[15..0])
C4 = C4 ^ IV[31..0]        C5 = C5 ^ (IV[63..48] || IV[31..16])
C6 = C6 ^ IV[63..32]       C7 = C7 ^ (IV[47..32] || IV[15..0])

Each round after that is a counter update and a next-state step, followed by extraction. The 128-bit keystream block S is built from 16-bit halves of the state words:

S[15..0]    = X0[15..0]  ^ X5[31..16]     S[79..64]   = X4[15..0]  ^ X1[31..16]
S[31..16]   = X0[31..16] ^ X3[15..0]      S[95..80]   = X4[31..16] ^ X7[15..0]
S[47..32]   = X2[15..0]  ^ X7[31..16]     S[111..96]  = X6[15..0]  ^ X3[31..16]
S[63..48]   = X2[31..16] ^ X5[15..0]      S[127..112] = X6[31..16] ^ X1[15..0]

Encryption XORs each 128-bit message block with the next S. If the message ends in a partial block, only the needed part of the last S is used. The designers say a single key may protect at most 2⁶⁴ blocks. The RFC adds that an IV must never repeat under the same key.

Byte Order

The RFC converts octet strings to integers with the conversion primitives OS2IP and I2OSP. The first byte is the most significant, and a keystream block is written the same way. This guide and its visualizer follow the RFC.

The eSTREAM test vectors use the opposite convention. The key bytes, the IV bytes, and every 16-byte output block are written in reverse order. I used a small conversion to check the code against both sets of vectors. Always check which convention a test vector uses before you compare any output.

A Worked Example

This example uses the key from the RFC’s debugging vectors, 91281329 2e3d36fe 3bfc62f1 dc51c3ac. The RFC prints one byte of that key incorrectly in its debugging section, as 2E ED instead of 2E 3D. The states printed in the RFC prove that 3D is right, and the keystream vectors in Appendix A use 3D as well.

Key setup. The eight subkeys are K0 = c3ac, K1 = dc51, K2 = 62f1, K3 = 3bfc, K4 = 36fe, K5 = 2e3d, K6 = 1329, and K7 = 9128. The crossed loading pattern gives X0 = dc51c3ac and C0 = 36fe2e3d. The full set is:

X0 = dc51c3ac   X1 = 13292e3d   X2 = 3bfc62f1   X3 = c3ac9128
X4 = 2e3d36fe   X5 = 62f1dc51   X6 = 91281329   X7 = 36fe3bfc
C0 = 36fe2e3d   C1 = dc5162f1   C2 = 13299128   C3 = 3bfc36fe
C4 = c3acdc51   C5 = 2e3d1329   C6 = 62f13bfc   C7 = 9128c3ac

First iteration. The counter update adds A0 to C0, which gives 08433018a. The carry out is 1, and the low 32 bits make the new C0 = 8433018a. For the nonlinear step, X0 + C0 = 6084c536 modulo 2³². Its square is 2463d8c4779c2764, and XORing the two halves gives G0 = 53ffffa0. The other two values that feed X0 are G7 = d25fdf55 and G6 = f6b2bf92, and rotating them by 16 bits gives df55d25f and bf92f6b2. Adding all three gives the new X0 = f2e8c8b1. The RFC lists 0xF2E8C8B1 for this value, and 0x8433018A for the new C0. The next word works the same way. With G1 = 6680efff and G0 rotated left by 8 bits, which is ffffa053, the sum G1 + (G0 <<< 8) + G7 gives the new X1 = 38e06fa7, which is the RFC’s value as well.

After the key setup. After the fourth iteration and the final XOR, the state is:

X0 = 1d059312   X1 = bddc3e45   X2 = f440927d   X3 = 50cbb553
X4 = 36709423   X5 = 0b6f0711   X6 = 3ada3a7b   X7 = eb9800c8
C0 = 5da1ef57   C1 = 22e9312f   C2 = dcacff87   C3 = 9b5784fa
C4 = 0de43c8c   C5 = bc5679b8   C6 = 63841b4c   C7 = 8e9623aa
b = 0

Keystream without an IV. Running three rounds from this state gives these keystream blocks, which match the RFC:

S[0] = 3d2df3c83ef627a1e97fc38487e2519c
S[1] = f576cd61f4405b8896bf53aa8554fc19
S[2] = e5547473fbdb43508ae53b20204d4c5e

With the IV c373f575c1267e59. After the IV is mixed in and four more iterations run, the state is X0 = 6274e424, X1 = e14ce120, and so on, with C0 = d15ade44 and b = 1. These values also match the RFC. The first keystream block is bb5cf163d7f93e8de95cec5bd7231abc.

Encrypting a message. The 31-byte message Rabbit is a fast stream cipher. is 526162626974206973206120666173742073747265616d206369706865722e in hex. With the IV above, the ciphertext is:

e93d9301be8d1ee49a7c8d7bb14269c85ce710845a5ef380c9c31114fbaa54

Without the IV, the same message encrypts to this:

6f4c91aa578207c89a5fa2a4e18322e8d505b913912136a8f5d623c2e026d2

Two more reference points are worth remembering. With an all-zero key and no IV, the first keystream block is b15754f036a5d6ecf56b45261c4af702. With an all-zero key and an all-zero IV, it is c6a7275ef85495d87ccd5d376705b7ed.

Python Implementation

This is a complete Rabbit, with key setup, IV setup, keystream generation, and encryption. The master state is kept separate, so one key can be used with many IVs.

# rabbit.py
#
# Rabbit, a fast software stream cipher (RFC 4503, eSTREAM portfolio).
# A 128-bit key and an optional 64-bit IV. The state is eight 32-bit words
# X, eight 32-bit counters C, and one carry bit. Each round produces 16 bytes
# of keystream, which is XORed with the message.
#
# Bytes are converted to integers the way the RFC does it (OS2IP): the first
# byte is the most significant. Keystream blocks are written the same way.

MASK = 0xFFFFFFFF
A = [0x4D34D34D, 0xD34D34D3, 0x34D34D34, 0x4D34D34D,
     0xD34D34D3, 0x34D34D34, 0x4D34D34D, 0xD34D34D3]


def rol(x, n):
    return ((x << n) | (x >> (32 - n))) & MASK


def g(u, v):
    square = ((u + v) & MASK) ** 2
    return (square ^ (square >> 32)) & MASK


def counter_update(c, b):
    # the eight words and the carry chain act like one 256-bit counter that adds a fixed constant every round
    for j in range(8):
        temp = c[j] + A[j] + b
        b = temp >> 32
        c[j] = temp & MASK
    return b


def next_state(x, c):
    gs = [g(x[j], c[j]) for j in range(8)]
    x[0] = (gs[0] + rol(gs[7], 16) + rol(gs[6], 16)) & MASK
    x[1] = (gs[1] + rol(gs[0], 8) + gs[7]) & MASK
    x[2] = (gs[2] + rol(gs[1], 16) + rol(gs[0], 16)) & MASK
    x[3] = (gs[3] + rol(gs[2], 8) + gs[1]) & MASK
    x[4] = (gs[4] + rol(gs[3], 16) + rol(gs[2], 16)) & MASK
    x[5] = (gs[5] + rol(gs[4], 8) + gs[3]) & MASK
    x[6] = (gs[6] + rol(gs[5], 16) + rol(gs[4], 16)) & MASK
    x[7] = (gs[7] + rol(gs[6], 8) + gs[5]) & MASK


def iterate(x, c, b):
    b = counter_update(c, b)
    next_state(x, c)
    return b


def key_setup(key):
    """Return the master state (x, c, b) for a 16-byte key."""
    if len(key) != 16:
        raise ValueError("Rabbit keys are 16 bytes")
    k = int.from_bytes(key, "big")
    sub = [(k >> (16 * j)) & 0xFFFF for j in range(8)]  # K0 .. K7
    x, c = [0] * 8, [0] * 8
    for j in range(8):
        if j % 2 == 0:
            x[j] = (sub[(j + 1) % 8] << 16) | sub[j]
            c[j] = (sub[(j + 4) % 8] << 16) | sub[(j + 5) % 8]
        else:
            x[j] = (sub[(j + 5) % 8] << 16) | sub[(j + 4) % 8]
            c[j] = (sub[j] << 16) | sub[(j + 1) % 8]
    b = 0
    for _ in range(4):
        b = iterate(x, c, b)
    for j in range(8):
        c[j] ^= x[(j + 4) % 8]
    return x, c, b


def iv_setup(state, iv):
    """Return the starting state for an 8-byte IV, leaving the master state alone."""
    if len(iv) != 8:
        raise ValueError("Rabbit IVs are 8 bytes")
    x, c, b = list(state[0]), list(state[1]), state[2]
    v = int.from_bytes(iv, "big")
    lo, hi = v & MASK, v >> 32
    c[0] ^= lo
    c[1] ^= (hi & 0xFFFF0000) | ((lo >> 16) & 0xFFFF)
    c[2] ^= hi
    c[3] ^= ((hi & 0xFFFF) << 16) | (lo & 0xFFFF)
    c[4] ^= lo
    c[5] ^= (hi & 0xFFFF0000) | ((lo >> 16) & 0xFFFF)
    c[6] ^= hi
    c[7] ^= ((hi & 0xFFFF) << 16) | (lo & 0xFFFF)
    for _ in range(4):
        b = iterate(x, c, b)
    return x, c, b


def extract(x):
    # s[j] is bits 16j to 16j+15 of the 128-bit block S of the RFC: s[0] is S[15..0], s[1] is S[31..16], and so on
    s = [
        (x[0] & 0xFFFF) ^ (x[5] >> 16),
        (x[0] >> 16) ^ (x[3] & 0xFFFF),
        (x[2] & 0xFFFF) ^ (x[7] >> 16),
        (x[2] >> 16) ^ (x[5] & 0xFFFF),
        (x[4] & 0xFFFF) ^ (x[1] >> 16),
        (x[4] >> 16) ^ (x[7] & 0xFFFF),
        (x[6] & 0xFFFF) ^ (x[3] >> 16),
        (x[6] >> 16) ^ (x[1] & 0xFFFF),
    ]
    value = 0
    for j in range(8):
        value |= s[j] << (16 * j)
    return value.to_bytes(16, "big")


def keystream(key, iv, length):
    state = key_setup(key)
    if iv is not None:
        state = iv_setup(state, iv)
    x, c, b = list(state[0]), list(state[1]), state[2]
    out = b""
    while len(out) < length:
        b = iterate(x, c, b)
        out += extract(x)
    return out[:length]


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


if __name__ == "__main__":
    key = bytes.fromhex("91281329" "2e3d36fe" "3bfc62f1" "dc51c3ac")
    iv = bytes.fromhex("c373f575c1267e59")
    message = b"Rabbit is a fast stream cipher."
    ciphertext = crypt(key, iv, message)
    recovered = crypt(key, iv, ciphertext)
    print("Key:        " + key.hex())
    print("IV:         " + iv.hex())
    print("Keystream:  " + keystream(key, iv, 16).hex())
    print("Plaintext:  " + message.hex())
    print("Ciphertext: " + ciphertext.hex())
    print("Recovered:  " + recovered.decode())

Running it produces this output:

Key:        912813292e3d36fe3bfc62f1dc51c3ac
IV:         c373f575c1267e59
Keystream:  bb5cf163d7f93e8de95cec5bd7231abc
Plaintext:  526162626974206973206120666173742073747265616d206369706865722e
Ciphertext: e93d9301be8d1ee49a7c8d7bb14269c85ce710845a5ef380c9c31114fbaa54
Recovered:  Rabbit is a fast stream cipher.

I checked this code against two sets of official vectors before writing it up. It reproduces all six 48-byte keystreams in Appendix A of RFC 4503, with and without an IV. It also matches every intermediate state in the RFC’s debugging vectors, including the key setup, the 48-byte output, and the IV setup. In addition, it reproduces all 356 keystream slices in the 89 eSTREAM test vectors, after converting the byte order described above.

Limitations

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

• Python is slow. Rabbit was designed for fast native code, and this version is meant for reading.
• No protection against IV reuse. The code will happily encrypt twice with the same key and IV. Doing that is a serious mistake, because it leaks the XOR of the two messages.
• No authentication. Rabbit only hides the message. Anyone can flip bits in the ciphertext, so real systems add a MAC.
• No side-channel hardening. Python integers are not constant-time. Rabbit itself uses no table lookups, which helps real implementations.

Security Status

No attack on the full cipher with a 128-bit key is known. Jean-Philippe Aumasson found a distinguisher in 2006 that needs about 2²⁴⁷ samples of keystream, and later work improved it to about 2¹⁵⁸. Both numbers are far beyond the 2¹²⁸ cost of searching for the key. They show a small statistical bias in the keystream, but they do not threaten real use.

Rabbit was reviewed during the eSTREAM project for several years, and it finished in the portfolio. That is a good sign, but it has had less attention than AES or ChaCha20. For new designs, ChaCha20 or AES-GCM are the usual choices, and Rabbit is mostly of interest for study and for existing systems.

FAQ

What makes Rabbit different from other stream ciphers?

It has no S-boxes and no long shift register. Its nonlinearity comes from squaring a 32-bit word and XORing the halves of the result. Eight counters guarantee a long period.

Is Rabbit secure?

No attack on the full cipher is known. The best published result is a distinguisher with a cost far above brute force. It was evaluated in the eSTREAM project and selected for the final portfolio.

Do I need an IV?

You can run Rabbit without one, but then you must never restart the cipher under the same key. An IV lets you reuse a key safely, as long as every IV is used only once.

How fast is Rabbit?

The designers claim up to 3.7 cycles per byte on a Pentium 3 and 9.7 cycles per byte on an ARM7. Those are the figures quoted on Wikipedia. Speed on modern processors depends on the implementation.

Is Rabbit free to use?

Rabbit was patented at first. According to Wikipedia, it was made free for any use on October 6, 2008, and the reference implementation is public domain.

References

1. Boesgaard, M., Vesterager, M., Pedersen, T., Christiansen, J., and Scavenius, O. “Rabbit: A New High-Performance Stream Cipher.” Fast Software Encryption (FSE) 2003, Lecture Notes in Computer Science 2887, pp. 307-329.

2. Boesgaard, M., Vesterager, M., and Zenner, E. “A Description of the Rabbit Stream Cipher Algorithm.” RFC 4503, 2006. Available at: https://www.rfc-editor.org/rfc/rfc4503

3. Aumasson, J.-P. “On a Bias of Rabbit.” SASC 2007, the State of the Art of Stream Ciphers workshop.

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