The Trivium Stream Cipher

The Trivium Stream Cipher

Introduction

Trivium is a stream cipher designed to be tiny. It uses an 80-bit key, an IV of up to 80 bits, and a 288-bit internal state. Every clock it makes one bit of keystream from a handful of XOR and AND operations. A basic hardware version needs only a few thousand logic gates.

That makes it a good fit for chips where every gate costs money, such as RFID tags and sensors. It is also a good cipher to study, because the whole design fits on a page and there are no tables, no key schedule, and no large words.

Table of Contents

• History
• The Three Registers
• The Update Rule
• Initialization
• Byte Order
• A Worked Example
• Python Implementation
• Limitations
• Security Status
• FAQ
• References

History

Christophe De Cannière and Bart Preneel designed Trivium and submitted it to the eSTREAM project. It entered the hardware category, called Profile 2, and it was selected for the final eSTREAM portfolio as a low-area hardware cipher. It has also been standardized as part of ISO/IEC 29192-3, the standard for lightweight stream ciphers. The design is not patented.

The authors describe the size in gates. A straightforward implementation producing one bit per clock needs 3,488 gates, and a version that produces 64 bits per clock needs 5,504. In software it runs at around 4 cycles per byte on some x86 processors, according to Wikipedia.

The Three Registers

The state is 288 bits, written s1 to s288. Three shift registers hold it:

Register	Bits	Length
A	s1 to s93	93
B	s94 to s177	84
C	s178 to s288	111

The registers are linked in a ring. A new bit for register A is computed from bits in register C and in A itself. A new bit for B uses A and B, and a new bit for C uses B and C.

Interactive Visualizer

The visualizer above runs this exact algorithm. Choose an IV size, enter an 80-bit key and a message in hex, and click Encrypt. The log shows the three registers after loading, after each quarter of the warm-up, and after each byte of keystream. The registers are written as bit strings, first bit on the left.

The Update Rule

Each clock computes three feedback bits, t1, t2, and t3, and one output bit z. All the work is XOR, written +, and AND, written ·:

t1 = s66  + s93
t2 = s162 + s177
t3 = s243 + s288
z  = t1 + t2 + t3

t1 = t1 + s91·s92   + s171
t2 = t2 + s175·s176 + s264
t3 = t3 + s286·s287 + s69

The first three lines are computed first, and their sum gives the output bit z. The last three lines then add one AND term each, and one tap taken from the next register in the ring, to the same variables before the bits are shifted in. Then the registers shift by one place, and the three new bits enter at the front:

(s1,   s2,   ..., s93)  = (t3, s1,   ..., s92)
(s94,  s95,  ..., s177) = (t1, s94,  ..., s176)
(s178, s179, ..., s288) = (t2, s178, ..., s287)

The three AND terms are the only nonlinear part of the cipher. Everything else is linear. Because only three AND terms exist per round, the cipher needs a long warm-up before its output is safe to use.

Initialization

Setting up the cipher takes three steps:

1. Load the key and IV. The 80 key bits go into s1 to s80. The IV bits go into s94 to s173, and a shorter IV leaves the rest zero.
2. Set the constant. Bits s286, s287, and s288 are set to 1. Every other bit that is not part of the key or the IV is zero.
3. Warm up. Run the update rule 1,152 times, which is 4 times 288, and throw away the output. After that the state is thoroughly mixed, so the keystream depends on the whole key and the whole IV.

After the warm-up, each clock gives one keystream bit. You encrypt by XORing the keystream with the message, and you decrypt the same way. Never reuse an IV with the same key, because the keystream would repeat.

Byte Order

The specification works with bits, so every implementation has to decide how bytes map to bits. This guide follows the eSTREAM API, which is also the convention of the official test vectors. The lowest bit of the first key byte is s80, and the highest bit of the last key byte is s1. The IV works the same way, and the first IV byte’s lowest bit is s173 for an 80-bit IV.

A shorter IV moves down by 8 positions for each missing byte, so a 64-bit IV fills s94 to s157, with the lowest bit of its first byte at s157, and s158 to s173 stay zero. For keystream, the first bit generated becomes the lowest bit of the first byte. Other code, including early versions of Trivium itself, uses other orders. If your output does not match a vector, the bit order is the first thing to check.

