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

Titre : Bornes de corrélation et analyse de Markov pour les TRNG à oscillateurs en anneau : Un cadre de validation conjoint

1. Problématique

Les Générateurs de Nombres Aléatoires Vrais (TRNG) basés sur des oscillateurs en anneau (Ring Oscillators - RO) sont essentiels pour la cryptographie, fournissant des clés et des nonces imprévisibles. Cependant, leur validation statistique rigoureuse reste un défi.

• Le manque de corrélation entre métriques : Bien que la mesure de corrélation d'ordre $k$ de Mauduit-Sárközy ($C_k$) offre des bornes théoriques sur le caractère pseudo-aléatoire et que le test universel de Maurer (basé sur l'entropie) fournisse une évaluation empirique, aucune étude antérieure n'avait établi de lien entre ces deux métriques.
• Besoin de validation unifiée : Les concepteurs de TRNG manquent d'un cadre unifié pour valider simultanément la qualité de l'entropie et les propriétés de corrélation, ce qui complique l'évaluation des nouveaux designs.
• Limites des modèles existants : Les modèles basés uniquement sur le bruit thermique ne prédisent pas toujours les performances réelles, notamment concernant les corrélations d'ordre 2 ($C_2$).

2. Méthodologie

Les auteurs proposent un cadre de validation conjoint combinant analyse théorique, modélisation mathématique et simulations computationnelles.

• Cadre Théorique et Mathématique :

  • Lien Markov-Corrélation : L'article établit une relation mathématique entre les probabilités de transition d'une chaîne de Markov d'ordre élevé (utilisée pour modéliser les TRNG) et la mesure de corrélation $C_k$. Le théorème 1 démontre que de faibles valeurs de $C_k$ garantissent des probabilités de transition proches de l'uniformité ($1/2$).
  • Lien Maurer-Corrélation : Le théorème 2 dérive des bornes théoriques reliant le score Z du test de Maurer ($Z$) à la fonction de corrélation $C_k$. Cela permet de relier la compressibilité de la séquence (entropie) à ses propriétés de corrélation.
  • Borne de Schmidt : L'analyse s'appuie sur la borne améliorée de Schmidt pour $C_k$, qui est plus stricte que la constante d'Alon précédente.

• Implémentation et Simulation :

  • Outil : Utilisation du framework open-source OpenTRNG.
  • Architecture : Étude de l'approche différentielle basée sur le comptage (differential counter-based approach) de Allini et al., utilisant deux oscillateurs en anneau libres (ERO) avec des fréquences légèrement différentes.
  • Extraction : Au lieu d'échantillonner directement les bits (ce qui donne de mauvais résultats), la méthode compte les périodes des oscillateurs entre les bords d'une horloge de référence. Les bits de poids faible (LSB) des deux compteurs sont XORés pour isoler le bruit thermique indépendant.
  • Paramètres : Exploration de 58 configurations (fréquences des oscillateurs, fréquence de référence, profondeur d'accumulation XOR $n$).
  • Métriques : Calcul simultané de la corrélation d'ordre 2 ($C_2$) et du score Z de Maurer pour chaque configuration ($N=10^5$ bits).

3. Contributions Clés

1. Première corrélation empirique : Établissement de la première relation empirique entre le score Z de Maurer et la corrélation hors-pic d'ordre 2 ($C_2$) dans les TRNG à oscillateurs en anneau.
2. Déduction théorique : Dérivation de relations explicites entre $C_k$, les probabilités de transition des chaînes de Markov d'ordre $k$ et le test de Maurer.
3. Validation pratique : Simulation et validation du cadre sur OpenTRNG, démontrant que les implémentations pratiques peuvent dépasser les bornes théoriques attendues.

4. Résultats

• Corrélation Forte : Une corrélation positive très forte a été observée entre le score Z de Maurer et $C_2$ (coefficient de Pearson $r = 0,95$).
• Performance des Configurations :
  • Les configurations avec un score $|Z| < 0,1$ atteignent systématiquement $C_2 < 0,01$.
  • Les valeurs élevées de $C_2$ ($> 0,8$) correspondent à des écarts significatifs par rapport à l'attente aléatoire ($Z > 1$).
  • L'accumulation XOR (avec $n \ge 4$) déplace les performances vers la région idéale ($|Z| \approx 0$, $C_2 < 0,01$).
• Comparaison Méthodes : La méthode basée sur le comptage (counter-based) surpasse massivement l'échantillonnage direct de bits. Pour des paramètres identiques, le comptage a réduit $C_2$ de $0,34$à$0,009$ (amélioration d'environ 40x) et a permis de passer le test de Maurer, contrairement à l'échantillonnage direct.
• Validation de la borne de Schmidt : Les résultats montrent que les implémentations pratiques atteignent des valeurs de $C_2$ 2 à 3 fois inférieures à la borne améliorée de Schmidt ($C_2 \lesssim 0,021$ pour $N=10^5$), confirmant l'efficacité du modèle différentiel.
• Statistiques de Runs : Les longueurs de runs des bits générés correspondent aux attentes théoriques d'une séquence aléatoire (moyenne $\mu \approx 2$, écart-type $\sigma \approx 1,41$), ce qui est directement corrélé à la réduction de $C_2$.

5. Signification et Impact

Ce travail propose un protocole de validation unifié pour les concepteurs de TRNG :

• Critère de qualité combiné : La combinaison d'un faible score Z de Maurer ($|Z| < 2$) et d'une faible corrélation hors-pic ($C_2 < 0,01$) sert de certificat de qualité robuste.
• Détection précoce : Une déviation dans l'une ou l'autre de ces métriques signale rapidement des défauts de conception, simplifiant l'évaluation de nouveaux designs sans avoir à exécuter des batteries de tests complètes (comme NIST ou AIS31) dès le début.
• Pont théorique-pratique : L'analyse des chaînes de Markov crée un lien rigoureux entre les évaluations combinatoires (corrélations) et probabilistes (entropie), offrant une compréhension plus profonde du comportement des TRNG à oscillateurs en anneau.

En conclusion, cette étude démontre que l'utilisation conjointe de la mesure de corrélation et du test de Maurer permet une validation plus efficace et plus rapide des générateurs de nombres aléatoires matériels, tout en validant théoriquement l'efficacité des architectures de comptage différentiel.