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, 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 und wurde als ISO/IEC 29192-3 standardisiert.

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 sechs Bits des Status, zwei aus jedem der drei 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 berechenbares Verhalten und damit für die Sicherheit des Verfahrens.

Spezifikation

Trivium kann sehr einfach mittels der folgenden drei rekursiven Gleichungen beschrieben werden. 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.

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

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

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

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

${\displaystyle 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 ${\displaystyle k_{0}...k_{79}}$ und einem l-Bit Initialisierungsvektor ${\displaystyle v_{0}...v_{l-1}}$ (wobei gilt ${\displaystyle 0\leq l\leq 80}$) auf diese Weise:

${\displaystyle (a_{-1245}...a_{-1153})=(0,0...0,k_{0}...k_{79})}$

${\displaystyle (b_{-1236}...a_{-1153})=(0,0...0,v_{0}...v_{l-1})}$

${\displaystyle (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:

${\displaystyle 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

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 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“. Dieser Angriff baut auf einem Angriff von Michael Vielhaber auf, das 576 Initialisierungsrunden in nur 2^12.3 Schritten bricht.

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). Vereinfachte Varianten von Trivium, die auf denselben Designprinzipien aufbauen, wurden mittels einer Technik zum Lösen von Gleichungen gebrochen. 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 Trivium – A Stream Cipher Construction Inspired by Block Cipher Design Principles 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. ↑ ISO/IEC 29192-3:2012
3. ↑ eSTREAM Phorum, 20. Februar 2006
4. ↑ Itai Dinur, Adi Shamir: Cube Attacks on Tweakable Black Box Polynomials. (PDF; ePrint 20080914:160327) Cryptology ePrint Archive, 13. September 2008, abgerufen am 4. Dezember 2008. 
5. ↑ Michael Vielhaber: Breaking ONE.FIVIUM by AIDA an Algebraic IV Differential Attack. 28. Oktober 2007, abgerufen am 5. März 2011. 
6. ↑ Michael Vielhaber: Shamir’s „cube attack“: A Remake of AIDA, The Algebraic IV Differential Attack. (Nicht mehr online verfügbar.) 23. Februar 2009, ehemals im Original; abgerufen am 5. März 2011.@1@2Vorlage:Toter Link/hs-bremerhaven.de (Seite nicht mehr abrufbar. Suche in Webarchiven.)  Info: Der Link wurde automatisch als defekt markiert. Bitte prüfe den Link gemäß Anleitung und entferne dann diesen Hinweis. 
7. ↑ Alexander Maximov, Alex Biryukov: Two Trivial Attacks on Trivium. (PDF) Cryptology ePrint, 23. Januar 2007, S. 11, Tabelle 6, abgerufen am 3. Februar 2015. 
8. ↑ Håvard Raddum: Cryptanalytic results on Trivium. (PostScript) eSTREAM submitted papers, 27. März 2006, abgerufen am 10. September 2006. 
9. ↑ Christophe De Cannière, Bart Preneel: Trivium – A Stream Cipher Construction Inspired by Block Cipher Design Principles. (PDF) eSTREAM submitted papers, 2. Januar 2006, abgerufen am 9. Oktober 2006.