Structural Analysis of Cryptographic Sequences using Stringology-Based Fingerprinting

Riepilogo Tecnico: Analisi Strutturale di Sequenze Crittografiche mediante Impronte Digitali Basate sulla Stringologia

Enunciazione del Problema
Le primitive crittografiche, inclusi i cifrari a flusso, i Generatori di Numeri Pseudocasuali (PRNG) e le modalità dei cifrari a blocco, sono progettate per produrre sequenze statisticamente indistinguibili dai dati casuali. La valutazione tradizionale si basa pesantemente su suite di test di casualità statistica (ad esempio, NIST STS, TestU01) per verificare proprietà globali come distribuzioni di frequenza, lunghezze delle corse ed entropia. Tuttavia, questi test sono progettati principalmente per rilevare deviazioni significative dalla casualità ideale piuttosto che per caratterizzare il comportamento strutturale specifico dei generatori deterministici sottostanti. Poiché gli algoritmi crittografici si basano su operazioni interne strutturate (addizione modulare, rotazioni di bit, sostituzioni, XOR), possono introdurre caratteristiche strutturali sottili che i metodi puramente statistici non riescono a rilevare. È necessario un framework che interpreti queste sequenze come stringhe simboliche per analizzarne le strutture di pattern interne.

Metodologia: Il Framework di Impronte Digitali Basate sulla Stringologia (SBF)
Il documento propone un framework di Impronte Digitali Basate sulla Stringologia (SBF) che tratta gli output crittografici come stringhe simboliche per estrarre statistiche di pattern strutturali. Il framework opera attraverso il seguente flusso di lavoro:

1. Trasformazione della Sequenza: Gli output crittografici (keystream, testi cifrati) vengono trasformati in stringhe simboliche binarie ($S \in \{0, 1\}^n$).
2. Estrazione dei Pattern: Utilizzando l'analisi a finestra scorrevole, il framework calcola statistiche di frequenza delle sottostringhe su più lunghezze di pattern ($m$). Conta le occorrenze dei pattern $P$ all'interno della sequenza $S$ definiti come $f(P, S) = |\{i \mid S_{i:i+m-1} = P\}|$.
3. Aggregazione delle Caratteristiche: Le statistiche estratte vengono aggregate in vettori di caratteristiche che catturano:
   • Distribuzioni di Frequenza delle Sottostringhe: Conteggi normalizzati delle occorrenze dei pattern.
   • Pattern di Ricorrenza: La frequenza con cui specifiche sottostringhe si ripetono.
   • Caratteristiche di Entropia: Misure di uniformità della distribuzione.
4. Costruzione dell'Impronta Digitale: Queste caratteristiche vengono mappate in un vettore di impronta digitale compatto ($X \in \mathbb{R}^d$) che caratterizza il comportamento strutturale del generatore di sequenze.
5. Analisi Comparativa: Il framework confronta le impronte digitali provenienti da Sequenze Generate da Cifrari (CGS) con Sequenze Casuali Uniformi (URS) utilizzando metriche come Punteggi di Deviazione dei Pattern ($D$) ed Entropia dei Pattern ($H$).

Contributi Chiave

• Introduzione del Framework SBF: Il documento introduce un framework innovativo per l'analisi strutturale delle sequenze crittografiche utilizzando tecniche di stringologia.
• Impronte Digitali Basate sui Pattern: Propone un metodo di rappresentazione che caratterizza i generatori di sequenze utilizzando statistiche di sottostringhe invece di metriche di casualità globale esclusivamente.
• Dimostrazione Sperimentale: Il lavoro dimostra, attraverso una valutazione sperimentale, che l'analisi dei pattern basata sulla stringologia può rivelare differenze strutturali misurabili tra sequenze crittografiche e sequenze casuali uniformi.

Risultati Sperimentali
La valutazione ha utilizzato un dataset di 20.000 sequenze (10.000 CGS e 10.000 URS), ciascuna lunga 2.048 bit ($2^{12}$). Sono stati analizzati pattern di sottostringhe di lunghezze 8, 16 e 32 bit.

• Frequenza dei Pattern: Le sequenze generate dal cifrario hanno mostrato una concentrazione strutturale leggermente superiore (ad esempio, frequenza normalizzata di 0,54 contro 0,50 per pattern di 8 bit) rispetto alle sequenze casuali.
• Punteggi di Deviazione: La metrica di deviazione dei pattern ($D$) ha prodotto punteggi costantemente diversi da zero su tutte le lunghezze dei pattern (variando da 0,09 a 0,13), indicando una variazione strutturale misurabile tra le due fonti.
• Entropia: Le sequenze generate dal cifrario hanno mostrato valori di entropia leggermente inferiori (ad esempio, 7,6 contro 8,0 per pattern di 8 bit) rispetto al massimo teorico delle sequenze casuali, suggerendo una leggera concentrazione di pattern.
• Ricorrenza: L'analisi dei conteggi di ricorrenza delle sottostringhe ha rivelato piccole ma distinte differenze nel comportamento di ripetizione tra i due tipi di sequenza.

Significato e Affermazioni
Il documento afferma che, sebbene i segnali strutturali osservati siano piccoli, sono misurabili e distinti dal rumore presente nelle sequenze casuali uniformi. Gli autori sottolineano che queste scoperte non implicano debolezze crittografiche pratiche; gli algoritmi moderni rimangono computazionalmente indistinguibili dai dati casuali. Piuttosto, il significato del framework SBF risiede nel fornire una prospettiva analitica aggiuntiva. Funge da strumento per studiare il comportamento strutturale e le regolarità interne dei generatori crittografici, completando i tradizionali test statistici globali. Il lavoro suggerisce che l'integrazione delle tecniche di stringologia nei flussi di lavoro di valutazione crittografica può offrire una comprensione più ricca della robustezza strutturale dei generatori di sequenze.