Sous Linux, les fichiers /dev/randomet les/dev/urandom fichiers sont les sources bloquantes et non bloquantes (respectivement) d'octets pseudo-aléatoires.
Ils peuvent être lus comme des fichiers normaux:
$ hexdump /dev/random
0000000 28eb d9e7 44bb 1ac9 d06f b943 f904 8ffa
0000010 5652 1f08 ccb8 9ee2 d85c 7c6b ddb2 bcbe
0000020 f841 bd90 9e7c 5be2 eecc e395 5971 ab7f
0000030 864f d402 74dd 1aa8 925d 8a80 de75 a0e3
0000040 cb64 4422 02f7 0c50 6174 f725 0653 2444
...
De nombreuses autres variantes Unix fournissent /dev/randomet /dev/urandomaussi, sans distinction de blocage / non-blocage.
L'équivalent Windows est la CryptGenRandom()fonction .
Comment le système d'exploitation génère-t-il un pseudo-aléatoire?
operating-systems
cryptography
randomness
security
entropy
Adam Matan
la source
la source
Réponses:
Le titre et le corps de votre question poser deux questions différentes: comment le système d' exploitation crée l' entropie (cela devrait vraiment être obtient l' entropie), et comment elle génère pseudo-aléatoire de cette entropie. Je vais commencer par expliquer la différence.
D'où vient le hasard?
Les générateurs de nombres aléatoires (RNG) sont de deux types:
Certaines applications, telles que les simulations de phénomènes physiques, peuvent se contenter de nombres aléatoires qui passent des tests statistiques. D'autres applications, comme la génération de clés cryptographiques, nécessitent une propriété plus forte: l' imprévisibilité . L'imprévisibilité est une propriété de sécurité, pas (seulement) une propriété statistique: cela signifie qu'un adversaire ne peut pas deviner la sortie du générateur de nombres aléatoires. (Plus précisément, vous pouvez mesurer la qualité du RNG en mesurant la probabilité qu'un adversaire devine chaque bit de sortie RNG. Si la probabilité est sensiblement différente de 1/2, le RNG est mauvais.)
Il y a des phénomènes physiques qui produisent des données aléatoires avec de bonnes propriétés statistiques - par exemple, la décroissance radioactive, ou certaines observations astronomiques de bruit de fond, ou les fluctuations des marchés boursiers. Ces mesures physiques nécessitent un conditionnement ( blanchiment ) pour transformer les distributions de probabilité biaisées en une distribution de probabilité uniforme. Une mesure physique connue de tout le monde n'est pas bonne pour la cryptographie: les fluctuations boursières peuvent être bonnes pour le geohashing , mais vous ne pouvez pas les utiliser pour générer des clés secrètes .
La cryptographie exige le secret : un adversaire ne doit pas être en mesure de découvrir les données qui ont été conditionnées. Il existe des générateurs de nombres pseudo-aléatoires cryptographiquement sécurisés (CSPRNG): des algorithmes PRNG dont la sortie peut être utilisée dans des applications cryptographiques, en plus d' avoir de bonnes propriétés statistiques . L'une des propriétés qui rendent un CSPRNG cryptographiquement sécurisé est que sa sortie ne permet pas à un adversaire de reconstruire l'état interne (connaître tous les bits sauf un produit par un CSPRNG n'aide pas à trouver le bit manquant). Je n'entrerai pas dans la façon de faire un CSPRNG car c'est le plus simple - vous pouvez suivre les recettes données par des cryptographes professionnels (utilisez un standard(comme Hash_DRBG, HMAC_DRBG ou CTR_DRBG de NIST SP 800-90A ) ou ANSI X9.31 PRNG . Le CSPRNG nécessite deux propriétés de son état pour être sécurisé:
Architecture d'un générateur de nombres aléatoires
En pratique, presque tous les bons générateurs de nombres aléatoires combinent un CSPRNG avec une ou plusieurs sources d'entropie . Pour résumer, l'entropie est une mesure de l'imprévisibilité d'une source de données. Baser un générateur de nombres aléatoires uniquement sur un RNG matériel est difficile:
Ainsi, le RNG dans un système d'exploitation fonctionne presque toujours comme ceci :
Un service de génération de nombres aléatoires fait partie du travail d'un système d'exploitation, car la collecte d'entropie nécessite un accès au matériel et les sources d'entropie constituent une ressource partagée: le système d'exploitation doit les assembler et en tirer une sortie adaptée aux applications. Un conditionnement pseudo-aléatoire des sources d'entropie est requis dans le système d'exploitation; il pourrait tout aussi bien être cryptographiquement sécurisé, car ce n'est pas fondamentalement plus difficile (et il est requis sur les systèmes d'exploitation où les applications ne se font pas confiance; sur les systèmes entièrement coopératifs, chaque application devrait exécuter son propre CSPRNG en interne si le système d'exploitation n'en a pas fourni de toute façon).
La plupart des systèmes avec stockage persistant chargeront une graine RNG à partir du disque (j'utiliserai «disque» comme abréviation pour tout type de stockage persistant) lors de leur démarrage et écraseront la graine avec de nouvelles données pseudo-aléatoires générées à partir de cette graine, ou si disponible avec des données aléatoires générées à partir de cette graine plus une autre source d'entropie. De cette façon, même si l'entropie n'est pas disponible après un redémarrage, l'entropie d'une session précédente est réutilisée.
Il faut faire attention à l'état sauvé. Rappelez-vous comment j'ai dit que l'état devait être linéaire? Si vous démarrez deux fois à partir du même état de disque, vous obtiendrez les mêmes sorties RNG. Si c'est une possibilité dans votre environnement, vous avez besoin d'une autre source d'entropie. Soyez prudent lors de la restauration à partir de sauvegardes ou lors du clonage d'une machine virtuelle . Une technique de clonage consiste à mélanger l'entropie stockée avec des données environnementales prévisibles mais uniques (par exemple, l'heure et l'adresse MAC); sachez que si les données environnementales sont prévisibles, toute personne en possession de l'état de la VM stockée peut reconstruire la graine d'une instance de VM forkée.
Sources d'entropie
Trouver (et utiliser correctement) des sources d'entropie est la partie la plus difficile de la génération de nombres aléatoires dans un système d'exploitation. Les sources d'entropie disponibles dépendront nécessairement du matériel et de l'environnement dans lequel le matériel fonctionne.
Si vous avez de la chance, votre matériel fournit un périphérique qui peut être utilisé comme source d'entropie: un générateur de nombres aléatoires matériel , dédié ou à usage latéral. Par exemple:
NIST SP800-90B fournit des directives de conception pour le RNG matériel. L'évaluation d'un RNG matériel est difficile . Les RNG matériels sont généralement des bêtes délicates, qui doivent être utilisées avec précaution: de nombreux types nécessitent un certain temps après le démarrage et un certain temps entre les lectures pour se déstabiliser, ils sont souvent sensibles aux conditions environnementales telles que la température, etc.
Les processeurs Intel x86-64 basés sur l' architecture Ivy Bridge fournissent l'
RdRandinstruction qui fournit la sortie d'un CSPRNG semé par le bruit thermique . La plupart des processeurs pour smartphones incluent une source d'entropie matérielle, bien qu'Android ne l'utilise pas toujours.Les systèmes qui ne disposent pas d'une source d'entropie forte doivent se contenter de combiner des sources d'entropie faibles et d'espérer ( s'assurer que ce serait un mot trop fort) qu'ils suffiront. Les mouvements aléatoires de la souris sont populaires pour les machines clientes, et vous avez peut-être vu la sécurité apparaître par certains programmes de cryptographie qui vous demandent de déplacer la souris (même si sur n'importe quel système d'exploitation PC du 21e siècle, le système d'exploitation aura accumulé l'entropie sans que l'application ait à déranger ).
Si vous voulez regarder un exemple, vous pouvez regarder Linux, mais attention, il n'est pas parfait . En particulier, il se
/dev/randombloque trop souvent (car il bloque jusqu'à ce que suffisamment d'entropie soit disponible, avec une notion d'entropie trop conservatrice), alors qu'il/dev/urandomest presque toujours bon sauf au premier démarrage mais ne donne aucune indication lorsqu'il n'a pas assez d'entropie. Linux possède des pilotes pour de nombreux périphériques HRNG , et accumule l'entropie de divers périphériques (y compris les périphériques d'entrée ) et les synchronisations de disque .Si vous disposez d'un stockage persistant (confidentiel), vous pouvez l'utiliser pour enregistrer l'entropie d'un démarrage à l'autre, comme indiqué ci-dessus. Le premier démarrage est une période délicate: le système peut être dans un état assez prévisible à ce stade, en particulier sur les appareils fabriqués en série qui fonctionnent essentiellement en dehors de l'usine de la même manière. Certains périphériques intégrés qui ont un stockage persistant sont provisionnés avec une graine initiale en usine (produite par un RNG fonctionnant sur un ordinateur en usine). Dans les environnements de serveurs virtualisés, l'entropie initiale peut être provisionnée lors de l'instanciation d'une machine virtuelle à partir de l'hôte ou d'un serveur d'entropie.
Les appareils mal ensemencés sont un problème répandu dans la pratique - une étude des clés RSA publiques a révélé que de nombreux serveurs et appareils avaient des clés qui étaient générées avec un RNG médiocre, très probablement un bon PRNG qui n'était pas suffisamment amorcé. En tant que concepteur de système d'exploitation, vous ne pouvez pas résoudre ce problème par vous-même: c'est le travail de l'entité qui contrôle la chaîne de déploiement de s'assurer que le RNG sera correctement amorcé au premier démarrage. Votre tâche en tant que concepteur de système d'exploitation est de fournir un RNG approprié, y compris une interface pour fournir cette première graine, et d'assurer une signalisation d'erreur appropriée si le RNG est utilisé avant qu'il ne soit correctement semé.
la source
En plus de la réponse de Gilles, des interruptions peuvent également être utilisées pour établir l'entropie. Sous Linux par exemple, lorsque vous ajoutez un gestionnaire d'interruption, vous pouvez définir si l'occurrence de cette interruption doit être utilisée comme contribution au pool d'entropie du noyau.
Bien sûr, cela ne devrait jamais être le cas avec des interruptions qu'un attaquant pourrait être en mesure de déterminer. Par exemple, à première vue, le trafic réseau (c'est-à-dire les interruptions qui en résultent) semble être une bonne source d'aléatoire. Cependant, un attaquant pourrait être en mesure de manipuler votre trafic de manière à pouvoir prédire le caractère aléatoire dont vous avez besoin pour une opération.
la source