Qu’est-ce qu’un nombre aléatoire ?

Avant d’aborder le cœur du sujet, en l’occurrence les nombres aléatoires dans un contexte de sécurité informatique, Commençons tout d’abord par quelques définitions :

aléatoire

Est aléatoire ce qui ne peut être prédit, en aucune façon.

déterministe

Est déterministe ce qui produit les mêmes résultats avec les mêmes données et les mêmes méthodes, en somme, ce qui peut être prédit.

générateur de nombres aléatoires

Un générateur de nombres aléatoires (ou RNG pour Random Number Generator) est un algorithme, un logiciel ou du matériel pouvant générer des nombres aléatoires.

générateur de nombres pseudo-aléatoires

Un générateur de nombres pseudo-aléatoires (ou PRNG pour Pseudo-Random Number Generator) est un générateur de nombres aléatoires qui produit une séquence de nombres presque aléatoires, qui ressemble à séquence de nombres aléatoires sans en être une. Parmi les propriétés des PRNG, on retrouve la capacité de reproduire une suite de nombres pseudo-aléatoires à partir d’une même graine initiale. Selon le contexte, cette propriété peut être tantôt une qualité, tantôt un défaut. Les ordinateurs étant déterministes, ils ne peuvent, en général, par eux-mêmes, produire des nombres aléatoires.

graine

Une graine est une valeur numérique servant à l’initialisation d’un générateur de nombres pseudo-aléatoires. Avec une même graine initiale, la séquence de nombres pseudo-aléatoires produite par le générateur de nombres pseudo-aléatoires est déterministe et peut par conséquent être reproduite.

nombre aléatoire

Un nombre aléatoire est un nombre qui ne peut être prédit.

séquence de nombres aléatoires

Une séquence de nombres aléatoires est une séquence de nombres choisis aléatoirement. Cette séquence a pour propriété que l’on ne peut prédire les nombres à venir à partir des nombres déjà connus, quels qu’ils soient. En informatique, on considère une (large) séquence aléatoire de 0 et de 1 comme une séquence dont la moitié des nombres est 1.

séquence de nombres pseudo-aléatoires

Une séquence de nombres pseudo-aléatoires est une séquence de nombres générés avec un générateur de nombres pseudo-aléatoires. Cette séquence a pour propriété que l’on peut prédire les nombres à venir à partir des nombres déjà connus et de la graine initiale.

véritable générateur de nombres aléatoires

Un véritable générateur de nombres aléatoires (ou TRNG pour True Random Number Generator) est un générateur matériel pouvant générer un nombre aléatoire de manière isolée ou sous forme d’une séquence de nombres aléatoires. Il s’agit nécessairement de générateurs matériels spécifiques ou intégrés s’appuyant sur des propriétés physiques connues pour être par définition aléatoires.

La sécurité informatique repose sur les nombres aléatoires

Si vous suivez l’actualité informatique depuis quelque temps, vous avez nécessairement entendu parler, en mai 2008, de la faille de sécurité touchant les Linux Debian concernant l’implémentation d’OpenSSL. En défaut un morceau de code simplifié à tort qui, au lieu de générer des nombres pseudo-aléatoires de grande qualité, a généré des nombres pseudo-aléatoires de piètre qualité, les rendant prévisibles. Il en a résulté une bien belle pagaille, puisque toutes les clés créées sur un système Linux Debian et les systèmes d’exploitation dérivés (dont Linux Ubuntu) ont dû être re-générés. Or, ces clés servent notamment à la sécurité des échanges commerciaux sur Internet, lorsque l’on effectue des achats en ligne, généralement lors de la saisie du code de la carte bancaire, afin d’empêcher un éventuel espion écoutant la communication de la comprendre. Cette faille pouvait autant permettre à un tiers de se faire passer pour votre banque avec un certificat usurpé, ou bien de déchiffrer vos communications cryptées avec celle-ci, et ceci s’appliquait à l’essentiel des échanges cryptés véhiculant sur Internet.

Plus récemment, en septembre 2008, vous avez peut-être mis à jour votre blog WordPress du fait d’une faille de sécurité touchant là encore les nombres pseudo-aléatoires. En effet, dans les versions précédentes, un intrus pouvait prendre le contrôle d’un blog WordPress en prédisant les nombres pseudo-aléatoires. Un intrus pouvait prétendre qu’un utilisateur du blog — par exemple son administrateur — avait perdu son mot de passe, ce qui engendrait un email de confirmation envoyé à l’utilisateur légitime lui demandant de cliquer sur un lien de validation généré de manière pseudo-aléatoire. Pseudo-aléatoire, certes, mais, dans certaines circonstances, prévisible par l’intrus. Or, une fois que l’intrus aura validé le lien pseudo-aléatoire qu’il aura prédit, il lui suffira de prédire le nouveau mot de passe et ainsi se connecter au blog, tout en empêchant l’utilisateur légitime du blog d’y accéder de nouveau, son mot de passe ayant été changé à son insu.

Les ordinateurs ont du mal à générer des nombres aléatoires

