Comment fonctionne un générateur de nombres aléatoires cryptographiquement sécurisé?

Question

Je comprends le fonctionnement des générateurs de nombres aléatoires standard. Mais quand on travaille avec la cryptographie, les nombres aléatoires doivent vraiment être aléatoires.

Je sais qu'il existe des instruments qui lisent le bruit blanc cosmique pour générer des hachages sécurisés, mais votre PC standard n'en est pas équipé.

Comment un générateur de nombres aléatoires cryptographiquement sécurisé obtient-il ses valeurs sans motif répétitif?

Answer 1

D'un point de vue cryptographique sécurisé nombre générateur aléatoire, que vous pouvez utiliser pour générer des clés de chiffrement, des ouvrages de collecte de l'entropie, imprévisible d'entrée à partir d'une source que d'autres personnes ne peuvent pas observer.

Par exemple, /dev/random(4) sur Linux recueille des informations à partir de la variation dans le calendrier des interruptions matérielles à partir de sources telles que les disques durs renvoi de données, des combinaisons de touches et les paquets réseau entrants. Cette approche est sûr à condition que le noyau n'a pas surestimer combien d'entropie qu'il a recueillies. Quelques années en arrière, les estimations de l'entropie à partir de différentes sources ont tous été réduits, ce qui les rend beaucoup plus conservateur. Voici une explication de la façon dont Linux estimations de l'entropie.

Aucun des ci-dessus est particulièrement haut débit. /dev/random(4) sans doute est sûr, mais il maintient que la sécurité en refusant de donner des données une fois qu'il ne peut pas être sûr que les données est bien aléatoire. Si vous souhaitez, par exemple, générer un lot de clés cryptographiques et nonces, alors vous aurez probablement besoin de recourir à du matériel générateurs de nombres aléatoires.

Souvent, du matériel Rng sont conçus sur l'échantillonnage à partir de la différence entre une paire d'oscillateurs qui sont en cours d'exécution à la même vitesse, mais dont le taux varie légèrement selon le bruit thermique. Si je me souviens bien, le générateur de nombre aléatoire qui est utilisé pour le royaume-UNI de l'obligation à prime de loterie, ERNIE, fonctionne de cette façon.

Alterner les régimes comprennent l'échantillonnage du bruit sur un CCD (voir lavaRND), la décroissance de la radioactivité (voir hotbits) ou le bruit atmosphérique (voir random.orgou il suffit de brancher une radio AM à l'écoute quelque part autre qu'une station de votre carte son). Ou vous pouvez demander directement à l'ordinateur de l'utilisateur à taper sur leur clavier comme un dérangé chimpanzé pour une minute, quelle que soit la flotte votre bateau.

Toutes mes excuses pour le manque de liens inline, mais apparemment je dois brûler plus de ma vie sur ce site avant que j'ai le droit de poster plus.

EDIT: d'assurage. Parce que certaines personnes ont eu la gentillesse de ce sac d'os en cliquant sur ce haut-pointu truc sur la gauche, je suis apparemment autorisé à mettre le reste des liens maintenant. Merci à vous les gens! ^_^

EDIT: comme il l'a souligné, je ne pensais parler de quelques-uns des les plus courantes de l'entropie de collecte de régimes. Thomas Pornin réponse et Johannes Rössel de répondre à la fois faire de bons emplois pour expliquer comment on peut aller sur la déformation d'réunis entropie dans la main afin de bits de nouveau.

Answer 2

Pour les fins, ce qui est nécessaire est que le flux est "mathématiquement impossible à distinguer de manière uniforme bits aléatoires". "Calcul" signifie qu'il a besoin de ne pas être vraiment au hasard, mais seulement qu'il apparaît ainsi à personne sans accès à Dieu de son propre ordinateur.

Dans la pratique, cela signifie que le système doit d'abord rassembler une séquence de n vraiment de bits aléatoires. n doit être assez large pour contrecarrer la recherche exhaustive, c'est à dire qu'il est impossible d'essayer tous les 2^n combinaisons de n bits. Cet objectif est atteint, en ce qui concerne la technologie d'aujourd'hui, aussi longtemps que n est supérieur à 90-ou-oui, mais les cryptographes juste l'amour des puissances de deux, de sorte qu'il est de coutume d'utiliser n = 128.