A Worked Example

This is the first official test vector. The key is 80000000000000000000 and the IV is all zero.

Loading. The only bits that are set are s73, s286, s287, s288. The first is the key bit, which is the top bit of the first key byte, and the other three are the constant. Register A is 000000000000000000800000, register B is 000000000000000000000, and register C is 000000000000000000000000000e. Bits are written first bit on the left and padded with zeros on the right to a whole hex digit.

The first round. The sums are t1 = s66 + s93 = 0, t2 = s162 + s177 = 0, and t3 = s243 + s288 = 1. The output bit is 1, and it is discarded because this is a warm-up round. For the new bits, s286 AND s287 = 1 AND 1 = 1, so t3 becomes 0. The new values for t1 and t2 are 0 and 0.

Warm-up. After 288, 576, 864, and 1,152 rounds, register A is 132d20d200f0827107830d00, 02a0559e27290c6a488cbb90, 358b6c2ede518734afeae6d8, and 70a783265c91a6ab9568a4b0. After the last round, register B is 1f03bd44bf1ea884d4c0a and register C is 9ec1031c5379b49cc067b227d7c6.

After the first byte. Eight more rounds leave the registers at A = 1270a783265c91a6ab9568a0, B = 091f03bd44bf1ea884d4c, and C = 499ec1031c5379b49cc067b227d6. These are the values in the visualizer’s row for byte 1.

Keystream. The first eight output bits are 0, 0, 0, 1, 1, 1, 0, 0. The first bit becomes the lowest bit of the byte, so the byte is 00111000 in binary, which is 38. The first 16 keystream bytes are:

38eb86ff730d7a9caf8df13a4420540d

This matches the first line of the official test vector. The message Trivium is tiny. is 5472697669756d2069732074696e792e in hex, and it encrypts to:

6c99ef891a7817bcc6fed14e2d4e2d23

A vector with both a key and an IV. For the key 0053a6f94c9ff24598eb and the IV 0d74db42a91077de45ac, the official test vector Set 6, vector# 0 begins with f4cd954a717f26a7d6930830c4e7cf08.

Python Implementation

This is a complete Trivium: loading, the update rule, warm-up, keystream bytes, and encryption. It accepts IVs from 0 to 10 bytes.

# trivium.py
#
# Trivium, the hardware stream cipher by Christophe De Cannière and Bart Preneel
# (eSTREAM portfolio, ISO/IEC 29192-3). An 80-bit key, an IV of up to 80 bits,
# and a 288-bit state held in three shift registers of 93, 84 and 111 bits.
# Each clock produces one keystream bit using only XOR and AND.
#
# State bits are numbered s1 ... s288 as in the specification. This code stores
# them in a list where s[i - 1] holds s_i.
#
# Bytes are mapped to bits the way the eSTREAM API does it: the lowest bit of
# the first key byte is s80, and the highest bit of the last key byte is s1.
# The IV works the same way: the lowest bit of its first byte is s173 for an
# 80-bit IV. A shorter IV moves down by 8 positions per missing byte, so a
# 64-bit IV starts at s157. Keystream bytes are filled from the lowest bit up,
# so the first bit generated is the lowest bit of byte 0.

WARMUP = 4 * 288


def load(key, iv):
    """Return the state after loading an 80-bit key and an IV of 0 to 10 bytes."""
    if len(key) != 10:
        raise ValueError("Trivium keys are 10 bytes")
    if len(iv) > 10:
        raise ValueError("Trivium IVs are at most 10 bytes")
    s = [0] * 288
    for p in range(10):
        for k in range(8):
            s[80 - 8 * p - k - 1] = (key[p] >> k) & 1
    # a short IV fills the highest-numbered positions, so a 64-bit IV starts at s157
    skip = 10 - len(iv)   # whole bytes missing from the IV; each one moves the IV down by 8 positions
    for p in range(len(iv)):
        for k in range(8):
            s[173 - 8 * (p + skip) - k - 1] = (iv[p] >> k) & 1
    s[285] = s[286] = s[287] = 1
    return s


