Trivium (cipher)

Trivium is a synchronous stream cipher, which represents a compromise between simplicity and high-performance implementability in hardware and efficient software implementation.

Trivium was developed by two Belgian cryptographers Bart Preneel and Christophe De Cannière. Both filed the method as a candidate for the profile II (hardware method) of eSTREAM competition. It is one of the three methods that have been selected as the " winner" for the profile II. In a vote on the cryptography conference SASC in 2008 Trivium reached among all the methods of the eSTREAM portfolio by far the best rating ( 4.35 on a scale of -5 to 5). Trivium is not patented and has been standardized as ISO / IEC 29192-3.

Trivium generated from a 80 bit key and a 80 -bit initialization vector up to 264 bit keystream. A keystream bit is output for each iteration. Stepping and keystream extraction are not key -dependent. The key is only used to initialize the state. Of all the eSTREAM candidates Trivium has the simplest design.

Although it shows a remarkable for its simplicity and performance resistance to cryptanalysis, but leave some have become known in recent times attacks the existing security buffer appear to be quite small.

Description

The 288 -bit wide status of Trivium consists of three different sized shift registers. At each iteration a bit is shifted to the beginning of the three shift registers each. Those bits are calculated by a non-linear combination of multiple bits from each other and one of the shift register. The extraction of the keystream bits is by a XOR operation of the six bits of the status, two from each of the three shift registers instead.

Initialization key and initialization vector are written to the status. Since they do not completely fill it (80b 80b Key IV < 288b status ), the rest is occupied on a predefined, always the same way. After 1136 iterations are run ( Four times the length of the state ), without compromising key stream is calculated. After this initialization, the process is ready for use.

Because none of the Tap- variables is in the first 64 bits of the shift register, each newly computed bit is earlier than 64 rounds after its generation turn into a calculation. This makes for a very difficult predictable behavior and thus for the safety of the procedure.

Specification

Trivium can be easily described by the following three recursive equations. All variables are elements of GF (2); they can be represented as bits, where " " an XOR operation and "× " indicates an AND operation.

Then the keystream bits are calculated as follows:

Initialization is performed with a 80 -bit key and a l -bit initialization vector ( which is true ) in this way:

The large negative indices stem from the 1152 iterations which must be executed before keystream is generated.

To represent a sequence of bits in a sequence of bytes r R, the little endian format is used:

Performance

A simple hardware implementation of Trivium needs 3488 logic gates and gives a bit keystream per clock cycle. However, one can, as each bit earlier than 64 rounds is received after its generation in a calculation, with slightly enhanced hardware requirement ( gate 5504 ) build an implementation that outputs 64 keystream bits in parallel. There are other trade-offs between speed and hardware requirements possible.

The same property allows for efficient software implementation; Performance testing of eSTREAM revealed an encryption speed of about 4 cycles / byte (on an x86 platform ), which ( on the same platform ) is not bad considering the 19 cycles / byte of the reference implementation of the AES.

Security

" [ Trivium ] which designed as to exercise in exploring how far a stream cipher can be simplified without apparel choice its security, speed or flexibility. While simple designs are more likely to be vulnerable to simple, and Possibly devastating, attacks ( Which is why we 'strongly discourage the use of Trivium at this stage ), THEY Certainly inspire more confidence than complex schemes, If They survive a long period of public Despite scrutiny Their simplicity. "

"The design of Trivium was an experiment how far a stream cipher can be simplified without sacrificing security, speed or flexibility. While simple designs with a higher probability are prone to simple and potentially devastating attacks (which is why we strongly advise against the current time from the use of Trivium ), they certainly deserve more confidence than complex designs when they stand up in spite of its simplicity, a longer public review. "

To date (September 2010 ), no cryptanalytic attacks are better known as a full key search, but there are several attacks that are near this limit. A cube attack ( s) requires 230 steps to break a variant of Trivium, are in place through 1152 only 735 Initialisierungsrunden; the authors suggest that these techniques can also be applied to a variant with 1100 Initialisierungsrunden, or " possibly even the original trial " This attack is based on an attack of Michael Vielhaber that breaks 576 Initialisierungsrunden in only 212.3 steps.

Another attack reveals the internal state (and thus the key ) of the complete cipher in about 289.5 steps ( each step is about as complex as a single attempt at a full key lookup ). Simplified versions of Trivium that are built on the same design principles were broken by means of a technique for solving equations .. These attacks surpass the known TMTO attack ( time-memory trade-off ) on stream ciphers, the of in the case of the 288 bits of internal state Trivium would need 2144 steps. They show that a variant of Trivium, which differs from the original method only by increasing the key length is specified by the eSTREAM Profile 2 80-bit addition, would not be safe.

A detailed description of the design of Trivium can be found in.