FACTOID # 7: The top five best educated states are all in the Northeast.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Trivium (cipher)
Structure of Trivium
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. Image File history File links Size of this preview: 569 × 600 pixelsFull resolution (1600 × 1686 pixel, file size: 155 KB, MIME type: image/png) Source: http://www. ... Image File history File links Size of this preview: 569 × 600 pixelsFull resolution (1600 × 1686 pixel, file size: 155 KB, MIME type: image/png) Source: http://www. ... Look up trivia, trivial in Wiktionary, the free dictionary. ... The operation of A5/1, a LFSR-based stream cipher used to encrypt mobile phone conversations. ... In microprocessor design, gate count refers to the number of transistor switches, or gates, that are needed to implement a design. ...


It was submitted[1] to the Profile II (hardware) of the eSTREAM competition by its authors, Christophe De Cannière and Bart Preneel, and has been selected as Phase 2 Focus Candidate for Profile 2 by the eSTREAM project. It is not patented. eSTREAM is a project to identify new stream ciphers that might become suitable for widespread adoption, organised by the EU ECRYPT network. ... Bart Preneel is a Belgian cryptographer and cryptanalyst. ...


It generates up to 264 bits of output from an 80-bit key and an 80-bit IV. It is the simplest eSTREAM entrant, and shows remarkable resistance to cryptanalysis for its simplicity. This article is about the unit of information. ... In cryptography, the key size (alternatively key length) is a measure of the number of possible keys which can be used in a cipher. ... In cryptography, an initialization vector (IV) is a block of bits that is required to allow a stream cipher or a block cipher executed in any of several streaming modes of operation to produce a unique stream independent from other streams produced by the same encryption key, without having to...

Contents

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. In digital circuits a shift register is a group of registers set up in a linear fashion which have their inputs and outputs connected together in such a way that the data is shifted down the line when the circuit is activated. ...


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.[2] Each variable is an element of GF(2); they can be represented as bits, with "+" being XOR and multiplication being AND. In abstract algebra, a finite field or Galois field (so named in honor of Évariste Galois) is a field that contains only finitely many elements. ... This article is about the unit of information. ... Exclusive disjunction (usual symbol xor) is a logical operator that results in true if one of the operands (not both) is true. ... If two conditions are combined by and, they must both be true for the compound condition to be true as well. ...

  • ai = ci-66 + ci-111 + ci-110 ci-109 + ai-69
  • bi = ai-66 + ai-93 + ai-92 ai-91 + bi-78
  • ci = bi-69 + bi-84 + bi-83 bi-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. A logic gate performs a logical operation on one or more logic inputs and produces a single logic output. ...


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. eSTREAM is a project to identify new stream ciphers that might become suitable for widespread adoption, organised by the EU ECRYPT network. ... x86 or 80x86 is the generic name of a microprocessor architecture first developed and manufactured by Intel. ... In cryptography, the Advanced Encryption Standard (AES), also known as Rijndael, is a block cipher adopted as an encryption standard by the U.S. government. ...


Security

According to the authors, 'Trivium was designed as an exercise in exploring how far a stream cipher can be simplified without sacrificing its security, speed or flexibility'.


The Trivium authors claim in the specifications that simple designs like Trivium are more likely to be vulnerable to simple, and possibly devastating, attacks. Such schemes are offered as they 'certainly inspire more confidence than complex schemes, if they survive a long period of public scrutiny despite their simplicity'. The authors 'strongly discourage the use of Trivium at this stage'.


As of June 2007, no cryptanalytic attacks better than brute force attack are known. The best attack in 2006, by Shahram Khazaei, requires around 2135 operations.[3][4] The best attack in 2007, by Alexander Maximov and Alex Biryukov, claims that the internal state of the full Trivium can be recovered in time around .[5] Year 2007 (MMVII) is the current year, a common year starting on Monday of the Gregorian calendar and the AD/CE era. ... The EFFs US$250,000 DES cracking machine contained over 1,800 custom chips and could brute force a DES key in a matter of days — the photograph shows a DES Cracker circuit board fitted with several Deep Crack chips. ... Year 2006 (MMVI) was a common year starting on Sunday (link displays full 2006 calendar) of the Gregorian calendar. ... Year 2007 (MMVII) is the current year, a common year starting on Monday of the Gregorian calendar and the AD/CE era. ...


Reduced variants of Trivium corresponding to the design's basic construction have been broken using an equation-solving technique.[6] The paper claims that the current implementation of their equation-solving attack can not break the full Trivium cipher due to the short key-length when compared to the size of the internal state of the cipher.


