HSC
Network Security Consulting Agency Since 1989 - Specialized in Unix, Windows, TCP/IP and Internet
Text mode: access to the page content
Hervé Schauer Consultants
You are here: Home > Resources > Articles > Random Numbers Generators
Go to: HSC Trainings
Search:  
Version française
   Services   
o Skills & Expertise
o Consulting
o ISO 27001 services
o Audit & Assessment
o Penetration tests
o Vunerability assessment (TSAR)
o Forensics
o ARJEL
o Training courses
o E-learning
   Conferences   
o Agenda
o Past events
o Tutorials
   Resources   
o Thematic index
o Tips
o Lectures
o Courses
o Articles
o Tools (download)
o Vulnerability watch
   Company   
o Hervé Schauer
o Team
o Job opportunities
o Credentials
o History
o Partnerships
o Associations
   Press and
 communication
 
 
o HSC Newsletter
o Press review
o Press releases
o Publications
   Contacts   
o How to reach us
o Specific inquiries
o Directions to our office
o Hotels near our office
|>|Random Numbers Generators  
> Access to the content HTML Beginning of the article  
> Description How to genrate random numbers using a computer.  
> Context & Dates Internship report, also published in Confidentiel Sécurité number 66.
February 2000 
> Author Nicolas Jombart 
> Type  
> Abstract &
Table of content
Introduction

1. Le hasard
1.1. Qu'est ce qu'un nombre aléatoire ?
1.2. Dans la nature
1.3. Dans un ordinateur

2. Tester un générateur
2.1. Mathématiques
2.2. Testeurs

3. Attaques

4. Produits
4.1. Matériel
4.2. Logiciel

Conclusion

Références  

> Related documents
themeCryptography
[Course]  Understanding PKI
[Course]  Data Exchanges Security: IPsec, SSL, SSH
[Presentation]  Analysis of the encryption structures provided by BitLocker [3 April 2012 - French]
[Course]  Understanding PKI [4 April 2003 - French]
[Course]  Introduction to cryptography [9 February 2001 - French]
[Presentation]  Overview of encryption tools and their use [25 November 1999 - French]
[Techno-watch]  Analyse du produit Security Box Classic [18 March 1999 - French]
[Techno-watch]  Point de vue de la DISSI : les lois françaises sur le chiffrement [3 July 1995 - French]
> Copyright © 2000, Hervé Schauer Consultants, all rights reserved.

 

Introduction

On a souvent besoin de nombres aléatoires dans un ordinateur. On les utilise dans les jeux vidéo, les simultations mathématiques ou physiques, les résolutions d'équation et la cryptographie.

Ce dernier cas nécessite beaucoup plus de précautions, car la connaissance de ces nombres peut compromettre un protocole cryptographique.
Si il existe une corrélation entre des nombres pour un jeu ou pour initialiser des réseaux de neurones, ça n'est pas grave. Mais lorsque qu'il s'agit de générer des clefs, de session par exemple, si on arrive à la calculer, ou à restreindre les possibilités de recherche, le protocole devient très vulnérable. Les systèmes de commerce électronique et de liaisons chiffrées sont sensibles à celà, même les numéros de séquence des paquets TCP.

1  Le hasard

1.1  Qu'est ce qu'un nombre aléatoire ?

Un nombre aléatoire est assez difficile à définir mathématiquement. On ne peut dire d'un nombre qu'il est aléatoire, mais qu'une suite de nombre est aléatoire. Il n'est pas possible de prouver réellement que les décimales de p ou de e soient distribuées aléatoirement1. Il s'agit d'une distribution uniforme des éléments dans leur espace (ici des bits).

Ils doivent aussi être non corrélés entre eux, c'est à dire qu'il n'existe aucune forme de ressemblance mathématique et statistique entre deux extraits différents d'une même suite. Cela définit l'imprédictibilité, c'est à dire que l'observation d'une partie même très grande de la suite ne peut pas conduire à déterminer les parties passées ou futures.

Claude Shannon, à qui nous devons la théorie de l'information [1], a permis de quantifier la quantité d'information contenue dans un message. En effet, chaque bit d'un message n'apporte pas toujours un bit d'information absolue. On mesure l'information en shannon, un shannon étant l'information nécessaire pour lever une incertitude (dans le cas de bits 0 pour ``faux'' et 1 pour ``vrai'' par exemple). Par abus de language, un shannon est aussi appelé un bit d'entropie.