Ces n bits aléatoires sont obtenus par la collecte de "phénomènes physiques" qui devrait être imprévisible, autant que la physique sont concernés. Généralement, le timing est utilisé: le CPU a un compteur de cycle qui est mis à jour plusieurs milliards de fois par seconde, et certains événements se produisent avec une inévitable montant de la gigue (les paquets réseau entrants, les mouvements de la souris, clavier...). Le système de code pour ces événements, puis "compresse" en appliquant une fonction de hachage cryptographique sécurisé tels que SHA-256 (sortie est alors tronqué à donner notre n bits). Ce qui importe ici, c'est que l'encodage de la physique des événements a assez d' entropie: grosso modo, que ces événements pourrait avoir collectivement assumé au moins 2^n combinaisons. La fonction de hachage, de par sa définition, devrait faire un bon travail en se concentrant que l'entropie dans un n-chaîne de bits.

Une fois que nous avons n bits, on utilise un GÉNÉRATEUR (Pseudo-Random Number Generator) pour produire autant de bits que nécessaire. Un GÉNÉRATEUR est dit être cryptographique sécurisé si, en supposant qu'il fonctionne sur une assez large inconnu nbits de la clé, sa sortie est mathématiquement impossible à distinguer de manière uniforme de bits aléatoires. Dans les années 90, un choix populaire a été RC4, qui est très simple à mettre en œuvre, et assez rapidement. Cependant, il s'est avéré être mesurables biais, c'est à dire qu'il n'était pas comme indiscernables qu'on l'avait initialement souhaité. Le eSTREAM Projet a consisté en la collecte de nouveaux modèles pour PRNG (en fait des chiffrements de flux, parce que la plupart des chiffrements de flux consiste en un PRNG, dont la sortie est XORed avec les données à chiffrer), les documenter, et de la promotion de l'analyse par les cryptographes. Le eSTREAM Portefeuille contient sept PRNG dessins qui ont été jugés suffisamment sécurisé (c'est à dire ils ont résisté à l'analyse et les cryptographes ont tendance à avoir une bonne compréhension de pourquoi ils ont résisté). Parmi eux, quatre sont "optimisés pour les logiciels". La bonne nouvelle est que, si le nouveau GÉNÉRATEUR semblent être beaucoup plus sécurisé que RC4, ils sont aussi nettement plus rapide (nous parlons de centaines de mégaoctets par seconde, ici). Trois d'entre eux sont "libres de toute utilisation" et le code source est fourni.

À partir d'une conception de point de vue, PRNG réutiliser une grande partie des éléments d'algorithmes de chiffrement par bloc. Les mêmes concepts d'avalanche et de la diffusion de bits dans un grand état interne sont utilisés. Sinon, le GÉNÉRATEUR peut être construit à partir d'un algorithme de chiffrement par bloc: il suffit d'utiliser les nbits de la séquence de clés dans un algorithme de chiffrement par bloc, et de chiffrer les valeurs successives d'un compteur (exprimé en m-séquence de bits, si l'algorithme de chiffrement par bloc utilise les mbits de blocs). Cela produit un flux pseudo-aléatoire de bits qui est mathématiquement impossible à distinguer de hasard, aussi longtemps que l'algorithme de chiffrement par bloc est sûr, et le produit des flux n'est plus que de la m*2^(m/2) bits (pour m = 128, ce qui signifie qu'environ 300 milliards de giga-octets, de sorte que c'est assez grand pour la plupart). Ce genre d'utilisation est connu comme mode compteur (CTR).

Généralement, un algorithme de chiffrement par bloc dans la CTR mode n'est pas aussi rapide qu'un dédié de chiffrement de flux (le point de l'algorithme de chiffrement par flux, c'est que, par renoncer à la flexibilité d'un algorithme de chiffrement par bloc, l'amélioration des performances est prévu). Toutefois, si vous arrive d'avoir l'un des plus récent PROCESSEUR d'Intel avec l' AES-NI d' instructions (qui sont fondamentalement une mise en œuvre AES dans le matériel, l'intégré dans le PROCESSEUR), puis AES avec CTR mode de rendement imbattable vitesse (plusieurs giga-octets par seconde).

Answer 3

Tout d'abord, le point d'une cryptographique sécurisé PRNG est pas de générer tout à fait imprévisible séquences. Comme vous l'avez remarqué, l'absence de quelque chose qui génère d'importants volumes de (plus ou moins) vrai caractère aléatoire de¹ rend cela impossible.

Si vous avez recours à quelque chose qui est seulement difficile à prédire. "En dur", qui signifie ici qu'il faut unfeasibly de longue date à laquelle ce qui était nécessaire pour serait de toute façon obsolète. Il y a un certain nombre d'algorithmes mathématiques qui jouent un rôle dans ce domaine-vous pouvez obtenir un aperçu si vous prenez certains bien connus CSPRNGs et de regarder comment ils fonctionnent.

Les variantes les plus courantes pour en construire un PRNG sont:

