Ein automatisiertes Modell für differentielle Meet-in-the-Middle-Angriffe auf AndRX-Chiffren

Warum diese Forschung wichtig ist

Jedes Mal, wenn wir ein Smartphone nutzen, online bezahlen oder ein medizinisches Gerät verbinden, schützen kleine digitale Schlösser namens Blockchiffren unsere Daten. Sicherheitsexperten versuchen diese Schlösser ständig zu knacken, um sicherere Entwürfe zu entwickeln. Dieses Paper stellt eine neue Methode vor, um eine leistungsfähige Angriffsart auf eine verbreitete Familie leichter Chiffren zu automatisieren und damit Forschern zu helfen, die tatsächliche Stärke dieser digitalen Schlösser zu prüfen.

Wie modernes Codeknacken funktioniert

Moderne Blockchiffren verschlüsseln Daten in vielen kleinen Schritten, sogenannten Runden, die von einem geheimen Schlüssel gesteuert werden. Um zu bewerten, ob eine Chiffre sicher ist, suchen Kryptanalytiker nach Mustern, die nicht existieren sollten, wenn das System rein zufällig wäre. Zwei klassische Werkzeuge sind die differentielle Kryptanalyse, die verfolgt, wie kleine Eingangsänderungen bis zum Ausgang durchschlagen, und Meet-in-the-Middle-Angriffe, die von beiden Enden der Chiffre rechnen und in der Mitte nach Übereinstimmungen suchen. Jedes Werkzeug für sich hat Grenzen, aber ihre Kombination erzeugt ein schärferes Prüfverfahren der Chiffrenstruktur.

Kombination zweier Angriffsansätze

Die Studie konzentriert sich auf eine hybride Technik namens differentieller Meet-in-the-Middle-Angriff. Dabei wird die Chiffre in drei Teile geteilt: einen Eingangsbereich, einen Mittelteil und einen Ausgangsbereich. Im Mittelteil sucht der Angreifer nach einem „differentiellen Distinguisher“ — einem Muster von Eingangs- und Ausgangsdifferenzen, das über mehrere Runden häufiger auftritt als zufällig. Um diesen Kern herum verschlüsselt der Angreifer teilweise von vorne und entschlüsselt teilweise von hinten und rät dabei nur ausgewählte Teile des Schlüssels. Treffen die beiden Richtungen im gleichen internen Zustand aufeinander, sind die geratenen Bits eher mit dem echten Schlüssel kompatibel, was den Suchraum einschränkt.

Handwerk in ein automatisiertes Werkzeug überführen

Solche kombinierten Angriffe von Hand zu entwerfen ist extrem schwierig, besonders für bitorientierte Chiffren mit internen Zuständen von 64, 96 oder 128 Bit. Die Autor:innen bauen ein automatisiertes Framework, das Constraint-Programmierung nutzt — eine Methode, um komplexe logische Bedingungen zu beschreiben, sodass ein Solver alle gültigen Möglichkeiten durchsuchen kann. Zuerst kodieren sie, wie sich Differenzen durch die Grundbausteine einer Chiffre bewegen, die auf AND-, Rotations- und XOR-Operationen basieren — eine Familie, die als AndRX-Designs bekannt ist. Dann modellieren sie, welche Schlüsselbits jede Stufe beeinflussen und wie viele dieser Bits tatsächlich geraten werden müssen. Der Solver durchsucht viele Möglichkeiten, die Chiffre in Eingangs-, Mittel- und Ausgangsabschnitte zu teilen, und wählt das Layout, das den Gesamtaufwand eines Angriffs minimiert.

Zusätzliche Tricks zur Reduktion des Schlüsselraums

Auf das Basismodell setzt das Framework zwei Optimierungs-Tricks, zugeschnitten auf Feistel-artige AndRX-Chiffren wie SIMON und Simeck. Der erste, die Idee der äquivalenten Subkeys, verschiebt mathematisch Teile der Rundenschlüssel vorwärts oder rückwärts, sodass mehrere verschiedene Schlüsselbits sich verhalten, als wären sie identisch. Das reduziert die Anzahl unabhängiger Bits, die der Angreifer berücksichtigen muss. Der zweite, selektives Schlüsselraten, analysiert, wie die nichtlineare AND-Operation ihre Eingänge verwendet, und zeigt, dass unter bestimmten Bedingungen ein geratenes Bit zwei Bits ersetzen kann. Die Autor:innen beschreiben außerdem, aber automatisieren noch nicht vollständig, zwei weitere Verbesserungen: parallele Partitionierung, die ohne zusätzlichen Zeitaufwand eine zusätzliche Runde zum Angriff hinzufügen kann, und einen Datensenkungstrick, der die benötigte Anzahl gewählter Nachrichten reduziert.

Was das Werkzeug über reale Chiffren offenbart

Um ihren Ansatz zu testen, wenden die Forschenden ihr automatisiertes Modell auf alle Standardversionen der leichten Chiffren SIMON und Simeck an, die als Kandidaten für den Einsatz in eingeschränkten Geräten wie Sensoren und eingebetteten Steuerungen gelten. Für jede Variante findet das Werkzeug einen differentiellen Meet-in-the-Middle-Angriff und schätzt dessen Daten-, Zeit- und Speicheraufwand. In vielen Fällen erreichen diese Angriffe mehr Runden als frühere Meet-in-the-Middle- oder verwandte Techniken und übertreffen häufig auch frühere impossible-differential- und zero-correlation-Angriffe in Bezug auf die abgedeckte Rundenzahl. Beispielsweise liefert das Werkzeug Angriffe auf bis zu 51 Runden einer 128-Bit-Version von SIMON mit einem 256-Bit-Schlüssel und erweitert damit die Reichweite früherer Methoden, während der Aufwand unter einer vollständigen Schlüsselsuche bleibt.

Gesamtbild für die künftige Kryptographie

Für Nichtfachleute ist die Kernbotschaft nicht, dass SIMON oder Simeck in praktischen Anwendungen „gebrochen“ sind, sondern dass automatisierte Werkzeuge zunehmend leistungsfähig genug werden, subtile Schwachstellen zu entdecken, die man von Hand nur sehr schwer finden würde. Das hier vorgestellte Framework ist auf Bit-Ebene generisch und kann prinzipiell an andere Chiffrenfamilien angepasst werden. Indem es Designern ermöglicht, neue Algorithmen schnell gegen fortgeschrittene kombinierte Angriffe zu testen, unterstützt ein solches Werkzeug das langfristige Ziel, Verschlüsselung zu bauen, die robust bleibt, selbst wenn die Analysemethoden weiter an Raffinesse gewinnen.

Zitation: Chakraborty, D., Sahoo, S., Nguyen, P.H. et al. An automated model for differential meet in the middle attacks on AndRX ciphers. Sci Rep 16, 14773 (2026). https://doi.org/10.1038/s41598-026-41390-w

Schlüsselwörter: Kryptanalyse von Blockchiffren, differentieller Meet-in-the-Middle, SIMON-Chiffre, Simeck-Chiffre, Constraint-Programmierung