L'entropie d'une source d'information, ici d'une source aléatoire, mesure la quantité d'information qui est contenue dans un message2 : elle doit être très élevée pour un générateur aléatoire, asymptotiquement 1 shannon par bit (i.e. 8 bits d'entropie par octet), c'est à dire que chaque bit de sortie apporte un bit d'information, il ne dépend donc pas des autres. L'entropie d'une source est définie mathématiquement par h = Ei pilog2pi où pi est la probabilité d'apparition d'un symbole, ici on utilise souvent un octet. Sur un échantillon de N octets aléatoires, si f[i] contient le nombre d'apparitions de l'octet i, alors l'entropie est :
h = FF
E
i = 0 
f[i]
N
log2 f[i]
N

1.2  Dans la nature

D'après la théorie du chaos, le hasard n'existe pas dans la nature. Le vol des mouches3, la météorologie, la forme des objets naturels comme les feuilles d'arbre sont régis pas des équations ou des systèmes d'équation. Mais celles-ci sont extrêmement sensibles à leurs conditions initiales : une petite variation impalpable se traduit par un changement total de comportement quelque temps plus tard. On illustre souvent cette caractéristique par ``l'effet papillon'', où un battement d'ailes de papillon finit par provoquer un ouragan dans une autre partie du globe.

Après avoir précisé la différence entre hasard et chaos, il est possible dans notre cas4 de considérer la nature comme étant source de hasard. Il n'est raisonnablement pas possible de prédire son comportement. Nous ne serions pas surpris par le temps si les prévisions météorologiques étaient exactes !

1.3  Dans un ordinateur

Les ordinateurs sont (et heureusement) des machines déterministes ; ils ne peuvent produirent d'eux-mêmes des nombres aléatoires.

On utilise alors pour obtenir des informations des sources extérieures ou périphériques aux ordinateurs comme l'utilisation des ports, les interruptions système, ce qu'il se passe sur le réseau, tous les événements qui ont une source à l'extérieur et qui ne sont pas prédictibles efficacement.

Si on regarde trois événements de la même nature, et que l'on observe la différence de temps entre le premier et le deuxième, et ensuite le deuxième et le troisième, on peut définir un bit aléatoire en comparant ces temps. D'autre part, il existe des générateurs matériels qui apportent leur propre source de bruit, les meilleures étant le bruit thermique dans une jonction PN ou les désintégrations des noyaux de matières radioactives ...

1.3.1  Générateurs aléatoires logiciels

Des programmes peuvent collecter l'entropie de différentes sources périphériques au fonctionnement de l'ordinateur. Les collecteurs d'entropie comme /dev/random, EGD utilisent les paramètres suivants :

  • Les mouvements de l'utilisateur, c'est à dire la souris et le clavier.
  • Les processus, les statistiques de l'activité du disque dur.
  • L'activité du réseau
  • La position courante du curseur ou le la ligne du moniteur en train d'être affichée
  • La charge du processeur
  • Certains paramètres du noyau dans le cas de /dev/random
  • ...

Le générateur servant à produire les clefs pour PGP utilise simplement la souris et le clavier lorsque /dev/random n'existe pas. Il demande à l'utilisateur de taper une phrase au clavier ou de bouger la souris et utilise les données temporelles pour collecter les données aléatoires.
Les mécanismes estiment alors l'entropie que l'on a collecté sur les différentes sources, en fonction de la difficulté à l'évaluer. Cette information est ensuite passée dans une fonction de hachage, le plus souvent de type SHA5 et sert à initialiser un générateur pseudo-aléatoire. Certaines données ne peuvent être obtenues qu'en étant utilisateur privilégié (i.e. root sous Unix), comme les données concernant le réseau ou les interruptions systèmes qui sont de très bonnes sources.

1.3.2  Générateurs pseudo-aléatoires (PRNG)

Souvent, lorsqu'on a besoin de nombres aléatoires à la demande, il faut utiliser un algorithme qui va produire une suite de tels nombres. Les plus simples sont les générateurs utilisant la congruence linéaire Xn+1 = (aXn+b) mod m, comme la fonction rand() du C, et qui produisent des nombres apparemment aléatoires, suffisamment dans les applications non cryptographiques.

