Structural Analysis of Cryptographic Sequences using Stringology-Based Fingerprinting

Résumé Technique : Analyse Structurelle de Séquences Cryptographiques par Empreintes Numériques Basées sur la Stringologie

Énoncé du Problème
Les primitives cryptographiques, y compris les chiffrements par flot, les Générateurs de Nombres Pseudo-Aléatoires (PRNG) et les modes de chiffrement par bloc, sont conçues pour produire des séquences statistiquement indiscernables de données aléatoires. L'évaluation traditionnelle repose fortement sur des suites de tests de hasard statistique (par exemple, NIST STS, TestU01) pour vérifier des propriétés globales telles que les distributions de fréquence, les longueurs de runs et l'entropie. Cependant, ces tests sont principalement conçus pour détecter des écarts significatifs par rapport au hasard idéal plutôt que pour caractériser le comportement structurel spécifique des générateurs déterministes sous-jacents. Étant donné que les algorithmes cryptographiques reposent sur des opérations internes structurées (addition modulaire, rotations de bits, substitutions, XOR), ils peuvent introduire des caractéristiques structurelles subtiles que les méthodes purement statistiques ne parviennent pas à détecter. Il existe un besoin d'un cadre qui interprète ces séquences comme des chaînes symboliques pour analyser leurs structures de motifs internes.

Méthodologie : Le Cadre d'Empreintes Numériques Basées sur la Stringologie (SBF)
L'article propose un cadre d'Empreintes Numériques Basées sur la Stringologie (SBF) qui traite les sorties cryptographiques comme des chaînes symboliques pour extraire des statistiques de motifs structurels. Le cadre fonctionne selon le flux de travail suivant :

1. Transformation de Séquence : Les sorties cryptographiques (flux de clés, textes chiffrés) sont transformées en chaînes symboliques binaires ($S \in \{0, 1\}^n$).
2. Extraction de Motifs : En utilisant une analyse par fenêtre glissante, le cadre calcule des statistiques de fréquence de sous-chaînes sur plusieurs longueurs de motifs ($m$). Il compte les occurrences de motifs $P$ dans la séquence $S$ définies par $f(P, S) = |\{i \mid S_{i:i+m-1} = P\}|$.
3. Agrégation de Caractéristiques : Les statistiques extraites sont agrégées en vecteurs de caractéristiques qui capturent :
   • Distributions de Fréquence de Sous-chaînes : Comptes normalisés des occurrences de motifs.
   • Motifs de Réurrence : La fréquence à laquelle des sous-chaînes spécifiques se répètent.
   • Caractéristiques d'Entropie : Mesures de l'uniformité de la distribution.
4. Construction d'Empreinte : Ces caractéristiques sont mappées dans un vecteur d'empreinte compact ($X \in \mathbb{R}^d$) qui caractérise le comportement structurel du générateur de séquence.
5. Analyse Comparative : Le cadre compare les empreintes des Séquences Générées par Chiffrement (CGS) avec des Séquences Aléatoires Uniformes (URS) en utilisant des métriques telles que les Scores de Déviation de Motif ($D$) et l'Entropie de Motif ($H$).

Contributions Clés

• Introduction du Cadre SBF : L'article présente un cadre novateur pour l'analyse structurelle des séquences cryptographiques utilisant des techniques de stringologie.
• Empreintes Numériques Basées sur les Motifs : Il propose une méthode de représentation qui caractérise les générateurs de séquences en utilisant des statistiques de sous-chaînes plutôt que des métriques de hasard global uniquement.
• Démonstration Expérimentale : Le travail démontre, par une évaluation expérimentale, que l'analyse de motifs basée sur la stringologie peut révéler des différences structurelles mesurables entre les séquences cryptographiques et les séquences aléatoires uniformes.

Résultats Expérimentaux
L'évaluation a utilisé un ensemble de données de 20 000 séquences (10 000 CGS et 10 000 URS), chacune ayant une longueur de 2 048 bits ($2^{12}$). Des motifs de sous-chaînes de longueurs 8, 16 et 32 bits ont été analysés.

• Fréquence de Motifs : Les séquences générées par chiffrement ont présenté une concentration structurelle légèrement plus élevée (par exemple, une fréquence normalisée de 0,54 contre 0,50 pour les motifs de 8 bits) par rapport aux séquences aléatoires.
• Scores de Déviation : La métrique de déviation de motif ($D$) a produit des scores constamment non nuls pour toutes les longueurs de motifs (variant de 0,09 à 0,13), indiquant une variation structurelle mesurable entre les deux sources.
• Entropie : Les séquences générées par chiffrement ont montré des valeurs d'entropie légèrement inférieures (par exemple, 7,6 contre 8,0 pour les motifs de 8 bits) par rapport au maximum théorique des séquences aléatoires, suggérant une concentration de motifs mineure.
• Réurrence : L'analyse des comptes de réurrence de sous-chaînes a révélé de petites mais distinctes différences dans le comportement de répétition entre les deux types de séquences.

Signification et Revendications
L'article affirme que, bien que les signaux structurels observés soient faibles, ils sont mesurables et distincts du bruit trouvé dans les séquences aléatoires uniformes. Les auteurs soulignent que ces résultats n'impliquent pas de faiblesses cryptographiques pratiques ; les algorithmes modernes restent computationnellement indiscernables des données aléatoires. Au contraire, la signification du cadre SBF réside dans la fourniture d'une perspective analytique supplémentaire. Il sert d'outil pour étudier le comportement structurel et les régularités internes des générateurs cryptographiques, complétant les tests statistiques globaux traditionnels. Le travail suggère que l'intégration de techniques de stringologie dans les flux de travail d'évaluation cryptographique peut offrir une compréhension plus riche de la robustesse structurelle des générateurs de séquences.