💻 computer science

Stringology-Based Cryptanalysis for EChaCha20 Stream Cipher

Dit artikel presenteert een cryptanalyse van de EChaCha20-streamcipher met behulp van stringologie-algoritmen (KMP en BM) en concludeert dat de cipher ondanks enkele kleine onregelmatigheden in het 8-bit-domein sterke pseudorandomiteit en snelle diffusie behoudt.

Oorspronkelijke auteurs: Victor Kebande

Gepubliceerd 2026-04-13

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Victor Kebande

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://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

🕵️‍♂️ De Digitale Detective: Een nieuwe manier om geheime codes te testen

Stel je voor dat EChaCha20 een zeer slimme slotmaker is. Deze machine neemt een geheim sleutel (een wachtwoord) en een startnummer, en draait daar een lange, onleesbare reeks cijfers uit (de "stream") die gebruikt wordt om berichten te versleutelen. Hoe beter de machine werkt, hoe onmogelijker het is om te raden wat er binnenin gebeurt.

Deze machine is een verbeterde versie van een beroemd slot: ChaCha20. De makers hebben de machine groter gemaakt (van een 4x4 raamwerk naar een 6x6 raamwerk) en de wielen die de cijfers draaien, iets anders ingesteld. Ze zeggen: "Onze machine is nu nog veiliger!"

Maar hoe weten we dat zeker? Meestal kijken onderzoekers naar de uitkomst met statistische tests. Dat is alsof je naar een bak met gekleurd zand kijkt en zegt: "Het ziet er allemaal gelijkmatig uit." Maar wat als er in het zand een heel klein, onzichtbaar patroon zit dat je met het blote oog niet ziet?

Victor Kebande, de auteur van dit paper, heeft een nieuwe aanpak bedacht. Hij gebruikt geen gewone statistiek, maar Stringology (de wetenschap van het zoeken naar patronen in teksten).

🧶 De Analogie: Het zoeken naar een speld in een hooiberg

Stel je voor dat je een enorme hooiberg hebt (de versleutelde data) en je zoekt naar een specifieke speld (een patroon dat zou kunnen wijzen op een zwakke plek).

De oude manier (Statistiek): Je neemt een steekproef van het hooi en meet hoeveel hooistengels er zijn. Als het gemiddeld klopt, denk je dat er geen speld is. Maar je mist misschien de speld die net onder een laagje hooi ligt.
De nieuwe manier (Stringology/KMP & BM): Victor gebruikt slimme zoekrobots (de KMP en Boyer-Moore algoritmen). Deze robots zijn getraind om niet elk stukje hooi één voor één te bekijken. Ze weten precies waar ze niet hoeven te kijken. Ze kunnen grote sprongen maken en weten: "Hier zit geen speld, ik spring direct naar daar!"

Dit maakt het zoeken veel sneller en slimmer. Ze kunnen zoeken naar patronen op het niveau van de machine zelf (woorden van 32 bits), in plaats van alleen op het niveau van losse bits (0 en 1).

🔍 Wat hebben ze gevonden?

Victor heeft de machine EChaCha20 onderworpen aan een extreme test met 1 miljoen verschillende versleutelde berichten. Hier zijn de resultaten, vertaald naar alledaagse taal:

De grote patronen (32-bit en 16-bit):
De machine werkt perfect. De robots vonden geen verdachte patronen. Het is alsof je in een rivier kijkt en geen enkele steen ziet die in een rechte lijn ligt. De data is volledig willekeurig. De machine doet precies wat hij moet doen: alles door elkaar schudden.
- Conclusie: Op het niveau waar computers normaal gesproken werken, is EChaCha20 zeer veilig.
De kleine patronen (8-bit / bytes):
Hier vonden ze een heel kleinigheidje. Als je heel dicht bij de start van de machine kijkt (met een vast wachtwoord), zie je een heel klein afwijking in de kleur van het zand. Het is alsof de eerste paar druppels uit een kraan net iets anders van kleur zijn dan de rest.
- Is dit gevaarlijk? Nee. Het verdwijnt direct als je een nieuw wachtwoord gebruikt. Het is een klein "start-effect", geen gebrek aan de machine zelf.
De "Avalanche"-test (Het sneeuwlawine-effect):
Een goede slotmachine moet zo werken dat als je één klein steentje (een bit) verandert, er direct een lawine loskomt en alles verandert.
Victor zag dat bij EChaCha20 de lawine nog sneller loskomt dan bij de oude versie. Na slechts twee rondjes draaien is alles volledig gemengd. Dit is een groot pluspunt!

