Simon's Algorithm for the Even-Mansour Cipher on Quantum Hardware

Dieser Artikel stellt eine Proof-of-Concept-Quantenkryptanalyse der Even-Mansour-Chiffre mit dem Simon-Algorithmus auf NISQ-Hardware vor, bei der erfolgreich geheime Schlüssel für 3-Bit- und 4-Bit-Konstruktionen auf dem ibm_miami-Prozessor wiederhergestellt wurden, wobei gleichzeitig Speicherengpässe in aktuellen Schaltungsoptimierungswerkzeugen für größere Schlüssellängen aufgezeigt werden.

Das Wesentliche

Stellen Sie sich vor, Sie versuchen, einen Safe zu knacken, der ein sehr spezifisches, trickreiches Schloss verwendet. Diese Arbeit handelt von einem Team von Forschern, das versucht hat, dieses Schloss mit einer neuen Art von „Super-Werkzeug" zu öffnen, einem Quantencomputer genannt. Sie haben nicht einfach die Kombination erraten; sie verwendeten einen cleveren mathematischen Trick, um das Muster zu finden, das im Inneren des Schlosses verborgen ist.

Hier ist die Aufschlüsselung ihres Experiments in einfachen Worten:

Das Schloss: Die Even-Mansour-Chiffre

Stellen Sie sich die Even-Mansour-Chiffre als einen einfachen, aber stabilen Safe vor. Sie funktioniert wie folgt:

1. Sie legen eine Nachricht (den Klartext) in den Safe.
2. Sie mischen sie mit einem geheimen Schlüssel (Schlüssel 1).
3. Sie führen sie durch eine öffentliche, chaotische Maschine (eine Permutation), die sie durcheinanderwirbelt.
4. Sie mischen sie erneut mit einem zweiten geheimen Schlüssel (Schlüssel 2).
5. Das Ergebnis ist die verschlüsselte Nachricht.

Das Ziel der Angreifer (der Forscher) war es, herauszufinden, was diese beiden geheimen Schlüssel waren.

Das Super-Werkzeug: Simons Algorithmus

Normalerweise müsste man, wenn man einen geheimen Schlüssel finden wollte, Milliarden von Kombinationen einzeln ausprobieren. Das ist wie der Versuch, jeden einzelnen Schlüssel an einem riesigen Schlüsselbund auszuprobieren, bis einer passt.

Aber die Forscher verwendeten Simons Algorithmus. Stellen Sie sich diesen Algorithmus als einen magischen Detektiv vor, der nicht direkt nach dem Schlüssel sucht. Stattdessen sucht er nach einem verborgenen Rhythmus oder einem Muster.

• Die Forscher bauten ein spezielles Szenario auf, bei dem sich das Schloss auf seltsame Weise verhält: Wenn Sie das Zifferblatt um einen bestimmten Betrag (den geheimen Schlüssel) drehen, landet das Schloss in exakt derselben Position, als hätten Sie es gar nicht gedreht.
• Simons Algorithmus ist hervorragend darin, diese „verborgenen Rhythmen" (Perioden) viel schneller zu finden als ein normaler Computer. Es ist, als würde man einem Lied lauschen und sofort den Beat erkennen, wohingegen ein normaler Computer jeden einzelnen Trommelschlag zählen müsste.

Das Experiment: Das Schloss auf einem Quantencomputer bauen

Die Forscher wollten sehen, ob dieser magische Detektiv tatsächlich auf echter, physischer Hardware funktionieren kann. Sie bauten eine winzige Version des Schlosses auf einem Quantencomputer namens IBM Miami.

