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. | German |
Drucken
Impressum