💻 computer science

A Generalized PNE Framework: Taking ChaCha Further in Syncopated Rhythm

Dit artikel introduceert een gegeneraliseerd Probabilistic Neutral Expressions (PNE) raamwerk dat nieuwe technieken zoals syncopatie en carry-preserving incorporeert om key-recovery aanvallen op ronde-gereduceerde ChaCha aanzienlijk te verbeteren, waarbij de eerste related-key aanval op ChaCha8 wordt gerealiseerd en 7,5 ronden van 256-bits ChaCha worden gebroken.

Oorspronkelijke auteurs: Shichang Wang, Meicheng Liu, Shiqi Hou, Chengan Hou, Dongdai Lin

Gepubliceerd 2026-08-31

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Shichang Wang, Meicheng Liu, Shiqi Hou, Chengan Hou, Dongdai Lin

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

In het uitgestrekte digitale landschap waar onze privéberichten, financiële transacties en beveiligde verbindingen doorheen reizen, bestaat een stille bewaker die bekend staat als een stroomcijfer (stream cipher). Denk eraan als een hogesnelheidsmachine die een lange, willekeurig ogende stroom van getallen genereert om gegevens te versleutelen, wat ervoor zorgt dat alleen iemand met de juiste geheime sleutel de oorspronkelijke boodschap kan ontcijferen en lezen. Een van de meest vertrouwde machines van dit soort heet ChaCha. Het is de motor achter de beveiliging van veel alledaagse internetprotocollen, die alles beschermt van je webbrowsing tot je versleutelde e-mails. Omdat het zo wijdverbreid wordt gebruikt, wordt de kracht ervan constant getest door cryptanalisten—specialisten die proberen deze codes te breken, niet om geheimen te stelen, maar om hun grenzen te begrijpen en te garanderen dat ze veilig blijven. De kernuitdaging bij het breken van een cijfer zoals ChaCha is dat het is gebouwd op een structuur die eenvoudige operaties zoals het optellen van getallen, het roteren van bits en het omdraaien van schakelaars combineert op een manier die snel ongelooflijk complex wordt. Om een zwakte te vinden, moeten onderzoekers traceren hoe een kleine verandering in de invoer door deze operaties rimpelt om te zien of het een voorspelbaar patroon in de uitvoer creëert.

Een team van onderzoekers heeft nu een belangrijke stap voorwaarts gezet in het begrijpen van de grenzen van ChaCha door een nieuwe methode te ontwikkelen om te analyseren hoe deze rimpelingen zich gedragen. Ze richtten zich op een specifieke techniek genaamd differentiële cryptanalyse, waarbij twee licht verschillende invoergegevens in het cijfer worden gevoerd en wordt geobserveerd hoe de verschillen evolueren. Bij eerdere pogingen om ChaCha te breken, moesten onderzoekers een enorm aantal mogelijke sleutels raden om te zien welke overeenkwam met de geobserveerde patronen, een proces dat vaak te traag was om praktisch bruikbaar te zijn. De nieuwe studie introduceert een verfijnde aanpak die gebruikmaakt van een concept genaamd "syncopatie". In de context van dit cijfer stelt deze techniek de onderzoekers in staat om specifieke delen van de geheime sleutel te identificeren die onder bepaalde omstandigheden bijna geen invloed hebben op de uiteindelijke versleutelde uitvoer. Door deze niet-invloedrijke delen te isoleren, kunnen de onderzoekers ze tijdens de initiële stadia van de aanval effectief negeren, wat het aantal mogelijkheden dat ze moeten testen drastisch vermindert. Dit is vergelijkbaar met het oplossen van een complexe puzzel door eerst de stukjes apart te leggen die duidelijk niet bij het centrale beeld horen, zodat je je energie kunt richten op de cruciale stukjes die er echt toe doen.

