💻 computer science

A Generalized PNE Framework: Taking ChaCha Further in Syncopated Rhythm

Dieses Paper führt ein verallgemeinertes Framework für Probabilistic Neutral Expressions (PNE) ein, das neuartige Techniken wie Syncopation und Carry-Preserving integriert, um Key-Recovery-Angriffe auf die rundenreduzierte ChaCha signifikant zu verbessern, wobei der erste Related-Key-Angriff auf ChaCha8 erzielt und 7,5 Runden von 256-Bit-ChaCha gebrochen werden.

Ursprüngliche Autoren: Shichang Wang, Meicheng Liu, Shiqi Hou, Chengan Hou, Dongdai Lin

Veröffentlicht 2026-08-31

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Shichang Wang, Meicheng Liu, Shiqi Hou, Chengan Hou, Dongdai Lin

Originalarbeit lizenziert unter CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

In der weiten digitalen Landschaft, in der unsere privaten Nachrichten, Finanztransaktionen und sicheren Verbindungen reisen, existiert ein stiller Wächter, der als Stromchiffre bekannt ist. Stellen Sie sich dies als eine Hochgeschwindigkeitsmaschine vor, die einen langen, zufällig aussehenden Strom von Zahlen erzeugt, um Daten zu verschlüsseln und sicherzustellen, dass nur jemand mit dem richtigen geheimen Schlüssel sie entschlüsseln und die ursprüngliche Nachricht lesen kann. Eine der vertrauenswürdigsten Maschinen dieser Art heißt ChaCha. Sie ist der Motor hinter der Sicherheit vieler alltäglicher Internetprotokolle und schützt alles, von Ihrem Webbrowser bis hin zu Ihren verschlüsselten E-Mails. Da sie so weit verbreitet ist, wird ihre Stärke ständig von Kryptanalysten getestet – Spezialisten, die versuchen, diese Codes zu knacken, nicht um Geheimnisse zu stehlen, sondern um ihre Grenzen zu verstehen und sicherzustellen, dass sie sicher bleiben. Die Kernherausforderung beim Knacken einer Chiffre wie ChaCha besteht darin, dass sie auf einer Struktur aufgebaut ist, die einfache Operationen wie das Addieren von Zahlen, das Rotieren von Bits und das Umlegen von Schaltern auf eine Weise kombiniert, die schnell unglaublich komplex wird. Um eine Schwachstelle zu finden, müssen Forscher nachverfolgen, wie eine winzige Änderung im Input durch diese Operationen kaskadiert, um zu sehen, ob sie ein vorhersagbares Muster im Output erzeugt.

Ein Team von Forschern hat nun einen bedeutenden Schritt nach vorn gemacht, um die Grenzen von ChaCha zu verstehen, indem es eine neue Methode entwickelte, um zu analysieren, wie sich diese Wellenbewegungen verhalten. Sie konzentrierten sich auf eine spezifische Technik namens differenzielle Kryptanalyse, bei der zwei leicht unterschiedliche Eingaben in die Chiffre eingespeist werden und beobachtet wird, wie sich die Unterschiede entwickeln. In früheren Versuchen, ChaCha zu knacken, mussten Forscher eine massive Anzahl möglicher Schlüssel erraten, um zu sehen, welcher zu den beobachteten Mustern passte – ein Prozess, der oft zu langsam für die Praxis war. Die neue Studie führt einen verfeinerten Ansatz ein, der ein Konzept namens „Syncopation“ verwendet. Im Kontext dieser Chiffre ermöglicht diese Technik den Forschern, spezifische Teile des geheimen Schlüssels zu identifizieren, die unter bestimmten Bedingungen fast keinen Einfluss auf den endgültigen verschlüsselten Output haben. Durch das Isolieren dieser nicht einflussreichen Teile können die Forscher sie während der Anfangsphasen des Angriffs effektiv ignorieren, was die Anzahl der zu testenden Möglichkeiten drastisch reduziert. Dies ist vergleichbar damit, ein komplexes Puzzle zu lösen, indem man zuerst die Teile beiseite legt, die offensichtlich nicht zum Zentrum des Bildes gehören, sodass man seine Energie auf die kritischen Teile konzentrieren kann, die tatsächlich wichtig sind.