• À l'aide d'un chiffrement de flux, qui déjà sorties d'un (soi-disant sécurisés) pseudo-aléatoire du flux de bits.
• À l'aide d'un algorithme de chiffrement par bloc en mode compteur

Les fonctions de hachage sur un contre, sont aussi parfois utilisés. Wikipédia a de plus sur cette.

Les exigences générales sont simplement qu'il est impossible de déterminer l'origine de vecteur d'initialisation à partir d'un générateur de flux de bits et que le bit suivant ne peut pas être facilement prévisibles.

Comme pour l'initialisation, la plupart des CSPRNGs utiliser diverses sources disponibles sur le système, allant de vraiment au hasard des choses comme le bruit d'une ligne, d'interruptions ou d'autres événements dans le système à d'autres choses comme certains emplacements de la mémoire, &c. Le vecteur d'initialisation est de préférence vraiment aléatoire et ne dépend pas d'un algorithme mathématique. Cette initialisation a été interrompue pour quelque temps dans Debian est la mise en œuvre d'OpenSSL qui a conduit à de graves problèmes de sécurité.

---

¹ Qui a aussi des problèmes et on doit être prudent dans l'élimination des préjugés que les choses telles que le bruit thermique a des caractéristiques différentes selon la température de l'-vous avez presque toujours la partialité et de la nécessité de l'éliminer. Et ce n'est pas une tâche triviale en lui-même.

Answer 4

Pour un générateur de nombre aléatoire pour être considéré comme cryptographique sécurisé, doit être sécurisée contre les attaques par un adversaire qui connaît l'algorithme et un (grand) nombre d'précédemment généré bits. Ce que cela signifie, c'est que quelqu'un avec cette information ne peut pas reconstruire l'un de l'caché état interne du générateur et de donner des prédictions de ce que la prochaine bits produit sera avec plus de 50% de précision.

Normal pseudo-générateurs de nombres aléatoires sont généralement pas cryptographique sécurisé, comme la reconstruction de l'état interne de déjà sortie de bits est généralement trivial (souvent, l'ensemble de l'état interne est juste les N derniers bits produit directement). Tout générateur de nombre aléatoire sans de bonnes propriétés statistiques est également pas cryptographique sécurisé, que sa sortie est au moins en partie prévisible, même sans connaître l'état interne.

Bref, la façon dont ils travaillent, toutes les bonnes crypto système peut être utilisé comme un point de vue cryptographique sécurisé générateur de nombre aléatoire -- utilisation de la crypto système pour chiffrer la sortie de "normal" générateur de nombre aléatoire. Depuis un adversaire ne peut pas reconstruire le texte en clair de sortie de la normale générateur de nombre aléatoire, il ne peut pas l'attaquer directement. C'est un peu circulaire définition pose la question de comment vous la clé de la crypto système pour les conserver de manière sécurisée, ce qui est un tout autre problème.

Answer 5

Chaque générateur d'utiliser ses propres semis stratégie, mais ici, c'est un peu de la documentation de l'API Windows sur CryptGenRandom

Avec Microsoft Dsp, CryptGenRandom utilise le même nombre aléatoire générateur utilisé par d'autres composants de sécurité. Cela permet à de nombreux les processus afin de contribuer à un système à l'échelle de la graine. CryptoAPI magasins un intermédiaire aléatoire à chaque utilisateur. Pour former les semences pour la générateur de nombres aléatoires, un appel de demande de fournitures bits, qu'il pourrait ont-par exemple, la souris ou le clavier de timing d'entrée-qui sont ensuite combiné avec à la fois les graines stockées et les différentes données du système et de l'utilisateur des données telles que l'ID de processus et thread ID, le système de l'horloge, l' système temps, le compteur du système, l'état de la mémoire, disque libre clusters, le haché environnement de l'utilisateur bloc. Ce résultat est utilisé pour amorcer le générateur de nombres pseudo-aléatoires (PRNG).

Dans Windows Vista avec Service Pack 1 (SP1) et, plus tard, la mise en œuvre de l'EI contre-mode de PRNG spécifié dans le NIST La Publication spéciale de l'800-90 est utilisé. Dans Windows Vista, Windows Storage Server 2003 et Windows XP, le PRNG spécifié dans l'Information du gouvernement Fédéral Processing Standard (FIPS) 186-2 est utilisé. Si une application a accès pour une bonne aléatoire de la source, il peut remplir le pbBuffer mémoire tampon avec de l' données aléatoires avant d'appeler CryptGenRandom. Le CSP utilise ensuite ces données pour de plus amples aléatoire interne de la graine. Il est acceptable d'omettre l' l'étape de l'initialisation de la pbBuffer tampon avant d'appeler CryptGenRandom.