1. Der Bauplan (S-Boxen): Um das Schloss funktionsfähig zu machen, benötigten sie einen „Wirbler" (eine sogenannte S-Box). Sie bauten diese Wirbler mit einer Logik, die derjenigen ähnelt, die im berühmten AES-Verschlüsselungsstandard verwendet wird, jedoch in viel kleinerem Maßstab (für 3-Bit- und 4-Bit-Schlüssel).
2. Das Übersetzungsproblem: Quantencomputer sprechen eine andere Sprache als herkömmliche Computer. Die Forscher mussten ihre klassischen „Wirbler"-Entwürfe in eine Sprache übersetzen, die der Quantencomputer verstehen konnte. Sie verwendeten ein Werkzeug namens DORCIS, um diese Übersetzung durchzuführen.
   • Der Flaschenhals: Dieses Werkzeug funktionierte hervorragend für die winzigen 3-Bit- und 4-Bit-Schlösser. Als sie jedoch versuchten, ein etwas größeres 5-Bit-Schloss zu übersetzen, lief dem Werkzeug der Speicher aus. Es war, als würde man versuchen, eine riesige Landkarte in eine winzige Hosentasche zu falten; das Papier passte einfach nicht hinein. Dies hinderte sie daran, größere Schlüssel zu testen.
