TU Darmstadt / ULB / TUbiblio

Algebraic Cryptanalysis of Block Ciphers Using Groebner Bases

Pyshkin, Andrey (2008)
Algebraic Cryptanalysis of Block Ciphers Using Groebner Bases.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

Kurzbeschreibung (Abstract)

This thesis investigates the application of Groebner bases to cryptanalysis of block ciphers. The basic for the application is an algorithm for solving systems of polynomial equations via Groebner basis computation. In our case, polynomial equations describe the key recovery problem for block ciphers, i.e., the solution of these systems corresponds to the value of the secret key. First we demonstrate that Groebner basis technique can be successfully used to break block ciphers, if the algebraic structure of these ciphers is relatively simple. To show this, we construct two families of block ciphers that satisfy this condition. However, our ciphers are not trivial, they have a reasonable block and key size as well as an acceptable number of rounds. Moreover, using suitable parameters we achieve good resistance of these ciphers against differential and linear cryptanalysis. At the same time, we design our ciphers so that the key recovery problem for each of them can be described by a system of simple polynomial equations. In addition, parameters of the ciphers can be varied independently. This makes the constructed families suitable for analysis of algebraic attacks. To study the vulnerable of such ciphers against Groebner basis attack, we have performed experiments using the computer algebra system Magma. Results of these experiments are given and analyzed. Also, for a subset of these ciphers we present an efficient method to construct zero-dimensional Groebner bases w.r.t. a degree-reverse lexicographical term order without a polynomial reduction. This reduces the key recovery problem to the problem of Groebner basis conversion. Using known complexity bounds for the last problem, we estimate the maximum resistance of these ciphers against Groebner basis attacks. We show that our method can be also applied to the AES block cipher. In the thesis we describe the AES key recovery problem in the form of a total-degree Groebner basis, explain how this Groebner basis can be obtained, and study the cryptanalytic significance of this result. Next, we investigate the semi-regularity of several polynomial representations for iterated block ciphers. We demonstrate that the constructed Groebner basis for the AES is semi-regular. Then we prove that polynomial systems that are similar to the BES quadratic equations are not semi-regular as well as the AES systems of quadratic equations over GF(2) are not semi-regular over GF(2). Finally, we propose a new method of side-channel cryptanalysis - algebraic collision attacks - and explain it by the example of the AES. The method is based on the standard power analysis technique, which is applied to derive an additional information from an implementation of a cryptosystem. In our case, this information is about generalized internal collisions occurring between S-boxes of the block cipher. However, we use a new approach to recover the secret key from the obtained information. Taking into account a specific structure of the attacked cryptographic algorithm, we express the detected collisions as a system of polynomial equations and use Groebner bases to solve this system. This approach provides significant advantages both in terms of measurements and post-processing complexity. Also, we use non-collisions to optimize our method. For the AES block cipher, we demonstrate several efficient algebraic collision attacks. The first of them works in the known-plaintext scenario and requires 5 measurements to derive the full secret key within several hours on a PC with success probability 0.93. This attack with 4 measurements recovers key in about 40% of all cases. The second attack works in the known plaintext/ciphertext pair scenario but leads to more efficient results: the key can be obtained in several seconds of offline computations with success probability of 0.82 for 4 measurements, and with probability close to 1 for 5 measurements. We also propose a successful algebraic collision attack on the AES with 3 measurements. The attack has a probability of 0.42 and needs 4.24 PC hours post-processing.

Typ des Eintrags: Dissertation
Erschienen: 2008
Autor(en): Pyshkin, Andrey
Art des Eintrags: Erstveröffentlichung
Titel: Algebraic Cryptanalysis of Block Ciphers Using Groebner Bases
Sprache: Englisch
Referenten: Buchmann, Prof. Dr. Johannes ; Ding, Prof. Dr. Jintai
Publikationsjahr: 25 Juli 2008
Ort: Darmstadt
Verlag: Technische Universität
Datum der mündlichen Prüfung: 16 April 2008
URL / URN: urn:nbn:de:tuda-tuprints-10608
Kurzbeschreibung (Abstract):