Plus évolués sont les systèmes à registre à décalage, c'est-à-dire qu'ils produisent des bits en fonction de ceux de leur état interne qui sont passés dans une fonction qui peut être une simple sommation, un ou-exclusif, et utilisent des techniques de substract with borrow, Multiply with carry, Inversive congruential. On trouvera toutes les configurations possibles de ces générateurs, qui servent aussi au chiffrement en continu, dans [2].

Un dernier type utilise des fonctions de brassage plus complexes, basées sur les algorithmes de chiffrement et de hachage.

loading

Tous ces algorithmes ont besoin d'une valeur initiale appelée germe (seed). On doit prendre soin du caractère aléatoire de cette donnée. On utilise parfois des données comme les bits les moins significatifs de l'heure6, mais il est préférable d'utiliser la sortie d'un générateur cité précédemment.
Un générateur peut être modélisé comme une machine à état : elle dispose d'un état interne qui se modifie à chaque tour en fonction de son état passé, des sorties et de la graine. Il s'agit d'une modélisation et chaque construction est propre. La fonction de fabrication doit permettre de générer des sorties sans pour autant informer l'extérieur sur l'état interne du générateur.

Les suites générées ne peuvent être que périodiques, avec une période cependant extrêmement grande. On considère par exemple qu'il est suffisant que la période puisse être de 2128.

2  Tester un générateur

On peut tester de manière automatique uniquement la qualité mathématique et statistique d'une suite de nombres aléatoires. Il existe beaucoup de méthodes, d'algorithmes, de papiers et de programmes pour tester les générateurs aléatoires : les premiers mettent en forme des calculs statistiques sur un échantillon donné, les deuxièmes proposent de faire passer des tests, qui seront réussis ou pas, donnant ainsi une indiquation sur la qualité du générateur.

2.1  Mathématiques

Une suite aléatoire doit bien sûr avoir quelques caractéristiques mathématiques fondamentales : un histogramme de population de chaque valeur plat, une corrélation nulle, et doit s'approcher d'un bit d'entropie par bit de sortie7.


Figure 1: A gauche : mauvaise suite, à droite : bonne suite

On peut aussi évaluer graphiquement, à l'aide d'une image dérivée de n'analyse noise sphere, la qualité de la suite aléatoire. C'est une analyse qui demande beaucoup de travail et qui est réservée au traitement du signal.

2.2  Testeurs

2.2.1  Caractéristiques statistiques

Des programmes comme ENT [3] calculent les caractéristiques mathématiques d'un échantillon produit par le générateur à tester. C'est le plus représentatif de ce genre de programme.
Il commence par calculer l'entropie, ainsi que la possibilité de comprimer la suite :
  Entropy = 7.999583 bits per byte.
  Optimum compression would reduce the size
  of this 417792 byte file by 0 percent.
Une suite aléatoire n'est jamais compressible car son entropie est très proche de 8 bits par octet. Le programme calcule le c2, qui est une valeur très représentative de la qualité aléatoire. Le pourcentage précisé est une autre vision de ce calcul, il ne doit pas s'approcher de 0 ou 100%. En pratique, il faut être très proche de 50%.
  Chi square distribution for 417792 samples is 241.44, and randomly
  would exceed this value 50.00 percent of the times.
puis la moyenne, l'analyse de Monte-Carlo et le coefficient de corrélation :
  Arithmetic mean value of data bytes is 127.5092 (127.5 = random).
  Monte Carlo value for Pi is 3.139361213 (error 0.07 percent).
  Serial correlation coefficient is -0.000324 (totally uncorrelated = 0.0).
La moyenne doit bien sûr être très proche de 127.5. On utilise également chaque séquence de 6 octets pour calculer p via l'analyse de Monte-Carlo. Le pourcentage d'erreur doît être le plus petit possible mais peut être faussé si on utilise un petit échantillon.
Le coefficient de corrélation série mesure la dépendance d'un octet à l'autre. Un flot aléatoire est proche de 0, un texte en anglais de 0.5 et des données très redondantes comme un fichier image bitmap s'approchent de 1.

2.2.2  Recettes

