Polynomial system solving for decoding linear codes and algebraic cryptanalysis

Lösen polynomialer Systeme zur Dekodierung linearer Codes und algebraischen Kryptoanalyse

  • This thesis is devoted to applying symbolic methods to the problems of decoding linear codes and of algebraic cryptanalysis. The paradigm we employ here is as follows. We reformulate the initial problem in terms of systems of polynomial equations over a finite field. The solution(s) of such systems should yield a way to solve the initial problem. Our main tools for handling polynomials and polynomial systems in such a paradigm is the technique of Gröbner bases and normal form reductions. The first part of the thesis is devoted to formulating and solving specific polynomial systems that reduce the problem of decoding linear codes to the problem of polynomial system solving. We analyze the existing methods (mainly for the cyclic codes) and propose an original method for arbitrary linear codes that in some sense generalizes the Newton identities method widely known for cyclic codes. We investigate the structure of the underlying ideals and show how one can solve the decoding problem - both the so-called bounded decoding and more general nearest codeword decoding - by finding reduced Gröbner bases of these ideals. The main feature of the method is that unlike usual methods based on Gröbner bases for "finite field" situations, we do not add the so-called field equations. This tremendously simplifies the underlying ideals, thus making feasible working with quite large parameters of codes. Further we address complexity issues, by giving some insight to the Macaulay matrix of the underlying systems. By making a series of assumptions we are able to provide an upper bound for the complexity coefficient of our method. We address also finding the minimum distance and the weight distribution. We provide solid experimental material and comparisons with some of the existing methods in this area. In the second part we deal with the algebraic cryptanalysis of block iterative ciphers. Namely, we analyze the small-scale variants of the Advanced Encryption Standard (AES), which is a widely used modern block cipher. Here a cryptanalyst composes the polynomial systems which solutions should yield a secret key used by communicating parties in a symmetric cryptosystem. We analyze the systems formulated by researchers for the algebraic cryptanalysis, and identify the problem that conventional systems have many auxiliary variables that are not actually needed for the key recovery. Moreover, having many such auxiliary variables, specific to a given plaintext/ciphertext pair, complicates the use of several pairs which is common in cryptanalysis. We thus provide a new system where the auxiliary variables are eliminated via normal form reductions. The resulting system in key-variables only is then solved. We present experimental evidence that such an approach is quite good for small scaled ciphers. We investigate further our approach and employ the so-called meet-in-the-middle principle to see how far one can go in analyzing just 2-3 rounds of scaled ciphers. Additional "tuning techniques" are discussed together with experimental material. Overall, we believe that the material of this part of the thesis makes a step further in algebraic cryptanalysis of block ciphers.
  • Diese Arbeit beschäftigt sich mit Anwendungen symbolischer Methoden auf Probleme der Dekodierung linearer Codes und der algebraischen Kryptoanalyse. Dabei benutzen wir folgendes Paradigma. Wir formulieren das Ausgangsproblem um und beschreiben es durch Systeme von Polynomen über endlichen Körpern. Die Lösungen solcher Systeme sollen es ermöglichen, das Ausgangsproblem zu lösen. Zur Behandlung von Polynomen und polynomialer Systemen bei einem Paradigma verwenden wir haupts"achlich die Technik von Gröbner Basen und Normalformreduktionen. Der erste Teil behandelt das Formulieren und Lösen spezifischer polynomialer Systeme, die das Problem der Dekodierung linearer Codes auf das Problem des Lösens polynomialer Systeme reduzieren. Wir analysieren die vorhandenen Methoden (hauptsächlich für zyklische Codes) und präsentieren eine neue Methode, die in gewissem Sinne die Methode der Newton Identitäten verallgemeinert, die für zyklische Codes wohlbekannt ist. Wir untersuchen die Struktur der entsprechenden Ideale und zeigen, wie man das Dekodierungproblem mittels Berechnung reduzierter Gröbner Basen dieser Ideale lösen kann. Das gilt für beide, die so genannte beschränkte Dekodierung als auch die allgemeinere Dekodierung durch das naheste Codewort. Die Hauptbesonderheit dieser Methode ist, dass im Gegensatz zu gewöhnlichen Gröbner-basierten Methoden für den Fall von endlichen Körpern die sogenannten Körpergleichungen nicht hinzugefügt werden. Das vereinfacht die entsprechenden Ideale erheblich. Deshalb ist es möglich, mit ziemlich großen Codes zu arbeiten. Weiter betrachten wir komplexitätsfragen, indem wir Einblick in die Macaulaymatrix der zugrunde liegenden Systeme geben. Unter gewissen Voraussetzungen sind wir in der Lage, eine obere Schranke für den Koplexitätskoeffizienten unserer Methode zu liefern. Es wird auch die Berechnung des minimalen Abstandes sowie die Gewichtsverteilung angesprochen. Wir liefern umfangreiches experimentelles Material und Vergleiche mit einigen existierenden Methoden. Im zweiten Teil betrachten wir die algebraische Kryptoanalyse von iterativen Blockchiffren. Wir analysieren insbesondere die skalierte Varianten des Advanced Encryption Standard (AES), welche eine weit verbreitete moderne Blockchiffre ist. Hier konstruiert der Kryptoanalyst ein polynomiales System, dessen Lösungen den geheimen Schlüssel liefern sollen, der in diesem symmetrischen Kryptosystem verwendet wird. Die Analyse verschiedener Systeme zeigt, dass diese Systeme viele Hilfsvariable haben, die für die Schlüsselfindung nicht wirklich gebraucht werden. Die Hilfsvariablen werden üblicherweise benutzt, um die Nutzung mehrer Klartext-Geheimtext Paare zu verkomplizieren. Aus diesem Grund konstruieren wir ein neues System, in dem die Hilfsvariablen mittels Normalformreduktionen eliminiert werden. Das sich so ergebende System in nur Schlüsselvariablen wird dann gelöst. Wir weisen experimentell nach, dass diese Methode für klein skalierte Varianten des AES gut geeignet ist. Weiterhin untersuchen wir die so genannte Meet-in-the-middle Methode, um zu sehen, wie weit man mit 2-3 Runden bei klein skalierten Varianten kommen kann. Zusätzliche "tuning techniques" werden zusammen mit experimentellem Material besprochen. Dieser Teil der Arbeit liefert damit einen Beitrag zur algebraischen Kryptoanalyse von Blockchiffren.

