Paper 2007/021

Two Trivial Attacks on Trivium

Alexander Maximov and 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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Triviumstream ciphers
Contact author(s)
movax @ it lth se
History
2007-01-26: received
Short URL
https://ia.cr/2007/021
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/021,
      author = {Alexander Maximov and Alex Biryukov},
      title = {Two Trivial Attacks on Trivium},
      howpublished = {Cryptology ePrint Archive, Paper 2007/021},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/021}},
      url = {https://eprint.iacr.org/2007/021}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.