This thesis investigates the application of Groebner bases to cryptanalysis of block ciphers. The basic for the application is an algorithm for solving systems of polynomial equations via Groebner basis computation. In our case, polynomial equations describe the key recovery problem for block ciphers, i.e., the solution of these systems corresponds to the value of the secret key. First we demonstrate that Groebner basis technique can be successfully used to break block ciphers, if the algebraic structure of these ciphers is relatively simple. To show this, we construct two families of block ciphers that satisfy this condition. However, our ciphers are not trivial, they have a reasonable block and key size as well as an acceptable number of rounds. Moreover, using suitable parameters we achieve good resistance of these ciphers against differential and linear cryptanalysis. At the same time, we design our ciphers so that the key recovery problem for each of them can be described by a system of simple polynomial equations. In addition, parameters of the ciphers can be varied independently. This makes the constructed families suitable for analysis of algebraic attacks. To study the vulnerable of such ciphers against Groebner basis attack, we have performed experiments using the computer algebra system Magma. Results of these experiments are given and analyzed. Also, for a subset of these ciphers we present an efficient method to construct zero-dimensional Groebner bases w.r.t. a degree-reverse lexicographical term order without a polynomial reduction. This reduces the key recovery problem to the problem of Groebner basis conversion. Using known complexity bounds for the last problem, we estimate the maximum resistance of these ciphers against Groebner basis attacks. We show that our method can be also applied to the AES block cipher. In the thesis we describe the AES key recovery problem in the form of a total-degree Groebner basis, explain how this Groebner basis can be obtained, and study the cryptanalytic significance of this result. Next, we investigate the semi-regularity of several polynomial representations for iterated block ciphers. We demonstrate that the constructed Groebner basis for the AES is semi-regular. Then we prove that polynomial systems that are similar to the BES quadratic equations are not semi-regular as well as the AES systems of quadratic equations over GF(2) are not semi-regular over GF(2). Finally, we propose a new method of side-channel cryptanalysis - algebraic collision attacks - and explain it by the example of the AES. The method is based on the standard power analysis technique, which is applied to derive an additional information from an implementation of a cryptosystem. In our case, this information is about generalized internal collisions occurring between S-boxes of the block cipher. However, we use a new approach to recover the secret key from the obtained information. Taking into account a specific structure of the attacked cryptographic algorithm, we express the detected collisions as a system of polynomial equations and use Groebner bases to solve this system. This approach provides significant advantages both in terms of measurements and post-processing complexity. Also, we use non-collisions to optimize our method. For the AES block cipher, we demonstrate several efficient algebraic collision attacks. The first of them works in the known-plaintext scenario and requires 5 measurements to derive the full secret key within several hours on a PC with success probability 0.93. This attack with 4 measurements recovers key in about 40% of all cases. The second attack works in the known plaintext/ciphertext pair scenario but leads to more efficient results: the key can be obtained in several seconds of offline computations with success probability of 0.82 for 4 measurements, and with probability close to 1 for 5 measurements. We also propose a successful algebraic collision attack on the AES with 3 measurements. The attack has a probability of 0.42 and needs 4.24 PC hours post-processing.
Alternatives oder übersetztes Abstract:
Alternatives AbstractSprache

