Algebraic attacks on certain stream ciphers

Armknecht, Frederik

Vorschau

PDF
Armknecht.pdf - Veröffentlichte Version
Download (1MB)

URL:	https://ub-madoc.bib.uni-mannheim.de/1352
URN:	urn:nbn:de:bsz:180-madoc-13523
Dokumenttyp:	Dissertation
Erscheinungsjahr:	2006
Titel einer Zeitschrift oder einer Reihe:	None
Ort der Veröffentlichung:	Mannheim
Verlag:	Univ.
Hochschule:	Universität Mannheim
Gutachter:	Krause, Matthias
Datum der mündl. Prüfung:	30 November 2006
Sprache der Veröffentlichung:	Englisch
Einrichtung:	Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Theoretische Informatik (Krause 1996-)
Fachgebiet:	004 Informatik
Fachklassifikation:	MSC: 94A60 ,
Normierte Schlagwörter (SWD):	Kryptologie , Stromchiffre , Kryptoanalyse
Freie Schlagwörter (Deutsch):	Algebraische Angriffe
Freie Schlagwörter (Englisch):	Cryptography , Algebraic attacks , stream ciphers
Abstract:	To encrypt data streams of arbitrary lengths, keystream generators are used in modern cryptography which transform a secret initial value, called the key, into a long sequence of seemingly random bits. Many designs are based on linear feedback shift registers (LFSRs), which can be constructed in such a way that the output stream has optimal statistical and periodical properties and which can be efficiently implemented in hardware. Particularly prominent is a certain class of LFSR-based keystream generators, called (ι,m)-combiners or simply combiners. The maybe most famous example is the E0 keystream generator deployed in the Bluetooth standard for encryption. To evaluate the combiner’s security, cryptographers adopted an adversary model where the design and some parts of the input and output are known. An attack is a method to derive the key using the given knowledge. In the last decades, several kinds of attacks against LFSR-based keystream generators have been developed. In 2002 a new kind of attacks came up, named ”algebraic attacks”. The basic idea is to model the knowledge by a system of equation whose solution is the secret key. For several existing combiners, algebraic attacks represent the fastest theoretical attacks publicly known so far. This thesis discusses algebraic attacks against combiners. After providing the required mathematical fundament and a background on combiners, we describe algebraic attacks and explore the two main steps (generating the system of equations and computing the solution) in detail. The efficiency of algebraic attacks is closely connected to the degree of the equations. Thus, we examine the existence of low-degree equations in several situations and discuss multiple design principles to thwart their existence. Furthermore, we investigate ”fast algebraic attacks”, an extension of algebraic attacks.To encrypt data streams of arbitrary lengths, keystream generators are used in modern cryptography which transform a secret initial value, called the key, into a long sequence of seemingly random bits. Many designs are based on linear feedback shift registers (LFSRs), which can be constructed in such a way that the output stream has optimal statistical and periodical properties and which can be efficiently implemented in hardware. Particularly prominent is a certain class of LFSR-based keystream generators, called (ι,m)-combiners or simply combiners. The maybe most famous example is the E0 keystream generator deployed in the Bluetooth standard for encryption. To evaluate the combiner’s security, cryptographers adopted an adversary model where the design and some parts of the input and output are known. An attack is a method to derive the key using the given knowledge. In the last decades, several kinds of attacks against LFSR-based keystream generators have been developed. In 2002 a new kind of attacks came up, named ”algebraic attacks”. The basic idea is to model the knowledge by a system of equation whose solution is the secret key. For several existing combiners, algebraic attacks represent the fastest theoretical attacks publicly known so far. This thesis discusses algebraic attacks against combiners. After providing the required mathematical fundament and a background on combiners, we describe algebraic attacks and explore the two main steps (generating the system of equations and computing the solution) in detail. The efficiency of algebraic attacks is closely connected to the degree of the equations. Thus, we examine the existence of low-degree equations in several situations and discuss multiple design principles to thwart their existence. Furthermore, we investigate ”fast algebraic attacks”, an extension of algebraic attacks.
Übersetzter Titel:	Algebraische Angriffe auf bestimmte Stromchiffren (Deutsch)
Übersetzung des Abstracts:	Um Datenströme beliebiger Länge zu verschlüsseln werden in der modernen Kryptographie Schlüsselstromgeneratorern eingesetzt, welche einen geheimen Initialwert, den so genannten Schlüssel, in einen langen Strom scheinbar zufälliger Bits zu transformieren. Viele Designs basieren auf linearen Rückkopplungsschieberegistern (in Englisch: linear feedback shift registers (LFSRs)), welche so konstruiert werden können, dass die Ausgabeströme optimale statistische und periodische Eigenschaften aufweisen, und welche effizient in Hardware implementiert werden können. Besonders bedeutend ist eine spezielle Klasse der LFSR-basierten Schlüsselstromgeneratoren, welche (ι,m)-Combiner oder einfach nur Combiner genannt werden. Das vielleicht bekannteste Beispiel ist der E0 Schlüsselstromgenerator, eingesetzt im Bluetooth Standard zur Verschlüsselung. Um die Sicherheit eines Combiners zu evaluieren wenden Kryptographen ein Feindmodell an, in welchem sowohl das Design als auch Teile der Ein- und Ausgabe bekannt sind. Ein Angriff stellt eine Methode dar, das vorhandene Wissen zu nutzen, um den geheimen Schlüssel abzuleiten. In den letzten Jahrzehnten wurden unterschiedliche Arten von Attacken gegen LFSR-basierten Schlüsselstromgeneratoren entwickelt. 2002 kam ein neues Verfahren auf, genannt ”algebraische Attacke”. Die zugrundeliegende Idee ist es, das Wissen durch eine Gleichungssystem darzustellen, dessen Lösung dem geheimen Schlüssel entspricht. Algebraische Attacken stellen für manche existierende Combiner die bisher schnellsten öffentlich bekannten Angriffe dar. Diese Arbeit behandelt algebraische Attacken gegen Combiner. Nach der Bereitstellung des notwendigen mathematischen Fundaments und des Hintergrundes zu Combinern erklären wir algebraische Attacken und untersuchen die beiden Hauptschritte (Erstellen des Gleichungssystems und Berechnung der Lösungen). Die Effizienz der algebraischen Attacken ist eng verknüpft mit dem Grad der Gleichungen. Aus diesem Grund erforschen wir die Existenz solcher Gleichungen mit niedrigem Grad und diskutieren mehrere Designprinzipien zur Vermeidung ihrer Existenz. Ausserdem untersuchen wir die so genannten ”schnellen algebraischen Attacken”, eine Erweiterung der algebraischen Attacken. (Deutsch)