Générateurs de nombres pseudo-aléatoires
Par haypo, dimanche 2 décembre 2007 à 21:09 :: Sécurité informatique :: #97 :: rss
Récemment, plusieurs vulnérabilités ont été trouvées dans des générateurs de nombre pseudo-aléatoires : Linux, Windows, FreeBSD et OpenSSL. Je prépare un billet dessus, mais avant je vais m'attarder sur les générateurs : comment un ordinateur purement déterministe pourrait être aléatoire ? Ce billet présente les algorithmes utilisés, comment mesurer la qualité d'un générateur, le groupe de travail du NIST, le choix de la graine et enfin les générateurs matériels.
Algorithmes
Il existe deux familles de générateurs de nombres : pseudo-aléatoires et aléatoires. La seconde catégorie utilise des phénomènes physiques (du matériel). Commençons par les générateurs pseudo-aléatoires qui sont purement algorithmiques.
Pour générer de l'entropie, différents opérateurs sont utilisés : addition, multiplication, décalage, XOR, congruence, fonctions de hachage, etc. D'ailleurs, les fonctions de hachage recherchent la même propriété que les générateurs de nombres aléatoires : l'effet avalanche (le but étant qu'en ne perturbant qu'un seul bit en entrée, on obtient idéalement une sortie totalement différente). Certains algorithmes utilisent également un accumulateur d'entropie pour regénérer régulièrement la graine (point de départ de la suite des nombres générés).
Les algorithmes les plus simples sont les générateurs congruentiels linéaires. C'est l'implémentation la plus courante de la fonction random(). Une autre famille repose sur l'opérateur Linear Feedback Shift Register (LFSR).
Pour la cryptographie, les algorithmes sont plus complexes :
- Blum Blum Shub (1986), écrit par Lenore Blum, Manuel Blum et Michael Shub
- ISAAC (1996), écrit par Bob Jenkins
- Mersenne Twister (1997), écrit par Makoto Matsumoto et Takuji Nishimura
- Yarrow (1999), écrit par Bruce Schneier, John Kelsey et Niels Ferguson
- Fortuna (2003), écrit par Bruce Schneier et Niels Ferguson
Mesurer la qualité d'un générateur
Un des premiers à avoir mesuré la qualité des générateurs est Pierre L’Ecuyer avec son papier : Testing random number generators (1992). Trois ans plus tard, George Marsaglia a écrit une suite de tests dédiés aux générateurs de nombres pseudo-aléatoires utilisant des mots de 32 bits : Diehard (Battery of Tests of Randomness, 1995). Enfin, Robert G. Brown a développé une nouvelle version : Dieharder (2007).
Quelques recommandations anciennes sur les générateurs pseudo-aléatoires :
- RFC 1750: Randomness Recommendations for Security (1994) par D. Eastlake, S. Crocker et J. Schiller
- Software Generation of Practically Strong Random Numbers (1998, mise à jour en 2000) par Peter Gutmann
Groupe de travail du NIST
Le National Institute of Standards and Technology (NIST) est une agence du Département du Commerce des États-Unis servant entre autre à émettre des standards pour l'industrie. Son département informatique a un groupe de travail dédié aux nombres aléatoires : Random Number Generation Technical Working Group. Deux publications sont plus particulièrement intéressantes :
- NIST 800-22 (A statistical test suite for random and pseudorandom number generators for cryptographic applications, mai 2001)
- NIST 800-90 (Recommendation for Random Number Generation Using Deterministic Random Bit Generators, mars 2007)
Choix de la graine
N'importe quel générateur de nombres pseudo-aléatoires a besoin d'une graine pour initialiser le générateur pour éviter que la suite débute toujours par les même nombres. Il faut alors se tourner vers des phénomènes physiques (non prédictibles) : frappes du clavier, mouvement de la souris et activité du disque dur. Le réseau ne peut pas être utilisé comme source d'entropie fiable étant donné qu'un attaquant peut contrôler le réseau en forgeant des paquets.
Linux offre le périphérique /dev/random qui est alimenté par ces événements, ainsi que /dev/urandom qui est moins sûr mais non bloquant. Côté pratique, pour générer manuellement de l'entropie sous Linux (pour générer une grosse clé RSA par exemple) : tapez n'importe quoi sur votre clavier, déplacez nerveusement votre souris et faites travailler votre disque dur (avec "find /" par exemple). On peut consulter le niveau d'entropie en lisant le fichier « /proc/sys/kernel/random/entropy_avail ». Le générateur de Windows utilise également le matériel pour initialiser son générateur interne.
Andreas Maier a écrit des pilotes /dev/random et /dev/urandom pour Solaris qu'il a maintenu jusqu'en 2002. Et l'équivalent pour Hurd : périphérique /dev/random.
Pour les systèmes qui n'offrent pas cette fonctionnalité, on peut utiliser le démon EGD (The Entropy Gathering Daemon), projet lancé en 2000 et écrit en Perl. GPG et OpenSSL, par exemple, peuvent l'utiliser. Une alternative est le démon PRNGD (Pseudo Random Number Generator Daemon) qui a la interface compatible avec EGD.
Générateurs matériel
L'idéal reste quand même d'utiliser du matériel dédié à la génération d'entropie. On peut utiliser une carte son (audio entropy daemon), une webcam (video entropy daemon), une carte wifi (iwrandom), etc. Il existe des boîtiers commerciaux branchés sur port COM ou USB. Côté insolite, le cryptologue Landon Noll et son équipe de Silicon Graphics ont breveté un système basé sur les lampes à lave (1996) :-) D'autres solutions utilisent la radioactivité, le bruit atmosphérique, etc. La nature est plutôt généreuse en entropie :-)
Conclusion
J'espère que ce billet vous a éclairé sur les générateurs de nombres aléatoires et pseudo-aléatoires. Vous en aurez besoin pour digérer le prochain billet dédié aux bugs de ces même générateurs :-)
Commentaires
1. Le lundi 3 décembre 2007 à 10:53, par pankkake
2. Le lundi 3 décembre 2007 à 11:04, par haypo
Ajouter un commentaire
Les commentaires pour ce billet sont fermés.