PICSI

On peut répartir les générateurs pseudo-aléatoires destinés au chiffrement à flot en trois grandes familles, qui dépendent de leur contexte d'application et notamment du type de ressources dont disposent les utilisateurs.

Les générateurs sûrs d'un point de vue calculatoire  dont la sécurité repose sur la difficulté de certains problèmes mathématiques. Il s'agit de générateurs pour lesquels on peut démontrer (sous certaines hypothèses comme la difficulté de la factorisation) qu'il n'existe aucun algorithme qui permette de distinguer la suite produite d'une suite aléatoire en un temps polynômial avec une probabilité significativement supérieure à 1/2. Toutefois, à l'instar des cryptosystèmes à clef publique, ces générateurs pseudo-aléatoires sont fondés sur des problèmes issus de la théorie des nombres. On peut mentionner par exemple le générateur RSA, qui consiste à appliquer récursivement l'algorithme RSA à partir d'une graine x₀ :

xt+1 = xte mod pq ,

et dont la sortie à l'instant t correspond au bit de poids faible de x_t [1]. Un autre exemple célèbre est le générateur Blum-Blum-Shub [3] qui consiste à itérer l'élévation au carré modulo pq. La sécurité de ce générateur repose sur la difficulté du problème des résidus quadratiques. Cependant, par la nature des opérations effectuées, tous ces générateurs sont extrêmement lents ; leur débit est très insuffisant et leur mise en oeuvre beaucoup trop compliquée pour qu'ils puissent être utilisés en pratique dans un chiffrement à flot.

Les générateurs inconditionnellement sûrs selon certains modèles  dont l'objectif est d'apporter une sécurité démontrable identique à celle du masque jetable mais sous l'hypothèse que l'adversaire, s'il peut disposer d'une puissance de calcul infinie, a certaines contraintes (par exemple, sa capacité de stockage ou le nombre d'accès réseau qu'il peut effectuer est limité) [5,2,6]. Ces générateurs nécessitent la mise en place d'une infrastructure extrêmement lourde et ne peuvent être déployés qu'à grande échelle : ils utilisent par exemple une source d'aléa commune diffusée par un satellite, ou à travers le réseau sous forme d'un très grand nombre de pages Web. Pour ces raisons, leur utilisation relève encore de la prospective. Toutefois, il s'agit de la seule classe de générateurs pseudo-aléatoires qui offre une sécurité démontrable (au sens de la théorie de l'information).

Les générateurs fondés sur un algorithme par blocs  qui engendrent une suite pseudo-aléatoire au moyen d'un système de chiffrement par blocs (par exemple l'AES) utilisé dans un mode opératoire particulier (mode OFB ou mode Compteur). Pour certaines constructions usuelles, on peut démontrer que le générateur pseudo-aléatoire est sûr s'il n'existe pas d'attaque sur l'algorithme par blocs sous-jacent. Un exemple de générateur de ce type est le chiffrement à flot f8 utilisé pour assurer la confidentialité des communications des téléphones mobiles de troisième génération dans la norme européenne UMTS. Le générateur pseudo-aléatoire employé dans f8 repose sur l'algorithme par blocs KASUMI (une description précise de l'algorithme f8 est disponible dans la fiche correspondant). L'avantage de ce type de générateurs est qu'ils reposent sur des algorithmes d'emploi très courant, souvent standardisés, dont la sécurité a fait l'objet de nombreuses études. Leur utilisation est donc conseillée dès lors que l'application visée n'impose pas de contraintes particulières en termes de débit de chiffrement ou d'implémentation matérielle. Pour plus de détails sur les constructions et leur sécurité, voir la fiche sur les générateurs fondés sur les algorithmes par blocs.

Les générateurs dits dédiés  au sens où ils sont conçus spécialement pour cet usage. On trouve dans cette famille les seuls générateurs capables de dépasser le débit de chiffrement offert usuellement par les algorithmes par blocs : la vitesse de chiffrement en logiciel d'un système par bloc classique tel l'AES est de l'ordre d'une vingtaine de cycles du processeur pour chiffrer un octet, alors que certains générateurs dédiés permettent d'atteindre des vitesses de l'ordre de 3 à 5 cycles par octet. De même, seuls des générateurs dédiés peuvent conduire à une mise en uvre par un circuit électronique de très petite taille et à une très faible consommation. Ce type de générateurs est donc particulièrement privilégié dans les systèmes embarqués. Toutefois, suite au développement de nouvelles techniques d'attaques, très peu de générateurs pseudo-aléatoires dédiés ont fait l'objet d'une standardisation ; seuls MUGI et SNOW 2.0 ont été standardisés par l'ISO/IEC en juillet 2005 (voir les fiches consacrées à ces deux générateurs pseudo-aléatoires pour une description détaillée). De plus, du fait de leur conception très récente, ils n'offrent évidemment pas les mêmes garanties de sécurité que les systèmes fondés sur des algorithmes par blocs dont la solidité a été éprouvée au cours de nombreux travaux de recherche. Pour plus de détails sur les différentes techniques de conception de générateurs pseudo-aléatoires dédiés et leur sécurité, voir la fiche Les générateurs pseudo-aléatoires dédiés.

 

Références

[1]

W.  Alexi, B.  Chor, O.  Goldreich,,name C.P. Shnorr. << RSA and Rabin functions: certain parts are as hard as the whole >>. SIAM Journal on Computing, 17, 1988.

[2]

Y.  Aumann,name M.O. Rabin. << Information Theoretically Secure Communication in the Limited Storage Space Model >>. Advances in Cryptology - CRYPTO'99, 1666 Lecture Notes in Computer Science, 65-79. Springer-Verlag, 1999.

[3]

L.  Blum, M.  Blum,,name M.  Shub. << A simple unpredicable pseudo-random number generator >>. SIAM Journal on Computing, 15, 1986.

[4]

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

[5]

U.  Maurer. << Conditionally-Perfect Secrecy and a Provably-Secure Randomized Cipher >>. Journal of Cryptology, 5(1):53-66, 1992.

[6]

M.O. Rabin. << Provably unbreakable Hyper-Encryption in the limited access model >>. Proceedings of the 2005 IEEE Information Theory Workshop on Theory and Practice in Information-Theoretic Security, 34-37. IEEE, 2005.