[Resource Topic] 2007/021: Two Trivial Attacks on Trivium

Welcome to the resource topic for 2007/021

Title:
Two Trivial Attacks on Trivium

Authors: Alexander Maximov, Alex Biryukov

Abstract:

Trivium is a stream cipher designed in 2005 by C. De Cannière and B. Preneel for the European project eSTREAM. It has successfully passed the first phase of the project and has been selected for a special focus in the second phase for the hardware portfolio of the project. Trivium has an internal state of size 288 bits and the key of length 80 bits. Although the design has a simple and elegant structure, no attack on it has been found yet. In this paper we study a class of Trivium-like designs. We propose a set of techniques that one can apply in cryptanalysis of such constructions. The first group of methods is for recovering the internal state and the secret key of the cipher, given a piece of a known keystream. Our attack is more than 2^{30} faster than the best known attack. Another group of techniques allows to gather statistics on the keystream, and to build a distinguisher. We study two designs: the original design of Trivium and a truncated version Bivium, which follows the same design principles as the original. We show that the internal state of the full Trivium can be recovered in time around c\cdot 2^{83.5}, and for Bivium this complexity is c\cdot 2^{36.1}. These are the best known results for these ciphers. Moreover, a distinguisher for Bivium with working time 2^{32} is presented, the correctness of which has been verified by simulations.

ePrint: https://eprint.iacr.org/2007/021

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .