PICSI

La sécurité des algorithmes de chiffrement à flot repose entièrement sur les propriétés du générateur pseudo-aléatoire utilisé. En effet, si l'on suppose que l'adversaire dispose de divers messages chiffrés ainsi que des textes clairs correspondants (qu'il a devinés par exemple en utilisant le fait que les messages envoyés suivent un format particulier), un simple XOR entre ces couples clairs-chiffrés fournit alors les valeurs de certains bits produits par le générateur. Dans ce contexte, il doit par exemple être impossible en pratique quand on connaît certains bits produits par le générateur de prédire la valeur des bits suivants. Autrement dit, cette propriété est celle que l'on exigerait si un tel procédé était utilisé pour tirer les numéros gagnants au Loto : une personne qui analyse tous les tirages du Loto doit être dans l'impossibilité matérielle d'en déduire une quelconque information sur les tirages à venir.

Plus précisément, pour être utilisé dans un chiffrement à flot, un générateur pseudo-aléatoire doit produire des suites que l'on ne peut pas distinguer facilement d'une suite aléatoire même si l'on connaît toutes les caractéristiques du générateur utilisé à l'exception de la clef secrète. Il est important de noter que les générateurs pseudo-aléatoires ne sont pas toujours destinés au chiffrement à flot. On a besoin de ces procédés dans de nombreuses applications, comme les simulations numériques, qui requièrent de bonnes qualités statistiques mais pas nécessairement sous l'hypothèse que les spécifications du générateur sont connues. Ainsi, certains générateurs pseudo-aléatoires usuels comme les fonctions rand() ou random() des principaux langages de programmation sont généralement très faibles d'un point de vue cryptographiques.

Pour pouvoir être utilisés dans un chiffrement à flot, les générateurs pseudo-aléatoires doivent résister à quatre grands types d'attaques :

• les attaques par recouvrement de clef, qui visent à retrouver la clef secrète du générateur pseudo-aléatoire à partir de la connaissance d'un certain nombre de bits de sa sortie ;
• les attaques par recouvrement de l'état initial, dont l'objectif est de retrouver l'initialisation du générateur (ou de façon équivalente un état interne complet). La connaissance de la clef secrète suffit naturellement pour retrouver l'initialisation, mais la réciproque n'est pas nécessairement vraie. Si ces attaques permettent à l'adversaire de calculer autant de bits qu'il le souhaite à partir de cette initialisation, elles ne lui permettent pas nécessairement d'engendrer les suites produites à partir de la même clef secrète, mais de valeurs initiales différentes. Leur portée peut donc être considérablement plus faible que celle des attaques par recouvrement de clef, notamment si la taille des paquets échangés est petite, puisque les paquets sont tous chiffrés à l'aide de valeurs initiales différentes ;
• les attaques par prédiction du bit suivant, qui consistent, à partir de la connaissance des n premiers bits de la suite engendrée par le générateur pour une certaine clef, à prédire la valeur du bit suivant ;
• les attaques par distingueur, qui déterminent si une suite de n bits correspond à la sortie du générateur pseudo-aléatoire considéré ou s'il s'agit d'une suite véritablement aléatoire.

Ces dernières attaques sont évidemment beaucoup moins puissantes que les premières ; elles ne fournissent à l'adversaire que des informations partielles sur le message clair. Elles permettent par exemple de vérifier si un chiffré intercepté correspond à un texte clair donné, alors que retrouver la clef secrète permet de déchiffrer tous les messages interceptés lors de la communication. Toutefois, on peut démontrer que l'existence d'attaques par distingueur de complexité polynomiale est strictement équivalente à celle d'attaques polynomiales par prédiction du bit suivant [2,1].

 

Références

[1]

M.  Blum,name S.  Micali. << How to generate cryptographically strong sequences of pseudo-random bits >>. SIAM Journal on Computing, 13, 1984.

[2]

A.C. Yao. << Theory and Applications of trapdoor functions >>. Proceedings of the IEEE 23rd Annual Symposium on Foundations of Computer Science, 80-91. IEEE, 1982.