Trivium (cipher)

Last updated
Structure of Trivium Trivium (cipher).png
Structure of Trivium

Trivium is a synchronous stream cipher designed to provide a flexible trade-off between speed and gate count in hardware, and reasonably efficient software implementation.

Contents

Trivium was submitted to the Profile II (hardware) of the 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 (Profile 2) by the eSTREAM project. It is not patented and has been specified as an International Standard under ISO/IEC 29192-3. [1]

It generates up to 264 bits of output from an 80-bit key and an 80-bit IV. It is the simplest eSTREAM entrant; while it shows remarkable resistance to cryptanalysis for its simplicity and performance, recent attacks leave the security margin looking rather slim.

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 65 bits of each shift register, so each novel state bit is not used until at least 65 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. [2] Each variable is an element of GF(2); they can be represented as bits, with "+" being XOR and "•" being AND.

The output bits r0 ... r264−1 are then generated by

Given an 80-bit key k0 ... k79 and an l-bit IV v0 ... vl−1 (where 0 ≤ l < 80), Trivium is initialized as follows:

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 LSb-first mapping Ri = Σj=0, ..., 7 2jr8i+j.

Performance

A straightforward hardware implementation of Trivium would use 3488 logic gates and produce one bit per clock cycle. However, because each 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] 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. [3]

As of April 2015, no cryptanalytic attacks better than brute-force attack are known, but several attacks come close. The cube attack requires 268 steps to break a variant of Trivium where the number of initialization rounds is reduced to 799. [4] Previously other authors speculate that these techniques could lead to a break for 1100 initialisation rounds, or "maybe even the original cipher". [5] This builds on an attack due to Michael Vielhaber that breaks 576 initialization rounds in only 212.3 steps. [6]

Another attack recovers the internal state (and thus the key) of the full cipher in around 289.5 steps (where each step is roughly the cost of a single trial in exhaustive search). [7] Reduced variants of Trivium using the same design principles have been broken using an equation-solving technique. [8] These attacks improve on the well-known time-space tradeoff attack on stream ciphers, which with Trivium's 288-bit internal state would take 2144 steps, and show that a variant on Trivium which made no change except to increase the key length beyond the 80 bits mandated by eSTREAM Profile 2 would not be secure. Using optimised solving strategy, it is further possible to reduce the state-recovery complexity to 2132 steps. [9]

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

Related Research Articles

<span class="mw-page-title-main">Advanced Encryption Standard</span> Standard for the encryption of electronic data

The Advanced Encryption Standard (AES), also known by its original name Rijndael, is a specification for the encryption of electronic data established by the U.S. National Institute of Standards and Technology (NIST) in 2001.

<span class="mw-page-title-main">International Data Encryption Algorithm</span>

In cryptography, the International Data Encryption Algorithm (IDEA), originally called Improved Proposed Encryption Standard (IPES), is a symmetric-key block cipher designed by James Massey of ETH Zurich and Xuejia Lai and was first described in 1991. The algorithm was intended as a replacement for the Data Encryption Standard (DES). IDEA is a minor revision of an earlier cipher Proposed Encryption Standard (PES).

In cryptography, RC4 is a stream cipher. While it is remarkable for its simplicity and speed in software, multiple vulnerabilities have been discovered in RC4, rendering it insecure. It is especially vulnerable when the beginning of the output keystream is not discarded, or when nonrandom or related keys are used. Particularly problematic uses of RC4 have led to very insecure protocols such as WEP.

In cryptography, an initialization vector (IV) or starting variable (SV) is an input to a cryptographic primitive being used to provide the initial state. The IV is typically required to be random or pseudorandom, but sometimes an IV only needs to be unpredictable or unique. Randomization is crucial for some encryption schemes to achieve semantic security, a property whereby repeated usage of the scheme under the same key does not allow an attacker to infer relationships between segments of the encrypted message. For block ciphers, the use of an IV is described by the modes of operation.

ISAAC is a cryptographically secure pseudorandom number generator and a stream cipher designed by Robert J. Jenkins Jr. in 1993. The reference implementation source code was dedicated to the public domain.

<span class="mw-page-title-main">XTEA</span> Block cipher

In cryptography, XTEA is a block cipher designed to correct weaknesses in TEA. The cipher's designers were David Wheeler and Roger Needham of the Cambridge Computer Laboratory, and the algorithm was presented in an unpublished technical report in 1997. It is not subject to any patents.

Phelix is a high-speed stream cipher with a built-in single-pass message authentication code (MAC) functionality, submitted in 2004 to the eSTREAM contest by Doug Whiting, Bruce Schneier, Stefan Lucks, and Frédéric Muller. The cipher uses only the operations of addition modulo 232, exclusive or, and rotation by a fixed number of bits. Phelix uses a 256-bit key and a 128-bit nonce, claiming a design strength of 128 bits. Concerns have been raised over the ability to recover the secret key if the cipher is used incorrectly.

In cryptography, a related-key attack is any form of cryptanalysis where the attacker can observe the operation of a cipher under several different keys whose values are initially unknown, but where some mathematical relationship connecting the keys is known to the attacker. For example, the attacker might know that the last 80 bits of the keys are always the same, even though they don't know, at first, what the bits are. This appears, at first glance, to be an unrealistic model; it would certainly be unlikely that an attacker could persuade a human cryptographer to encrypt plaintexts under numerous secret keys related in some way.

Bart Preneel is a Flemish cryptographer and cryptanalyst. He is a professor at Katholieke Universiteit Leuven, in the COSIC group.