Diehard
Les tests de Diehard sont une série de tests empiriques au nombre de 15. Ils ont été originellement écrits en fortran par G. Marsaglia [4], puis portés en C [5]. Une version graphique est également en cours [6] de développement.

Il s'agit de tests basés sur des manipulations de bits ou de matrices obtenues avec l'échantillon. Pour plus de détails, la sortie du programme (voir exemple ci-dessous) précise mathématiquement chaque test avant de donner les résultats. Ces tests retournent une valeur de c2 qui ne doit pas etre 0 ou 1, ou trop proche de ces valeurs. Le test est considèré réussi si le c2 est compris entre 0,025 et 0,975.

Ce test est néanmoins très gourmand, si de nos jours les machines ne mettent que moins de quelques minutes à effectuer les tests, il faut néanmoins un échantillon d'environ 10Mo pour parvenir à effectuer tous les tests.

Voici un exemple de résultat de Diehard; le ``parking lot test'' :

     :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
     ::               THIS IS A PARKING LOT TEST                      ::
     :: In a square of side 100, randomly "park" a car---a circle of  ::
     :: radius 1.   Then try to park a 2nd, a 3rd, and so on, each    ::
     ::                           (...)                               ::
     :: to normally distributed.  Thus (k-3523)/21.9 should be a st-  ::
     :: andard normal variable, which, converted to a uniform varia-  ::
     :: ble, provides input to a KSTEST based on a sample of 10.      ::
     :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
           CDPARK: result of ten tests on file toto
            Of 12,000 tries, the average no. of successes
                 should be 3523 with sigma=21.9
            Successes: 3512    z-score: -0.502 p-value:0.307734
            Successes: 3512    z-score: -0.502 p-value:0.307734
                                  (...)
            Successes: 3535    z-score:  0.548 p-value:0.708135
            Successes: 3501    z-score: -1.005 p-value:0.157553

           square size   avg. no.  parked   sample sigma
              100            3516.200       10.675
            KSTEST for the above 10: p= 0.818041
Ici le test est réussi car la valeur du KSTEST résultant n'est pas trop proche de 1.

FIPS
Le National Institude of Standards and Technology (NIST [7]) a décrit dans la norme FIPS 140-1 [8] des tests au nombre de 4 et définissent le comportement des générateurs pseudo-aléatoires (on teste ici une série de 20.000 bits) :

  • Le test Monobit : Il s'agit simplement de compter le nombre de bits à 1. Ce nombre doit être compris entre 9.654 et 10346, c'est à dire la moitié avec une marge d'erreur de 346 bits, soit ±1.73%
  • Le test du Poker : On divise l'échantillon en 5000 quartets8 et on place leur nombre dans une table f[i] avec i la valeur des quartets.
    On calcule ensuite
    X = 16
    5000
    E  f2[i] - 5000
    Le test est réussi si 1,03 < X < 57,4.
  • Runs : Un run est une suite contigue de 0 ou de 1. On les compte toutes, séparément pour les 0 et les 1 et on réussit le test si :

    Longueur du run intervalle
    1 [2267,2733]
    2 [1079,1421]
    3 [502,748]
    4 [223,402]
    5 [90,223]
    6 et plus [90,223]

  • Long Run : Un long run est un run quelconque de taille supérieure ou égale à 34 bits. Le test est réussi si il n'y en a aucun dans l'échantillon.



MUST : Maurer Universal Statistical Test
Ueli Maurer [9] a montré que les tests statistiques sur les suites aléatoires pouvaient se déduire de tentatives de comprimer la suite. Une suite aléatoire est bien sûr non comprimable car son entropie est maximale, une compression cherchant à éliminer les redondances du message. Ce type de test est très peu utilisé en dehors des laboratoires de recherche car il n'apporte pas beaucoup d'éléments utilisables. Sa sortie est :

  Summary for 7 measurements:
   Mean fTU= 7.1831216 (7.1836656 expected)
  StDev fTU= 0.0015138 (0.0021339 expected)
c'est à dire l'effet de la compression sur l'entropie d'un échantillon.

Les tests de diehard sont les plus significatifs et les plus utilisés car les plus difficiles à passer. Malgré tout, ils ne peuvent donner que des indications statistiques sur les générateurs. Si l'un d'entre-eux doit faire l'objet d'une attention particulière, la meilleure façon est de le confier à un cryptologue. Les tests FIPS ne sont par contre pas très limitatifs : la fonction rand() du C les passe !

