Quantum Circuit Realization and Grover Cryptanalysis of the Hybrid ARX-SPN Cipher GFSPX

Dieser Beitrag stellt eine qubit-optimierte Quantenschaltkreis-Implementierung des leichten hybriden ARX-SPN-Chiffriers GFSPX vor und bewertet dessen Post-Quanten-Sicherheit durch einen parallelisierten Grover-Angriff, wobei eine gesamte Quantenkosten von $1{,}12 \times 2^{159}$ Gattern ermittelt werden, die zwar unter den NIST-Level-1-Schwellenwerten liegen, jedoch eine überlegene Resistenz im Vergleich zu anderen leichten Designs aufweisen.

Das Wesentliche

Stellen Sie sich vor, Sie hätten ein sehr spezielles, leichtgewichtiges digitales Schloss (genannt GFSPX), das entwickelt wurde, um Daten auf kleinen Geräten wie intelligenten Sensoren oder RFID-Tags zu schützen. Dieses Schloss ist darauf ausgelegt, schnell zu sein und sehr wenig Energie zu verbrauchen, was es perfekt für das „Internet der Dinge" macht.

Allerdings taucht eine neue Art von „Super-Werkzeug" auf, ein Quantencomputer. Im Gegensatz zu herkömmlichen Computern, die Schlüssel nacheinander prüfen, kann ein Quantencomputer viele Schlüssel gleichzeitig überprüfen und könnte diese Schlösser potenziell viel schneller knacken. Dieser Artikel stellt eine einfache Frage: Wenn ein Quantencomputer versucht, dieses spezifische Schloss zu brechen, wie schwer wird es dann tatsächlich sein?

Hier ist die Aufschlüsselung ihrer Erkenntnisse mit alltäglichen Analogien:

1. Das Design des Schlosses: Ein Hybrid-Motor

Das GFSPX-Schloss ist nicht nur mit einem einzigen Mechanismus aufgebaut. Es ist ein Hybrid, wie ein Auto, das sowohl einen Verbrennungsmotor als auch einen Elektromotor nutzt.

• Der „Benzin"-Teil (ARX): Dieser verwendet einfache mathematische Operationen (Addieren, Rotieren, XOR), die sehr effizient sind, aber Änderungen in den Daten etwas langsamer verbreiten können.
• Der „Elektrische"-Teil (SPN): Dieser verwendet ein komplexes Substitutionsnetzwerk (wie das Mischen eines Kartendecks), das Änderungen sehr schnell verbreitet.
• Das Ergebnis: Durch die Kombination sind das Schloss schnell und effizient. Die Autoren erstellten einen digitalen Bauplan dieses Schlosses speziell für einen Quantencomputer, um genau zu sehen, wie es im Inneren funktioniert.

2. Der Quanten-Bauplan: Aufbau der Schaltung

Um das Schloss zu testen, mussten die Forscher eine „Quantenschaltung" bauen. Stellen Sie sich dies als den Bau einer miniaturisierten, reversiblen Fabrik vor, in der jeder Schritt perfekt rückgängig gemacht werden kann (damit keine Informationen verloren gehen).

• Die Herausforderung: Quantencomputer sind zerbrechlich. Man kann Daten nicht einfach kopieren; man muss sehr vorsichtig mit den „Qubits" umgehen (den Quantenbits, wie winzigen Kreisel).
• Die Lösung: Die Forscher optimierten das Design, um die geringstmögliche Anzahl an Qubits zu verwenden (insgesamt 209). Für die mathematischen Teile verwendeten sie einen cleveren Trick namens „Ripple-Carry-Addierer", der wie eine sehr effiziente Fließbandanlage funktioniert, die keinen Platz verschwendet.
• Der Platzbedarf: Der endgültige Bauplan ist kompakt und erfordert einen „Fabrikboden" von 209 Qubits sowie eine bestimmte Anzahl an Schritten (Gattern), um eine vollständige Verschlüsselung auszuführen.

3. Der Angriff: Die „Grover"-Suche

