World Library  
Flag as Inappropriate
Email this Article

Trivium (cipher)

Article Id: WHEBN0002620653
Reproduction Date:

Title: Trivium (cipher)  
Author: World Heritage Encyclopedia
Language: English
Subject: Stream cipher, WikiProject Cryptography, Trivia (disambiguation), Nonlinear feedback shift register, LEX (cipher)
Collection: Stream Ciphers
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Trivium (cipher)

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.

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.

Contents

  • Description 1
  • Specification 2
  • Performance 3
  • Security 4
  • References 5
  • External links 6

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.

  • ai = ci−66 + ci−111 + ci−110ci−109 + ai−69
  • bi = ai−66 + ai−93 + ai−92ai−91 + bi−78
  • ci = bi−69 + bi−84 + bi−83bi−82 + ci−87

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

  • ri = ci−66 + ci−111 + ai−66 + ai−93 + bi−69 + bi−84

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

  • (a−1245 ... a−1153) = (0, 0 ... 0, k0 ... k79)
  • (b−1236 ... b−1153) = (0, 0 ... 0, v0 ... vl−1)
  • (c−1263 ... c−1153) = (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 Ri = Σj=0 ... 7 2j r8i+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][7]

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).[8] Reduced variants of Trivium using the same design principles have been broken using an equation-solving technique.[9] 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.[10]

A detailed justification of the design of Trivium is given in.[11]

References

  1. ^ ISO/IEC 29192-3:2012
  2. ^ eSTREAM Phorum, 2006-02-20
  3. ^ Christophe De Cannière,  
  4. ^ Fouque, Alain; Vannet, Thomas (2015-04-05). "Improving Key Recovery to 784 and 799 rounds of Trivium using Optimized Cube Attacks" (PDF).  
  5. ^ Dinur, Itai; Shamir, Adi (2008-09-13). "Cube Attacks on Tweakable Black Box Polynomials" (PDF).  
  6. ^ Michael Vielhaber (2007-10-28). "Breaking ONE.FIVIUM by AIDA an Algebraic IV Differential Attack". 
  7. ^ Michael Vielhaber (2009-02-23). "Shamir's "cube attack": A Remake of AIDA, The Algebraic IV Differential Attack" (PDF). 
  8. ^ Alexander Maximov,   (Table 6, page 11)
  9. ^ Håvard Raddum (2006-03-27). "Cryptanalytic results on Trivium" ( 
  10. ^ Pavol Zajac (2012-08-01). "Solving Trivium-based Boolean Equations Using the Method of Syllogisms". IOS Press. 
  11. ^ Christophe De Cannière,  

External links

  • eSTREAM page on Trivium
  • eSTREAM Implementation
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.