The Trivium specifications do not support the use of keys at least twice the security rating of the cipher to prevent parallel brute-force attacks as recommend by Daniel J. Bernstein in his paper "Understanding Brute Force" [7]. A detailed justification of the design of Trivium is given in [8].


References

  1. ^ Christophe De Cannière, Bart Preneel (2005-04-29). "Trivium specifications" (PDF). eSTREAM submitted papers. Retrieved on 2006-10-09.
  2. ^ eSTREAM Phorum, 2006-02-20
  3. ^ Shahram Khazaei, Mehdi Hassanzadeh (2005-09-27). "Linear Sequential Circuit Approximation of the TRIVIUM Stream Cipher" (PDF). eSTREAM submitted papers. Retrieved on 2006-10-09.
  4. ^ Shahram Khazaei (2006-02-21). Re: A reformulation of TRIVIUM. eSTREAM discussion forum. Retrieved on 2007-01-15.
  5. ^ Alexander Maximov, Alex Biryukov (2007-01-23). "Two Trivial Attacks on Trivium" (PDF). Cryptology ePrint.
  6. ^ Håvard Raddum (2006-03-27). "Cryptanalytic results on Trivium" (PostScript). eSTREAM submitted papers. Retrieved on 2006-10-09.
  7. ^ Daniel J. Bernstein (2005-04-25). "Understanding Brute Force" (PDF). cr.yp.to. Retrieved on 2006-10-09.
  8. ^ 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 on 2006-10-09.

Bart Preneel is a Belgian cryptographer and cryptanalyst. ... PDF is an abbreviation with several meanings: Portable Document Format Post-doctoral fellowship Probability density function There also is an electronic design automation company named PDF Solutions. ... Year 2006 (MMVI) was a common year starting on Sunday (link displays full 2006 calendar) of the Gregorian calendar. ... is the 282nd day of the year (283rd in leap years) in the Gregorian calendar. ... PDF is an abbreviation with several meanings: Portable Document Format Post-doctoral fellowship Probability density function There also is an electronic design automation company named PDF Solutions. ... Year 2006 (MMVI) was a common year starting on Sunday (link displays full 2006 calendar) of the Gregorian calendar. ... is the 282nd day of the year (283rd in leap years) in the Gregorian calendar. ... Year 2007 (MMVII) is the current year, a common year starting on Monday of the Gregorian calendar and the AD/CE era. ... January 15 is the 15th day of the year in the Gregorian calendar. ... PDF is an abbreviation with several meanings: Portable Document Format Post-doctoral fellowship Probability density function There also is an electronic design automation company named PDF Solutions. ... PostScript (PS) is a page description language and programming language used primarily in the electronic and desktop publishing areas. ... Year 2006 (MMVI) was a common year starting on Sunday (link displays full 2006 calendar) of the Gregorian calendar. ... is the 282nd day of the year (283rd in leap years) in the Gregorian calendar. ... Daniel Julius Bernstein (sometimes known simply as djb; born October 29, 1971) is a professor at the University of Illinois at Chicago, a mathematician, a cryptologist, and a programmer. ... PDF is an abbreviation with several meanings: Portable Document Format Post-doctoral fellowship Probability density function There also is an electronic design automation company named PDF Solutions. ... Year 2006 (MMVI) was a common year starting on Sunday (link displays full 2006 calendar) of the Gregorian calendar. ... is the 282nd day of the year (283rd in leap years) in the Gregorian calendar. ... Bart Preneel is a Belgian cryptographer and cryptanalyst. ... PDF is an abbreviation with several meanings: Portable Document Format Post-doctoral fellowship Probability density function There also is an electronic design automation company named PDF Solutions. ... Year 2006 (MMVI) was a common year starting on Sunday (link displays full 2006 calendar) of the Gregorian calendar. ... is the 282nd day of the year (283rd in leap years) in the Gregorian calendar. ...

External links

Stream ciphers
v  d  e
Algorithms: A5/1 | A5/2 | E0 | FISH | Grain | HC-256 | ISAAC | LILI-128 | MUGI | Panama | Phelix | Pike | Py | Rabbit | RC4 | Salsa20 | Scream | SEAL | SOBER | SOBER-128 | SOSEMANUK | Trivium | VEST | WAKE
Theory: Shift register | LFSR | NLFSR | Shrinking generator | T-function | IV
Standardization: eSTREAM
Cryptography
v  d  e
History of cryptography | Cryptanalysis | Cryptography portal | Topics in cryptography
Symmetric-key algorithm | Block cipher | Stream cipher | Public-key cryptography | Cryptographic hash function | Message authentication code | Random numbers

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m