Correlation Bounds and Markov Analysis for Ring-Oscillator TRNGs: A Joint Validation Framework

Titolo: Correlation Bounds and Markov Analysis for Ring-Oscillator TRNGs: A Joint Validation Framework

Autori: Miguel Alcocer, Ana Isabel Gómez, Domingo Gómez-Pérez (Università Rey Juan Carlos e Università di Cantabria, Spagna).

1. Il Problema

I Generatori di Numeri Casuali Veri (TRNG) basati su oscillatori ad anello (Ring Oscillators - RO) sono fondamentali per la crittografia, poiché forniscono l'imprevedibilità necessaria per chiavi, nonce e parametri di sicurezza. Tuttavia, la loro validazione statistica è complessa e frammentata:

• Esistono misure teoriche come la correlazione di ordine $k$ di Mauduit-Sárközy ($C_k$) che forniscono limiti teorici sulla pseudocasualità.
• Esistono test empirici come il Test Universale di Maurer (che valuta l'entropia e la comprimibilità) per la valutazione pratica.
• Il Gap: Non esisteva precedentemente alcun lavoro che collegasse empiricamente o teoricamente queste metriche (in particolare il punteggio Z di Maurer e la correlazione di secondo ordine $C_2$) né che esplorasse la loro relazione con le catene di Markov di ordine superiore nei TRNG basati su contatori. Senza questa connessione, la validazione dei nuovi design richiede l'esecuzione di suite di test complete e dispendiose, senza una metrica unificata per la previsione della qualità.

2. Metodologia

Gli autori hanno proposto un framework di validazione congiunta che integra modelli teorici e simulazioni computazionali:

• Analisi Teorica:
  • Derivazione di relazioni matematiche tra la misura di correlazione $C_k(S)$ e le probabilità di transizione delle catene di Markov di ordine $k$.
  • Stabilimento di limiti teorici che legano il test di Maurer alla funzione di correlazione di ordine $k$.
  • Utilizzo del limite migliorato di Schmidt per $C_k$, che è più stringente rispetto ai limiti precedenti (es. Alon).
• Implementazione e Simulazione:
  • Utilizzo del framework open-source OpenTRNG per simulare diverse architetture di TRNG basati su oscillatori ad anello.
  • Confronto tra due metodi di estrazione: il campionamento diretto dei bit (che tende a produrre scarsa casualità) e il metodo basato su contatori (differential counter-based), che conta i periodi degli oscillatori tra i bordi di un clock di riferimento.
  • Variazione dei parametri: frequenze degli oscillatori ($f_1, f_2$), frequenza di riferimento ($f_{ref}$) e profondità di accumulazione XOR ($n = 1, 2, 4, 8, 16$).
  • Generazione di sequenze di $N = 10^5$ bit per ciascuna configurazione per calcolare simultaneamente $C_2$ e il punteggio Z di Maurer.

3. Contributi Chiave

Il lavoro apporta tre contributi principali alla letteratura scientifica:

1. Relazione Empirica: È la prima dimostrazione empirica di una forte correlazione positiva tra il punteggio Z di Maurer e la correlazione di secondo ordine fuori picco ($C_2$) negli TRNG a oscillatore ad anello.
2. Derivazione Teorica: Gli autori hanno derivato relazioni esplicite tra:
   • $C_k$ e le probabilità di transizione delle catene di Markov di ordine $k$.
   • Il test di Maurer e la funzione di correlazione, fornendo limiti superiori e inferiori per la funzione di test $f_{TU}$ in funzione di $C_k$.
3. Validazione Computazionale: Dimostrazione che le implementazioni pratiche basate su contatori differenziali raggiungono valori di $C_2$ significativamente inferiori al limite teorico migliorato di Schmidt, confermando l'efficacia di questo approccio rispetto al campionamento diretto.

4. Risultati

Le simulazioni su 58 configurazioni di parametri (34 ERO e 24 COSO) hanno prodotto i seguenti risultati:

• Correlazione Forte: È stata osservata una forte correlazione positiva tra il punteggio Z di Maurer e $C_2$ (coefficiente di Pearson $r = 0.95$).
• Soglie di Qualità: Le configurazioni con un punteggio assoluto di Maurer $|Z| < 0.1$ hanno consistentemente raggiunto $C_2 < 0.01$. Al contrario, valori di $C_2$ elevati (> 0.8) sono correlati a $Z > 1$, indicando deviazioni dalla casualità attesa.
• Effetto dell'Accumulazione XOR: L'aumento della profondità di accumulazione XOR ($n \ge 4$) sposta le prestazioni delle configurazioni verso la regione ideale ($|Z| \approx 0$, $C_2 < 0.01$).
• Confronto Metodi: Il metodo basato su contatori ha mostrato un miglioramento di circa 40 volte nella misura $C_2$ rispetto al campionamento diretto (da 0.34 a 0.009), superando con successo i test di casualità.
• Confronto con il Limite di Schmidt: Le implementazioni pratiche hanno raggiunto valori di $C_2$ da 2 a 3 volte inferiori al limite teorico migliorato di Schmidt ($C_2 \lesssim 0.021$ per $N=10^5$), suggerendo che i modelli reali possono essere più efficienti di quanto previsto dai modelli teorici puri basati solo sul rumore termico.

5. Significato e Implicazioni

Questo studio ha un impatto significativo sulla progettazione e validazione dei TRNG:

• Metrica Unificata: Propone un protocollo di validazione semplificato. Invece di eseguire suite di test complete (come NIST o AIS31) per ogni iterazione di design, i progettisti possono calcolare rapidamente $C_2$ (tramite FFT) e il punteggio Z di Maurer. Se entrambi soddisfano le soglie ($C_2 < 0.01$ e $|Z| < 2$), è altamente probabile che il design superi tutti i test di casualità.
• Rilevamento Precoce di Errori: La deviazione in una di queste metriche funge da segnale precoce di difetti di progettazione, riducendo i tempi di valutazione.
• Ponte Teorico-Pratico: Il lavoro collega rigorosamente l'analisi combinatoria (correlazioni) con l'analisi probabilistica (catene di Markov), fornendo una base teorica solida per l'uso di modelli di Markov di ordine superiore nella stima dell'entropia.
• Guida per i Progettisti: Conferma che l'architettura basata su contatori differenziali è superiore al campionamento diretto per gli oscillatori ad anello e fornisce parametri ottimali per l'accumulazione XOR.

In sintesi, il paper offre un framework unificato che semplifica lo studio di nuovi design TRNG, riducendo la complessità della validazione statistica e fornendo limiti teorici più precisi per le implementazioni pratiche.