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

A continuación se presenta un resumen técnico detallado del artículo en español, estructurado según los puntos solicitados:

Título: Límites de Correlación y Análisis de Markov para TRNGs de Osciladores de Anillo: Un Marco de Validación Conjunta

1. Planteamiento del Problema

Los Generadores de Números Aleatorios Verdaderos (TRNG) basados en osciladores de anillo (RO) son fundamentales para aplicaciones criptográficas, ya que proporcionan la entropía necesaria para claves y nonces. Sin embargo, su validación estadística rigurosa es un desafío crítico.

• Falta de correlación entre métricas: Aunque existen medidas teóricas como la correlación de orden $k$ de Mauduit-Sárközy ($C_k$) y pruebas empíricas como la prueba universal de Maurer (que evalúa la entropía mediante el puntaje Z), no existía trabajo previo que vinculara empíricamente estas métricas ni que estableciera su relación con cadenas de Markov de alto orden en arquitecturas de muestreo de osciladores.
• Necesidad de validación unificada: Los diseñadores carecían de un marco unificado que permitiera predecir el comportamiento de un TRNG basándose en una combinación de estas métricas, lo que dificulta la evaluación rápida de nuevos diseños y la detección temprana de fallos o ataques.

2. Metodología

El estudio propone un marco de validación conjunta que integra análisis teórico, modelado probabilístico y simulación computacional:

• Marco Teórico:
  • Se establecen relaciones matemáticas entre la medida de correlación $C_k(S)$ y las probabilidades de transición de cadenas de Markov de memoria $k$.
  • Se derivan límites teóricos que vinculan la prueba de Maurer (función $f_{TU}$) con la función de correlación de orden $k$.
  • Se utiliza el límite mejorado de Schmidt para $C_k$, que es más estricto que el límite clásico de Alon.
• Implementación Computacional:
  • Se utilizó el framework de código abierto OpenTRNG para simular diseños de TRNG basados en osciladores de anillo.
  • Se exploraron tres arquitecturas de referencia: Oscilador de Anillo Elemental (ERO), Multi-Oscilador (MURO) y Muestreo Coherente (COSO).
  • Se implementó un enfoque de extracción diferencial basada en contadores (en lugar de muestreo directo de bits), donde se cuentan los periodos de oscilación entre bordes de reloj de referencia y se aplica una acumulación XOR de los bits menos significativos (LSB) de múltiples fuentes.
  • Experimentación: Se probaron 58 configuraciones de parámetros (frecuencias de osciladores, frecuencia de referencia y profundidad de acumulación XOR $n$) generando secuencias de $N = 10^5$ bits.
  • Se calcularon simultáneamente la correlación de segundo orden fuera de pico ($C_2$) y el puntaje Z de la prueba de Maurer.

3. Contribuciones Clave

El artículo aporta tres contribuciones principales al estado del arte:

1. Relación Empírica Inédita: Se establece por primera vez una relación empírica fuerte y positiva entre el puntaje Z de la prueba de Maurer y la correlación $C_2$ fuera de pico en TRNGs de osciladores de anillo.
2. Derivación Teórica de Límites: Se derivan relaciones explícitas entre:
   • La medida de correlación $C_k$ y las probabilidades de transición de cadenas de Markov de orden $k$.
   • La prueba de Maurer y la función de correlación, proporcionando límites teóricos que vinculan la compresibilidad de la secuencia con su estructura de correlación.
3. Validación del Marco Unificado: Se demuestra mediante simulaciones que las implementaciones prácticas basadas en contadores diferenciales pueden superar los límites teóricos esperados, alcanzando valores de $C_2$ significativamente menores que el límite mejorado de Schmidt.

4. Resultados

Los resultados computacionales y teóricos muestran lo siguiente:

• Correlación Fuerte: Existe una correlación positiva muy alta (Pearson $r = 0.95$) entre el puntaje Z de Maurer y $C_2$. Esto implica que una baja correlación ($C_2$) se traduce directamente en un puntaje Z cercano a cero (comportamiento aleatorio ideal).
• Eficacia del Método de Contadores:
  • El método de muestreo directo de bits falló en las pruebas ($C_2 = 0.34$, $Z = -2.1$).
  • El método basado en contar periodos (con acumulación XOR) logró una mejora de aproximadamente 40 veces en $C_2$ ($C_2 = 0.009$) y pasó la prueba de Maurer ($|Z| < 1$).
• Superación de Límites Teóricos: Las configuraciones óptimas alcanzaron valores de $C_2$ entre 2 y 3 veces inferiores al límite mejorado de Schmidt ($C_2 \lesssim 0.021$ para $N=10^5$), demostrando que las implementaciones prácticas pueden ser más eficientes que los modelos teóricos básicos de ruido térmico.
• Estadísticas de Ejecución: Las longitudes de las corridas de bits en los diseños óptimos coincidieron con las expectativas teóricas de aleatoriedad ($\mu \approx 2$, $\sigma \approx 1.41$), validando la calidad de la entropía extraída.

5. Significado e Impacto

Este trabajo tiene un impacto significativo en el diseño y validación de TRNGs:

• Protocolo de Validación Simplificado: Propone un protocolo práctico donde el cálculo conjunto de $C_2$ (vía FFT) y el puntaje Z de Maurer actúa como un indicador unificado de calidad. Si un diseño cumple con $C_2 < 0.01$ y $|Z| < 2$, es altamente probable que pase suites de pruebas completas (como NIST o AIS31).
• Detección Temprana de Fallos: La fuerte correlación permite a los diseñadores identificar defectos en el diseño o desviaciones de la aleatoriedad ideal midiendo solo una de estas métricas, reduciendo el tiempo de evaluación.
• Puente Teórico-Práctico: Al conectar las medidas combinatorias ($C_k$) con modelos probabilísticos (Cadenas de Markov), el artículo proporciona una base teórica sólida para entender por qué ciertas arquitecturas (como la extracción diferencial basada en contadores) funcionan mejor que otras.
• Dirección Futura: Abre la puerta a investigar límites de correlación específicos de la arquitectura y a extender el marco a acumulaciones XOR de múltiples fuentes y correlaciones de orden superior.

En resumen, el artículo demuestra que la combinación de la prueba de Maurer y los límites de correlación de Mauduit-Sárközy ofrece una herramienta robusta y unificada para garantizar la calidad criptográfica de los TRNGs basados en osciladores de anillo.