Nous abordons maintenant le problème central de la cryptographie moderne : la construction de schémas de chiffrement qui sont formellement sécurisés en présence d’un espion passif.
L’objectif est de concevoir des mécanismes de chiffrement dont les chiffrés ne révèlent aucune information sur les messages clairs, hormis leur longueur, sous des hypothèses computationnelles raisonnables.
Nous commençons par construire un schéma de chiffrement symétrique à longueur fixe qui possède la propriété d’ indistinguabilité des chiffrés en présence d’un espion.
La construction est très proche du chiffrement par masque jetable (one-time pad). La différence fondamentale réside dans le fait que le masque n’est plus parfaitement aléatoire, mais pseudorandom.
clé k
|
v
générateur pseudorandom
|
v
masque pseudorandom
|
v
message clair ⊕ masque = chiffré
Cette idée permet de chiffrer des messages longs à l’aide de clés courtes, tout en conservant une sécurité de nature computationnelle.
Soit G un générateur pseudorandom ayant un facteur d’expansion ℓ, c’est-à-dire |G(s)| = ℓ(|s|).
Le schéma de chiffrement repose sur trois algorithmes :
Le chiffrement consiste à appliquer le générateur pseudorandom à la clé secrète (qui joue le rôle de graine) afin d’obtenir un masque long, lequel est ensuite combiné au message clair par un XOR bit à bit.
Soit G un générateur pseudorandom de facteur d’expansion ℓ. On définit un schéma de chiffrement symétrique Π = (Gen, Enc, Dec) pour des messages de longueur ℓ(n) comme suit :
La correction du schéma est immédiate puisque l’opération XOR est sa propre inverse.
Théorème. Si G est un générateur pseudorandom, alors ce schéma possède des chiffrés indistinguables en présence d’un espion.
La démonstration repose sur un argument de réduction : tout adversaire capable de distinguer les chiffrés permettrait de distinguer la sortie de G d’une chaîne parfaitement aléatoire.
La construction précédente suppose des messages de longueur fixe. Cette limitation peut être levée en utilisant un générateur pseudorandom à sortie de longueur variable.
Informellement, nous souhaitons un générateur capable de produire une chaîne pseudorandom de longueur arbitraire.
Plus précisément, le générateur G prend deux entrées :
Le codage unaire empêche un adversaire de demander une sortie de longueur exponentielle en temps polynomial.
Un chiffre par flot est un algorithme qui génère un flot pseudorandom. Un chiffre par flot sécurisé doit donc satisfaire la définition d’un générateur pseudorandom à sortie de longueur variable.
Il est important de souligner qu’un chiffre par flot n’est pas un schéma de chiffrement en soi, mais un outil permettant d’en construire un.
Historiquement, RC4 a été largement utilisé et longtemps considéré comme sécurisé. Il est aujourd’hui reconnu comme faible en raison de biais statistiques dans les premiers octets de sa sortie, lesquels ont permis des attaques pratiques comme la compromission de WEP.
Les registres à décalage à rétroaction linéaire (LFSR) ont également été populaires, mais sont insuffisants seuls. Les recommandations modernes privilégient des constructions fondées sur des chiffrements par blocs.
Jusqu’ici, nous avons supposé que l’adversaire observait un seul chiffré. En pratique, un espion peut observer de nombreux chiffrés produits avec la même clé.
Définition. Un schéma de chiffrement symétrique possède des chiffrés indistinguables sous chiffrement multiple si aucun adversaire probabiliste en temps polynomial ne peut distinguer des vecteurs de chiffrés, sauf avec un avantage négligeable.
Il est crucial de noter que certains schémas sont sécurisés pour un seul chiffré, mais deviennent vulnérables dès que plusieurs chiffrés sont observés.
Théorème. Tout schéma de chiffrement symétrique dont l’algorithme de chiffrement est déterministe ne possède pas la propriété d’indistinguabilité sous chiffrement multiple.
Une erreur tragique et malheureusement fréquente consiste à chiffrer plusieurs messages en réutilisant naïvement un même flot pseudorandom.
Des constructions sécurisées pour le chiffrement multiple nécessitent une randomisation soigneusement conçue et seront étudiées ultérieurement.