3. Das Rauschen: Quantencomputer sind derzeit sehr empfindlich, wie ein Kartenhaus in einem Sturm. Um das Experiment stabil zu halten, verwendeten die Forscher spezielle Techniken (wie „Dynamical Decoupling"), um die Qubits zu beruhigen, ähnlich wie man eine Kamera festhält, um bei Wind ein scharfes Foto zu machen.

Die Ergebnisse

Sie führten das Experiment an zwei kleinen Schlössern durch: einem mit einem 3-Bit-Schlüssel und einem mit einem 4-Bit-Schlüssel.

• Erfolg: In beiden Fällen fand der Quantencomputer erfolgreich den verborgenen Rhythmus. Aus diesem Rhythmus berechneten die Forscher die geheimen Schlüssel.
• Reproduzierbarkeit: Sie führten den Test fünf Mal für jede Schlossgröße durch, und er funktionierte jedes Mal.
• Die Einschränkung: Wie erwähnt, konnten sie kein 5-Bit-Schloss testen, da das Übersetzungswerkzeug (DORCIS) aufgrund von Speichergrenzen abstürzte.

Die Kernaussage

Die Arbeit kommt zu zwei Hauptergebnissen:

1. Es funktioniert (vorläufig): Simons Algorithmus ist eine echte, funktionierende Methode, um diese spezifische Art von Verschlüsselung auf aktueller Quantenhardware zu brechen, jedoch nur für sehr kleine Schlüssel. Es beweist, dass Quantencomputer diese verborgenen Muster theoretisch exponentiell schneller finden können als klassische Computer.
2. Die Werkzeuge benötigen ein Upgrade: Während der Quantencomputer seine Arbeit erledigte, stieß die Software, die verwendet wurde, um die „Baupläne" für den Quantencomputer vorzubereiten, an eine Wand. Um in Zukunft größere, realistischere Schlösser zu knacken, benötigen wir bessere Werkzeuge, um diese Entwürfe in Quantenschaltungen zu übersetzen, ohne den Speicher zu erschöpfen.

Kurz gesagt: Sie bewiesen, dass das Konzept im kleinen Maßstab funktioniert, aber die „Baumannschaft" (die Software-Werkzeuge) muss stärker werden, bevor sie die großen Wolkenkratzer errichten können.

Technische Zusammenfassung

1. Problemstellung

Das Papier adressiert die praktische Durchführbarkeit von Quantenkryptoanalyse-Angriffen auf symmetrische Chiffren unter Verwendung aktueller Noisy Intermediate-Scale Quantum (NISQ)-Hardware. Konkret richtet es sich auf die Even-Mansour-Chiffre (EM), eine minimale Blockchiffre-Konstruktion, die auf einer öffentlichen Permutation und zwei geheimen Schlüsseln basiert.

Während der theoretische Rahmen zum Brechen der EM-Chiffre mittels Simons Algorithmus gut etabliert ist (und eine exponentielle Beschleunigung gegenüber klassischen Angriffen durch das Finden einer versteckten Periode bietet), war die praktische Umsetzung begrenzt. Die Kernherausforderungen umfassen:

• Hardware-Einschränkungen: NISQ-Geräte leiden unter Rauschen, Dekohärenz und begrenzter Qubit-Konnektivität, was die Ausführung tiefer Schaltungen (erforderlich für komplexe Permutationen) erschwert.
• Engpässe bei der Schaltungssynthese: Die Umwandlung klassischer kryptografischer Permutationen (S-Boxen) in optimierte, reversible Quantenschaltungen ist rechenintensiv. Bestehende Tools versagen oft bei größeren Schlüssellängen aufgrund von Speicherbeschränkungen.
• Orakel-Implementierung: Der Angriff erfordert die Implementierung der Verschlüsselungsfunktion als Quanten-Orakel, was die Synthese nicht-linearer Permutationen in Quantengatter beinhaltet.

2. Methodik

Die Autoren implementierten einen Proof-of-Concept-Angriff auf dem IBM-Prozessor ibm_miami. Die Methodik umfasste drei Hauptphasen:

A. Kryptografische Konstruktion

• Chiffre: Das Even-Mansour-Schema $EM_{k_1, k_2}(x) = P(x \oplus k_1) \oplus k_2$, wobei $P$ eine öffentliche Permutation und $k_1, k_2$ geheime Schlüssel sind.
• Permutation ($P$): Für $N=3$ und $N=4$ konstruierten die Autoren bijektive Abbildungen, die von der AES-S-Box inspiriert sind. Diese wurden als Inversion im endlichen Körper $F_{2^N}$ gefolgt von einer affinen Transformation definiert.
• Angriffsvektor: Der Angriff definiert eine Funktion $f(x) = EM(x) \oplus P(x)$. Diese Funktion besitzt eine versteckte Periode $k_1$. Simons Algorithmus wird verwendet, um $k_1$ zu finden, woraufhin $k_2$ klassisch oder über eine einfache Quantenabfrage recovered wird.

B. Quantenschaltungssynthese (DORCIS)

• Toolchain: Die Autoren verwendeten das Tool DORCIS (Depth Optimized Quantum Implementation of Substitution Boxes), um die klassischen Permutationstabellen in reversible Quantenschaltungen zu synthetisieren.
• Optimierung: DORCIS zerlegt Permutationen in elementare Gatter (Pauli-X, Toffoli/CCNOT, SWAP) und minimiert die Schaltungstiefe.
• Skalierungsgrenze: Das Tool generierte erfolgreich Schaltungen für $N=3$ und $N=4$, scheiterte jedoch bei $N=5$ aufgrund eines Speicherengpasses auf einem Hochleistungs-CPU (3,9 TiB RAM), was die Generierung von Schaltungen für größere Instanzen verhinderte.

C. Hardware-Ausführung und Fehlerminderung

Um den Angriff auf dem verrauschten ibm_miami-Prozessor auszuführen, setzte das Team spezifische Minderungsstrategien ein:

• Qubit-Zuordnung: Sie ordneten logische Qubits manuell spezifischen physikalischen Qubit-Teilgraphen zu ($[0, 1, 2, 12, 11, 10]$ für $N=3$ und $[0, 1, 2, 3, 13, 12, 11, 10]$ für $N=4$), um die Gittertopologie zu nutzen und den Overhead durch automatisches Routing zu vermeiden.
• Dynamische Entkopplung (DD): Auf idle-Qubits wurden symmetrische Sequenzen von Unitäroperationen (z. B. abwechselnde X-Impulse) angewendet, um niederfrequentes Umgebungsrauschen und Übersprechen zu unterdrücken.
• Pauli-Twirling: Logisch äquivalente Pauli-Operator-Paare wurden zufällig vor und nach Gattern eingefügt, um kohärente Fehler in stochastische Pauli-Fehler umzuwandeln und systematische Phasenverzerrungen zu verhindern, die strukturelle Kollisionen des Algorithmus verschleiern könnten.

3. Hauptbeiträge

1. Erste praktische Demonstration: Dies ist ein erfolgreicher Proof-of-Concept, der die Wiederherstellung des geheimen Schlüssels für die Even-Mansour-Chiffre auf tatsächlicher Quantenhardware ($N=3$ und $N=4$) demonstriert.
2. Validierung der Fehlerminderung: Das Papier validiert, dass die Kombination aus Dynamischer Entkopplung und Pauli-Twirling es Simons Algorithmus ermöglicht, trotz der tiefen Schaltungstiefen und des Rauschens, die NISQ-Geräten inhärent sind, effektiv zu funktionieren.
3. Identifikation klassischer Engpässe: Die Studie hebt hervor, dass der limitierende Faktor für die Skalierung dieser Angriffe derzeit die klassische Vorverarbeitung (Schaltungssynthese) und nicht die Quantenhardware selbst ist. Das DORCIS-Tool scheiterte bei $N=5$ aufgrund von Speicherbeschränkungen.
4. Empirische Daten: Die Autoren liefern detaillierte statistische Verteilungen von Messergebnissen, die zeigen, dass die experimentellen Ergebnisse mit theoretischen Vorhersagen übereinstimmen, wenn Rauschen berücksichtigt wird.

4. Ergebnisse

• 3-Bit-Fall ($N=3$):
  • Erfolgreiche Wiederherstellung des geheimen Schlüssels $k_1 = (0, 1, 0)$ und $k_2 = (1, 1, 0)$.
  • Die Schaltungstiefe betrug 23 (T-Tiefe 3).
  • Nach 5 unabhängigen Experimenten (jeweils 105 Schüsse) zeigte die Messverteilung einen klaren Peak bei den Vektoren, die orthogonal zur wahren Periode stehen, was eine erfolgreiche lineare Algebra-Wiederherstellung des Schlüssels ermöglichte.
• 4-Bit-Fall ($N=4$):
  • Erfolgreiche Wiederherstellung von $k_1 = (0, 1, 0, 1)$ und $k_2 = (1, 1, 0, 1)$.
  • Die Schaltungstiefe stieg auf 54 (T-Tiefe 7).
  • Trotz der erhöhten Tiefe und des Rauschens blieb die Verteilung der Ergebnisse deutlich genug, um das System linearer Gleichungen für den Schlüssel zu lösen.
• Fehleranalyse:
  • Die Autoren modellierten das Rauschen als depolarisierenden Kanal. Basierend auf Gatterfehlerraten und der Gesamtzahl der Impulse schätzten sie einen Rauschparameter von $p \approx 0,434$.
  • Die experimentellen Daten stimmten mit der theoretischen verrauschten Verteilung überein, was bestätigte, dass die Abweichungen auf Hardware-Rauschen und nicht auf algorithmisches Versagen zurückzuführen waren.
• Skalierungsversagen: Das DORCIS-Tool konnte keine Schaltung für $N=5$ generieren, was darauf hinweist, dass aktuelle klassische Synthese-Tools für größere Schlüssellängen noch nicht skalierbar sind.

5. Bedeutung

• Theoretische Validierung: Die Ergebnisse bestätigen, dass die theoretische exponentielle Beschleunigung von Simons Algorithmus in der Praxis für symmetrische Chiffren erreichbar ist, sofern die Schlüssellänge für die aktuelle Hardware klein genug ist.
• Sicherheitsimplikationen: Es unterstreicht die Verwundbarkeit symmetrischer Konstruktionen wie Even-Mansour (und damit auch von 1-Runden-AES) gegenüber Quantenangriffen, wenn ein Verschlüsselungsorakel in Superposition zugänglich ist.
• Hardware- vs. Software-Engpass: Das Papier verlagert den Fokus der Herausforderung von „Können wir den Quantenalgorithmus ausführen?" zu „Können wir die Schaltung synthetisieren?". Es legt nahe, dass zukünftige Fortschritte in der Quantenkryptoanalyse stark von der Entwicklung skalierbarer klassischer Synthese-Tools (möglicherweise unter Verwendung von maschinellem Lernen oder Heuristiken) abhängen und nicht nur vom Warten auf bessere Qubits.
• NISQ-Tauglichkeit: Es zeigt, dass mit ausgefeilter Fehlerminderung und manueller Qubit-Zuordnung komplexe kryptoanalytische Algorithmen auf aktueller, verrauschter Hardware korrekte Ergebnisse liefern können.