Met behulp van deze syncopatietechniek, gecombineerd met een nieuwe strategie voor het raden van de resterende sleutelbits, waren de onderzoekers in staat om versies van ChaCha te breken die voorheen als veilig tegen dergelijke aanvallen werden beschouwd. Specifiek demonstreerden ze een succesvolle aanval op een versie van het cijfer met 7,5 rondes van verwerking. Hoewel de volledige, standaardversie van ChaCha 20 rondes gebruikt, is het breken van 7,5 rondes een opmerkelijke prestatie omdat dit de eerste keer is dat een sleutelherstelaanval (key-recovery attack) is uitgevoerd op dit specifieke aantal rondes die sneller is dan simpelweg elke mogelijke sleutel één voor één raden. De onderzoekers toonden ook aan dat hun methoden aanvallen op 7-ronde versies van het cijfer kunnen verbeteren, waardoor ze aanzienlijk efficiënter zijn dan eerdere pogingen. Bovendien pasten ze hun technieken toe op een gerelateerde versie van het cijfer genaamd ChaCha8, die slechts 8 rondes gebruikt. In een scenario waarin een aanvaller wordt toegestaan om twee sleutels te gebruiken die zeer vergelijkbaar met elkaar zijn, vonden ze een manier om ChaCha8 te breken, wat suggereert dat deze specifieke variant mogelijk niet het volledige niveau van beveiliging biedt dat de ontwerpers beoogden als aan die voorwaarde wordt voldaan.

De studie onderzocht ook een kortere versie van het cijfer die een 128-bit sleutel gebruikt in plaats van de standaard 256-bit sleutel. Hierin slaagden de onderzoekers erin om een 7-ronde versie van dit kortere cijfer te breken, mits de allerlaatste stap van het versleutelingsproces werd verwijderd. Deze resultaten betekenen niet dat de volledige, 20-ronde ChaCha die in real-world toepassingen zoals je webbrowser wordt gebruikt, momenteel gebroken is. De volledige versie blijft veilig. Deze bevindingen zijn echter cruciaal omdat ze de grenzen verleggen van wat bekend is over de interne mechanica van het cijfer. Door te bewijzen dat het cijfer onder specifieke, gecontroleerde omstandigheden verzwakt kan worden, geven de onderzoekers waardevolle feedback aan de cryptografische gemeenschap. Dit helpt ervoor dat de algoritmen die ons digitale leven beschermen robuust zijn en dat eventuele kwetsbaarheden worden geïdentificeerd en aangepakt voordat ze in de echte wereld kunnen worden misbruikt. Het werk vertegenwoordigt een kleine maar moeilijke stap voorwaarts in de voortdurende inspanning om de wiskundige fundamenten van onze digitale privacy te begrijpen en te beveiligen.

Technisch Overzicht: Een Gegeneraliseerd PNE-raamwerk: ChaCha verder brengen met Syncopatie in Ritme

1. Probleemstelling

De stroomcijfer ChaCha, in het bijzonder de 256-bits variant, wordt breed ingezet in real-world protocollen zoals TLS, SSH en QUIC. Ondanks het uitgebreide gebruik is de beveiligingsmarge van de met een beperkt aantal ronden uitgevoerde ChaCha een onderwerp geweest van intensief cryptanalytisch onderzoek. Voorafgaand aan dit werk waren de meest effectieve sleutelherstelaanvallen op 2-rotonde 256-bits ChaCha beperkt tot 7 ronden (met tijdscomplexiteiten die vaak boven $2^{220}$ uitkomen) of 7,25 ronden, en is er geen aanval sneller dan brute force ( $2^{256}$ ) succesvol gedemonstreerd voor 7,5 ronden in de single-key setting. Bov�els stond de veiligheid van de 8-ronde variant (ChaCha8) in de related-key setting grotendeels onverkend met efficiënte aanvallen.

De kernuitdaging in de differentiële cryptanalyse van ChaCha ligt in de afruil tussen het aantal geïdentificeerde Probabilistic Neutral Bits (PNBs) en de correlatie van de backward-benadering. Traditionele methoden hebben vaak moeite om een grote verzameling PNB's te vinden die tegelijkertijd een hoge correlatie behouden, wat de efficiëntie van meet-in-the-middle aanvallen beperkt. Daarnaast ontbrak het eerdere analyses van "sterke sleutels" (sleutels waarvoor geen geschikte IV bestaat die aan differentiële kenmerken voldoet) aan een uitgebreide theoretische rechtvaardiging voor alle gevallen.

2. Methodologie

