Two Trivial Attacks on Trivium
Trivium is a stream cipher designed in 2005 by C. De Cannière and B. Preneel for the European project eSTREAM. It has an internal state of 288 bits and the key of length 80 bits. Although the design has a simple and elegant structure, no attack on it has
- PDF / 435,683 Bytes
- 20 Pages / 430 x 660 pts Page_size
- 61 Downloads / 214 Views
Abstract. Trivium is a stream cipher designed in 2005 by C. De Canni`ere and B. Preneel for the European project eSTREAM. It has an internal state of 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 a family of Trivium-like designs is studied. We propose a set of techniques for methodological cryptanalysis of these structures in general, including state recovering and linear distinguishing attacks. In particular, we study the original Trivium and present a state recovering attack with time complexity around c283.5 , which is 230 faster than the best previous result. Our attack clearly shows that Trivium has a very thin safety margin and that in its current form it can not be used with longer 128-bit keys. Finally, we identify interesting open problems and propose a new design Trivium/128, which resists all of our attacks proposed in this paper. It also accepts a 128 bit secret key due to the improved security level.
1
Introduction
Additive stream ciphers are an important class of data encryption primitives, in which the process of encryption simulates the one-time-pad. The core of any stream cipher is its pseudo-random keystream generator (PRKG). It is initialized with a secret key K, and an initial value (IV). Afterwards, it produces a long pseudo-random sequence called keystream u. In the encryption procedure, the ciphertext c is then obtained by a bitwise xor of the message m and the keystream u, i.e., c = m ⊕ u. Many stream ciphers are currently used in various aspects of our life. To mention some of them, they are: RC4 [Sma03] (is used on the Internet), E0 [Blu03] (in Bluetooth), A5/1 [BGW99] (in GSM communication), and others. However, it has been shown that these primitives are susceptible to various kinds of weaknesses and attacks [FM00, MS01, LV04, LMV05, BSW00, MJB04]. In 1999 the European project NESSIE was launched [NES99] and among other encryption and signature primitives it attempted to select stream ciphers for its final portfolio. However after a few rounds of evaluation and cryptanalysis, most of the C. Adams, A. Miri, and M. Wiener (Eds.): SAC 2007, LNCS 4876, pp. 36–55, 2007. c Springer-Verlag Berlin Heidelberg 2007
Two Trivial Attacks on Trivium
37
proposals were broken1 . As a result the board of the project NESSIE could not select any of the stream cipher proposals for its final portfolio. The recent European project ECRYPT [ECR05] has started in 2004 within the Sixth Framework Programme (FP6). It announced a new call for stream cipher proposals, for its subproject eSTREAM. In the first phase 34 proposals were received, but only a few of them got the status of “focused” algorithms in the second phase. In the hardware portfolio only four new designs are in focus, they are: Trivium [CP05], Grain [HJM05], Mickey [BD05], and Phelix [WSLM05]. In this paper we analyze one of these designs – Trivium. The stream cipher Trivium was proposed in 2005 for the project eSTREAM by C. De Canni´ere and B. Pr
Data Loading...
