Trivium (algorithm)

Structure of Trivium

Trivium is a synchronous stream cipher that represents a compromise between simple and high-performance implementation in hardware and efficient implementation in software.

Trivium was developed by the two Belgian cryptographers Bart Preneel and Christophe De Cannière . The two submitted the procedure as a candidate for Profile II (hardware procedure) of the eSTREAM competition . It is one of the three processes selected as the “winners” for Profile II. In a vote at the SASC cryptography conference in 2008, Trivium achieved by far the best rating among all processes in the eSTREAM portfolio (+4.35 on a scale from −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 2 ⁶⁴ bit keystream. One bit keystream is output per iteration. Switching and keystream extraction are not key-dependent. The key is only used to initialize the status. Of all the eSTREAM candidates, Trivium has the simplest design.

Although it shows considerable resistance to cryptanalysis for its simplicity and performance , some attacks that have become known recently make the existing security buffer appear to be quite small.

description

The 288 bit status of Trivium consists of three shift registers of different sizes . In each iteration, one bit is shifted to the beginning of the three shift registers. These bits are calculated by a non-linear combination of several bits from the respective and one of the other shift registers. The keystream bit is extracted by XORing six bits of the status, two from each of the three shift registers.

For initialization, the key and initialization vector are written to the status. Since you do not fill it out completely (80b Key + 80b IV <288b Status), the rest is assigned in a predefined, always the same way. Then 1136 iterations (four times the length of the status) are run through without calculating the keystream. After this initialization, the procedure is ready for use.

Because none of the tap variables are in the first 64 bits of one of the shift registers, each newly calculated bit is included in a calculation at the earliest 64 rounds after its generation. This ensures behavior that is very difficult to calculate and thus the security of the process.

specification

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

${\displaystyle a_{i}=c_{i-66}+c_{i-111}+c_{i-110}\times c_{i-109}+a_{i-69}}$

${\displaystyle b_{i}=a_{i-66}+a_{i-93}+a_{i-92}\times a_{i-91}+b_{i-78}}$

${\displaystyle c_{i}=b_{i-69}+b_{i-84}+b_{i-83}\times b_{i-82}+c_{i-87}}$

Then the keystream bits are calculated as follows: ${\displaystyle r_{0}...r_{2^{64}-1}}$

${\displaystyle r_{i}=c_{i-66}+c_{i-111}+a_{i-66}+a_{i-93}+b_{i-69}+b_{i-84}}$

The initialization takes place with an 80-bit key and an 1- bit initialization vector (where the following applies ): ${\displaystyle k_{0}...k_{79}}$ ${\displaystyle v_{0}...v_{l-1}}$ ${\displaystyle 0\leq l\leq 80}$

${\displaystyle (a_{-1245}...a_{-1153})=(0,0...0,k_{0}...k_{79})}$

${\displaystyle (b_{-1236}...a_{-1153})=(0,0...0,v_{0}...v_{l-1})}$

${\displaystyle (c_{-1263}...a_{-1153})=(1,1,1,0,0...0)}$

The large negative indexes result from the 1152 iterations that must be run through before the keystream is generated.

The little-endian representation is used to map a sequence of bits r to a sequence of bytes R :

${\displaystyle R_{i}=\sum _{j=0}^{7}2^{j}\times r_{8\times i+j}}$.

performance

A simple hardware implementation of Trivium requires 3488 logic gates and outputs one bit keystream per clock cycle. However, since each bit is included in a calculation at the earliest 64 rounds after its generation, an implementation can be built with slightly increased hardware requirements (5504 gates) that outputs 64 keystream bits in parallel. Further compromises are possible between speed and hardware requirements.

The same property enables efficient software implementation; Performance tests by eSTREAM showed an encryption speed of around 4 cycles / byte (on an x86 platform ), which is not bad considering the 19 cycles / byte of the reference implementation of the AES (on the same platform).

safety

"[Trivium] was designed as an exercise in exploring how far a stream cipher can be simplified without sacrificing 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 scrutiny despite their simplicity. "

“Trivium's design was an experiment in how much a stream cipher can be simplified without sacrificing security, speed, or flexibility. While simple designs are more likely to be susceptible to simple and potentially devastating attacks (which is why we strongly advise against using Trivium at this point in time), they certainly deserve more trust than complex designs if, despite their simplicity, they can withstand prolonged public scrutiny. "

- Christophe De Cannière , Bart Preneel : Trivium specifications (PDF; 92 kB). In: eSTREAM submitted papers.Retrieved April 29, 2005

So far (September 2010), no cryptanalysis attacks are better known than a full key search, but there are several attacks that are close to this limit. A cube attack takes 2 ³⁰ steps to break a variant of Trivium in which only 735 initialization rounds are carried out instead of 1152; the authors suspect that these techniques can also be applied to a variant with 1100 initialization rounds, or “possibly even the original method”. This attack is based on an attack by Michael Vielhaber, which breaks 576 initialization rounds in just 2 ^12.3 steps.

Another attack reveals the internal status (and thus the key) of the complete cipher in around 2 ^89.5 steps (each step being about as time-consuming as a single attempt at a complete key search). Simplified variants of Trivium, based on the same design principles, have been broken using an equation-solving technique. These attacks surpass the well-known TMTO (Time Memory Tradeoff) attack on stream ciphers, which would require ¹⁴⁴ steps in the case of the 288 bits of the internal status of Trivium 2 . They show that a variant of Trivium that differs from the original method only by increasing the key length beyond the 80 bits prescribed by eSTREAM Profile 2 would not be secure.

A detailed description of the design of Trivium can be found in Trivium - A Stream Cipher Construction Inspired by Block Cipher Design Principles .

Web links

• eSTREAM page about Trivium
• eSTREAM implementation

Individual evidence

1. ↑ Of the four methods that were originally selected, only three are now part of the portfolio, as a vulnerability was discovered in F-FCSR-H 2008
2. ↑ ISO / IEC 29192-3: 2012
3. ↑ eSTREAM Phorum, February 20, 2006
4. ↑ Itai Dinur, Adi Shamir: Cube Attacks on Tweakable Black Box Polynomials. (PDF, ePrint 20080914: 160327) Cryptology ePrint Archive , September 13, 2008, accessed December 4, 2008 . 
5. ↑ Michael Vielhaber: Breaking ONE.FIVIUM by AIDA an Algebraic IV Differential Attack . October 28, 2007. Retrieved March 5, 2011.
6. ↑ Michael Vielhaber: Shamir's "cube attack": A Remake of AIDA, The Algebraic IV Differential Attack . February 23, 2009. Retrieved on March 5, 2011.  ( Page no longer available , search in web archives )  Info: The link was automatically marked as defective. Please check the link according to the instructions and then remove this notice.  
7. ↑ Alexander Maximov, Alex Biryukov: Two Trivial Attacks on Trivium. (PDF) Cryptology ePrint, January 23, 2007, p. 11, Table 6 , accessed on February 3, 2015 . 
8. ↑ Håvard Raddum: cryptanalytic results on Trivium. ( PostScript ) eSTREAM submitted papers, March 27, 2006, accessed on September 10, 2006 . 
9. ↑ Christophe De Cannière, Bart Preneel : Trivium - A Stream Cipher Construction Inspired by Block Cipher Design Principles. (PDF) eSTREAM submitted papers, January 2, 2006, accessed October 9, 2006 .