Dans ce chapitre, vous allez apprendre à générer des nombres aléatoires de manière sécurisée. C'est une fonction essentielle en cryptographie et en sécurité informatique. Ça vous étonne de laisser faire le hasard pour garantir la sécurité ? En fait, c'est la meilleure méthode pour générer des nombres imprévisibles. Cependant, générer un nombre aléatoire ne veut pas dire faire n'importe quoi !
Pourquoi générer des nombres aléatoires ?
Vous utiliserez des nombres aléatoires en particulier pour :
Générer des clés secrètes
Les clés secrètes des systèmes de chiffrement, comme le One-Time Pad, doivent être choisies de manière aléatoire. Il en va de même pour les clés privées de chiffrement asymétrique ou de signature, et les clés secrètes de code d'authentification.
Générer des nonces cryptographiques
Un nonce est un nombre aléatoire destiné à n'être utilisé qu'une seule fois. Ils ne sont pas forcément secrets mais ils doivent généralement être imprévisibles. Ils sont souvent utilisés en cryptographie et sont cruciaux pour la sécurité. Selon leur rôle, ils sont appelés vecteurs d'initialisation, salts ou simplement randoms.
Générer des nombres imprévisibles en sécurité informatique
Les nombres aléatoires sécurisés ne sont pas uniquement utilisés en cryptographie, mais aussi dans la sécurité informatique en général.
Par exemple, lorsque vous créez un compte sur un site Internet, vous recevez en général un lien par email que vous devez ouvrir pour valider votre email. Ce lien contient un nombre aléatoire appelé jeton (token) CSRF. Lorsque vous cliquez sur le lien, vous prouvez au serveur que vous connaissez la valeur de ce jeton, et donc que vous avez bien accès à l'adresse email sur laquelle le lien contenant le jeton a été envoyé.
Simuler des jeux de hasard
Pour simuler un jeu de hasard avec un programme informatique, comme un jeu de cartes ou le résultat d'une loterie, vous devez vous assurer de générer de manière sécurisée des nombres aléatoires. Dans le cas contraire, un joueur pourrait tricher en prédisant le résultat du jeu !
Pour générer un nombre aléatoire en cryptographie, je vous propose d’abord de voir en détail les fonctions de génération de nombres aléatoires, puis les générations de nombres pseudo-aléatoires qui sont plus largement utilisées. Regardons pourquoi ensemble !
Quelques exemples de fonctions cryptographiquement non sécurisées : Math.random() en Java et JavaScript, random() en Python, rand() en PhP, rand() de glibc en C/C++.
Découvrez les fonctions de génération de nombres aléatoires
On dit que les algorithmes informatiques sont déterministes, c'est-à-dire qu'ils reproduisent toujours le même résultat si on leur fournit les mêmes paramètres en entrée. Pour obtenir un nombre aléatoire différent à chaque exécution en informatique, il faut donc ajouter une source d'entropie externe.
Pour trouver cette source d’entropie externe, les fonctions de génération de nombres aléatoires vont utiliser les phénomènes physiques aléatoires issus des périphériques d'un ordinateur. Par exemple, le logiciel de chiffrement PGP utilise notamment le mouvement de la souris et le temps entre deux frappes de touches au clavier pour générer un nombre aléatoire.
Une souris ? Un clavier ? Mmh d’accord, mais je croyais que ces fonctions s'exécutaient surtout sur des serveurs ?
Effectivement, et en général, les serveurs informatiques ne possèdent ni souris ni clavier, et les interactions humaines sont rares. Pour générer un nombre aléatoire, on utilise d'autres phénomènes physiques, comme le bruit électromagnétique d'un disque dur ou la température du processeur.
Il existe également des équipements matériels qui sont conçus pour générer des nombres aléatoires issus de l'entropie externe, qui utilisent par exemple les phénomènes radioactifs ou même quantiques. L'important est que ces phénomènes observables doivent être eux-mêmes imprévisibles.
Les résultats de ces phénomènes sont ensuite combinés entre eux pour obtenir un maximum d'entropie, c'est-à-dire de hasard, puis passent par des fonctions mathématiques appelées extracteurs de hasard, pour fournir en sortie une suite de bits aléatoires de 0 et de 1.
Vous verrez que les systèmes d'exploitation proposent souvent des fonctions de génération de nombres aléatoires sécurisés.
Sur Linux (et certains Unix), vous pouvez obtenir un nombre aléatoire issu de l'entropie externe, avec l'appel système Get-Random(). Si celui-ci n'existe pas dans votre version, il est possible de lire le fichier spécial /dev/urandom qui produit un nombre aléatoire issu de l'entropie externe. Il est conseillé de vérifier, avant de le lire la première fois, que suffisamment d'entropie a été collectée.
Sur Windows, il existe la fonction BCryptGenRandom (ou son prédécesseur RtlGenRandom sur les anciens systèmes) pour générer un nombre aléatoire issu de l'entropie externe.
La plupart des langages de programmation proposent également une fonction de génération de nombres aléatoires cryptographiquement sécurisés. Il existe enfin des bibliothèques cryptographiques dans pratiquement tous les langages. Consultez la documentation pour voir comment générer un nombre aléatoire sécurisé. Vous pouvez également avoir un aperçu général sur ce site.
Les fonctions de génération de nombres aléatoires sont très lentes et coûteuses en ressources, car elles sont basées sur des phénomènes physiques. Dans la pratique, il serait donc extrêmement long de générer des clés réellement aléatoires aussi longues. C'est pourquoi on utilise, en plus des fonctions de génération de nombres aléatoires, des fonctions de génération de nombres pseudo-aléatoires. Je vous propose de les voir dans la section suivante.
Utilisez la fonction de génération de nombres pseudo-aléatoires
Découvrez la fonction GNPA
Comme nous venons de le voir précédemment, les fonctions de générations de nombres aléatoires sont coûteuses en ressources et en temps. On ne les utilise donc que pour générer la graine des fonctions des générateurs de nombres pseudo-aléatoires. Ce sont ces dernières qui vont alors prendre le relais .
Générateur de nombres pseudo-aléatoires ? Graine ? J’ai pas tout compris là !
Les GNPA ont deux utilités :
un GNPA permet de générer un nombre pseudo-aléatoire d'une taille plus grande que le nombre aléatoire utilisé comme graine, et donc de limiter les ralentissements liés à l'entropie externe. On gagne donc du temps et des ressources ;
si on appelle un GNPA avec la même graine plusieurs fois, on obtiendra le même nombre pseudo-aléatoire en sortie à chaque fois. C'est pour ça qu'on qualifie ce nombre de "pseudo-aléatoire". On dit que le GNPA est déterministe.
Pour vous aider à comprendre, voici le fonctionnement d'un générateur de nombres pseudo-aléatoires.
Un GNPA est composé d'une fonction de transformation et d'un nombre appelé état interne. Tout d'abord, on fournit un nombre aléatoire appelé graine en entrée du GNPA qui initialise son état interne à la valeur de la graine.
La fonction de transformation prend son état interne en entrée et fournit en sortie un nouvel état interne et un nombre pseudo-aléatoire, qui est fourni en sortie du GNPA.
La fonction de transformation prend son nouvel état interne en entrée et fournit en sortie un nouvel état interne et un autre nombre pseudo-aléatoire, qui est fourni en sortie du GNPA, et ainsi de suite.
Découvrez les débuts du GNPA : la méthode des carrés médians
Un des premiers GNPA inventés fut la méthode des carrés médians.
Dans ce GNPA, la fonction de transformation est la puissance 2. On prend les k chiffres au milieu du résultat, avec k la taille (le nombre de chiffres) de la graine (k doit être pair). Le nombre obtenu est le nombre pseudo-aléatoire généré. C'est aussi le nouvel état interne. Puis on renouvelle l'opération de transformation.
Essayons avec un exemple concret :
Choisissez une graine, par exemple 46. Dans ce cas k=2 (car 46 est composé de 2 chiffres).
Élevez ce nombre au carré, vous obtenez 2116.
Prenez les 2 chiffres au milieu de 2116, donc 11.
Le premier nombre pseudo-aléatoire généré est 11. C'est aussi le nouvel état interne.
Élevez 11 au carré, vous obtenez 0121 (Si le carré est composé d'un nombre de chiffres inférieur à 2 fois k, ajoutez un ou plusieurs zéros devant le nombre).
Le deuxième nombre pseudo-aléatoire généré est 12 ; etc.
Ce GNPA a plusieurs défauts :
il entre rapidement dans un cycle. À partir de ce moment, il génère toujours les mêmes nombres. Le temps qu'un GNPA met à entrer dans un cycle est appelé la période. Tous les GNPA déterministes ont une période. Pour la méthode du carré médian, il est possible d'augmenter la période en augmentant la taille de la graine ;
l'état interne est révélé car c'est le nombre pseudo-aléatoire fourni en sortie. Par conséquent, il est possible de prédire tous les résultats suivants en observant un seul résultat du GNPA ;
un peu plus subtil, la fonction de transformation n'est pas une fonction à sens unique. Par conséquent, en observant un résultat du GNPA il est possible de savoir quels sont les nombres qui ont été générés avant. Par exemple, si on obtient 48, on sait que le nombre pseudo-aléatoire est un nombre dont le carré est *48*. Ce qui élimine beaucoup de possibilités.
Identifiez les règles d'un GNPA cryptographiquement sécurisé
Voici les règles d'un GNPA cryptographiquement sécurisé. Il doit :
être statistiquement aléatoire
Pour le vérifier, on applique des tests statistiques sur la suite générée, et on compare avec les résultats des mêmes tests sur une suite véritablement aléatoire. S'il n'y a pas de différences entre les deux, on dit que le GNPA est statistiquement indistinguable d'une fonction réellement aléatoire. Il existe de nombreux tests statistiques pour évaluer la qualité d'un GNPA, notamment la librairie TestU01. Un GNPA sécurisé doit réussir tous les tests statistiques possibles.
Voici quelques exemples de tests statistiques sur un GNPA :
La fréquence de bits de valeur 1 est-elle proche de 1/2 ?
La fréquence de deux bits de valeur 1 consécutifs est-elle proche de 1/4 ?
La fréquence avec laquelle le premier bit de la suite est 1 est-elle proche de 1/2 ?
être imprédictible
Cette condition peut être étudiée avec un test "next-bit" : connaissant les n premiers bits de sortie d'un GNPA, est-il possible de deviner le bit suivant n+1 ? Si un algorithme réussit ce test, il est considéré comme imprédictible. En particulier, les nombres générés par le GNPA ne doivent pas révéler d'information sur son état interne ;
être résistant à une attaque sur les résultats précédents
Si un attaquant parvient à obtenir l'état interne du GNPA à un instant n, il ne doit pas être capable de prédire le résultat du GNPA précédent, à l'instant n-1. En d'autres termes, la fonction de transformation du GNPA doit être une fonction à sens unique.
avoir une période suffisamment longue
Les GNPA actuels ont une période supérieure à 2exp64, ce qui dans la pratique est équivalent à une longueur infinie.
Comparez les deux types de GNPA
Les GNPA déterministes
Ce sont les GNPA qui n'ont pas d'entropie externe. Seule la graine fournie en entrée détermine le nombre pseudo-aléatoire en sortie. Ils sont notamment utilisés pour rallonger la taille d'une clé secrète.
On les utilise donc en fournissant en entrée la clé secrète, qui fait office de graine, et en recevant en sortie une clé pseudo-aléatoire beaucoup plus longue. Avec la même clé secrète, ils fournissent toujours la même clé pseudo-aléatoire.
Les GNPA non déterministes ou GNPA avec entropie
Ce sont des GNPA qui utilisent l'entropie externe comme graine initiale. De plus, l'état interne du GNPA est régulièrement modifié par ajout d'entropie externe. Ainsi, il est impossible de reproduire plusieurs fois le même résultat avec un GNPA non déterministe. Vous avez vu les GNA au début du chapitre.
En réalité, les GNA intègrent en interne un GNPA non déterministe. Ainsi, ils peuvent générer une grande quantité de clés secrètes sans avoir besoin de beaucoup d'entropie, ce qui les rend beaucoup plus rapides.
Vous les utiliserez donc généralement sans fournir de graine en entrée, car c'est le GNPA qui initialise la graine en utilisant l'entropie externe. Les nombres pseudo-aléatoires fournis en sortie peuvent être utilisés comme de vrais nombres aléatoires, et notamment comme clés secrètes de chiffrement.
En résumé
Pour générer un nombre aléatoire sécurisé, il faut utiliser un GNA (aussi appelé GNPA non déterministe) qui utilise l'entropie externe ;
un GNPA déterministe donnera toujours le même résultat si on lui donne la même graine en entrée. Il permet par exemple d'augmenter la taille d'une clé secrète ;
il ne faut jamais utiliser de générateur de nombres (aléatoires ou pseudo-aléatoires) non cryptographiquement sécurisé pour générer un nombre aléatoire qui doit être imprévisible ;
en particulier, il faut éviter les fonctions maths.random().