In der vorliegenden Arbeit untersuchen wir die Anwendbarkeit von Gröbner Basen zur Kryptoanalyse von Blockchiffren. Eine der wichtigsten Anwendungen von Gröbner Basen ist der Lösung von Polynomial-Gleichungssystemen. Viele Kryptoverfahren lassen sich als Gleichungssysteme beschreiben, nicht alle von solchen Gleichungssystemen sind aber effizient lösbar. Um zu untersuchen, wie gut Gröbner Basis-Angriffe auf Blockchiffre funktionieren und wie das von Parametern (die Größe des Blockes, die Anzahl der Runden, sowie der Grad der Polynome) der Chiffre abhängt, haben wir die zwei Familien der populärsten Klassen von modernen Blockchiffren, Feistel und SP Netzwerke, konstruiert und analysiert. Wir zeigen, dass es nicht triviale Blockchiffre gibt, die resistent gegen die linearen und differentiellen Angriffe sind, aber sich algebraisch angreifen lassen. Außerdem ist beschrieben, wie Gröbner Basen bezüglich die graduiert-lexikographische Termordnung für eine großen Untermenge dieser Blockchiffre effektiv berechnen werden können, d.h., algebraische Angriffe auf diese Chiffre werden auf das Problem, eine graduiert-lexikographische Gröbner Basis in die lexikographischen Termordnung umzurechnen, zurückgeführt. Durch bekannten Abschätzungen der Komplexität des letzten Problems schätzen wir die Effizient von Gröbner Basis-Angriffe in diesem Fall ab. Die vorschlagene Methode lässt sich auch auf das AES-Verschlüsselungsverfahren anwenden. In der Dissertation erklären wir, wie eine graduiert-lexikographishe Gröbner Basis für den AES bekommen werden kann, sowie die Auswirkung dieser Gröbner Basis auf die Sicherheit des Verfahrens. Dann betrachten wir die Semi-Regularität von verschiedenen Gleichungssystemen, die iterierte Blockchiffren beschreiben. Für reguläre und semi-reguläre Mengen von Polynomen sind Abschätzungen über die Komplexität der Gröbner Basis-Algorithmen bekannt. Man weiß auch, dass die Polynome, die ein Kryptosystem beschreiben, fast nie regulär sind. Es wurde aber vermutet, dass diese Polynome semi-regulär sind. Wir beweisen, dass diese Vermutung für iterierte Blockchiffren meistens falsch ist, u.a., quadratische Gleichungssysteme für den AES sind weder semi-regulär, noch semi-regulär über GF(2). Schlie{\ss}lich demonstrieren wir, dass Seitenkanalangriffe sich durch Gröbner Basis-Methoden verbessern lassen. Unsere Methode basiert auf Kollisionen, die zwischen verschiedenen S-Boxen bei Verschlüsselung einiger Klartexte auftreten. Es ist bekannt, dass man solche Kollisionen mittels Differential Power Analysis nachweisen kann, falls die Implementierung des Verfahrens nicht gegen Seitenkanalangriffe abgesichert ist. Um den Schlüssel aus den festgestellte Kollisionen zu ziehen, beschreiben wir sie als Polynomial-Gleichungssysteme. Wir zeigen, dass einige Klassen von diesen Systemen effektiv durch Gröbner Basen lösbar sind. Außerdem werden Nicht-Kollisionen zur Verbesserung der Methode benutzt. In der Dissertation werden drei Varianten dieser Angriffe auf den AES präsentiert. Die Erste verwendet Kollisionen zwischen S-boxen der ersten zwei Runden und braucht 5 oder 4 gemessene Klartexte, um den AES-Schlüssel mit Wahrscheinlichkeit 0.93 bzw. 0.4 zu ziehen. Falls Ein- und Ausgaben des Verfahrens dem Angreifer bekannt sind, kann man die S-boxen der ersten und letzten Runden betrachten. Algebraische Angriffe, die auf Kollisionen zwischen diesen S-boxen basieren, haben eine bessere Laufzeit sowie eine höhere Erfolgswahrscheinlichkeit. Wenn beide Varianten kombiniert werden, ist man in der Lage, den AES-Schlüssel mit 3 gemessenen Klartexten mit der Wahrscheinlichkeit 0.42 zu finden.

Deutsch
Freie Schlagworte: cryptanalysis, algebraic cryptanalysis, side-channel cryptanalysis, algebraic collision attack, Groebner basis attack, block cipher, Groebner Basis, semi-regular sequence, AES, Flurry, Curry
Sachgruppe der Dewey Dezimalklassifikatin (DDC): 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Fachbereich(e)/-gebiet(e): 20 Fachbereich Informatik
Hinterlegungsdatum: 17 Okt 2008 09:23
Letzte Änderung: 26 Aug 2018 21:25
PPN:
Referenten: Buchmann, Prof. Dr. Johannes ; Ding, Prof. Dr. Jintai
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: 16 April 2008
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen
OAI 2.0-Basis-URL: https://tubiblio.ulb.tu-darmstadt.de/cgi/oai2 TUbiblio verwendet EPrints 3.
Drucken | Impressum | Datenschutzerklärung