🚀 Waarom is dit belangrijk?

Nieuwe gereedschapskist: Tot nu toe keken we naar versleutelde data met "statistische brillen". Victor laat zien dat we ook "zoek-robots" kunnen gebruiken. Dit is als het verschil tussen kijken of een muur recht is (statistiek) en er met een meetlat langs lopen om de kleinste kieren te vinden (stringology).
Bevestiging: De nieuwe, grotere versie van ChaCha20 (EChaCha20) is inderdaad sterker en sneller in het door elkaar schudden van data dan de oude versie.
Veiligheid: Er is geen manier gevonden om de machine te hacken. De kleine onregelmatigheden die gevonden werden, zijn te klein om iets mee te doen en verdwijnen in de echte wereld.

🏁 Samenvatting

Stel je voor dat je een nieuwe, super-veilige kluis bouwt. Iedereen zegt: "Kijk, hij is groot en zwaar!"
Deze onderzoeker zegt: "Laat me eens kijken of er geen klein kiertje in zit."
Hij gebruikt een slimme scanner die sneller is dan ooit tevoren. Hij vindt een heel klein kiertje aan de voorkant (alleen als je de kluis niet beweegt), maar zodra je hem gebruikt, is het kiertje weg. De rest van de kluis is ondoordringbaar.

De boodschap: EChaCha20 is een sterke, veilige versleuteling, en deze nieuwe "zoek-robot" methode is een uitstekend hulpmiddel om in de toekomst nog betere sloten te bouwen.

Titel: Stringologie-gebaseerde cryptanalyse voor de EChaCha20 stream cipher

Auteur: Victor Kebande (University of Colorado Denver)
Datum: 13 april 2026

1. Het Probleem

Stream ciphers zoals ChaCha20 zijn een de facto standaard in beveiligingskritische toepassingen (bijv. TLS 1.3, IoT). Echter, traditionele statistische tests (zoals NIST SP 800-22 of TestU01) evalueren vaak alleen globale bit-niveau willekeurigheid. Deze methoden kunnen gefaald hebben om lokaliseerde zwaktes te detecteren die specifiek voortkomen uit de interne structuur van ARX-cijfers (Add-Rotate-XOR).

EChaCha20 is een variant van ChaCha20 met twee belangrijke wijzigingen:

Een uitgebreide 6×6 state matrix (1152 bits) in plaats van de originele 4×4 matrix (512 bits).
Een aangepaste Quarter-Round Function (QR-F) met extra rotatieconstanten (4-bit en 2-bit) om de diffusie te verbeteren.

Er was tot nu toe geen systematisch onderzoek gedaan naar of deze wijzigingen subtiele patronen in de keystream, rotatie-bias of partiële botsingen introduceren die als statistische onderscheiders kunnen dienen. Het doel van dit onderzoek is om te bepalen of deze structurele aanpassingen de beveiligingsmarge onbedoeld verkleinen.

2. Methodologie

De auteur introduceert Stringology-Based Cryptanalysis (SBC), een aanpak die geavanceerde string matching-algoritmen toepast op cryptanalyse. In plaats van alleen bit-tellingen, analyseert deze methode de keystream op woord-niveau (32-bit woorden) die overeenkomen met de interne ARX-operaties.

Kerncomponenten van de methodologie:

Algoritmen: Aanpassing van de Knuth-Morris-Pratt (KMP) en Boyer-Moore (BM) algoritmen. Deze zijn geoptimaliseerd voor 32-bit woordniveaus en incorporeren XOR-operaties direct in de matching-logica.
Hybride Benadering: Een hybride KMP-BM algoritme werd ontwikkeld dat de deterministische backtracking van KMP combineert met de heuristieken voor het overslaan van tekens (skip heuristics) van BM. Dit resulteert in een gemiddelde complexiteit van $O(n/m)$ , wat zeer efficiënt is voor grote datasets.
Experimenteel Opzet:
- Dataset: Generatie van 1 miljoen keystream-blokken (elk 1152 bits).
- Scenario's: Analyse onder zowel Known Plaintext Environment (KPE) als Chosen Plaintext Environment (CPE).
- Patroonanalyse: Detectie van m-gram herhalingen op bit-niveaus van 8, 16 en 32 bits.
- Differential Cryptanalyse: Injectie van rotatieverschillen ( $\Delta$ ) in de QR-F om de diffusie en botsingskansen te meten.

