Date
2015-04-22Metadata
Show full item record
Dissertation
Modellbildung in der algebraischen Kryptoanalyse
Abstract
In der algebraischen Kryptoanalyse werden moderne Kryptosysteme als polynomielle, nichtlineare Gleichungssysteme dargestellt. Das Lösen solcher Gleichungssysteme ist NP-hart. Es gibt also keinen Algorithmus, der in polynomieller Zeit ein beliebiges nichtlineares Gleichungssystem löst. Dennoch kann man aus modernen Kryptosystemen Gleichungssysteme mit viel Struktur generieren. So sind diese Gleichungssysteme bei geeigneter Modellierung quadratisch und dünn besetzt, damit nicht beliebig. Dafür gibt es spezielle Algorithmen, die eine Lösung solcher Gleichungssysteme finden. Ein Beispiel dafür ist der ElimLin-Algorithmus, der mit Hilfe von linearen Gleichungen das Gleichungssystem iterativ vereinfacht. In der Dissertation wird auf Basis dieses Algorithmus ein neuer Solver für quadratische, dünn besetzte Gleichungssysteme vorgestellt und damit zwei symmetrische Kryptosysteme angegriffen. Dabei sind die Techniken zur Modellierung der Chiffren von entscheidender Bedeutung, so das neue Techniken entwickelt werden, um Kryptosysteme darzustellen. Die Idee für das Modell kommt von Cube-Angriffen. Diese Angriffe sind besonders wirksam gegen Stromchiffren. In der Arbeit werden unterschiedliche Varianten klassifiziert und mögliche Erweiterungen vorgestellt. Das entstandene Modell hingegen, lässt sich auch erfolgreich auf Blockchiffren und auch auf andere Szenarien erweitern. Bei diesen Änderungen muss das Modell nur geringfügig geändert werden.
In algebraic cryptanalysis ciphers are represented by polynomial, nonlinear systems of equations. Solving such systems is known to be NP-hard. Thus there is no algorithm that solves a random, nonlinear system of equations in polynomial time. But systems of equations generated by modern ciphers have certain structures. Using proper modelling techniques we get sparse quadratic systems of equations. There are algorithms for solving such systems available, for instance ElimLin-algorithm. It uses linear equations to simplify the overall system iteratively. In the dissertation a new solver for sparse, quadratic systems of equations based on ElimLin is presented and two symmetric primitives are attacked. Therefore using new modelling techniques is crucial. These new techniques are inspired by the cube attack. Variants of cube attacks are especially efficient in attacking stream ciphers. Different variants of the cube attack are described and possible extensions proposed. The new model is more flexible than the cube attack. In the dissertation are attacks against the stream cipher Trivium and the block cipher katan in different attack scenarios presented. For these quite different attacks the new algebraic representation (the model) stays nearly the same.
Citation
@phdthesis{urn:nbn:de:hebis:34-2015042248155,
author={Quedenfeld, Frank-Michael},
title={Modellbildung in der algebraischen Kryptoanalyse},
school={Kassel, Universität Kassel, Fachbereich Mathematik und Naturwissenschaften},
month={04},
year={2015}
}
0500 Oax
0501 Text $btxt$2rdacontent
0502 Computermedien $bc$2rdacarrier
1100 2015$n2015
1500 1/ger
2050 ##0##urn:nbn:de:hebis:34-2015042248155
3000 Quedenfeld, Frank-Michael
4000 Modellbildung in der algebraischen Kryptoanalyse / Quedenfeld, Frank-Michael
4030
4060 Online-Ressource
4085 ##0##=u http://nbn-resolving.de/urn:nbn:de:hebis:34-2015042248155=x R
4204 \$dDissertation
4170
5550 {{Kryptoanalyse}}
5550 {{Nichtlineare Gleichung}}
7136 ##0##urn:nbn:de:hebis:34-2015042248155
<resource xsi:schemaLocation="http://datacite.org/schema/kernel-2.2 http://schema.datacite.org/meta/kernel-2.2/metadata.xsd"> 2015-04-22T06:54:21Z 2015-04-22T06:54:21Z 2015-04-22 urn:nbn:de:hebis:34-2015042248155 http://hdl.handle.net/123456789/2015042248155 ger Urheberrechtlich geschützt https://rightsstatements.org/page/InC/1.0/ Nichtlineare Gleichungen Kryptoanalyse Symmetrische Chiffren Fehler-Angriff Algebraischer Angriff Trivium Katan ElimLin Dünn besetzte Gleichungssysteme Gröbnerbasen XL Cube-Angriff Modellbildung Quadratische Gleichungssysteme 004 510 Modellbildung in der algebraischen Kryptoanalyse Dissertation In der algebraischen Kryptoanalyse werden moderne Kryptosysteme als polynomielle, nichtlineare Gleichungssysteme dargestellt. Das Lösen solcher Gleichungssysteme ist NP-hart. Es gibt also keinen Algorithmus, der in polynomieller Zeit ein beliebiges nichtlineares Gleichungssystem löst. Dennoch kann man aus modernen Kryptosystemen Gleichungssysteme mit viel Struktur generieren. So sind diese Gleichungssysteme bei geeigneter Modellierung quadratisch und dünn besetzt, damit nicht beliebig. Dafür gibt es spezielle Algorithmen, die eine Lösung solcher Gleichungssysteme finden. Ein Beispiel dafür ist der ElimLin-Algorithmus, der mit Hilfe von linearen Gleichungen das Gleichungssystem iterativ vereinfacht. In der Dissertation wird auf Basis dieses Algorithmus ein neuer Solver für quadratische, dünn besetzte Gleichungssysteme vorgestellt und damit zwei symmetrische Kryptosysteme angegriffen. Dabei sind die Techniken zur Modellierung der Chiffren von entscheidender Bedeutung, so das neue Techniken entwickelt werden, um Kryptosysteme darzustellen. Die Idee für das Modell kommt von Cube-Angriffen. Diese Angriffe sind besonders wirksam gegen Stromchiffren. In der Arbeit werden unterschiedliche Varianten klassifiziert und mögliche Erweiterungen vorgestellt. Das entstandene Modell hingegen, lässt sich auch erfolgreich auf Blockchiffren und auch auf andere Szenarien erweitern. Bei diesen Änderungen muss das Modell nur geringfügig geändert werden. In algebraic cryptanalysis ciphers are represented by polynomial, nonlinear systems of equations. Solving such systems is known to be NP-hard. Thus there is no algorithm that solves a random, nonlinear system of equations in polynomial time. But systems of equations generated by modern ciphers have certain structures. Using proper modelling techniques we get sparse quadratic systems of equations. There are algorithms for solving such systems available, for instance ElimLin-algorithm. It uses linear equations to simplify the overall system iteratively. In the dissertation a new solver for sparse, quadratic systems of equations based on ElimLin is presented and two symmetric primitives are attacked. Therefore using new modelling techniques is crucial. These new techniques are inspired by the cube attack. Variants of cube attacks are especially efficient in attacking stream ciphers. Different variants of the cube attack are described and possible extensions proposed. The new model is more flexible than the cube attack. In the dissertation are attacks against the stream cipher Trivium and the block cipher katan in different attack scenarios presented. For these quite different attacks the new algebraic representation (the model) stays nearly the same. open access Quedenfeld, Frank-Michael Kassel, Universität Kassel, Fachbereich Mathematik und Naturwissenschaften Koepf, Wolfram (Prof. Dr.) Wacker, Arno (Prof. Dr.) 94A60 14G50 Kryptoanalyse Nichtlineare Gleichung 2015-04-13 </resource>
The following license files are associated with this item:
:Urheberrechtlich geschützt