Stringology Based Cryptology

Titel: Stringology Based Cryptology (SBC)

Auteur: Victor Kebande (University of Colorado Denver & ATLAS Institute, CU Boulder)

---

1. Probleemstelling

Moderne cryptografische primitieven (zoals stream ciphers, hash-functies en PRNG's) genereren grote hoeveelheden sequentiële data (bijv. keystreams en ciphertext-blokken). De fundamentele veiligheidseis is dat deze sequenties ononderscheidbaar zijn van uniform willekeurige data.

Traditionele evaluatiemethoden vertrouwen bijna uitsluitend op statistische randomiteitstests (zoals de NIST STS, TestU01 en PractRand). Hoewel deze tools waardevolle inzichten geven in globale statistische eigenschappen (zoals frequentieverdelingen, runs en entropie), hebben ze beperkingen:

• Ze focussen op globale statistieken en missen vaak gelokaliseerde structurele relaties.
• Ze detecteren mogelijk geen subtiele structurele patronen die ontstaan door deterministische interne transformaties binnen cryptografische algoritmen (bijv. ARX-operaties: Add-Rotate-XOR).
• Er is een behoefte aan aanvullende methoden om de structurele integriteit van cryptografische output te analyseren.

2. Methodologie: Stringology-Based Cryptology (SBC)

Het paper introduceert het concept Stringology-Based Cryptology (SBC), een raamwerk dat klassieke stringverwerkingstechnieken en patroonmatching-algoritmen toepast op cryptografische output.

Kernprincipes:

• Modellering: Cryptografische output wordt niet gezien als een reeks getallen, maar als een symbolische string (een binaire reeks $S \in \{0, 1\}^n$).
• Analyse: In plaats van alleen globale statistieken te meten, worden lokale structurele patronen geanalyseerd.
• Algoritmen: Er wordt gebruikgemaakt van klassieke stringology-algoritmen zoals Knuth–Morris–Pratt (KMP) en Boyer–Moore (BM) om terugkerende patronen, substring-frequenties en structurele correlaties te detecteren.

Het SBC-raamwerk (Pipeline):

1. Input: Een binaire sequentie $S$ (bijv. een keystream).
2. Functie-extractie ($\Phi$): Een mapping die de binaire sequentie omzet in een vector van structurele statistieken.
   • Er wordt een "sliding window" van lengte $m$ over de sequentie bewogen.
   • Voor een patroon $P$ van lengte $m$ wordt de frequentie $f(P, S)$ berekend: het aantal keren dat $P$ voorkomt in $S$.
3. Statistieken: Er worden diverse metrics berekend:
   • Genormaliseerde patroonfrequenties: Hoe vaak komen specifieke substrings voor?
   • Afwijkingsscores (Deviation): Het absolute verschil in frequentieverdeling tussen cryptografische output en willekeurige output.
   • Patroonentropie: Een maat voor de onvoorspelbaarheid van de patronen binnen de string.

3. Belangrijkste Bijdragen

• Conceptuele Innovatie: Het introduceren van SBC als een complementaire benadering voor cryptanalyse, die de kloof overbrugt tussen stringverwerking en cryptografie.
• Methodologisch Kader: Een gestructureerde pipeline voor het extraheren van structurele features uit cryptografische sequenties via substring-analyse.
• Experimentele Validatie: Een empirisch onderzoek dat aantoont dat cryptografisch gegenereerde sequenties meetbare structurele verschillen vertonen ten opzichte van uniform willekeurige sequenties, zelfs wanneer ze statistisch "goed" lijken.
• Threat Model: Een definitiescenario waarin een adversary probeert een cryptografische generator te onderscheiden van een willekeurige bron puur op basis van structurele patroonstatistieken.

4. Experimentele Resultaten

De auteur voerde experimenten uit met twee datasets:

1. Cipher-generatie: Sequences gegenereerd door een generieke keystream-generator.
2. Random: Sequences gegenereerd door een cryptografisch veilige PRNG (uniforme verdeling).

• Dataset: 20.000 sequenties van $2^{12}$ bits (10.000 per type).
• Patroonlengtes: Geanalyseerd voor $m \in \{8, 16, 32\}$ bits.

Kernbevindingen:

• Frequentieverschillen (Tabel I): Cipher-gegenereerde sequenties vertoonden hogere genormaliseerde frequenties voor bepaalde patronen vergeleken met willekeurige data (bijv. bij 8 bits: 0.61 vs 0.50; bij 32 bits: 0.17 vs 0.06). Dit suggereert structurele regulariteiten door deterministische transformaties.
• Afwijkingsscore (Tabel II & Figuur 3): Er werden significante afwijkingsscores gemeten tussen de twee datasets, wat aantoont dat de verdeling van patronen systematisch verschilt.
• Entropie (Figuur 5): Willekeurige sequenties hadden een iets hogere entropie dan cipher-sequenties. De iets lagere entropie bij cipher-sequenties duidt op kleine structurele bias veroorzaakt door de interne werking van de generator.

5. Betekenis en Conclusie

• Geen directe kwetsbaarheid: De auteurs benadrukken dat deze structurele signalen niet betekenen dat de onderzochte algoritmen praktisch kwetsbaar zijn. Moderne cryptografie is ontworpen om computationeel ononderscheidbaar te zijn. De gevonden verschillen zijn subtiel en inherent aan deterministische processen.
• Complementair Inzicht: SBC biedt een waardevol aanvullend perspectief op bestaande statistische tests. Waar traditionele tests kijken naar "hoe willekeurig" een reeks is, kijkt SBC naar "welke structurele patronen" erin zitten.
• Toekomstperspectief: Het paper opent de weg voor verder onderzoek, waaronder:
  • Toepassing van geavanceerde stringstructuren (suffixbomen, suffixarrays).
  • Integratie van Machine Learning-modellen met stringology-features voor automatische detectie van structurele correlaties.
  • Uitbreiding naar bredere klassen van cryptografische primitieven.

Samenvattend: Dit paper pleit voor een verschuiving in cryptanalyse door cryptografische output te behandelen als tekstuele data. Door patronen te analyseren die door traditionele statistische tests worden gemist, biedt SBC een dieper inzicht in de interne structuur en robustheid van cryptografische systemen.