Algebraic attacks on certain stream ciphers


Armknecht, Frederik


[img]
Preview
PDF
Armknecht.pdf - Published

Download (1MB)

URL: https://ub-madoc.bib.uni-mannheim.de/1352
URN: urn:nbn:de:bsz:180-madoc-13523
Document Type: Doctoral dissertation
Year of publication: 2006
The title of a journal, publication series: None
Place of publication: Mannheim
Publishing house: Univ.
University: Universität Mannheim
Evaluator: Krause, Matthias
Date of oral examination: 30 November 2006
Publication language: English
Institution: School of Business Informatics and Mathematics > Theoretische Informatik (Krause 1996-)
Subject: 004 Computer science, internet
Classification: MSC: 94A60 ,
Subject headings (SWD): Kryptologie , Stromchiffre , Kryptoanalyse
Individual keywords (German): Algebraische Angriffe
Keywords (English): 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.
Translation of the title: Algebraische Angriffe auf bestimmte Stromchiffren (German)
Translation of the abstract: 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. (German)




Dieser Eintrag ist Teil der Universitätsbibliographie.

Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt.




Metadata export


Citation


+ Search Authors in

BASE: Armknecht, Frederik

Google Scholar: Armknecht, Frederik

ORCID: Armknecht, Frederik ORCID: 0009-0003-9935-8095

+ Download Statistics

Downloads per month over past year

View more statistics



You have found an error? Please let us know about your desired correction here: E-Mail


Actions (login required)

Show item Show item