Het artikel introduceert een verfijnd raamwerk voor differentiële cryptanalyse gebaseerd op Probabilistic Neutral Bits (PNBs) en generaliseert dit naar een raamwerk gebaseerd op Probabilistic Neutral Expressions (PNEs). De methodologie bestaat uit drie primaire technische pijlers:

2.1 Syncopatie-techniek voor PNB's

De auteurs introduceren "syncopatie" om de tegenstrijdigheid aan te pakken tussen het vinden van talrijke PNB's en het behouden van een hoge correlatie.

Concept: De backward-benaderingsfunctie $f$ wordt gedecomposeerd als $f = f_1 \circ f_0$ . De techniek past restricties toe op specifieke niet-PNB bits (restrictie-bits) om ervoor te zorgen dat de output van het eerste deel ( $f_0$ ) onafhankelijk wordt van de PNB's (syncopatie-bits).
Mechanisme: Door gebruik te maken van de eigenschappen van modulaire optelling en aftrekking in ARX-structuren, leiden de auteurs voorwaarden af waaronder de carry-propagatie gecontroleerd kan worden. Dit maakt het mogelijk om de output van specifieke segmenten uitsluitend te laten bepalen door bekende publieke waarden en niet-PNB's, waardoor de afhankelijkheid van onbekende PNB's effectief wordt "gesyncopeerd".
Resultaat: Deze techniek vergroot de correlatie van de backward-benadering aanzienlijk. De auteurs bieden ook een hulpmiddel (Algoritme 1) om systematisch winstgevende gesyncopeerde segmenten te bepalen en een gulzig algoritme (Algoritme 2) om optimale verzamelingen van Conditional PNB's (CPNB's) te construeren.

2.2 Gegeneraliseerd PNE-raamwerk

Om de efficiëntie verder te verbeteren, generaliseert het artikel het PNB-concept naar Probabilistic Neutral Expressions (PNEs).