Introduced by Martin Hellman and Susan K. Langford in 1994, the differential-linear attack is a mix of both linear cryptanalysis and differential cryptanalysis.

<span class="mw-page-title-main">VEST</span> Family of stream ciphers

VEST (Very Efficient Substitution Transposition) ciphers are a set of families of general-purpose hardware-dedicated ciphers that support single pass authenticated encryption and can operate as collision-resistant hash functions designed by Sean O'Neil, Benjamin Gittins and Howard Landman. VEST cannot be implemented efficiently in software.

<span class="mw-page-title-main">Salsa20</span> Stream ciphers

Salsa20 and the closely related ChaCha are stream ciphers developed by Daniel J. Bernstein. Salsa20, the original cipher, was designed in 2005, then later submitted to the eSTREAM European Union cryptographic validation process by Bernstein. ChaCha is a modification of Salsa20 published in 2008. It uses a new round function that increases diffusion and increases performance on some architectures.

Grain is a stream cipher submitted to eSTREAM in 2004 by Martin Hell, Thomas Johansson and Willi Meier. It has been selected for the final eSTREAM portfolio for Profile 2 by the eSTREAM project. Grain is designed primarily for restricted hardware environments. It accepts an 80-bit key and a 64-bit IV. The specifications do not recommend a maximum length of output per pair. A number of potential weaknesses in the cipher have been identified and corrected in Grain 128a which is now the recommended cipher to use for hardware environments providing both 128bit security and authentication.

Py is a stream cipher submitted to eSTREAM by Eli Biham and Jennifer Seberry. It is one of the fastest eSTREAM candidates at around 2.6 cycles per byte on some platforms. It has a structure a little like RC4, but adds an array of 260 32-bit words which are indexed using a permutation of bytes, and produces 64 bits in each round.

Rabbit is a high-speed stream cipher from 2003. The algorithm and source code was released in 2008 as public domain software.

The cube attack is a method of cryptanalysis applicable to a wide variety of symmetric-key algorithms, published by Itai Dinur and Adi Shamir in a September 2008 preprint.

This article summarizes publicly known attacks against block ciphers and stream ciphers. Note that there are perhaps attacks that are not publicly known, and not all entries may be up to date.

In cryptography, Mutual Irregular Clocking KEYstream generator (MICKEY) is a stream cipher algorithm developed by Steve Babbage and Matthew Dodd. The cipher is designed to be used in hardware platforms with limited resources, and was one of the three ciphers accepted into Profile 2 of the eSTREAM portfolio. The algorithm is not patented and is free for any use.

Prince is a block cipher targeting low latency, unrolled hardware implementations. It is based on the so-called FX construction. Its most notable feature is the alpha reflection: the decryption is the encryption with a related key which is very cheap to compute. Unlike most other "lightweight" ciphers, it has a small number of rounds and the layers constituting a round have low logic depth. As a result, fully unrolled implementation are able to reach much higher frequencies than AES or PRESENT. According to the authors, for the same time constraints and technologies, PRINCE uses 6–7 times less area than PRESENT-80 and 14–15 times less area than AES-128.

<span class="mw-page-title-main">Orr Dunkelman</span> Israeli cryptographer and cryptanalyst

Orr Dunkelman is an Israeli cryptographer and cryptanalyst, currently a professor at the University of Haifa Computer Science department. Dunkelman is a co-director of the Center for Cyber Law & Privacy at the University of Haifa and a co-founder of Privacy Israel, an Israeli NGO for promoting privacy in Israel.

References

  1. ↑ ISO/IEC 29192-3:2012
  2. ↑ eSTREAM Phorum, 2006-02-20
  3. ↑ Christophe De Cannière, Bart Preneel (2005-04-29). "Trivium specifications" (PDF). eSTREAM submitted papers. Retrieved 2006-10-09.{{cite journal}}: Cite journal requires |journal= (help)
  4. ↑ Fouque, Pierre-Alain; Vannet, Thomas (2015-04-05). "Improving Key Recovery to 784 and 799 rounds of Trivium using Optimized Cube Attacks" (PDF). Cryptology ePrint Archive. ePrint 20150406:231124. Retrieved 2015-04-17.{{cite journal}}: Cite journal requires |journal= (help)
  5. ↑ Dinur, Itai; Shamir, Adi (2008-09-13). "Cube Attacks on Tweakable Black Box Polynomials" (PDF). Cryptology ePrint Archive. ePrint 20080914:160327. Retrieved 2008-12-04.{{cite journal}}: Cite journal requires |journal= (help)
  6. ↑ Michael Vielhaber (2007-10-28). "Breaking ONE.FIVIUM by AIDA an Algebraic IV Differential Attack".
  7. ↑ Alexander Maximov, Alex Biryukov (2007-01-23). "Two Trivial Attacks on Trivium" (PDF). Cryptology ePrint.{{cite journal}}: Cite journal requires |journal= (help) (Table 6, page 11)
  8. ↑ Håvard Raddum (2006-03-27). "Cryptanalytic results on Trivium" (PostScript). eSTREAM submitted papers. Retrieved 2006-10-09.{{cite journal}}: Cite journal requires |journal= (help)
  9. ↑ Pavol Zajac (2012-08-01). "Solving Trivium-based Boolean Equations Using the Method of Syllogisms". IOS Press.{{cite journal}}: Cite journal requires |journal= (help)
  10. ↑ Christophe De Cannière, Bart Preneel (2006-01-02). "Trivium - A Stream Cipher Construction Inspired by Block Cipher Design Principles" (PDF). eSTREAM submitted papers. Retrieved 2006-10-09.{{cite journal}}: Cite journal requires |journal= (help)
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.