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

aux fins de la cryptographie, il faut que le flux soit "indiscernable du point de vue du calcul par rapport à des bits uniformément aléatoires". "Computationally" signifie qu'il ne doit pas être vraiment aléatoire, seulement qu'il apparaît à quiconque n'a pas accès à L'ordinateur de Dieu.

dans la pratique, cela signifie que le système doit d'abord rassembler une séquence de n bits vraiment aléatoires. n doit être assez grand pour contrecarrer exhaustif recherche, c'est-à-dire qu'il doit être impossible d'essayer toutes les combinaisons 2^n de n bits. Ceci est atteint, en ce qui concerne la technologie d'aujourd'hui, aussi longtemps que n est plus grand que 90-ou-ainsi, mais les cryptographes juste amour pouvoirs de deux, il est donc d'usage d'utiliser n = 128 .

Ces n des bits aléatoires sont obtenus par la collecte des "événements physiques" ce qui devrait être imprévisible, autant que la physique sont concernés. Habituellement, le timing est utilisé: le CPU a un compteur de cycles qui est mis à jour plusieurs milliards de fois par seconde, et certains événements se produisent avec une quantité inévitable de jitter (paquets réseau entrants, mouvements de souris, touches)...). Le système encode ces événements et les" comprime "en appliquant une fonction de hachage cryptographique sécurisée telle que SHA-256 (la sortie est alors tronquée pour donner nos bits n ). Quel ce qui importe ici, c'est que l'encodage des événements physiques a suffisamment de entropie : en gros, que lesdits événements auraient pu collectivement supposer au moins des combinaisons 2^n . La fonction de hachage, par sa définition, devrait faire un bon travail pour concentrer cette entropie dans une chaîne de bits n .