Pour tester un générateur de façon plus profonde, il faut étudier sa structure (c'est à dire tenter de le cryptanalyser). Il est néanmoins possible de tester de façon meilleure sa production, avec les tests de Knuth [10], une analyse spectrale (traitement du signal) ou une analyse de Kolmogorov-Smirnov.

3  Attaques

Il n'est traité ici que les possibilités d'attaques du générateur en lui-même. Il est toujours possible de contourner un générateur pseudo-aléatoire en ayant accès à la machine, à la mémoire si elle n'est pas sécurisée (la fonction free() qui libère de la mémoire ne prend pas soin de la vider).
On peut attaquer un générateur aléatoire uniquement en captant ses sorties, ou par entrée choisie. Pour un générateur pseudo-aléatoire, cela peut être possible par attaque sur les entrées, sur l'état interne ou par cryptanalyse directe. Quelques générateurs ont pu être cryptanalysés [11], notamment RSARef [12] et ANSI X9.17 [13] mais ils deumeurent tous sécurisés jusqu'à ce que que ne soit découverte la faille, comme un algorithme de chiffrement. Un exemple célèbre de problème survenu est le browser Netscape [14] qui permettait de décrypter les échanges réalisés avec SSL. Il s'agissait de restreindre fortement les possibilités pour le germe9.

Sur les entrées, on peut réaliser des attaques :

  • Entrée choisie : on restreint les possibilités de choix des entrées du générateur, par exemple quand il est utilisé avec un token ou que l'on peut simuler la source d'entropie utilisée. On restreint donc par exemple le nombre de clefs possibles.
  • Rejeu de l'entrée : cette attaque consiste à observer le fonctionnement du générateur en connaissant les entrées, et ainsi pouvoir déterminer ses sorties.
  • Entrée connue : il suffit alors de faire tourner le générateur pour connaître des sorties. Cela se passe par exemple quand l'entrée est l'activité d'un disque et que celle-ci peut être mesurée via le réseau.
  • Un attaquant qui peut accéder à l'entrée ne doit pas pouvoir connaître les sorties qu'il va générer.

Sur l'état interne :

  • Backtracking : Permet de retrouver les sorties passées.
  • Permanent compromise : Donne accès à toute la suite de nombres, les passés et les futurs.
  • Iterative : Si un attaquant connait l'état interne S et la sortie à l'instant t, il peut connaitre l'état S' à t+e.

Il est possible de se protéger contre ces attaques par des précautions simples qui font maintenant intégralement partie de la conception des générateurs, notamment :

  • Hacher les entrées, ce qui se fait partout, avec un compteur ou une variable dépendant du temps par exemple. Cette méthode ajoute une difficulté qui n'est pas insurmontable mais qui est indispensable. Il est aussi efficace d'utiliser une transformée de Fourier (FFT) sur les entrées.
  • Hacher les sorties, pour brouiller les pistes quant à la méthode de génération du PRNG.
  • Réinitialiser (reseed) les entrées périodiquement.
  • Faire attention à ce qui se passe autour du générateur, notamment la façon de l'initialiser. Il peut souvent être plus facile de récupérer un fichier où le germe est stocké en vue d'une utilisation, que de se livrer à un travail d'investigation plus coûteux.

4  Produits

4.1  Matériel

Les ordinateurs peuvent être utilisés en ``bricolant'' un peu : Il existe des programmes pour les ordinateurs disposant d'une carte son, en enregistrant le son provenant de l'entrée mais sans micro, captant ainsi le bruit ambiant. Par exemple, sur une station Sun (Sparc), la commande cat /dev/audio | compress produit des bits aléatoires.

Silicon Graphics produit des nombres aléatoires avec des Lava Lite Lamps [15]. Ce sont des lampes décoratives qui peuvent avoir un comportement chaotique dans certaines conditions, en les filmant avec une caméra numérique et en utilisant ces images en entrée d'une fonction de hachage, on produit des bits aléatoires [16]. N'importe quelle scène imprévisible, comme une rue fréquentée, peut produire les images aléatoires.

Ces générateurs produisent relativement peu de bits et ils sont en général utilisés pour initialiser un PRNG. Ils constituent en fait une solution amusante ou expérimentale à ce problème. Mais il est également possible et préférable d'utiliser une source matérielle directement.

Spécifiquements dédiés à cette tâche, les générateurs matériels disponibles pour les ordinateurs utilisent principalement les propriétés des jonctions dans les diodes ou les transistors. On récupère toujours un bruit qui peut être échantillonné et mis sous forme numérique à disposition d'un ordinateur via un port série, parallèle ou par une carte d'extension directement. De telles sources de bruit analogiques sont très souvent utilisées par les électroniciens. Leur numérisation produit des nombres aléatoires.

Les principaux exemples de ce qui existe sur le marché :

  • Atom-Age RNG Utilise le bruit d'une jonction et dispose d'un driver pour le périphérique /dev/random des systèmes BSD.
    Débit 7840 bits/s. Prix : $189. http://www.nshore.com/atom_age.htm
  • Protego SG-100 (Produit suédois) Ce générateur dispose de drivers pour Windows 95/NT, ainsi que des exemples de programmation en C++. Un support de Linux est en cours en GPL. Prix : $103.
    http://www.protego.se/sg100_en.htm
  • ConScire Utilise également le bruit thermique d'une jonction, et dispose de drivers pour DOS et Windows NT. Prix : $295. Débit de 5 à 10 Kb/s.
    http://home.rmi.net/~comscire/
  • Aware Elec Ce générateur utilise les compteurs geiger produits par la même société pour produire des nombre aléatoires en mesurant les désintégrations de noyaux atomiques radioactifs10.
    C'est certainement le meilleur générateur mais aussi le plus cher car il doit être accompagé de tout un outillage spécifique. Il n'est utilisé qu'en recherche. http://www.aw-el.com
  • Z5000 (WestPhal Electronic) (Produit allemand) sous la forme d'un générateur qui utilise également le bruit thermique et d'une carte ISA pour PC. Ce produit est un peu cher : $740 et a un débit de 5000 bits/s.
    http://home.t-online.de/home/p.westphal/zzeng.htm
  • Open Random Bit : C'est une puce basée sur les propriétés bruyantes d'un condensateur et qui utilise un microcontrôleur. De telles références sont disponibles chez beaucoup de fabricants de composants électroniques. Leur utilisation n'est néanmoins pas directe et n'intéresse que les concepteurs de systèmes. Débit : 1000 bits/s
    http://members.home.com/apa1/orb/

Intel produit également des générateurs aléatoires [17], utilisables sur des cartes mères à base de processeur Pentium. De tels générateurs intégrés à l'ordinateur feront très probablement partie de l'avenir, en étant intégrés sur les serveurs, les stations de travail, les PC et dans les cartes de communication pour les protocoles chiffrés. Voir par exemple [18] Des études ont également montré qu'on pouvait utiliser la mesure de la turbulence de l'air dans les disques des ordinateurs [19] mais cette technique n'est pas pratiquement utilisable.

4.2  Logiciel

Il existe une quantité de générateurs pseudo-aléatoires, des générateurs congruentiels standards des langages de programmation qui sont satisfaisants pour une utilisation non cryptographique, aux bibliothèques cryptographiques, aux générateurs dédiés, aux extensions comme la fonction random() ou la classe SecureRandom [20] du JDK. Ils utilisent pour la plupart deux réserves d'entropie, une dite rapide et une dite lente plus sécurisée, qui sont la sortie d'une fonction de hachage (généralement SHA, Secure Hash Algorithm) des données collectées. Les méthodes sont ensuite diverses et variées, souvent propre à un logiciel.

Sur le plan législatif, il est à noter que les générateurs pseudo-aléatoires ne souffrent pas de restriction d'utilisation ou d'exportation. Ils ne sont pas considérés comme des mécanismes cryptographiques à part entière.

Sont décris ici quelques générateurs parmi les plus utilisés car les meilleurs. Il existe beaucoup de constructions possibles sur le schéma décrit plus haut, ainsi que des constructions propres aux systèmes.

4.2.1  /dev/random

Ce périphérique est présent sur les unix libres : Linux et *BSD. Il est dérivé du générateur aléatoire de PGP [21]. Il fournir deux périphériques : /dev/random/ [22] en lui même qui fournit les bits qu'il a pu accumuler, et /dev/urandom qui en fournit tant que l'on en demande, c'est un générateur pseudo-aléatoire. Le premier périphérique fait partie du noyau et peut donc utiliser plus de sources (interruptions). Il est possible de le paramétrer pour ajouter ou retirer des sources, ce qui peut être utile pour une configuration très particulière. Ils sont utilisables depuis le fichier ou avec des routines en language C. La graine du générateur est sauvegardée dans un fichier à l'extinction du système (shutdown) pour être rechargée au démarrage suivant.

4.2.2  Cryptlib

La bibliothèque de fonctions cryptographiques Cryptlib [23]est gratuite et open-source pour une utilisation non commerciale. Comme d'autres (cryptix [24] par exemple), elle founit des mécanismes de collection d'entropie et de pseudo-aléatoire générateur pseudo-aléatoires. Les collecteurs d'entropie fonctionnent avec deux sources, une rapide et une lente plus sûre, et ce pour tous les systèmes d'exploitation possibles. Citons par exemple Windows, Unix, mais aussi BeOS, Mac OS, NSK, VM/CMS, ...

4.2.3  Yarrow

Yarrow [25] est né des travaux de la société Counterpane 11 [26] sur les attaques des générateurs pseudo-aléatoires. Ce générateur est toujours en développement, fait partie du domaine public et une implémentation a été réalisée pour Windows.

Le mécanisme de génération utilise un compteur et une clef qui représente l'état interne du générateur. La sortie est générée en chiffrant le compteur avec la clef. Après un nombre défini de blocs sortis, on change la clef. La version en cours utilise le triple-DES comme algorithme de chiffrement. La principale caractéristique est le mécanisme appelé Reseed control, contrôleur de réinitialisation. Il détermine le moment où le générateur doît être réinitialisé et de quelle façon : pour la réserve rapide, quand l'entropie d'une des sources a dépassé une valeur de seuil, on réinitialise avec celle-ci; pour la réserve lente, il faut qu'un nombre prédéfini de sources dépassent une autre valeur, plus élevée. Ceci garantit une réinitialisation optimale.

4.2.4  EGD (Entropy Gathering Daemon)

Il s'agit d'un programme prévu initialement pour GPG [27], GNU Privacy Guard, implémentation GNU de PGP, en remplacement de /dev/random notamment pour les Unix propriétaires, ce script perl met à la disposition des utilisateurs des bits d'entropie collectés par l'intermédiaire de commandes du type vmstat, ps, netstat ou tcpdump. On les récupère au moyen d'un socket Unix ou TCP et il est préférable que le daemon tourne sous l'identité root, ou en setuid chrooté pour plus de sûreté, pour avoir accès à un maximum d'informations. Des scripts sont mis à disposition, avec des commandes de contrôle et de lecture, bloquante ou non. Le collecteur d'entropie est inspiré de celui de la cryptlib sous unix, décrit ci-dessus.

4.2.5  Blum Blum Shub ou générateur à résidu quadratique

Le générateur de Blum Blum Shub [28] est à la fois simple et très efficace. On choisit deux grands nombres premiers p et q congrus à 3 modulo 4. On a alors n = p ×q et on choisit x non premier avec n aléatoire. alors x0 = x2 mod n est le germe du générateur et le iieme bit pseudo-aléatoire est le LSB de xi où xi = x2i-1 mod n.

Il a été montré qu'à moins de factoriser n, on ne peut trouver les sorties présentes, passées ou futures du générateur. Sa sécurité dépend de la difficulté à factoriser n et non pas à sa conception algorithmique. Il est possible de l'accélérer en utilisant non pas le LSB mais les log2 l bits les moins significatifs où l est la longueur de xi en bits. Il s'agit du meilleur rapport efficacité/complexité de mise en oeuvre.

Conclusion

Les générateurs de nombres aléatoires sont essentiels dans les applications cryptographiques. En tant que source de données secrètes (les clefs), et en tant que fonction d'un cryptosystème. Il est extrêmement difficile de définir un bon générateur ou de le tester; on ne peut se baser que sur les tests réputés empiriques et faire attention à l'actualité.

En cas de besoin de générateur aléatoire pour une utilisation plus que ponctuelle, principalement pour générer des clefs de session, il est préférable d'utiliser un des nombreux générateurs matériels existant. Ceux-ci se démocratisent peu à peu, commencent à être disponibles directement dans les équipements comme les cartes de chiffrement ou les cartes-mères d'ordinateur. Le concept de générateur pseudo-aléatoire ne peut être vu que comme un système provisoire, pour pallier au manque de non-déterminisme dans les machines.

John von Neumann a dit en 1951 : Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin. Sa conception de l'informatique est toujours et plus que jamais d'actualité.

References

[1]
Claude Shannon's famous 1948 article that founded Information Theory
(originally from: Bell System Technical Journal, July and October 1948)
[2]
Bruce Schneier, Applied Cryptography, John Wiley & Sons, Inc., 1996. Traduction française ISBN 2-84180-036-9.
[3]
ENT
http://www.fourmilab.ch/random/
[4]
George Marsaglia's Diehard tests
http://stat.fsu.edu/~geo/diehard.html
[5]
DiehardC The C version of DIEHARD
[6]
Balasubramanian Narasimhan
http://www-stat.stanford.edu/~naras/
[7]
National Institude of Standards and Technology
http://www.nist.gov/
[8]
FIPS 140-1
http://csrc.nist.gov/publications/fips/fips1401.htm
[9]
Maurer Universal Statistical Test, code-source C.
[10]
Knuth Donald E., The art of computer programming : Seminumerical Algorithms, Vol 2, Ch. 3, Addison Wesley Longman, 1998.
[11]
Cryptanalitics attacks on pseudo-random numbers generators
http://www.counterpane.com/
[12]
RSA Laboratories
ftp://ftp.funet.fi/pub/crypt/cryptography/asymmetric/rsa/rsaref2.tar.gz
[13]
``American National Standard for Financial Institution Key Management''
American Bankers Association, 1985.
[14]
Randomness and the Netscape Browser
http://www.ddj.com/
[15]
Lava World
http://www.lavaworld.com/
[16]
Welcome to Lavarand :
http://www.lavarnd.org/
[17]
Intel(R) Random Number Generator (RNG)
http://developer.intel.com/design/index.htm
[18]
Intel Corporation
http://www.intel.com/
[19]
SuperPower 6XW Motherboard i810
http://www.an-labs.com/
[20]
Don Davis, Ross Ihaka, Philip Fenstermacher, Cryptographic randomness from air turbulence in disk drives, Proceedings of Crypto, 1994.
http://world.std.com/~dtd/random/forward.pdf
[21]
The international PGP Home Page
http://www.pgpi.org/
[22]
/dev/random support page
http://www.openpgp.org/
[23]
Cryptlib encryption toolkit
http://www.cs.auckland.ac.nz/~pgut001/cryptlib/
[24]
Cryptix
http://www.cryptix.org/
[25]
Yarrow
http://www.counterpane.com/yarrow.html
[26]
Counterpane systems
http://www.counterpane.com/
[27]
The GNU Privacy Guard
http://www.gnupg.org/
[28]
L. Blum, M. Blum et M. Shub, A simple unpredictable pseudo-random number generator. SIAM Journal on Computing, vol 15, n°2, pp364-383, 1986.
[29]
Java 2 Platform SE v1.3: Class SecureRandom
http://java.sun.com/


Footnotes:

1Elles ne peuvent cependant pas être utilisées ici car connues ...

2Un texte en français a par exemple une entropie de quelques dixièmes de shannons par symbole, alors que quand il est compressé, celle-ci devient maximale et s'approche de 1 shannon par symbole

3Mouvement Brownien

4et dans bien d'autres !

5Secure Hash Algorithm

6Tout le monde a déjà écrit au début d'un programme en C l'instruction srand(time(0)); sous peine d'avoir toujours les mêmes nombres pour des nombres aléatoires

7On aurait 1 shannon par bit d'entropie pour une suite aléatoire infinie

8bloc de 4 bits ou demi-octet

9Netscape utilisait, sur les machines UNIX, le PID, PPID, le temps en secondes et microsecondes.

10faiblement ...

11Consultants et recherche en cryptologie, Bruce Schneier.

Last modified on 6 November 2007 at 15:54:38 CET - webmaster@hsc.fr
Information on this server - © 1989-2013 Hervé Schauer Consultants