def step(s):
    """Clock the state once and return one keystream bit."""
    t1 = s[65] ^ s[92]
    t2 = s[161] ^ s[176]
    t3 = s[242] ^ s[287]
    z = t1 ^ t2 ^ t3
    t1 ^= (s[90] & s[91]) ^ s[170]
    t2 ^= (s[174] & s[175]) ^ s[263]
    t3 ^= (s[285] & s[286]) ^ s[68]
    s[1:93] = s[0:92]
    s[0] = t3
    s[94:177] = s[93:176]
    s[93] = t1
    s[178:288] = s[177:287]
    s[177] = t2
    return z


def init(key, iv):
    s = load(key, iv)
    for _ in range(WARMUP):
        step(s)
    return s


def next_byte(s):
    value = 0
    for k in range(8):
        value |= step(s) << k
    return value


def keystream(key, iv, length):
    s = init(key, iv)
    return bytes(next_byte(s) for _ in range(length))


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


if __name__ == "__main__":
    key = bytes.fromhex("80000000000000000000")
    iv = bytes(10)
    message = b"Trivium is tiny."
    ciphertext = crypt(key, iv, message)
    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:  " + crypt(key, iv, ciphertext).decode())

Running it produces this output:

Key:        80000000000000000000
IV:         00000000000000000000
Keystream:  38eb86ff730d7a9caf8df13a4420540d
Plaintext:  5472697669756d2069732074696e792e
Ciphertext: 6c99ef891a7817bcc6fed14e2d4e2d23
Recovered:  Trivium is tiny.

I checked this code against two independent sources before writing it up. It reproduces every keystream slice in the official eSTREAM test vectors for 80-bit keys with 80-bit, 64-bit, and 32-bit IVs. That is 984 slices from 246 vectors. It also agrees with a literal port of an independent C++ reference implementation, written by Joris van Rantwijk, on 60 random keys and IVs, and on the five vectors listed in that code.

Limitations

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

• It is slow. Trivium is built to run bit by bit in hardware, and this Python version does the same, so it is far slower than software designed for bytes.
• Never reuse an IV. The code will happily encrypt two messages with the same key and IV, which leaks the XOR of the messages.
• No authentication. Trivium only hides the message. Anyone can flip bits in a ciphertext, so real systems add a MAC.
• Only 80 bits of key. That is a lower security level than modern designs aim for.

Security Status

No attack better than brute force on the full cipher is known. The published results work on a reduced number of warm-up rounds, or they are too expensive to matter. A cube attack by Zhang and Sun recovers keys in about 2⁵⁰ steps for 832 of the 1,152 warm-up rounds. Earlier cube attacks reached 799 rounds. Maximov and Biryukov showed in 2007 that recovering the state of the full cipher takes about 2⁸⁹·⁵ steps, which is still above the cost of searching the 80-bit key.

The small key is the main limit. Eighty bits is not a comfortable margin against a very large attacker. A variant with a 128-bit key would be needed for a higher security level, and Trivium itself does not offer one.

FAQ

What makes Trivium so small?

It needs only three shift registers, XOR gates, and three AND gates. There are no S-boxes, no multipliers, and no key schedule. A basic hardware version fits in about 3,500 gates.

Is Trivium secure?

No attack on the full cipher is known that beats brute force. The best attacks reach about 72 percent of the warm-up rounds. Its 80-bit key is the main concern for long-term use.

Why does Trivium run 1,152 rounds before output?

The nonlinear part is small, so the cipher needs many rounds for the key and IV to affect every state bit. The designers chose 1,152 rounds, which is four times the length of the state.

Where is Trivium used?

It is part of ISO/IEC 29192-3, which makes it a candidate for lightweight devices. It is mostly of interest for research and for constrained hardware.

Can I use a different IV length?

Yes, within the rules of the specification. The IV can be up to 80 bits long. The eSTREAM test vectors cover 80, 64, and 32-bit IVs, and this guide’s visualizer supports all three.

References

1. De Cannière, C. and Preneel, B. “Trivium Specifications.” eSTREAM, ECRYPT Stream Cipher Project. Available at: https://cr.yp.to/streamciphers/trivium/desc.pdf

2. De Cannière, C. and Preneel, B. “Trivium.” In New Stream Cipher Designs, Lecture Notes in Computer Science 4986, Springer, 2008.

3. Maximov, A. and Biryukov, A. “Two Trivial Attacks on Trivium.” Selected Areas in Cryptography (SAC) 2007.

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