une fois que nous avons n bits, nous utilisons un PRNG (Pseudo-générateur de nombres aléatoires) pour lancer autant de bits que nécessaire. Un NNG est considéré comme étant cryptographiquement sûr si, en supposant qu'il fonctionne sur une clé de bits n assez large inconnue, sa sortie est computationnellement indiscernable des bits uniformément aléatoires. Dans les années 90, un choix populaire était RC4 , qui est très simple à mettre en œuvre, et assez rapide. 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 le projet eSTREAM consistait à rassembler de nouvelles conceptions pour PRNG (en fait, stream ciphers, parce que la plupart des stream ciphers consistent en un PRNG, dont la sortie est Xorée avec les données pour crypter), les documenter, et promouvoir l'analyse par les cryptographes. Le portefeuille eSTREAM contient sept conceptions PRNG qui ont été jugées assez sûres (c.-à-d. qu'elles 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é pour le logiciel". La bonne nouvelle est que bien que ces nouveaux PRNG semblent être beaucoup plus sûrs que RC4, ils sont aussi nettement plus rapides (nous parlons de centaines de mégaoctets par seconde, ici). Trois d'entre eux sont" libres pour tout usage " et le code source est fourni.

D'un point de vue de la conception, PRNG réutiliser la plupart des éléments des blocs de chiffrement. Les mêmes concepts d'avalanche et de diffusion de bits dans un large état interne sont utilisés. Par ailleurs, un PRNG décent peut être construit à partir d'un bloc de chiffrement: il suffit d'utiliser la séquence de bits n comme clé dans un bloc de chiffrement, et de chiffrer les valeurs successives d'un compteur (exprimé comme une séquence de bits m , si le bloc de chiffrement utilise m - blocs de bits). Ceci produit un flux pseudo-aléatoire de bits qui est computationnellement indiscernable du hasard, aussi longtemps que le chiffrement de bloc est sûr, et le flux produit n'est pas plus de m*2^(m / 2) bits (pour m = 128 , cela signifie environ 300 milliards de gigaoctets, donc c'est assez grand pour la plupart des buts). Ce type d'utilisation est connu sous le nom de counter mode (CTR) .

habituellement, un chiffrement de bloc en mode CTR n'est pas aussi rapide qu'un chiffrement de flux dédié (le point du chiffrement de flux est que, en perdant la flexibilité d'un chiffrement de bloc, une meilleure performance est attendue). Cependant, si vous avez l'un des CPU les plus récents D'Intel avec les instructions AES-NI (qui sont essentiellement une implémentation AES dans le matériel, intégré dans le CPU), puis AES avec le mode CTR donnera une vitesse imbattable (plusieurs gigaoctets par seconde).

tout d'abord, le point d'un PRNG cryptographiquement sécurisé est et non pour générer des séquences totalement imprévisibles. Comme vous l'avez noté, l'absence de quelque chose qui génère de grands volumes de (plus ou moins) véritable aléatoire ¹ rend cela impossible.

donc vous avez recours à quelque chose qui est seulement difficile à prédire. "Dur" signifie ici que cela prend un temps incommensurable par lequel peu importe ce que c'était nécessaire serait de toute façon obsolète. Il existe un certain nombre d'algorithmes mathématiques qui jouent un rôle à cet égard-vous pouvez avoir un aperçu si vous prenez quelques CSPRNGs bien connus et de regarder comment ils fonctionnent.

les variantes les plus courantes pour construire un tel PRNG sont:

• utilisant un chiffrement de flux, qui produit déjà un flux binaire pseudo-aléatoire (supposé sécurisé).
• utilisant un chiffrement de bloc en mode compteur

des fonctions de hachage sur un comptoir sont également parfois utilisées. Wikipedia a plus sur ce .

Exigences Générales sont juste qu'il est impossible de déterminer le vecteur d'initialisation original à partir du flux de bits d'un générateur et que le prochain bit ne peut pas être facilement prédit.

en ce qui concerne l'initialisation, la plupart des Csprng utilisent diverses sources disponibles sur le système, allant de choses vraiment aléatoires comme le bruit de ligne, interruptions ou autres événements dans le système à d'autres choses comme certains emplacements de mémoire, etc. 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 pendant un certain temps dans L'implémentation D'OpenSSL par Debian, ce qui a entraîné de graves problèmes de sécurité.

¹ qui a ses problèmes aussi et on doit être prudent dans l'élimination de biais comme des choses telles que la chaleur le bruit a des caractéristiques différentes selon la température-vous avez presque toujours un biais et besoin de l'éliminer. Et ce n'est pas une tâche insignifiante en soi.

pour qu'un générateur de nombres aléatoires soit considéré comme cryptographiquement sécurisé , in doit être sécurisé contre l'attaque par un adversaire qui connaît l'algorithme et un (grand) nombre de bits générés précédemment. Ce que cela signifie est que quelqu'un avec cette information ne peut reconstruire aucun de l'état interne caché du générateur et de donner des prédictions de ce que les prochains bits produits seront avec une précision de plus de 50%.

Normal les générateurs de nombres pseudo-aléatoires ne sont généralement pas cryptographiquement sûrs, car la reconstruction de l'état interne à partir de bits de sortie antérieurs est généralement triviale (souvent, l'état interne entier est juste le dernier n bits produit directement). Tout générateur de nombres aléatoires sans bonnes propriétés statistiques n'est pas non plus cryptographiquement sûr, car sa sortie est au moins partie prévisible, même sans connaître l'état interne.

ainsi, quant à la façon dont ils fonctionnent, toute bonne crypto le système peut être utilisé comme générateur de nombres aléatoires cryptographiquement sécurisé -- utilisez le système crypto pour chiffrer la sortie d'un générateur de nombres aléatoires 'normal'. Comme un adversaire ne peut pas reconstruire la sortie en clair du générateur de nombres aléatoires normal, il ne peut pas l'attaquer directement. Il s'agit d'une définition quelque peu circulaire et qui pose la question de savoir comment vous appuyez sur le système de crypto pour le maintenir en sécurité, ce qui est un tout autre problème.

Chaque générateur utilisera sa propre stratégie de semis, mais voici un peu de la documentation API de Windows sur CryptGenRandom

avec Microsoft CSPs, CryptGenRandom utilise le même nombre aléatoire générateur utilisé par d'autres composants de sécurité. Cela permet de nombreux processus visant à contribuer à la création d'un système semencier à l'échelle du système. CryptoAPI stocke un intermédiaire aléatoire à chaque utilisateur. Pour former les semences pour la nombre aléatoire Générateur, une application appelant fournit les bits qu'il pourrait ont-par exemple, la souris ou le clavier timing input-qui sont alors combiné avec le seed stocké et diverses données du système et l'utilisateur les données telles que l'ID de processus et l'ID de thread, l'horloge du système, le le temps du système, le compteur système, l'état de la mémoire, les clusters de disques libres, le haché environnement de l'utilisateur bloc. Ce résultat est utilisé pour amorcer le générateur de nombres pseudorandom (PRNG).

dans Windows Vista avec Le Service Pack 1 (SP1) et, plus tard, mise en œuvre du PRNG basé sur le contre-mode AES spécifié dans le NIST La Publication spéciale 800-90 est utilisée. Dans Windows Vista, Windows De Stockage Server 2003, et Windows XP, le PRNG précisé dans L'Information fédérale La norme de traitement (FIPS) 186-2 est utilisée. Si une application a accès à une bonne source aléatoire, il peut remplir le tampon données aléatoires avant D'appeler CryptGenRandom. Le CSP utilise ensuite ces données pour de plus amples aléatoire de ses intérieur de la graine. Il est acceptable d'omettre l' étape d'initialisation du tampon pbBuffer avant d'appeler CryptGenRandom.