Unter Verwendung dieser Syncopation-Technik, kombiniert mit einer neuen Strategie zum Erraten der verbleibenden Schlüsselbits, konnten die Forscher Versionen von ChaCha brechen, die zuvor als sicher gegen solche Angriffe galten. Konkret demonstrierten sie einen erfolgreichen Angriff auf eine Version der Chiffre mit 7,5 Runden der Verarbeitung. Während die vollständige, Standardversion von ChaCha 20 Runden verwendet, ist das Knacken von 7,5 Runden eine bemerkenswerte Leistung, da es das erste Mal ist, dass ein Key-Recovery-Angriff auf diese spezifische Anzahl von Runden durchgeführt wurde, der schneller ist als das bloße systematische Durchprobieren jedes möglichen Schlüssels. Die Forscher zeigten auch, dass ihre Methoden Angriffe auf 7-Runden-Versionen der Chiffre verbessern können, indem sie diese signifikant effizienter als bisherige Versuche machen. Darüber hinaus wandten sie ihre Techniken auf eine verwandte Version der Chiffre namens ChaCha8 an, die nur 8 Runden verwendet. In einem Szenario, in dem ein Angreifer erlaubt ist, zwei Schlüssel zu verwenden, die einander sehr ähnlich sind, fanden sie einen Weg, ChaCha8 zu brechen, was darauf hindeutet, dass diese spezifische Variante möglicherweise nicht das volle Sicherheitsniveau bietet, das ihre Entwickler vorgesehen haben, falls eine solche Bedingung jemals eintritt.

Die Studie untersuchte auch eine kürzere Version der Chiffre, die einen 128-Bit-Schlüssel anstelle des Standard-256-Bit-Schlüssels verwendet. Hier gelang es den Forschern, eine 7-Runden-Version dieser kürzeren Chiffre zu brechen, vorausgesetzt, der allerletzte Schritt des Verschlüsselungsprozesses wird entfernt. Diese Ergebnisse bedeuten nicht, dass die vollständige, 20-Runden-Version von ChaCha, die in realen Anwendungen wie Ihrem Webbrowser verwendet wird, derzeit gebrochen ist. Die vollständige Version bleibt sicher. Dennoch sind diese Erkenntnisse entscheidend, da sie die Grenzen dessen verschieben, was über die internen Mechanismen der Chiffre bekannt ist. Indem sie beweisen, dass die Chiffre unter spezifischen, kontrollierten Bedingungen geschwächt werden kann, liefern die Forscher wertvolles Feedback an die Kryptographie-Gemeinschaft. Dies hilft sicherzustellen, dass die Algorithmen, die unser digitales Leben schützen, robust sind und dass potenzielle Schwachstellen identifiziert und behoben werden, bevor sie in der realen Welt ausgenutzt werden können. Die Arbeit stellt einen kleinen, aber schwierigen Fortschritt im fortlaufenden Bemühen dar, die mathematischen Grundlagen unserer digitalen Privatsphäre zu verstehen und zu sichern.

Technisches Resümee: Ein generalisiertes PNE-Framework: ChaCha durch Synkopierung weiterentwickeln

1. Problemstellung

Die Stromchiffre ChaCha, insbesondere die 256-Bit-Variante, wird weit verbreitet in realen Protokollen wie TLS, SSH und QUIC eingesetzt. Trotz ihrer extensiven Nutzung war die Sicherheitsmarge von rundenreduzierten ChaCha-Versionen Gegenstand intensiver kryptanalytischer Forschung. Vor dieser Arbeit waren die effektivsten Key-Recovery-Angriffe auf 256-Bit-ChaCha auf 7 Runden (mit Zeitkomplexitäten oft über $2^{220}$ ) oder 7,25 Runden beschränkt, und kein Angriff, der schneller als Brute-Force ( $2^{256}$ ) war, konnte erfolgreich für 7,5 Runden im Single-Key-Setting demonstriert werden. Darüber hinaus blieb die Sicherheit der 8-Runden-Variante (ChaCha8) im Related-Key-Setting weitgehend unerforscht hinsichtlich effizienter Angriffe.

Die zentrale Herausforderung in der Differenzialkryptanalyse von ChaCha liegt im Kompromiss zwischen der Anzahl der identifizierten Probabilistischen Neutralen Bits (PNBs) und der Korrelation der Rückwärtsapproximation. Traditionelle Methoden haben oft Schwierigkeiten, eine große Menge an PNBs zu finden, die gleichzeitig eine hohe Korrelation aufrechterhalten, was die Effizienz von Meet-in-the-Middle-Angriffen einschränkt. Zudem mangelte es den bisherigen Analysen von „starken Schlüsseln“ (Schlüsseln, für die kein geeignetes IV existiert, um Differenzialcharakteristika zu erfüllen) an einer umfassenden theoretischen Rechtfertigung für alle Fälle.

2. Methodik

