Trivium (cipher) - AbsoluteAstronomy.com

Trivium is a synchronous stream cipher

Stream cipher

In cryptography, a stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream . In a stream cipher the plaintext digits are encrypted one at a time, and the transformation of successive digits varies during the encryption...

designed to provide a flexible trade-off between speed and gate count

Gate count

In microprocessor design, gate count refers to the number of gates build with transistor and other electronic devices, that are needed to implement a design. Even with today's process technology providing what was formerly considered impossible numbers of gates on a single chip, gate counts remain...

in hardware, and reasonably efficient software implementation.

It was submitted to the Profile II (hardware) of the eSTREAM

ESTREAM

eSTREAM is a project to "identify new stream ciphers suitable for widespread adoption", organised by the EU ECRYPT network. It was set up as a result of the failure of all six stream ciphers submitted to the NESSIE project. The call for primitives was first issued in November 2004. The project was...

competition by its authors, Christophe De Cannière and Bart Preneel

Bart Preneel

Bart Preneel is a Belgian cryptographer and cryptanalyst. He is a professor at Katholieke Universiteit Leuven, in the COSIC group, president of the International Association for Cryptologic Research, and project manager of ECRYPT....

, and has been selected as part of the portfolio for low area hardware ciphers (Profile 2) by the eSTREAM project. It is not patented.

It generates up to 2⁶⁴ bit

Bit

A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...

s of output from an 80-bit key and an 80-bit IV

Initialization vector

In cryptography, an initialization vector is a fixed-size input to a cryptographic primitive that is typically required to be random or pseudorandom...

. 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 register

Shift register

In digital circuits, a shift register is a cascade of flip flops, sharing the same clock, which has the output of any one but the last flip-flop connected to the "data" input of the next one in the chain, resulting in a circuit that shifts by one position the one-dimensional "bit array" stored in...

s 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. Each variable is an element of GF

Finite field

In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...

(2); they can be represented as bit

Bit

s, with "+" being XOR and "•" 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 (where 0 ≤ l ≤ 80), Trivium is initialized as follows:

(a₋₁₂₄₅ ... a₋₁₁₅₃) = (0, 0 ... 0, k₀ ... k₇₉)
(b₋₁₂₃₆ ... b₋₁₁₅₃) = (0, 0 ... 0, v₀ ... v_l−1)
(c₋₁₂₆₃ ... c₋₁₁₅₃) = (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 gate

Logic gate

A logic gate is an idealized or physical device implementing a Boolean function, that is, it performs a logical operation on one or more logic inputs and produces a single logic output. Depending on the context, the term may refer to an ideal logic gate, one that has for instance zero rise time and...

s 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

ESTREAM

give bulk encryption speeds of around 4 cycles/byte

Cycles per byte

Cycles per byte is a unit of measurement which indicates the number of clock cycles a microprocessor will perform per byte of data processed in an algorithm. It is commonly used as a partial indicator of real-world performance in cryptographic functions....

on some x86 platforms, which compares well to the 19 cycles/byte of the AES

Advanced Encryption Standard

Advanced Encryption Standard is a specification for the encryption of electronic data. It has been adopted by the U.S. government and is now used worldwide. It supersedes DES...

reference implementation on the same platform.

Security

, no cryptanalytic attacks better than brute force attack

Brute force attack

In cryptography, a brute-force attack, or exhaustive key search, is a strategy that can, in theory, be used against any encrypted data. Such an attack might be utilized when it is not possible to take advantage of other weaknesses in an encryption system that would make the task easier...

are known, but several attacks come close. The cube attack

Cube attack

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...

requires 2³⁰ steps to break a variant of Trivium where the number of initialization rounds is reduced to 735; the authors speculate that these techniques could lead to a break for 1100 initialisation rounds, or "maybe even the original cipher". This builds on an attack due to Michael Vielhaber that breaks 576 initialization rounds in only 2^12.3 steps.

Another attack recovers the internal state (and thus the key) of the full cipher in around 2^89.5 steps (where each step is roughly the cost of a single trial in exhaustive search). Reduced variants of Trivium using the same design principles have been broken using an equation-solving technique. These attacks improve on the well-known time-space tradeoff attack on stream ciphers, which with Trivium's 288-bit internal state would take 2¹⁴⁴ 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.

A detailed justification of the design of Trivium is given in.

External links

The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.