Download full text files

Export metadata

Additional Services

Search Google Scholar
Metadaten
Author:Stanislav Bulygin
URN:urn:nbn:de:hbz:386-kluedo-23502
Advisor:Gert-Martin Greuel
Document Type:Doctoral Thesis
Language of publication:English
Year of Completion:2009
Year of first Publication:2009
Publishing Institution:Technische Universität Kaiserslautern
Granting Institution:Technische Universität Kaiserslautern
Acceptance Date of the Thesis:2009/06/12
Date of the Publication (Server):2009/06/16
Tag:PolyBoRi; algebraic attack; decoding; linear code
GND Keyword:Kanalcodierung; Gröbner-Basis; Kryptoanalyse; Singular <Programm>; Advanced Encryption Standard
Faculties / Organisational entities:Kaiserslautern - Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
MSC-Classification (mathematics):13-XX COMMUTATIVE RINGS AND ALGEBRAS / 13Pxx Computational aspects and applications [See also 14Qxx, 68W30] / 13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
94-XX INFORMATION AND COMMUNICATION, CIRCUITS / 94Axx Communication, information / 94A60 Cryptography [See also 11T71, 14G50, 68P25, 81P94]
94-XX INFORMATION AND COMMUNICATION, CIRCUITS / 94Bxx Theory of error-correcting codes and error-detecting codes / 94B05 Linear codes, general
94-XX INFORMATION AND COMMUNICATION, CIRCUITS / 94Bxx Theory of error-correcting codes and error-detecting codes / 94B35 Decoding
Licence (German):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011