Le problème des ordinateurs sont qu’ils sont déterministes. Vous leur faites faire mille fois le même calcul, avec les mêmes données initiales, vous obtiendrez à chaque fois les mêmes résultats. Par conséquent, il est difficile pour les ordinateurs de générer des nombres aléatoires. D’où le terme généralement employé de nombres pseudo-aléatoires. En effet, il existe des algorithmes mathématiques plus ou moins complexes qui permettent de générer une séquence de nombres plus ou moins longue qui a l’air d’être aléatoire, alors qu’elle est en réalité déterministe.

Pour rendre cette séquence aléatoire, la plupart des utilisateurs initialisent la « graine » de ces algorithmes avec une valeur qu’ils espèrent aléatoire. Laquelle ? Par exemple, l’heure actuelle à la milliseconde près, dont on ne retient que les millisecondes. Cela ne fait que 1.000 valeurs différentes pour initialiser l’algorithme, et donc en réalité à peine mille séquences différentes de nombres aléatoires, donc très peu, finalement. On peut bien entendu utiliser une valeur de temps plus précise, mais si cela réduit le problème, cela ne le résout pas.

Solutions de génération de nombres pseudo-aléatoires

Il existe de nombreux algorithmes de génération de nombres pseudo-aléatoires utilisés en informatique :

• En langages C et C++, ainsi que dans de nombreux langages dérivés ou inspirés de ces deux langages de programmation, la fonction rand() permet de générer des nombres pseudo-aélatoires. Elle a cependant la réputation d’être lente et peu aléatoire.
• Certains proposent des implémentations optimisées de la fonction rand() afin d’en améliorer les performances en exploitant les spécificités matérielles du processeur. Cependant, la qualité des nombres aléatoires n’en est pas spécialement améliorée.
• L’algorithme de génération de nombres pseudo-aléatoires Mersenne Twister, implémenté généralement sous la forme d’une fonction mt_rand() proposée en de nombreux langages de programmation, dont le PHP, très répandu sur le web. Cet algorithme se veut plus rapide et plus aléatoire que la fonction rand() historique.
• De nombreuses bibliothèques prêtes à l’emploi existent, fournissant divers algorithmes de génération de nombres pseudo-aléatoires.

Néanmoins, dans tous les cas précités, une fois que l’on connaît la graine initiale de la séquence, on peut déterminer l’ensemble de la séquence pseudo-aléatoire, d’où des limitations dans la sécurité informatique qui repose sur l’aléatoire, à savoir, par définition, l’imprévisible. Il existe cependant des algorithmes permettant d’améliorer la qualité aléatoire des séquences de nombres pseudo-aléatoires, par exemple en appliquant un ou exclusif entre deux séquences de nombres pseudo-aléatoires.

Solutions de génération de véritables nombres aléatoires

Il existe par ailleurs des générateurs de véritables nombres aléatoires — généralement matériels — permettant de générer des nombres aléatoires ou du moins des nombres quasiment aléatoires. Ces solutions se basent sur diverses approches :

• le bruit blanc (dont la « neige » que vous voyez sur votre téléviseur lorsque vous l’allumez sur une chaîne qui n’existe pas), généralement basé sur la variation de température, amplifiée, d’un composant électronique, convertie en nombres aléatoires via une puce spécialisée ;
• diverses approches de la mécanique quantique, rendant la qualité des nombres aléatoires en principe optimale ;
• une lampe à lave filmée avec une webcam peut aussi servir à créer de manière aléatoire une graine devant servir à initialiser un générateur de nombres aléatoires (ce n’est pas une plaisanterie, c’est même un brevet de Silicon Graphics, Inc.) ;
• le bruit vidéo issu d’une webcam ou de capteurs photosensibles peut lui aussi servir de source de nombres aléatoires de qualité ;
• etc.

Application personnelle : générateur de mots de passe

A mon échelle, l’intérêt pour les nombres aléatoires a une application concrète : la génération de mots de passes aléatoires, donc imprévisibles. En effet, en tant qu’administrateur de nombreuses machines, serveurs, logiciels ou comptes informatiques, je suis régulièrement confronté à la problématique d’avoir à générer des mots de passe. Or, s’il existe de nombreux outils gratuits de génération de mots de passe en ligne, dont certains réellement excellents, ils ne sont pas parfaits.

En effet, ils considèrent que les mots de passe se doivent d’être exclusivement aléatoires. Si c’est une propriété nécessaire aux mots de passes de qualité, cela induit aussi un gros défaut : nous, êtres humains, avons une capacité de mémorisation limitée pour tout ce qui touche l’aléatoire. En conséquence, il nous est impossible de mémoriser de nombreux mots de passes composés de caractères aléatoires, d’autant que ceux-ci sont censés être régulièrement modifiés. Il en résulte que nous les notons (dans un cahier, sur un post-it collé à l’écran ou posé sous le clavier, voire même dans un fichier stocké généralement de manière non sécurisée sur l’ordinateur), alors que c’est généralement proscrit en matière de sécurité.

Aussi, je souhaite développer des scripts de génération de nombres aléatoires qui le sont sans l’être. Par exemple, un bon moyen, souvent recommandé par les administrateurs système à leurs utilisateurs, consiste à composer un mot de passe à base de deux mots courts pris au hasard et séparés par des chiffres ou des points de ponctuation. Ainsi, 9ChIeN+3PoMmE est plus facile à mémoriser qu’un mot de passe totalement aléatoire et de même longueur tel que ?5usp!cU64FaP, alors que les deux ont (presque) le même niveau de sécurité.