Das Paper führt ein verfeinertes Framework für die Differenzialkryptanalyse basierend auf Probabilistischen Neutralen Bits (PNBs) ein und generalisiert dieses in ein Framework basierend auf Probabilistischen Neutralen Ausdrücken (PNEs). Die Methodik besteht aus drei primären technischen Säulen:

2.1 Synkopierungstechnik für PNBs

Die Autoren führen die „Synkopierung“ ein, um den Widerspruch zwischen dem Finden zahlreicher PNBs und der Aufrechterhaltung einer hohen Korrelation zu lösen.

Konzept: Die Rückwärtsapproximationsfunktion $f$ wird in $f = f_1 \circ f_0$ zerlegt. Die Technik wendet Einschränkungen auf spezifische Nicht-PNB-Bits (eingeschränkte Bits) an, um sicherzustellen, dass der Ausgang des ersten Teils ( $f_0$ ) unabhängig von den PNBs (Synkopierungs-Bits) wird.
Mechanismus: Durch die Nutzung der Eigenschaften der modularen Addition und Subtraktion in ARX-Strukturen leiten die Autoren Bedingungen ab, unter denen die Übertragungsfortpflanzung (Carry Propagation) kontrolliert werden kann. Dies ermöglicht es, den Ausgang spezifischer Segmente allein durch bekannte öffentliche Werte und Nicht-PNBs zu bestimmen, wodurch die Abhängigkeit von unbekannten PNBs effektiv „synkopiert“ wird.
Ergebnis: Diese Technik verstärkt die Korrelation der Rückwärtsapproximation signifikant. Die Autoren stellen zudem ein Werkzeug (Algorithmus 1) bereit, um profitable synkopierte Segmente systematisch zu bestimmen, sowie einen Greedy-Algorithmus (Algorithmus 2), um optimale Mengen an Konditionalen PNBs (CPNBs) zu konstruieren.

2.2 Generalisiertes PNE-Framework

Um die Effizienz weiter zu steigern, generalisiert das Paper das PNB-Konzept zu Probabilistischen Neutralen Ausdrücken (PNEs).

Key-Guessing-Strategie: Anstatt die ursprünglichen Schlüsselbits direkt zu raten, rät der Angriff einen äquivalenten Schlüssel $H(K)$ , wobei $H$ eine auf die Struktur der Chiffre zugeschnittene invertierbare Funktion ist (z. B. lineare Kombinationen unter Verwendung von Rotationen und XOR).
Carry-Preserving-Technik: Eine neuartige Technik für die modulare Addition wird eingeführt. Durch das Auferlegen linearer Bedingungen auf die öffentlichen Daten kann der Übertragsvektor der modularen Addition bestimmt werden, ohne die unbekannten Schlüsselbits (PNBs) zu kennen. Dies vereinfacht die nichtlineare Operation und ermöglicht es der Approximation, die unbekannten Teile des Schlüssels zu ignorieren, während eine hohe Korrelation beibehalten wird.
Integration: Dieses Framework ermöglicht die Entdeckung von mehr neutralen Elementen (PNEs) in Szenarien, in denen traditionelle PNBs selten sind, insbesondere in den späteren Runden oder spezifischen Diagonalen der Zustandsmatrix.

2.3 Verfeinerte Vorwärts-Differenzialanalyse

Das Paper liefert eine tiefere theoretische Analyse der Differenzialgleichungen, die die erste Runde von ChaCha steuern.

Strong Key Analyse: Die Autoren bieten eine umfassende theoretische Erklärung für die Existenz von „starken Schlüsseln“ (Schlüssel, für die kein IV die Differenz erfüllt), deckend über alle acht Fälle der internen Zustandsvariablen, während frühere Arbeiten nur zwei Fälle abdeckten. Sie beweisen, dass etwa 29,6875 % der Schlüssel starke Schlüssel sind.
Effiziente Paar-Generierung: Durch die Analyse der Differenzialgleichungen identifizieren die Autoren spezifische IV-Bits, die geflippt werden können, um die Differenzialbedingungen mit hoher Wahrscheinlichkeit zu erfüllen, was die Datenkomplexität reduziert, die zur Findung korrekter Paare erforderlich ist.

3. Kernbeiträge