3. Belangrijkste Bijdragen

Nieuwe Cryptanalyse Framework: De eerste toepassing van stringologie-algoritmen (KMP/BM) specifiek aangepast voor ARX-stream ciphers met een uitgebreide state matrix.
Efficiëntie: Het hybride algoritme toont een 18,3% hogere precisie en een 24,4% hogere nauwkeurigheid vergeleken met standaard KMP en BM, met een verwerkingssnelheid van 3,6 GB/s.
Structuur-georiënteerde Analyse: De methologie detecteert anomalieën die op woord-niveau (32-bit) aligned zijn met de cipher-interne operaties, wat vaak onzichtbaar blijft voor globale statistische tests.
Evaluatie van EChaCha20: Een grondige validatie van de beveiligingsclaims van EChaCha20, met name de impact van de 6×6 matrix en de nieuwe rotatieconstanten.

4. Resultaten

De experimentele resultaten tonen een gemengd maar overwegend positief beeld van de beveiliging van EChaCha20:

Pseudorandomheid:
- 32-bit en 16-bit niveaus: De cipher vertoont sterke pseudorandomheid. Er werden geen statistisch significante herhalingen of patronen gevonden op deze niveaus. De entropie is perfect uniform.
- 8-bit niveau: Er werden kleine afwijkingen waargenomen bij 8-bit patronen, voornamelijk in datasets met een vaste sleutel (fixed-key) aan het begin van de keystream. Echter, deze afwijkingen verdwenen volledig bij variabele sleutels en nonces, wat aangeeft dat het een structureel, niet-exploiteerbaar artefact is van de initiële toestand en geen fundamenteel ontwerpdefect.
Diffusie en Avalanche-effect:
- De cipher bereikt volledige state-diffusie binnen 3 rondes van de QR-F.
- Na 2 rondes is het avalanche-effect bijna ideaal (bit-flip kans convergeert naar 0,5).
- Rotatie-differentieel aanval: Er werden geen statistisch significante rotatie-botsingen waargenomen binnen de geëvalueerde grenzen. De kans op botsingen daalt exponentieel en ligt onder de theoretische bovengrens ( $2^{-32}$ ) na slechts 2 rondes.
Vergelijking met ChaCha20: EChaCha20 toont een snellere diffusie dan de originele ChaCha20 (volledige diffusie in 3 rondes versus 3-4 rondes), dankzij de uitgebreide matrix en extra rotatieconstanten.

5. Betekenis en Conclusie

Dit onderzoek bevestigt dat EChaCha20 een robuuste verbetering is ten opzichte van de standaard ChaCha20, met name wat betreft weerstand tegen differentieel- en rotatie-aanvallen.

Beveiligingsmarge: De wijzigingen (6×6 matrix, extra rotaties) hebben de beveiligingsmarge niet verkleind; integendeel, ze hebben de diffusie versneld.
Methodologische Innovatie: De paper demonstreert dat stringologie een waardevol complementair hulpmiddel is voor traditionele cryptanalyse. Het biedt een fijnkorrelige, structuur-gealigneerde manier om zwaktes te vinden die door aggregatie-statistiek worden gemaskeerd.
Toekomstperspectief: Hoewel er geen directe sleutelherwinning (key-recovery) is gevonden, biedt deze methode een nieuwe weg voor het evalueren van ARX-cijfers. De auteur stelt voor om deze technieken uit te breiden naar andere ARX-varianten en post-kwantum scenario's.

Conclusie: EChaCha20 behoudt sterke pseudorandomheid op kritieke woordniveaus (16/32-bit) en vertoont een snelle, effectieve diffusie, waardoor het geschikt is voor hoge-beveiligingstoepassingen, mits de kleine 8-bit bias in vaste-sleutel scenario's als een niet-exploiteerbaar artefact wordt beschouwd.