PICSI

Pour qu'un chiffrement à flot résiste aux attaques par distingueur, il faut que le générateur pseudo-aléatoire utilisé possède de bonnes propriétés statistiques. Même si l'existence d'une attaque par distingueur ne remet pas toujours en cause complètement la sécurité du chiffrement (car elle ne permet pas nécessairement de retrouver le texte clair, ou la clef secrète), un critère classique de sécurité est que 2^k bits de sortie du générateur pseudo-aléatoire ne puissent pas être distingués d'une suite aléatoire au moyen d'un algorithme dont le coût soit inférieur à 2^k, où k correspond ici au nombre de bits de la clef secrète.

Pour les générateurs pseudo-aléatoires utilisés en pratique pour le chiffrement à flot, il n'existe pas de preuve théorique de l'absence de distingueur de complexité polynômiale. Toutefois, on dispose d'un certain nombre de tests statistiques classiques que tout générateur pseudo-aléatoire doit au minimum vérifier pour prétendre à une sécurité raisonnable, mais il ne s'agit évidemment pas d'une condition de sécurité suffisante.
Les premières propriétés statistiques requises pour une suite pseudo-aléatoire ont été décrites par Knuth [2] et Golomb [1]. Elles ont donné lieu à des familles de tests, qui ont été enrichies depuis. On distingue usuellement les tests probabilistes dits de normalité, qui déterminent la probabilité pour qu'une suite tirée aléatoirement vérifie une propriété identique à celle de la suite à tester, et les tests dits de compression qui déterminent si la suite à tester peut être compressée de façon significative.
Les tests de normalité.   Les tests de normalité reposent sur le principe suivant : à toute suite de n bits on associe une certaine quantité dont on peut déterminer la distribution de probabilité pour une suite aléatoire. Par exemple, dans le test de fréquence qui vérifie si l'écart entre le nombre de zéros et le nombre de uns dans une suite binaire de longueur n est raisonnablement faible, on utilise la quantité

X = (n0−n1)2 n

(1)

où n₀ (resp. n₁) est le nombre de 0 (resp. de 1) dans la suite. Cette quantité suit une distribution du χ² de degré 1 quand n ≥ 10 (en pratique, il est préférable d'effectuer ce test sur une longueur de l'ordre de quelques milliers de bits). On calcule ensuite la valeur de cette quantité pour la suite pseudo-aléatoire à tester (ou pour l'ensemble de suites produites par le générateur) et on la compare à la valeur moyenne attendue pour une suite aléatoire. Plus exactement, on détermine, à partir de la distribution de référence, la probabilité d'obtenir un tel écart par rapport à la moyenne. Par exemple, si la suite pseudo-aléatoire à tester est de longueur 100, et possède 38 zéros et 62 uns, on obtient pour la formule (1) la valeur x=5,76. On déduit de la distribution de probabilité du χ² que la probabilité pour qu'une suite aléatoire possède une valeur de X supérieure à 5,02 est 0,025. Ainsi il y a moins de 2,5 % de chance d'obtenir cette valeur pour une suite aléatoire. On décide donc que la suite testée passe ou ne passe le test en fonction d'un niveau de confiance, c'est-à-dire en fonction de la probabilité que ce test échoue pour une suite aléatoire. De façon similaire, on peut tester la proportion de zéros et de uns dans des blocs de k bits. Parmi les autres tests de normalité classiques, on peut aussi mentionner le test de répétition, le test d'oscillation, le test du poker...
Les tests de compression.   Ces tests statistiques déterminent si une suite peut être compressée de façon significative sans perte d'information, ce qui la distinguerait d'une suite aléatoire. Parmi ces tests, les plus connus sont le test universel de Maurer [3], le test de compression Lempel-Ziv, le test de l'entropie de Pincus, Singer et Kalman et le test de la complexité linéaire.

Pour plus de précisions sur les tests, voir le parcours "description des tests statistiques

 

Références

[1]

S.W. Golomb. Shift register sequences. Aegean Park Press, 1982.

[2]

D. E. Knuth. The Art of Computer Programming, 2 - Seminumerical Algorithms. Addison Wesley, 1969.

[3]

U.  Maurer. << A universal statistical test for random bit generators >>. Advances in Cryptology - CRYPTO'90, 473 Lecture Notes in Computer Science. Springer-Verlag, 1990.

[4]

NIST SP 800-22. << A Statistical Test Suite for the Validation of Random Number Generators and Pseudo Random Number Generators for Cryptographic Applications >>. NIST Special Publication 800-22, 2000. National Institute of Standards and Technology.