Synkopierungstechnik: Eine neue Methode zur Verstärkung der Rückwärtsapproximations-Korrelationen durch Ausnutzung von ARX-Struktur-Eigenschaften, was zu einer effizienteren PNB-Selektion führt.
Generalisiertes PNE-Framework: Eine Erweiterung der PNB-Methode unter Verwendung von äquivalenten Schlüssel-Ausdrücken und einer Carry-Preserving-Technik, was Angriffe mit weniger geratenen Bits und höheren Korrelationen ermöglicht.
Theoretische Vollständigkeit: Eine vollständige theoretische Ableitung der Wahrscheinlichkeiten für starke Schlüssel für alle Differenzialfälle in der ersten Runde, welche die bisherigen partiellen Analysen korrigiert und erweitert.
Neue Angriffsergebnisse:
- 256-Bit ChaCha: Der erste Key-Recovery-Angriff auf 7,5 Runden, der schneller als Brute-Force ( $2^{254,6}$ Zeitkomplexität) ist. Verbesserte Angriffe auf 7 und 7,25 Runden mit reduzierten Komplexitäten.
- ChaCha8 (Related-Key): Der erste Related-Key-Angriff auf 256-Bit ChaCha8 (8 Runden), der eine Zeitkomplexität von $2^{253,3}$ aufweist, wenn ein Paar von Schlüsseln mit einer fixen Differenz verwendet wird.
- 128-Bit ChaCha: Verbesserte Angriffe auf 6,5 Runden und ein neuer Angriff auf 7 Runden (unter Ausschluss der letzten Rotation, bezeichnet als $7\ll$ ).

4. Ergebnisse

Das Paper präsentiert die folgenden spezifischen Angriffskomplexitäten (Zeit/Daten):

256-Bit ChaCha7:
- $2^{210,3}$ Zeit / $2^{103,3}$ Daten (unter Verwendung von 89 CPNBs).
- $2^{216,9}$ Zeit / $2^{68,9}$ Daten (unter Verwendung von 74 CPNBs).
- Verbessert auf $2^{187,2}$ Zeit / $2^{108,2}$ Daten durch Synkopierung auf einem 5-Runden DL-Distinguisher.
256-Bit ChaCha7.25:
- $2^{220,0}$ Zeit / $2^{109}$ Daten.
256-Bit ChaCha7.5:
- $2^{254,6}$ Zeit / $2^{125,3}$ Daten. Dies ist der erste Angriff auf 7,5 Runden, der schneller als Brute-Force ( $2^{256}$ ) ist.
256-Bit ChaCha8 (Related-Key):
- $2^{253,3}$ Zeit / $2^{99,2}$ Daten. Dies bricht den 256-Bit-Sicherheitsanspruch von ChaCha8 im Related-Key-Modell.
128-Bit ChaCha:
- ChaCha6.5: $2^{114,3}$ Zeit / $2^{100,3}$ Daten.
- ChaCha7 $\ll$ : $2^{122,9}$ Zeit / $2^{108,8}$ Daten.

Die experimentelle Verifizierung wurde an 5-Runden- und 6-Runden-ChaCha mit 64 unbekannten Schlüsselbits durchgeführt, was die theoretischen Korrelationsverbesserungen und Erfolgswahrscheinlichkeiten (ca. 70 % für 5 Runden und 62,5–71,4 % für 6 Runden) bestätigte.

5. Bedeutung und Ansprüche

Das Paper beansprucht, einen „kleinen, aber schwierigen Schritt nach vorne“ in der Sicherheitsanalyse von ChaCha zu machen. Seine primäre Bedeutung liegt in:

Durchbrechen der 7,5-Runden-Barriere: Es ist das erste Mal, dass ein Key-Recovery-Angriff auf 7,5 Runden von 256-Bit-ChaCha demonstriert wurde, der effizienter als eine Brute-Force-Suche ist.
Erster Related-Key-Angriff auf ChaCha8: Es zeigt, dass ChaCha8 die 256-Bit-Sicherheit nicht erreicht, wenn ein Paar von Schlüsseln mit einer spezifischen Differenz zulässig ist, was die praktischen Sicherheitsannahmen der 8-Runden-Variante infrage stellt.
Methodische Weiterentwicklung: Die Einführung der Synkopierungstechnik und des Generalisierten PNE-Frameworks (einschließlich Carry-Preserving und neuer Key-Guessing-Strategien) bietet ein mächtigeres Werkzeug zur Analyse von ARX-basierten Chiffren, das potenziell auf andere Designs wie Salsa oder Chaskey anwendbar ist.

Die Autoren stellen explizit klar, dass diese Angriffe nicht die vollen 20 Runden von ChaCha bedrohen, die in realen Anwendungen eingesetzt werden, aber sie verengen die Sicherheitsmarge für rundenreduzierte Varianten erheblich und verdeutlichen theoretische Schwächen im 8-Runden-Related-Key-Setting.