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 :

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 :-)