TU Darmstadt / ULB / TUbiblio

Algebraic Methods in Block Cipher Cryptanalysis

Weinmann, Ralf-Philipp (2009)
Algebraic Methods in Block Cipher Cryptanalysis.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

Kurzbeschreibung (Abstract)

This thesis is a contribution to the field of algebraic cryptanalysis. Specifically the following topics have been studied: We construct and analyze Feistel and SLN ciphers that have a sound design strategy against linear and differential cryptanalysis. The encryption process for these cipher can be described by very simple polynomial equations. For a block and key size of 128 bits, we present ciphers for which practical Gröbner Basis Attacks can recover the full cipher key for up to 12 rounds requiring only a minimal number of plaintext/ciphertext pairs. We show how Gröbner bases for a subset of these ciphers can be constructed with negligible computational effort. This reduces the key-recovery problem to a Gröbner basis conversion problem. By bounding the running time of a Gröbner basis conversion algorithm, FGLM, we demonstrate the existence of block ciphers resistant against differential and linear cryptanalysis but vulnerable against Gröbner basis attacks. A paper on this subject has been published in the "Proceedings of The Cryptographers' Track at the RSA Conference 2006 (CT-RSA 2006)". We demonstrate an efficient method for computing a Gröbner basis of a zero-dimensional ideal describing the key-recovery problem from a single plaintext/ciphertext pair for the full AES-128. This Gröbner basis is relative to a degree-lexicographical order. We investigate whether the existence of this Gröbner basis has any security implications for the AES. This result has been published in the "Revised Selected Papers of the Fast Software Encryption Workshop 2006 (FSE 2006)". SMS4 is a 128-bit block cipher used in the WAPI standard for providing data confidentiality in wireless networks. For this cipher we explain how to construct a extension field embedding similar to BES, and demonstrate the fragility of the cipher design by giving variants that exhibit 2^{64} weak keys. These results have been published in the "Proceedings of Information Security and Privacy, 12th Australasian Conference (ACISP 2007)''. Cryptomeria is a 64-bit block cipher with a 56-bit key used in the CPRM / CPPM standard for content protection on DVD Audio discs, Video DVD-Rs and SD cards. The design of this cipher is public, the S-Box - which is application-specific - is treated as a trade secret which needs to be licensed from the 4C Entity, Inc. We show how for Cryptomeria and similarly structured ciphers the S-Box can be recovered in a chosen-key setting by a combination of differential and algebraic methods. This attack has been practically validated against reduced round versions of Cryptomeria. This is unpublished work. We look into Gröbner bases algorithms which use linear algebra methods. Because these algorithms are extremely memory-hungry, we have developed strategies for implementing the reduced row-echelon computation efficiently on distributed memory systems. We give an algorithm to efficiently tackle this problem in the dense case and discuss the sparse case. A extended abstract on this subject has been submitted to and accepted at "The First International Conference on Symbolic Computation and Cryptography (SCC 2008)".

Typ des Eintrags: Dissertation
Erschienen: 2009
Autor(en): Weinmann, Ralf-Philipp
Art des Eintrags: Erstveröffentlichung
Titel: Algebraic Methods in Block Cipher Cryptanalysis
Sprache: Englisch
Referenten: Buchmann, Prof. Dr. Johannes A. ; Rijmen, Prof. Dr. Vincent
Publikationsjahr: 8 April 2009
Ort: Darmstadt
Verlag: Technische Universität
Datum der mündlichen Prüfung: 16 April 2008
URL / URN: urn:nbn:de:tuda-tuprints-13624
Zugehörige Links:
Kurzbeschreibung (Abstract):

This thesis is a contribution to the field of algebraic cryptanalysis. Specifically the following topics have been studied: We construct and analyze Feistel and SLN ciphers that have a sound design strategy against linear and differential cryptanalysis. The encryption process for these cipher can be described by very simple polynomial equations. For a block and key size of 128 bits, we present ciphers for which practical Gröbner Basis Attacks can recover the full cipher key for up to 12 rounds requiring only a minimal number of plaintext/ciphertext pairs. We show how Gröbner bases for a subset of these ciphers can be constructed with negligible computational effort. This reduces the key-recovery problem to a Gröbner basis conversion problem. By bounding the running time of a Gröbner basis conversion algorithm, FGLM, we demonstrate the existence of block ciphers resistant against differential and linear cryptanalysis but vulnerable against Gröbner basis attacks. A paper on this subject has been published in the "Proceedings of The Cryptographers' Track at the RSA Conference 2006 (CT-RSA 2006)". We demonstrate an efficient method for computing a Gröbner basis of a zero-dimensional ideal describing the key-recovery problem from a single plaintext/ciphertext pair for the full AES-128. This Gröbner basis is relative to a degree-lexicographical order. We investigate whether the existence of this Gröbner basis has any security implications for the AES. This result has been published in the "Revised Selected Papers of the Fast Software Encryption Workshop 2006 (FSE 2006)". SMS4 is a 128-bit block cipher used in the WAPI standard for providing data confidentiality in wireless networks. For this cipher we explain how to construct a extension field embedding similar to BES, and demonstrate the fragility of the cipher design by giving variants that exhibit 2^{64} weak keys. These results have been published in the "Proceedings of Information Security and Privacy, 12th Australasian Conference (ACISP 2007)''. Cryptomeria is a 64-bit block cipher with a 56-bit key used in the CPRM / CPPM standard for content protection on DVD Audio discs, Video DVD-Rs and SD cards. The design of this cipher is public, the S-Box - which is application-specific - is treated as a trade secret which needs to be licensed from the 4C Entity, Inc. We show how for Cryptomeria and similarly structured ciphers the S-Box can be recovered in a chosen-key setting by a combination of differential and algebraic methods. This attack has been practically validated against reduced round versions of Cryptomeria. This is unpublished work. We look into Gröbner bases algorithms which use linear algebra methods. Because these algorithms are extremely memory-hungry, we have developed strategies for implementing the reduced row-echelon computation efficiently on distributed memory systems. We give an algorithm to efficiently tackle this problem in the dense case and discuss the sparse case. A extended abstract on this subject has been submitted to and accepted at "The First International Conference on Symbolic Computation and Cryptography (SCC 2008)".
Alternatives oder übersetztes Abstract:
Alternatives AbstractSprache

