Härtegarantien für AES

14

Viele Kryptosysteme mit öffentlichem Schlüssel weisen eine nachweisbare Sicherheit auf. Zum Beispiel ist das Rabin-Kryptosystem nachweislich so hart wie Factoring.

Ich frage mich, ob es für Kryptosysteme mit geheimen Schlüsseln wie AES eine solche nachweisbare Sicherheit gibt. Wenn nicht, was ist der Beweis dafür, dass die Zerstörung solcher Kryptosysteme schwierig ist? (außer Resistenz gegen Trial-and-Error-Angriffe)

Anmerkung: Ich bin mit AES-Operationen vertraut (AddRoundKey, SubBytes, ShiftRows und MixColumns). Es scheint, dass die Härte von AES von der MixColumns-Operation herrührt, die wiederum ihre Schwierigkeit von einem schwierigen Problem mit Galois Fields (und damit der Algebra) erben muss. Tatsächlich kann ich meine Frage wie folgt wiederholen: "Welches schwierige algebraische Problem garantiert die Sicherheit von AES?"

MS Dousti
quelle

Antworten:

8

MIXCOLUMNS verhindert Angriffe, die sich nur auf wenige S-Boxen konzentrieren, da zum Mischen der Spalten alle S-Boxen an der Verschlüsselung teilnehmen müssen. (Die Designer von Rijndael nannten dies eine "Wide-Trail-Strategie".) Die Ursachenanalyse einer S-Box ist schwierig, da die finite Feldinversionsoperation verwendet wird. Die Inversion "glättet" die Verteilungstabellen von S-Box-Einträgen, so dass die Einträge (fast) einheitlich erscheinen, dh nicht von einer zufälligen Verteilung ohne den Schlüssel zu unterscheiden sind. Es ist die Kombination der beiden Merkmale, die Rijndael nachweislich vor bekannten Angriffen sicher macht.

Abgesehen davon ist das Buch The Design of Rijndael eine sehr gute Lektüre und diskutiert die Theorie und Philosophie der Kryptographie.

Aaron Sterling
quelle
1
Gute Erklärung. Vielen Dank. Tatsächlich hatte ich Zugang zu dem Buch, wusste aber nicht, welchen Teil ich lesen sollte (in Bezug auf meine Frage). Schlagen Sie ein spezielles Kapitel oder einen speziellen Abschnitt vor?
MS Dousti
3
Ich habe es vor über zwei Jahren aus einer Bibliothek gelesen, daher habe ich das Inhaltsverzeichnis nicht vor mir und ich bin nicht sicher, ob ich Ihre Frage konkret beantworten kann, außer dass mir der Weg gefällt Sie haben die S-Boxen so konzipiert, dass sie einfach zu implementieren sind. Ich kann jedoch vorschlagen, dass Stinson AES und andere Substitutions-Permutations-Netzwerke in Cryptography: Theory and Practice erklärt. Ich habe Kapitel 3 der Ausgabe und es sieht so aus, als könnten Sie das Buch kostenlos unter folgendem Link herunterladen
Aaron Sterling
1
Vielen Dank, dass Sie Stinsons Buch vorgeschlagen haben. Könnten Sie auch das Inhaltsverzeichnis von The Design of Rijndael nachschlagen und nachsehen , ob es an etwas Nützliches erinnert?
MS Dousti,
2
Danke für den Link! :-) Ja, Abschnitt 3.6 und Kapitel 5 waren für mich beide sehr interessant, weil sie "warum" diskutierten, nicht nur "was".
Aaron Sterling
10

Wie David sagte, haben wir keine solchen Ermäßigungen für AES. Dies bedeutet jedoch nicht, dass Rabin- oder RSA-Kryptosysteme sicherer sind als AES. Tatsächlich würde ich der (zumindest einseitigen, wahrscheinlich auch pseudozufälligen) Sicherheit von Block-Chiffren wie AES / DES usw. (möglicherweise mit etwas mehr Runden als normalerweise verwendet) mehr vertrauen als der Annahme, dass Factoring ist schwer, gerade weil es keine algebraische Struktur gibt und es daher schwerer vorstellbar ist, dass es eine Art Durchbruch-Algorithmus geben wird.

Man kann Blockchiffren direkt aus Einwegfunktionen konstruieren, was eine minimale Annahme für einen Großteil der Kryptographie ist, aber die resultierende Konstruktion wird schrecklich ineffizient sein und daher nicht verwendet werden.

Boaz Barak
quelle
Danke Boaz. Ich denke, das Luby-Rackoff-Konstrukt ist eines, das beweisbare Pseudozufälligkeiten auf der Basis DES-ähnlicher Strukturen liefert, oder?
MS Dousti,
3
Ja. Genauer gesagt, Sie beginnen mit einer Einwegfunktion, konvertieren sie mit Hastad, Impagliazzo, Luby, Levin in einen Pseudozufallsgenerator, konvertieren sie dann mit Goldreich, Goldwasser, Micali in eine Pseudozufallsfunktion und konvertieren sie dann tatsächlich mit Luby-Rackoff in eine pseudozufällige Permutation (dh Block Zi Pher)
Boaz Barak
6

Da ein beliebiges Verschlüsselungsschema mit öffentlichem Schlüssel auf generische Weise in ein Schema mit geheimem Schlüssel umgewandelt werden kann, können Sie Geheimschlüsselschemata mit ähnlichen nachweisbaren Sicherheitsgarantien erhalten.

Diese Antwort ist jedoch umständlich: Für die typische implementierte Blockchiffre gibt es keine nachweisbare Sicherheitsanalyse im Sinne einer Reduktion auf ein Computerproblem. Es gab Vorschläge für Blockchiffren mit Sicherheitsreduzierungen, aber das zur Erleichterung einer Reduzierung erforderliche Rechengepäck macht sie mit effizienteren Schemata wie den AES-Algorithmen nicht konkurrenzfähig.

Interessanterweise hat die Community für nachweisbare Sicherheit allgemein zugestimmt, dass es vernünftig ist, die Blockverschlüsselungssicherheit (Pseudozufalls-Permutation) als Annahme zu betrachten und sie dann auf diese zu reduzieren, wenn übergeordnete Protokolle analysiert werden, die die Blockverschlüsselung als Komponente verwenden. Das heißt, im Gegensatz zu einigen anderen Herausforderungen beim Entwurf sicherer Protokolle scheint es ausreichend zu sein, der Sicherheit von Kryptoanalytikern zu vertrauen, wenn es um Blockchiffren geht.

David Cash
quelle