Um das Schloss zu brechen, verwendet ein Quantencomputer den Grover-Algorithmus.

• Die Analogie: Stellen Sie sich vor, Sie haben eine riesige Bibliothek mit $2^{128}$ Büchern (eine Zahl, die so riesig ist, dass sie kaum vorstellbar ist), und nur ein einziges Buch enthält den richtigen Schlüssel.
  • Ein herkömmlicher Computer ist wie ein Bibliothekar, der ein Buch nach dem anderen prüft. Das würde ewig dauern.
  • Ein Quantencomputer ist wie ein magischer Bibliothekar, der viele Bücher gleichzeitig prüfen kann. Er findet das richtige Buch in ungefähr der Quadratwurzel der Zeit.
• Die Falle: Um sicherzustellen, dass der Quantencomputer nicht das falsche Buch auswählt (ein „falsch-positives" Ergebnis), ließen die Forscher den Computer drei verschiedene Schlösser gleichzeitig prüfen (unter Verwendung von drei verschiedenen Paaren aus verschlüsselten/entschlüsselten Nachrichten). Wenn ein Schlüssel alle drei öffnet, ist er definitiv der richtige.

4. Das Urteil: Stark, aber kein „Post-Quanten"-Beweis

Die Forscher berechneten die gesamten „Kosten" dieses Quantenangriffs.

• Die Kosten: Sie stellten fest, dass das Brechen des Schlosses eine massive Rechenleistung erfordern würde, die ungefähr $1,12 \times 2^{159}$ Operationen entspricht.
• Der Standard: Das US-amerikanische National Institute of Standards and Technology (NIST) hat eine „Sicherheitslatze" für die Zukunft festgelegt. Um als wirklich sicher gegen Quantencomputer zu gelten (Sicherheitsebene 1), muss ein Schloss Kosten von mindestens $2^{170}$ aufweisen.
• Das Ergebnis: Das GFSPX-Schloss liegt unter der Sicherheitslatze. Es ist nicht sicher genug für die strengsten Post-Quanten-Standards.
  • Allerdings stellt der Artikel fest, dass GFSPX im Vergleich zu anderen leichtgewichtigen Schlössern tatsächlich eines der am schwersten zu brechenden ist. Es befindet sich in einem „Sweet Spot", wo es für kleine Geräte sehr effizient ist, aber dennoch einen anständigen Widerstand gegen Quantenangriffe bietet, auch wenn es den strengsten Sicherheitstest nicht besteht.

5. Das Fazit

Der Artikel kommt zu dem Schluss, dass dieses Hybrid-Schloss zwar hervorragend für aktuelle, ressourcenbeschränkte Geräte geeignet ist, die Schlüssellänge von 128 Bit jedoch einfach zu klein ist, um einen entschlossenen Quantenangriff in der Zukunft zu überstehen.

• Der Kompromiss: Sie können entweder ein Schloss haben, das winzig und schnell ist (gut für heutige Sensoren), oder ein Schloss, das riesig und langsam ist (gut für zukünftige Quantensicherheit), aber dieses spezifische Design versucht, beides zu tun und bleibt auf dem Gebiet der „zukünftigen Sicherheit" etwas zurück.
• Zukünftige Ratschläge: Um dieses Design wirklich quantenresistent zu machen, schlagen die Autoren vor, entweder den Schlüssel länger zu machen (wie 192 oder 256 Bit) oder die mathematischen Teile so anzupassen, dass sie für Quantencomputer noch schwieriger zu verarbeiten sind.

Kurz gesagt: GFSPX ist ein sehr kluges, effizientes Schloss, das schwieriger zu knacken ist als die meisten seiner Mitbewerber, aber es ist nicht stark genug, um den supermächtigen Quantencomputern der Zukunft ohne einige Upgrades standzuhalten.

Technische Zusammenfassung

Technisches Fazit: Quantenschaltungsimplementierung und Grover-Kryptoanalyse des hybriden ARX-SPN-Chiffriersystems GFSPX

Problemstellung
Die Entstehung des Quantencomputings stellt die Sicherheit klassischer symmetrischer Kryptoprimitiva grundlegend in Frage. Während Shors Algorithmus die Public-Key-Kryptographie bedroht, bietet Grovers Algorithmus eine quadratische Beschleunigung für unstrukturierte Suchen, was die Sicherheitsmarge symmetrischer Konstruktionen effektiv halbiert. Folglich erfordern leichte Blockchiffren (BCs), die für ressourcenbeschränkte Umgebungen wie das Internet der Dinge (IoT) und RFID entwickelt wurden, eine rigorose Neubewertung ihrer Resilienz gegenüber Quantenangriffen. Insbesondere besteht ein Bedarf, die Quantenressourcen zu quantifizieren, die für die Durchführung eines Schlüsselwiederangriffs auf hybride Designs erforderlich sind, die Addition-Rotation-XOR (ARX) und Substitutions-Permutations-Netzwerk (SPN) Paradigmen kombinieren.

Methodik
Die Autoren präsentieren eine umfassende Quantenschaltungsimplementierung und Grover-Kryptoanalyse von GFSPX, einer leichten Blockchiffre mit einem 64-Bit-Datenblock und einem 128-Bit-Geheimschlüssel. GFSPX nutzt eine 4-Branch-Verallgemeinerte Feistel-Struktur (GFS), die zwei unterschiedliche Funktionsblöcke integriert: eine ARX-basierte Funktion ($F_1$) für Nichtlinearität und eine 32-Bit-SPN-Struktur ($F_2$) für schnelle Diffusion.

Die Methodik verläuft in drei Stufen:

1. Quantenschaltungsimplementierung: Die klassische Struktur von GFSPX wird in eine reversible Quantenschaltung abgebildet. Die Autoren nutzen die inhärente Reversibilität des Feistel-Netzwerks aus, um den Verbrauch von Ancilla-Qubits zu minimieren.
   • $F_1$ (ARX): Implementiert unter Verwendung eines kompakten Ripple-Carry-Addierers (RCA) basierend auf der Architektur von Cuccaro et al. Dieser Ansatz minimiert den Qubit-Overhead, indem das letzte Übertragsbit für modulare Addition weggelassen und In-Place-Majority (MAJ) sowie UnMajority-and-Add (UMA) Gatter verwendet werden.
   • $F_2$ (SPN): Die S-Box-Schicht (basierend auf PRESENT) wird unter Verwendung eines minimalen Satzes von CNOT- und Toffoli-Gattern ohne zusätzliche Ancillae synthetisiert. Die Permutationsschicht (P-Schicht) wird durch parallelisierbare SWAP-Gatter implementiert, um eine geringe Schaltungstiefe zu gewährleisten.
   • Schlüsselplan: Der 128-Bit-Hauptschlüsselplan wird als unitäre Evolution realisiert, die eine 113-Bit-links-zyklische Rotation, S-Box-Substitutionen und Round-Counter-XORs umfasst, optimiert für die Ausführung In-Place.
2. Ressourcenschätzung: Die Quantenkosten werden unter Verwendung standardisierter Zerlegungsmetriken berechnet (NOT- und CNOT-Kosten = 1, Toffoli-Kosten = 6). Die Analyse bewertet sowohl eine Baseline-Kosten (ohne SWAP-Routing-Overhead) als auch eine Obergrenze (Zerlegung von SWAPs in drei CNOTs).
3. Grover-Kryptoanalyse: Ein parallelisierter Grover-Oracle ($U_f$) wird konstruiert, um die Chiffre gegen Schlüsselwiederangriffe zu bewerten. Um falsche Treffer im 128-Bit-Schlüsselraum zu eliminieren, nutzt der Oracle drei Klartext-Chiffretext-Paare ($r=3$). Die Angriffskomplexität wird abgeschätzt, indem die Ressourcenmetriken des Oracles mit der optimalen Anzahl von Grover-Iterationen skaliert werden ($\approx \frac{\pi}{4}2^{64}$).

Hauptbeiträge

• Optimierte Quantenimplementierung: Die Arbeit liefert eine qubit-optimierte Quantenschaltung für GFSPX mit einer Fläche von 209 Qubits. Das Design erreicht eine Baseline-Quantenkosten von 32.498 Gattern bei einer Schaltungstiefe von 7.617.
• Analyse hybrider Architekturen: Die Studie detailliert die Ressourcenverteilung eines hybriden ARX-SPN-Designs und zeigt auf, dass zwar das modulare Additionsprimitiv die Gesamtgate-Anzahl dominiert, die parallelisierten Permutationsschichten in der SPN-Komponente jedoch dazu beitragen, ein wettbewerbsfähiges Gate-zu-Tiefe-Verhältnis aufrechtzuerhalten.
• Quantitative Sicherheitsbewertung: Die Autoren konstruieren einen Grover-Oracle unter Verwendung von drei Klartext-Chiffretext-Paaren und berechnen die Gesamtkosten des Angriffs im Rahmen von NISTs MAXDEPTH-Rahmenwerk. Die Analyse ergibt Gesamtkosten für den Quantenangriff von ungefähr $1,12 \times 2^{159}$ Gattern für $r=3$.
• Vergleichendes Benchmarking: Die Implementierung wird mit anderen leichten Chiffren (z. B. PRESENT, GIFT, SIMON, SPECK) verglichen. GFSPX erreicht das niedrigste Kosten-zu-Tiefe-Verhältnis (4,27) unter den verglichenen Designs, was auf eine hohe parallele Ausführungseffizienz hinweist.

Ergebnisse

• Ressourcenmetriken: Der vollständige 20-Runden-GFSPX-Schaltung erfordert 209 Qubits. Die Baseline-Kosten betragen 32.498 und steigen auf 47.789, wenn der SWAP-Routing-Overhead einbezogen wird. Die Schaltungstiefe beträgt 7.617.
• Angriffskomplexität: Die gesamten Quantenkosten für einen Schlüsselwiederangriff werden auf $1,12 \times 2^{159}$ geschätzt (für $r=3$).
• Sicherheitsklassifizierung: Im Rahmen des NIST-Post-Quantum-Kryptographie-Rahmenwerks erfordert die Sicherheitsschwelle Level 1 (äquivalent zu AES-128) Gesamtkosten für einen Angriff von mindestens $2^{170}$. Die geschätzten Kosten für GFSPX ($2^{159}$) liegen unter dieser Schwelle.
• Designkompromisse: Während GFSPX eine höhere Widerstandsfähigkeit gegen Quantenangriffe als viele reine SPN-Designs (die sich um $2^{152}$ gruppieren) aufweist, erfüllt es nicht die strengen Sicherheitskriterien von Level 1 für eine Schlüssellänge von 128 Bit. Die Kosten des hybriden Designs werden stark von der ARX-Komponente (modulare Addition) beeinflusst, was sein Sicherheitsprofil näher an ARX-basierte Chiffren wie SIMON und SPECK rückt.

Bedeutung
Die Arbeit behauptet, dass ihre Erkenntnisse kritische Einblicke in das Gleichgewicht zwischen klassischer Hardware-Effizienz und Quantenresilienz für kryptographische Designs der nächsten Generation liefern. Die Studie hebt einen fundamentalen Kompromiss hervor: Während hybride ARX-SPN-Konstruktionen eine robuste klassische Leistung und eine bessere Quantenresistenz als reine SPN-Designs bieten, bleibt eine Schlüssellänge von 128 Bit strukturell unzureichend, um NIST-Level-1-Sicherheit gegen fortgeschrittene Quantenadversarien zu erreichen. Die Autoren schlagen vor, dass zukünftige Forschung sich auf die Erweiterung der Schlüssellängen (z. B. auf 192 oder 256 Bit) oder auf die Optimierung reversibler modularer Additionsprimitiven konzentrieren sollte, um die Sicherheitsmargen zu verbessern. Die in dieser Arbeit etablierte Methodik dient als rigoroses Rahmenwerk zur Bewertung anderer hybrider Designs in ressourcenbeschränkten Umgebungen.