Trivium (Algorithmus)

Trivium is a simple synchronous stream cipher designed to provide a flexible trade-off between speed and gate count in hardware, and reasonably efficient software implementation. It generates up to 2^{64 bits of output from an 80-bit key and an 80-bit IV.}

Trivium is submitted to the Profile II (hardware) of the eSTREAM competition by its authors, Christophe De Cannière and Bart Preneel. It is not patented.

Description

Trivium's 288-bit internal state consists of three shift registers of different lengths. At each round, a bit is shifted into each of the three shift registers using a non-linear combination of taps from that and one other register; one bit of output is produced. To initialize the cipher, the key and IV are written into two of the shift registers, with the remaining bits starting in a fixed pattern; the cipher state is then updated 4 × 288 = 1152 times, so that every bit of the internal state depends on every bit of the key and of the IV in a complex nonlinear way.

No taps appear on the first 64 bits of each shift register, so each novel state bit is not used until at least 64 rounds after it is generated. This is the key to Trivium's software performance and flexibility in hardware.

Specification

Trivium may be specified very concisely using three recursive equations [1]. Each variable is an element of GF(2); they can be represented as bits, with "+" being XOR and multiplication being AND.

a_i = c_i-66 + c_i-111 + c_i-110 c_i-109 + a_i-69
b_i = a_i-66 + a_i-93 + a_i-92 a_i-91 + b_i-78
c_i = b_i-69 + b_i-84 + b_i-83 b_i-82 + c_i-87

The output bits r₀ ... r_2⁶⁴-1 are then generated by

r_i = c_i-66 + c_i-111 + a_i-66 + a_i-93 + b_i-69 + b_i-84

Given an 80-bit key k₀ ... k₇₉ and an l-bit IV v₀ ... v_l-1, Trivium is initialized as follows:

(a_-1245 ... a_-1153) = (0, 0 ... 0, k₀ ... k₇₉)
(b_-1236 ... b_-1153) = (0, 0 ... 0, v₀ ... v_l-1)
(c_-1263 ... c_-1153) = (1, 1, 1, 0, 0 ... 0)

The large negative indices on the initial values reflect the 1152 steps that must take place before output is produced.

To map a stream of bits r to a stream of bytes R, we use the little-endian mapping R_i = Σ_{j=0 ... 7} 2^j r_8i+j.

Performance

A straightforward hardware implementation of Trivium would use 3488 logic gates and produce one bit per clock cycle. However, because each novel state bit is not used for at least 64 rounds, 64 state bits can be generated in parallel at a slightly greater hardware cost of 5504 gates. Different tradeoffs between speed and area are also possible.

The same property allows an efficient bitslice implementation in software; performance testing by eSTREAM give bulk encryption speeds of around 4 cycles/byte on some x86 platforms, which compares well to the 19 cycles/byte of the AES reference implementation on the same platform.

Security

Trivium's security is bounded by its 80-bit key length. As of January 2006, no cryptanalytic attacks better than brute force attack are known; the best attack, by Shahram Khazaei, requires around 2¹³⁵ operations [2].

A detailed justification of the design of Trivium is given in the paper "Trivium - A Stream Cipher Construction Inspired by Block Cipher Design Principles".

No new design should be fielded for real use until it has survived a period of public scrutiny, and Trivium's design is also fairly novel. The authors express the hope that its simple design should inspire greater confidence in its security once it survives such scrutiny.

External links

Vorlage:Stream ciphers