Stream ciphers: Trivium

What is Trivium?

Trivium is a hardware oriented synchronous stream cipher, that was designed as an exercise in exploring how far a stream cipher can be simplified without sacrificing its security, speed or flexibility. 

Trivium is a synchronous stream cipher designed to generate up to 2 ^64 bits of key stream from an 80-bit secret key and an 80-bit initial value (IV), the process consists of two phases: first the interntal state of the cipher is initialized using the key and the IV, then the state is repeatedly updated and used to generate key stream bits. These are the parameters:

Key size: 80 bit

IV size: 80 bit

Internal state: 288 bit

Who invented Trivium?

It was submitted to a eSTREAM competition by its authors, Christophe De Cannière and Bart Preneel, and has been selected as part of the portfolio for low area hardware ciphers by the eSTREAM project, It's not patented.

How does It work?

Key stream generation; The proposed design contains a 288-bit internal state denoted by (s 1, ..., s 288). The key stream generation consists of an iterative process which extracts the values of 15 specific state bits and uses them both to update 3 bits of the state and to compute 1 bit of key stream z i. The state bits are then rotated and the process repeats itself until the requested N <= 2 ^64 bits of keys stream have been generated. Here is a pseudo-code:

Where "+" and "." operations stand for addition and multiplication over GF(2), which is the Galois Field of two elements (XOR and AND).

Key and IV setup; the algorithm is initialized by loading an 80-bit key and an 80-bit IV into the 288-bit initial state, and setting all remaining bits to 0, except for s ^286, s ^287 and 2 ^288, then the state is rotated over 4 full cycles without generating key stream bits.

Implementation  

Trivium is a hardware oriented design focussed on flexibility; It aims to be compact in environments with restrictions on the gate count, faster in applications that needs high-speed encryption and limited power resources. The design must provide a way to parallelize its operations, Trivium did it by ensuring any state bit that is not used for at least 64 iterations after it has been modified. This way, up to 64 iterations can be computed at once, provided that the 3 AND gates and 11 XOR gates in the original scheme are duplicated a corresponding number of times. This allows the clock frequency to be divided by a factor 64 without a ecting the throughput.

Attacks known

There are some attacks known as you can see below:

- Algebraic Attack

- Two Trivial Attacks

- Cube Attacks

Source:

Article where you can see specifications. 

http://www.ecrypt.eu.org/stream/p3ciphers/trivium/trivium_p3.pdf

Article Algebraic Attack
http://www-polsys.lip6.fr/~jcf/Papers/SCC08c.pdf

Two Trivial Attacks on Trivium
https://www.cosic.esat.kuleuven.be/ecrypt/stream/papersdir/2007/006.pdf

Cube Attacks on Trivium
http://eprint.iacr.org/2009/015.pdf