Trivium (Algorithmus)

Struktur von Trivium

Trivium ist eine synchrone Stromchiffre, die einen Kompromiss zwischen einfacher und performanter Umsetzbarkeit in Hardware und effizienter Implementierung in Software darstellt.

Trivium wurde von den beiden belgischen Kryptographen Bart Preneel und Christophe De Cannière entwickelt. Die beiden reichten das Verfahren als Kandidaten für das Profil II (Hardware-Verfahren) des eSTREAM-Wettbewerbs ein. Es gehört zu den drei Verfahren^[1], die als „Gewinner“ für das Profil II ausgewählt wurden. Bei einer Abstimmung auf der Kryptographie-Konferenz SASC im Jahre 2008 erreichte Trivium unter allen Verfahren des eSTREAM-Portfolios die mit Abstand beste Bewertung (+4,35 bei einer Skala von -5 bis +5). Trivium ist nicht patentiert.

Trivium erzeugt aus einem 80-Bit-Schlüssel und einem 80-Bit-Initialisierungsvektor bis zu 2⁶⁴ Bit Keystream. Pro Iteration wird ein Bit Keystream ausgegeben. Fortschaltung und Keystream-Extraktion sind nicht schlüsselabhängig. Der Schlüssel dient nur der Initialisierung des Status. Von allen eSTREAM-Kandidaten hat Trivium das einfachste Design.

Es zeigt zwar eine für seine Einfachheit und Performance beachtliche Widerstandskraft gegenüber einer Kryptoanalyse, jedoch lassen einige in der jüngeren Zeit bekannt gewordenen Angriffe den vorhandenen Sicherheitspuffer als recht klein erscheinen.

Beschreibung

Der 288 Bit große Status von Trivium besteht aus drei verschieden großen Schieberegistern. In jeder Iteration wird je ein Bit an den Anfang der drei Schieberegister geschoben. Diese Bits werden durch eine nichtlineare Kombination mehrerer Bits aus dem jeweiligen sowie einem der anderen Schieberegister berechnet. Die Extraktion des Keystream-Bits findet durch eine XOR-Verknüpfung von 6 Bits des Status, 2 aus jedem Schieberegister, statt.

Zur Initialisierung werden Schlüssel und Initialisierungsvektor in den Status geschrieben. Da sie ihn nicht vollständig ausfüllen (80b Key + 80b IV < 288b Status), wird der Rest auf eine vordefinierte, immer gleiche Weise belegt. Danach werden 1136 Iterationen (Das Vierfache der Länge des Status) durchlaufen, ohne dass dabei Keystream berechnet wird. Nach dieser Initialisierung ist das Verfahren einsatzbereit.

Weil sich keine der Tap-Variablen in den ersten 64 Bit eines der Schieberegister befindet, geht jedes neu berechnete Bit frühestens 64 Runden nach seiner Generierung wiederum in eine Berechnung ein. Dies sorgt für ein nur sehr schwer berechnebares Verhalten und damit für die Sicherheit des Verfahrens.

Spezifikation

Trivium kann sehr einfach mittels der folgenden drei rekursiven Gleichungen beschrieben werden.^[2] Alle Variablen sind Elemente von GF(2); sie können als Bits dargestellt werden, wobei „+“ eine XOR-Verknüpfung und „ד eine AND-Verknüpfung bedeutet.

$a_i=c_{i-66}+c_{i-111}+c_{i-110} \times +c_{i-109}+a_{i-69}$

$b_i=a_{i-66}+a_{i-93}+a_{i-92} \times +a_{i-91}+b_{i-78}$

$c_i=b_{i-69}+b_{i-84}+b_{i-83} \times +b_{i-82}+c_{i-87}$

Danach werden die Keystream-Bits $r_0 ... r_{2^64-1}$ folgendermaßen berechnet:

r_i = c_{i − 66} + c_{i − 111} + a_{i − 66} + a_{i − 93} + b_{i − 69} + b_{i − 84}

Die Initialisierung erfolgt mit einem 80-Bit Key k₀...k₇₉ und einem l-Bit Initialisierungsvektor v₀...v_{l − 1} (wobei gilt $0 \le l \le 80$ ) auf diese Weise:

(a _{− 1245}...a _{− 1153}) = (0,0...0,k₀...k₇₉)

(b _{− 1236}...a _{− 1153}) = (0,0...0,v₀...v_{l − 1})

(c _{− 1263}...a _{− 1153}) = (1,1,1,0,0...0)

Die großen negativen Indizes rühren von den 1152 Iterationen her, die durchlaufen werden müssen, bevor Keystream erzeugt wird.

Um eine Folge von Bits r auf eine Folge von Bytes R abzubilden, wird die Little-Endian-Darstellung verwendet:

$R_i = \sum_{j=0}^7 2^j \times r_{8 \times i + j}$.

Performance

