Structural Analysis of Cryptographic Sequences using Stringology-Based Fingerprinting

Resumen Técnico: Análisis Estructural de Secuencias Criptográficas mediante Huellas Dactilares Basadas en Stringología

Enunciado del Problema
Los primitivos criptográficos, incluidos los cifradores de flujo, los Generadores de Números Pseudoaleatorios (PRNG) y los modos de cifrado por bloques, están diseñados para producir secuencias estadísticamente indistinguibles de datos aleatorios. La evaluación tradicional depende en gran medida de suites de pruebas de aleatoriedad estadística (por ejemplo, NIST STS, TestU01) para verificar propiedades globales como distribuciones de frecuencia, longitudes de series y entropía. Sin embargo, estas pruebas están diseñadas principalmente para detectar desviaciones significativas de la aleatoriedad ideal en lugar de caracterizar el comportamiento estructural específico de los generadores deterministas subyacentes. Dado que los algoritmos criptográficos dependen de operaciones internas estructuradas (suma modular, rotaciones de bits, sustituciones, XOR), pueden introducir características estructurales sutiles que los métodos puramente estadísticos no logran detectar. Existe la necesidad de un marco que interprete estas secuencias como cadenas simbólicas para analizar sus estructuras de patrones internos.

Metodología: El Marco de Huellas Dactilares Basadas en Stringología (SBF)
El artículo propone un marco de Huellas Dactilares Basadas en Stringología (SBF) que trata las salidas criptográficas como cadenas simbólicas para extraer estadísticas de patrones estructurales. El marco opera a través del siguiente flujo de trabajo:

1. Transformación de Secuencia: Las salidas criptográficas (flujos de clave, textos cifrados) se transforman en cadenas simbólicas binarias ($S \in \{0, 1\}^n$).
2. Extracción de Patrones: Utilizando análisis de ventana deslizante, el marco calcula estadísticas de frecuencia de subcadenas a través de múltiples longitudes de patrón ($m$). Cuenta las ocurrencias de patrones $P$ dentro de la secuencia $S$ definidas como $f(P, S) = |\{i \mid S_{i:i+m-1} = P\}|$.
3. Agregación de Características: Las estadísticas extraídas se agregan en vectores de características que capturan:
   • Distribuciones de Frecuencia de Subcadenas: Recuentos normalizados de ocurrencias de patrones.
   • Patrones de Recurrencia: La frecuencia con la que se repiten subcadenas específicas.
   • Características de Entropía: Medidas de uniformidad de distribución.
4. Construcción de Huella Dactilar: Estas características se mapean en un vector de huella dactilar compacto ($X \in \mathbb{R}^d$) que caracteriza el comportamiento estructural del generador de secuencias.
5. Análisis Comparativo: El marco compara huellas dactilares de Secuencias Generadas por Cifrado (CGS) contra Secuencias Uniformemente Aleatorias (URS) utilizando métricas como Puntuaciones de Desviación de Patrón ($D$) y Entropía de Patrón ($H$).

Contribuciones Clave

• Introducción del Marco SBF: El artículo introduce un marco novedoso para el análisis estructural de secuencias criptográficas utilizando técnicas de stringología.
• Huellas Dactilares Basadas en Patrones: Propone un método de representación que caracteriza los generadores de secuencias utilizando estadísticas de subcadenas en lugar de únicamente métricas de aleatoriedad global.
• Demostración Experimental: El trabajo demuestra, mediante evaluación experimental, que el análisis de patrones basado en stringología puede revelar diferencias estructurales medibles entre secuencias criptográficas y secuencias uniformemente aleatorias.

Resultados Experimentales
La evaluación utilizó un conjunto de datos de 20.000 secuencias (10.000 CGS y 10.000 URS), cada una con una longitud de 2.048 bits ($2^{12}$). Se analizaron patrones de subcadenas de longitudes de 8, 16 y 32 bits.

• Frecuencia de Patrones: Las secuencias generadas por cifrado exhibieron una concentración estructural ligeramente mayor (por ejemplo, frecuencia normalizada de 0,54 frente a 0,50 para patrones de 8 bits) en comparación con las secuencias aleatorias.
• Puntuaciones de Desviación: La métrica de desviación de patrón ($D$) arrojó puntuaciones consistentemente distintas de cero en todas las longitudes de patrón (oscilando entre 0,09 y 0,13), lo que indica una variación estructural medible entre ambas fuentes.
• Entropía: Las secuencias generadas por cifrado mostraron valores de entropía ligeramente más bajos (por ejemplo, 7,6 frente a 8,0 para patrones de 8 bits) en comparación con el máximo teórico de las secuencias aleatorias, lo que sugiere una ligera concentración de patrones.
• Recurrencia: El análisis de los recuentos de recurrencia de subcadenas reveló diferencias pequeñas pero distintas en el comportamiento de repetición entre los dos tipos de secuencias.

Significado y Afirmaciones
El artículo afirma que, aunque las señales estructurales observadas son pequeñas, son medibles y distintas del ruido encontrado en secuencias aleatorias uniformes. Los autores enfatizan que estos hallazgos no implican debilidades criptográficas prácticas; los algoritmos modernos siguen siendo computacionalmente indistinguibles de los datos aleatorios. En cambio, el significado del marco SBF radica en proporcionar una perspectiva analítica adicional. Sirve como una herramienta para estudiar el comportamiento estructural y las regularidades internas de los generadores criptográficos, complementando las pruebas estadísticas globales tradicionales. El trabajo sugiere que integrar técnicas de stringología en los flujos de trabajo de evaluación criptográfica puede ofrecer una comprensión más rica de la robustez estructural de los generadores de secuencias.