Sleutelraad-strategie: In plaats van direct de originele sleutelbits te raden, raadt de aanval een equivalente sleutel $H(K)$ waarbij $H$ een inverseerbare functie is die is afgestemd op de structuur van de cijfer (bijv. lineaire combinaties met rotaties en XOR's).
Carry-preserverende techniek: Een nieuwe techniek wordt geïntroduceerd voor modulaire optelling. Door lineaire voorwaarden op de publieke data op te leggen, kan de carry-vector van de modulaire optelling worden bepaald zonder de onbekende sleutelbits (PNB's) te kennen. Dit vereenvoudigt de niet-lineaire operatie, waardoor de benadering de onbekende delen van de sleutel kan negeren terwijl een hoge correlatie behouden blijft.
Integratie: Dit raamwerk maakt het mogelijk om meer neutrale elementen (PNE's) te ontdekken in scenario's waar traditionele PNB's schaars zijn, met name in de latere ronden of specifieke diagonalen van de state-matrix.

2.3 Verfijnde Forward Differentiële Analyse

Het artikel biedt een diepere theoretische analyse van de differentiële vergelijkingen die de eerste ronde van ChaCha beheersen.

Sterke Sleutel Analyse: De auteurs bieden een uitgebreide theoretische verklaring voor het bestaan van "sterke sleutels" (sleutels waarbij geen IV voldoet aan de differentiaal), over alle acht gevallen van de interne state-variabelen, terwijl eerder werk slechts twee gevallen dekte. Ze bewijzen dat ongeveer 29,6875% van de sleutels sterke sleutels zijn.
Efficiënte Paargeneratie: Door de differentiële vergelijkingen te analyseren, identificeren de auteurs specifieke IV-bits die kunnen worden omgeklapt om aan differentiële beperkingen te voldoen met een hoge waarschijnlijkheid, wat de datacomplexiteit vermindert die nodig is om juiste paren te vinden.

3. Belangrijkste Bijdragen

Syncopatie-techniek: Een nieuwe methode om de correlaties van de backward-benadering te versterken door gebruik te maken van ARX-structurele eigenschappen, wat leidt tot een efficiëntere PNB-selectie.
Gegeneraliseerd PNE-raamwerk: Een uitbreiding van de PNB-methode met behulp van equivalente sleutelexpressies en een carry-preserverende techniek, wat aanvallen mogelijk maakt met minder geraden bits en hogere correlaties.
Theoretische Volledigheid: Een volledige theoretische afleiding van de kansen op sterke sleutels voor alle differentiële gevallen in de eerste ronde, waarmee eerdere gedeeltelijke analyses worden gecorrigeerd en uitgebreid.
Nieuwe Aanvalsresultaten:
- 256-bit ChaCha: De eerste sleutelherstelaanval op 7,5 ronden die sneller is dan brute force ( $2^{254,6}$ tijdscomplexiteit). Verbeterde aanvallen op 7 en 7,25 ronden met verminderde complexiteiten.
- ChaCha8 (Related-Key): De eerste related-key aanval op 256-bit ChaCha8 (8 ronden), die een tijdscomplexiteit van $2^{253,3}$ vertoont wanneer een paar sleutels met een vast verschil wordt gebruikt.
- 128-bit ChaCha: Verbeterde aanvallen op 6,5 ronden en een nieuwe aanval op 7 ronden (exclusief de laatste rotatie, aangeduid als $7\ll$ ).

4. Resultaten

Het artikel presenteert de volgende specifieke aanvalscomplexiteiten (Tijd/Data):

256-bit ChaCha7:
- $2^{210,3}$ tijd / $2^{103,3}$ data (gebruikmakend van 89 CPNB's).
- $2^{216,9}$ tijd / $2^{68,9}$ data (gebruikmakend van 74 CPNB's).
- Verbeterd naar $2^{187,2}$ tijd / $2^{108,2}$ data met syncopatie op een 5-ronde DL distinguisher.
256-bit ChaCha7.25:
- $2^{220,0}$ tijd / $2^{109}$ data.
256-bit ChaCha7.5:
- $2^{254,6}$ tijd / $2^{125,3}$ data. Dit is de eerste aanval op 7,5 ronden die sneller is dan brute force ( $2^{256}$ ).
256-bit ChaCha8 (Related-Key):
- $2^{253,3}$ tijd / $2^{99,2}$ data. Dit doorbreekt de 256-bit beveiligingsclaim van ChaCha8 onder het related-key model.
128-bit ChaCha:
- ChaCha6.5: $2^{114,3}$ tijd / $2^{100,3}$ data.
- ChaCha7 $\ll$ : $2^{122,9}$ tijd / $2^{108,8}$ data.

Experimentele verificatie werd uitgevoerd op 5- en 6-ronde ChaCha met 64 onbekende sleutelbits, wat de theoretische verbeteringen in correlatie en succespercentages bevestigde (ongeveer 70% voor 5-ronde en 62,5-71,4% voor 6-ronde).

5. Betekenis en Claims

Het artikel beweert een "kleine maar moeilijke stap voorwaarts" te zetten in de beveiligingsanalyse van ChaCha. De primaire betekenis ligt in:

Het doorbreken van de 7,5-ronde barrière: Dit is de eerste keer dat een sleutelherstelaanval op 7,5 ronden van 256-bit ChaCha is gedemonstreerd die efficiënter is dan een brute-force zoekopdracht.
Eerste Related-Key Aanval op ChaCha8: Het toont aan dat ChaCha8 niet voldoet aan de 256-bit beveiliging als een paar sleutels met een specifiek verschil is toegestaan, wat de praktische beveiligingsaannames van de 8-ronde variant uitdaagt.
Methodologische Vooruitgang: De introductie van de Syncopatie-techniek en het Gegeneraliseerde PNE-raamwerk (inclusief carry-preserverende en nieuwe sleutelraad-strategieën) biedt een krachtiger instrumentarium voor het analyseren van ARX-gebaseerde cijfers, potentieel toepasbaar op andere ontwerpen zoals Salsa of Chaskey.

De auteurs stellen expliciet dat deze aanvallen de volledige 20-ronde ChaCha die in de praktijk wordt gebruikt, niet bedreigen, maar ze verkleinen wel de beveiligingsmarge voor varianten met een beperkt aantal ronden en benadrukken theoretische zwakheden in de 8-ronde related-key setting.