Diese Dissertation ist ein Beitrag zum Gebiet der algebraischen Kryptanalyse. Die folgenden Themen werden in ihr behandelt: Wir konstruieren und analysieren sowohl Feistel als auch SLN Chiffren die eine fundierte Konstruktionsstrategie gegen lineare und differentielle Kryptanalyse aufweisen. Der Verschlüsselungsprozess für diese Chiffren kann als ein sehr einfaches System polynomieller Gleichungen beschrieben werden. Für eine Block- und Schlüsselgröße von 128 Bits präsentieren wir Chiffren mit bis zu 12 Runden für die praktische Gröbnerbasisangriffe den gesamten Schlüssel errechnen können; mit einer minimalen Anzahl von Klartext-/ Schlüsseltextpaaren. Wir zeigen wie für eine Untermenge der Chiffren Gröbnerbasen mit vernachlässigbarem Rechenaufwand direkt konstruiert werden können. Diese Vorgehensweise reduziert das Problem der Schlüsselrückgewinnung (Key Recovery) auf das Problem, Gröbnerbasen zwischen zwei verschiedenen Termordnungen zu konvertieren. Für FGLM, einen Algorithmus zum Konvertieren von Gröbnerbasen, können wir obere Schranken für seine Laufzeit sowie seinen Speicherplatzbedarf angeben. Hierdurch sind wir in der Lage zu zeigen, dass es Blockchiffren gibt, die resistent gegen lineare und differentielle Kryptanalyse sind, jedoch mit Gröbnerbasisangriffen angreifbar. Eine Einreichung zu diesem Thema wurde in "Proceedings of The Cryptographers' Track at the RSA Conference 2006 (CT-RSA 2006)" veröffentlicht. Wir zeigen eine effiziente Methode zum Berechnen einer Gröbnerbasis für ein null-dimensionales Ideal welches das Schlüsselrückgewinnungsproblem für den vollen AES-128 ausgehend von einem einzigen Klartext-/Chiffretextpaar beschreibt. Diese Gröbnerbasis ist relativ zu einer graduiert-lexikografischen Ordnung. Wir untersuchen, welche Auswirkungen die Existenz dieser Gröbnerbasis auf die Sicherheit von AES hat. Dieses Resultat wurde in "Revised Selected Papers of the Fast Software Encryption Workshop 2006 (FSE 2006)" veröffentlicht. SMS4 ist eine 128-Bit Blockchiffre, die im WAPI Standard verwendet wird um eine Vetraulichkeit der übermittelten Daten in Funknetzwerken zu erreichen. Für diese Chiffre erklären wir, wie eine Einbettung in einen Erweiterungskörper ähnlich zu BES erreicht werden kann. Weiterhin zeigen wir, dass die Konstruktion der Chiffre fragil ist. Varianten der Chiffre weisen 2^{64} schwache Schlüssel auf. Die erzielten Ergebnisse wurden in "Proceedings of Information Security and Privacy, 12th Australasian Conference (ACISP 2007)". publiziert. Cryptomeria ist eine 64-Bit Blockchiffre mit einem 56-Bit Schlüssel, die in dem CPPM/CPRM Standard für den Schutz von Inhalten auf DVD Audio Medien, Video DVD-Rs sowie SD Karten Verwendung findet. Die Spezifikation dieser Chiffre ist bis auf die verwendete S-Box öffentlich. Die S-Box, die anwendungsspezifisch ist, wird als Geschäftsgeheimnis behandelt und muss von 4C Entity, Inc. lizenziert werden. Wir zeigen wie man für Cryptomeria und ähnlich aufgebaute Chiffren die S-Box durch eine Kombination von differenziellen und algebraischen Methoden zurück gewinnen kann, wenn man den Schlüssel sowie die Eingaben der Chiffre wählen kann. Dieser Angriff wurde gegen rundenreduzierte Varianten von Cryptomeria praktisch verifiziert. Diese Ergebnisse sind bisher unpubliziert. Wir betrachten Algorithmen zum Berechnen von Gröbnerbasen die auf Methoden aus der linearen Algebrau aufbauen. Da diese Algorithmen extrem speicherhungrig sind haben wir Strategien entwickelt, um die reduzierte Zeilenstufenform einer Matrix effizient auf speicherverteilten Systemen berechnen zu können. Wir geben einen Algorithmus an, der dieses Problem effizient im dichtbesetzten Fall löst und diskutieren den dünnbesetzten Fall. Ein Extended Abstract wurde im Tagungsband "The First International Conference on Symbolic Computation and Cryptography (SCC 2008)'' veröffentlicht.

Deutsch
Sachgruppe der Dewey Dezimalklassifikatin (DDC): 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Fachbereich(e)/-gebiet(e): 20 Fachbereich Informatik
20 Fachbereich Informatik > Theoretische Informatik - Kryptographie und Computeralgebra
Hinterlegungsdatum: 15 Apr 2009 12:05
Letzte Änderung: 26 Aug 2018 21:25
PPN:
Referenten: Buchmann, Prof. Dr. Johannes A. ; Rijmen, Prof. Dr. Vincent
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