Härtegarantien für AES

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?"

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.

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.

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.