Eine einfache Hardwareumsetzung von Trivium benötigt 3488 Logikgatter und gibt pro Taktzyklus ein Bit Keystream aus. Allerdings kann man, da jedes Bit frühestens 64 Runden nach seiner Erzeugung in eine Berechnung eingeht, mit leicht gesteigertem Hardwarebedarf (5504 Gatter) eine Implementierung aufbauen, die 64 Keystream-Bits parallel ausgibt. Es sind noch weitere Kompromisse zwischen Schnelligkeit und Hardwarebedarf möglich.

Dieselbe Eigenschaft ermöglicht eine effiziente Software-Implementierung; Performance-Tests von eSTREAM ergaben eine Verschlüsselungsgeschwindigkeit von etwa 4 Zyklen/Byte (auf einer x86-Plattform), was in Anbetracht der 19 Zyklen/Byte der Referenzimplementation des AES (auf derselben Plattform) nicht schlecht ist.

Sicherheit

“ [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.”

„Das Design von Trivium war ein Experiment, wie weit eine Stromchiffre vereinfacht werden kann, ohne dabei Sicherheit, Geschwindigkeit oder Flexibilität zu opfern. Während einfache Designs mit einer höheren Wahrscheinlichkeit anfällig für einfache und möglicherweise vernichtende Angriffe sind (weshalb wir zum aktuellen Zeitpunkt stark von der Verwendung von Trivium abraten), verdienen sie sicherlich mehr Vertrauen als komplexe Designs, wenn sie trotz ihrer Einfachheit einer längeren öffentlichen Überprüfung standhalten.“

– Christophe De Cannière, Bart Preneel: Trivium specifications. In: eSTREAM submitted papers Abgerufen am 29. April 2005

Bisher (September 2010), sind keine kryptoanalytischen Angriffe besser als eine vollständige Schlüsselsuche bekannt, aber es gibt mehrere Angriffe, die in der Nähe dieser Grenze sind. Eine Cube-Attacke _(en) benötigt 2³⁰ Schritte, um eine Variante von Trivium zu brechen, bei der statt 1152 nur 735 Initialisierungsrunden durchlaufen werden; die Autoren vermuten, dass sich diese Techniken auch auf eine Variante mit 1100 Initialisierungsrunden anwenden lässt, oder „möglicherweise sogar das ursprüngliche Verfahren“^[3] Dieser Angriff baut auf einem Angriff von Michael Vielhaber auf, das 576 Initialisierungsrunden in nur 2^12.3 Schritten bricht.^{[4] [5]}

Eine andere Attacke enthüllt den internen Status (und damit den Schlüssel) der vollständigen Chiffre in etwa 2^89.5 Schritten (wobei jeder Schritt etwa so aufwändig ist wie ein einzelner Versuch einer vollständigen Schlüsselsuche).^[6] Vereinfachte Varianten von Trivium, die auf denselben Designprinzipien aufbauen, wurden mittels einer Technik zum Lösen von Gleichungen gebrochen.^[7]. Diese Angriffe übertreffen den bekannten TMTO-Angriff (Time-Memory-Tradeoff) auf Stromchiffren, der im Falle der 288 Bit des internen Status von Trivium 2¹⁴⁴ Schritte benötigen würde. Sie zeigen, dass eine Variante von Trivium, die sich vom originalen Verfahren nur durch eine Vergrößerung der Schlüssellänge über die vom eSTREAM Profile 2 vorgeschriebenen 80 Bit hinaus unterscheidet, nicht sicher sein würde.

Eine detaillierte Beschreibung des Designs von Trivium kann man in ^[8] finden.

Weblinks

• eSTREAM-Seite über Trivium
• eSTREAM Implementation

Einzelnachweise

1. ↑ Von den vier Verfahren, die ursprünglich ausgewählt wurden, gehören inzwischen nur noch drei dem Portfolio an, da in F-FCSR-H 2008 eine Schwachstelle entdeckt wurde
2. ↑ eSTREAM Phorum, 20. Februar 2006
3. ↑ Itai Dinur, Shamir, Adi: Cube Attacks on Tweakable Black Box Polynomials. (PDF) 13.09.2008. ePrint 20080914:160327. Abgerufen am 4.12.
4. ↑ Michael Vielhaber (28. Oktober 2007): Breaking ONE.FIVIUM by AIDA an Algebraic IV Differential Attack. Abgerufen am 5. März 2011.
5. ↑ Michael Vielhaber (23. Februar 2009): Shamir's „cube attack“: A Remake of AIDA, The Algebraic IV Differential Attack. Abgerufen am 5. März 2011.
6. ↑ Alexander Maximov, Alex Biryukov: Two Trivial Attacks on Trivium. (PDF) 2007-01-23. (Table 6, page 11)
7. ↑ Håvard Raddum: Cryptanalytic results on Trivium. (PostScript) 2006-03-27. Abgerufen am 10. September 2006.
8. ↑ Christophe De Cannière, Bart Preneel: Trivium - A Stream Cipher Construction Inspired by Block Cipher Design Principles. (PDF) 2006-01-02. Abgerufen am 9. Oktober 2006.