Stringology Based Cryptology

Titolo: Stringology Based Cryptology (SBC)

Autore: Victor Kebande (Università del Colorado Denver e ATLAS Institute, CU Boulder)

---

1. Il Problema

Le primitive crittografiche moderne (come cifrari a flusso, blocchi di cifratura e funzioni hash) generano grandi volumi di dati sequenziali (es. flussi di chiavi o keystreams). La sicurezza di questi sistemi dipende dalla capacità delle sequenze generate di essere indistinguibili da dati casuali uniformi.

Attualmente, la valutazione della sicurezza si basa principalmente su:

• Test statistici di casualità: Suite come NIST STS, TestU01 e PractRand analizzano proprietà globali (distribuzioni di frequenza, entropia, corse, correlazioni).
• Crittoanalisi algebrica.

Limitazione identificata: I metodi tradizionali si concentrano sulle caratteristiche statistiche globali e potrebbero non catturare appieno le relazioni strutturali localizzate che emergono dalle operazioni deterministiche interne degli algoritmi crittografici. Queste strutture nascoste potrebbero non essere rilevate dai test statistici standard, lasciando potenziali lacune nell'analisi della robustezza strutturale.

2. Metodologia: Stringology-Based Cryptology (SBC)

Il paper introduce un nuovo quadro concettuale, la Stringology-Based Cryptology (SBC), che applica tecniche classiche di elaborazione delle stringhe e di rilevamento dei pattern per analizzare le proprietà strutturali degli output crittografici.

Approccio Fondamentale:

• Modellazione: Gli output crittografici (bitstream) sono trattati come sequenze simboliche (stringhe).
• Algoritmi Utilizzati: Vengono impiegati algoritmi di stringology classici, come Knuth-Morris-Pratt (KMP) e Boyer-Moore (BM), noti per la loro efficienza nell'identificare pattern ricorrenti e sottostringhe.
• Pipeline di Analisi (Figura 2):
  1. Input: Sequenza binaria $S \in \{0, 1\}^n$ (es. keystream).
  2. Estrazione delle Caratteristiche: Utilizzo di una finestra scorrevole (sliding window) per estrarre sottostringhe di lunghezza $m$.
  3. Metriche Calcolate:
     • Frequenza delle sottostringhe: $f(P, S)$, che conta quante volte un pattern $P$ appare nella sequenza.
     • Statistiche di ricorrenza: Analisi della distribuzione dei pattern.
     • Densità posizionale: Misura di quanto frequentemente certi pattern appaiono in posizioni specifiche.
     • Entropia dei pattern: Calcolata sulla distribuzione delle probabilità dei pattern osservati.
  4. Output: Un vettore di statistiche strutturali che descrive la "firma" della sequenza.

3. Modello di Minaccia

Il modello considera un avversario probabilistico in tempo polinomiale ($A$) in un contesto di distinzione:

• L'avversario riceve una sequenza $S$ che può provenire da un generatore crittografico $G(K, N)$ o da una distribuzione uniforme casuale.
• L'obiettivo è determinare l'origine della sequenza analizzando le sue proprietà strutturali tramite la pipeline SBC.
• La capacità di distinzione è misurata dal vantaggio dell'avversario: $Adv_A = |Pr[A(S_c) = 1] - Pr[A(S_r) = 1]|$.
• L'obiettivo di sicurezza è che questo vantaggio sia trascurabile, anche sfruttando pattern strutturali.

4. Risultati Sperimentali

L'autore ha condotto esperimenti su due dataset (10.000 sequenze ciascuno di $2^{12}$ bit):

1. Sequenze generate da un generatore di keystream sintetico.
2. Sequenze estratte da una distribuzione uniforme (PRNG crittograficamente sicuro).

Analisi effettuata:

• Pattern di lunghezza $m \in \{8, 16, 32\}$ bit.
• Confronto tra frequenze normalizzate, metriche di deviazione ed entropia.

Risultati Chiave (Tabelle I e II, Figure 3-5):

• Frequenza dei Pattern: Le sequenze crittografiche mostrano frequenze normalizzate più elevate per diverse lunghezze di pattern rispetto alle sequenze casuali (es. 0.61 vs 0.50 per 8 bit; 0.17 vs 0.06 per 32 bit).
• Metrica di Deviazione: È stata calcolata una deviazione significativa ($D$) tra le distribuzioni di frequenza dei due dataset (es. 0.14 per 16 bit), indicando differenze strutturali misurabili.
• Entropia: Le sequenze casuali mostrano un'entropia leggermente più alta, mentre le sequenze crittografiche presentano una lieve riduzione dell'entropia, suggerendo bias strutturali minori introdotti dalle operazioni interne deterministiche (es. addizioni modulari, rotazioni, XOR nei cifrari ARX come ChaCha20).

5. Contributi Chiave

1. Nuovo Framework (SBC): Introduzione di un approccio complementare alla crittoanalisi che utilizza la teoria delle stringhe invece di affidarsi esclusivamente alla statistica globale.
2. Rilevamento di Strutture Locali: Dimostrazione che le trasformazioni deterministiche interne degli algoritmi crittografici lasciano "impronte" strutturali (pattern ricorrenti, distribuzioni di sottostringhe) rilevabili tramite algoritmi di stringology.
3. Metodologia Sperimentale: Validazione empirica che le metriche basate sui pattern (frequenza, deviazione, entropia) possono distinguere tra output crittografici e casuali con una precisione superiore ai soli test statistici aggregati.
4. Ponte Disciplinare: Collegamento tra l'informatica teorica (elaborazione delle stringhe) e la crittologia applicata.

6. Significato e Conclusioni

• Non è una vulnerabilità pratica: L'autore sottolinea che le differenze strutturali rilevate non implicano debolezze crittografiche pratiche o vulnerabilità sfruttabili. Gli algoritmi moderni sono progettati per essere computazionalmente indistinguibili dal caso.
• Valore Analitico: L'SBC offre uno strumento analitico potente per comprendere il comportamento interno delle primitive crittografiche.
• Complementarità: Questo approccio non sostituisce i test statistici (NIST, ecc.), ma li integra, offrendo una visione più ricca delle proprietà strutturali locali.
• Prospettive Future: Il paper suggerisce l'uso di strutture dati avanzate (alberi dei suffissi, array dei suffissi) e l'integrazione con modelli di Machine Learning per scoprire correlazioni strutturali complesse in dataset su larga scala.

In sintesi, il paper propone un cambio di paradigma nell'analisi crittografica, trattando i dati cifrati come testi da analizzare linguisticamente/strutturalmente, fornendo nuovi insight sulla robustezza interna degli algoritmi di generazione sequenziale.