 |
|
||
| You are here: Home > Resources > Articles > Random Numbers Generators |  |
 |
|
|
|
||||||||||
|
|||||||||||
|
|||||||||||
|
|||||||||||
|
Ce dernier cas nécessite beaucoup plus de précautions, car la connaissance de ces nombres peut compromettre un protocole cryptographique.
1 Le hasard1.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 :
1.2 Dans la natureD'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 ordinateurLes 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 logicielsDes 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 :
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.
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.
 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. 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érateurOn 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ématiquesUne 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 Testeurs2.2.1 Caractéristiques statistiquesDes 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 RecettesDiehardLes 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
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 AttaquesIl 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 :
Sur l'état interne :
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 :
4 Produits4.1 MatérielLes 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é :
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 LogicielIl 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/randomCe 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 CryptlibLa 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 YarrowYarrow [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 quadratiqueLe 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.
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é.
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-2007 Hervé Schauer Consultants |
|
![[Course]](/gif/icone.formations.png){kind=small}
![[Course]](/gif/icone.supports.png){kind=small}
]
![[Techno-watch]](/gif/icone.veille.png){kind=small}