RNG matériel vs logiciel

La première chose que vous mentionnez est une source de bruit matériel. La mesure de haute précision de certains phénomènes métastables suffit à générer des données imprévisibles. Cela peut être fait avec une diode Zener polarisée en inverse, avec des oscillateurs en anneau, avec un ADC, ou même avec un compteur Geiger. Cela peut même être fait en mesurant les retards au niveau de la nanoseconde dans le temps entre les frappes. Ces sources de bruit peuvent échouer si le matériel lui-même commence à tomber en panne. Par exemple, un transistor peut tomber en panne s'il n'est pas spécifiquement conçu pour fonctionner en sens inverse à des tensions élevées. Bien que ces techniques aient différents niveaux de fragilité, ce n'est pas ce qui est discuté dans le texte que vous avez cité.

Le deuxième type de RNG que vous mentionnez est un logiciel RNG appelé générateur de nombres pseudo-aléatoires (PRNG ^* ). Il s'agit d'un algorithme qui prend une graine , qui est comme une clé de chiffrement, et l'étend en un flux de données sans fin. Il essaie de s'assurer que les données ne peuvent pas être prédites, ou divisées en dehors du pur hasard, sans connaissance de la graine aléatoire secrète avec laquelle l'algorithme a commencé. Dans ce cas, le PRNG est implémenté dans un logiciel pur, il suffit donc d'introduire un bogue dans le code, ce dont parle le texte que vous avez cité. Il s'agit simplement d'un code fragile , risquant un échec complet si des modifications apportées au code s'écartent du comportement prévu de l'algorithme.

Un PRNG peut être considéré comme une nouvelle algorithme de cryptage ciblé. En fait, vous pouvez créer un PRNG sécurisé par cryptographie en utilisant un chiffrement comme AES pour crypter un compteur. Tant que la clé de chiffrement (graine) est secrète, la sortie ne peut pas être prédite et la graine ne peut pas être découverte. Quand on y pense de cette façon, il devient plus facile de comprendre comment un petit changement sans conséquence dans le code peut complètement briser la sécurité de l'algorithme.

Collecter le caractère aléatoire

Alors, comment les appareils modernes collectent-ils le caractère aléatoire? Prenons un serveur fonctionnant tranquillement dans un centre de données quelque part. Afin de prendre en charge des éléments tels que TLS, il a besoin d'une grande quantité de données totalement imprévisibles qui ne peuvent pas être distinguées d'un flux vraiment aléatoire. Sans une source de bruit matérielle dédiée, le caractère aléatoire doit provenir de l'intérieur. Les ordinateurs s'efforcent d'être pleinement déterministes, mais ils ont beaucoup d'entrées provenant d'appareils non déterministes. Entrez ... interruptions!

Dans le matériel moderne, une interruption est un signal émis par le matériel pour alerter le CPU d'un changement d'état. Cela permet au processeur d'éviter d'interroger rapidement chaque périphérique matériel pour les mises à jour et de croire à la place que le périphérique l'alerte de manière asynchrone le moment venu. Lorsqu'une interruption se produit, un gestionnaire d'interruption est appelé pour traiter le signal. Il s'avère que ce gestionnaire est l'endroit idéal pour obtenir le hasard! Lorsque vous mesurez la synchronisation des interruptions au niveau de la nanoseconde, vous pouvez rapidement obtenir un peu de hasard. En effet, des interruptions sont déclenchées pour toutes sortes de choses, des paquets arrivant sur le NIC aux données lues à partir d'un disque dur. Certaines de ces sources d'interruption sont hautement non déterministes, comme un disque dur qui repose sur le mouvement physique d'un actionneur.

Une fois que suffisamment de bits aléatoires ont été collectés par le système d'exploitation, une petite graine d'au moins 128 bits peuvent être introduits dans un PRNG cryptographiquement sécurisé pour générer un flux illimité de données pseudo-aléatoires. À moins que quelqu'un puisse prédire exactement quand chaque interruption passée s'est produite, avec une précision de l'ordre de la nanoseconde, il ne sera pas en mesure de dériver la graine et ne pourra pas prédire la sortie future du PRNG. Cela rend la sortie parfaitement adaptée aux clés TLS.

_{* Un PRNG axé sur la sécurité est appelé un PRNG cryptographiquement sécurisé, ou CSPRNG. L'utilisation d'un PRNG normal lorsqu'une application appelle un CSPRNG peut entraîner des failles de sécurité.}

Historiquement, les RNG matériels adaptés à la cryptographie n'étaient pas couramment disponibles sur le PC: par exemple, selon cette question, AMD n'a ajouté le support qu'il y a quelques années, de sorte que même aujourd'hui, un éditeur de logiciel peut " t supposons simplement qu'il sera disponible. C'est probablement pourquoi OpenSSL (comme indiqué dans votre devis) utilisait un logiciel RNG, ce qui le rendait vulnérable au bogue trouvé dans le code.

(Comme discuté en détail dans les commentaires, un PC standard contient un certain nombre de «sources d'entropie» qu'un logiciel RNG peut utiliser - et je crois qu'OpenSSL le fait, même si je ne suis pas très familier avec lui - mais de toute évidence dans ce scénario, un bogue dans le logiciel peut entraîner de mauvais nombres aléatoires, comme cela s'est produit.)

Il y a aussi des inquiétudes concernant le fait que les RNG matériels aient pu être détournés , amenant les gens à combiner les RNG matériels avec d'autres sources d'entropie plutôt que de les utiliser tels quels. (Le matériel de porte dérobée est également mentionné dans votre article lié, à quelques paragraphes du bit que vous avez cité.)

Il convient également de mentionner que les RNG matériels ne sont pas aussi simples à implémenter que votre question suggère ... d'une part, les implémentations naïves pourraient être vulnérables à diverses attaques physiques, par exemple, si vous générez des bits aléatoires basés sur des vibrations, que se passe-t-il si quelqu'un vise une échographie? Même dans des conditions idéales, il y aura probablement une sorte de biais dans les résultats qui pourrait rendre les bits générés dangereux pour une utilisation cryptographique.

C'est pourquoi les implémentations du monde réel utilisent le bruit matériel mais aussi le traitent cryptographiquement. Mais à ce stade, vous revenez à la question de savoir si l'algorithme (ou son implémentation) a été délibérément saboté, ou peut-être n'est-il pas aussi robuste qu'on le croit.

Parce qu'ils sont difficiles à tester

Bien qu'il soit facile de tester qu'un générateur de nombres aléatoires produit une sortie avec le bon format, déterminer s'il est statistiquement aléatoire est beaucoup plus complexe et peu susceptible d'être inclus dans une suite de tests automatisés. Beaucoup d'autres codes seront beaucoup plus évidents si vous le cassez.

La cryptographie doit être correcte

En général, s'assurer que le code est correct est difficile. Une grâce salvatrice pour beaucoup de code est que seule une petite proportion d'erreurs d'exactitude entraîne des vulnérabilités de sécurité. Mais avec le code cryptographique - y compris les générateurs de nombres aléatoires - de nombreuses erreurs d'exactitude entraîneront des vulnérabilités. Le code cryptographique doit être correct, pour être sécurisé, et s'assurer qu'il est correct est difficile.

Le responsable Debian a fait une erreur majeure

Le code n'est pas en fait si fragile. Pour qu'il soit rendu non sécurisé, il a fallu des défaillances majeures de la part du mainteneur. Simplement découper les lignes qui produisent des avertissements avec seulement des vérifications superficielles que rien n'est cassé, c'est plutôt de mauvaise qualité.

Modifier: ce n'était pas seulement le faute du mainteneur, voir le commentaire d'Angel

L'un des aspects les plus importants de tout générateur aléatoire est que la valeur de chaque bit aléatoire doit non seulement être complètement indépendante des valeurs de tous les autres bits qu'il génère, mais elle doit également être complètement indépendante de tout le reste dans l'univers, un adversaire pourrait observer ou influencer . Malheureusement, cette propriété est souvent l'une des plus difficiles à garantir. Le mieux que l'on puisse faire est généralement de générer des bits d'une manière qui est peu susceptible d'avoir une relation exploitable avec quoi que ce soit d'autre dans l'univers.

À titre d'exemple simple, si un adversaire avec un émetteur RF hautement focalisé avait une capacité à influencer votre générateur de nombres aléatoires de sorte que certains échantillons de son choix aient une probabilité de 95% d'en donner, tandis que le reste n'aurait qu'une probabilité de 5% de le faire. Si l'on devait simplement lire 128 bits à partir d'un tel générateur et les intégrer dans une clé de 128 bits, un attaquant qui focalisait une attaque par force brute sur des modèles de bits proches de celui utilisé pour influencer le générateur aurait une bien plus grande probabilité de succès rapide que si le générateur avait été impartial. Supposons, cependant, qu'au lieu de choisir les bits un à la fois, on choisisse des groupes de 7 bits et les corrige ensemble. Faire cela augmenterait sept fois le temps de génération d'une clé de 128 bits, mais l'influence d'un attaquant passerait de 95/5 à 74/26, réduisant considérablement la probabilité que la clé finisse par être proche du motif de bits de l'attaquant. essayer de forcer.

Comme alternative, supposons que l'on génère 128 bits aléatoires, les hache d'une manière ou d'une autre, puis les xor avec 128 autres bits aléatoires. Cela ne nécessiterait que la génération de 256 bits au lieu de 896, mais rendrait très difficile pour un attaquant d'exploiter tout biais dans le générateur. Même si l'énumération des modèles les plus probables de 95 000 000 000 bits de 128 bits aurait environ 50% de chances de correspondre à un groupe de 128 bits utilisé avant le hachage, ou celui avec lequel la valeur hachée a été xor'ed, la distribution finale après le xor il est peu probable qu'il y ait un biais exploitable ou des fuites d'informations.

Les RNG sécurisés couramment utilisés comme Linux / dev / random, ChaCha20 ou RdRand fonctionnent bien dans de nombreux cas conventionnels. Cependant, ils sont loin d'être à l'épreuve des idiots. Supposons que vous fassiez quelque chose de drôle, comme ne pas configurer votre horloge en temps réel lors de la génération de nombres aléatoires au démarrage. Si vous ne comprenez pas comment cela affectera votre RNG, quelqu'un qui le fait pourrait repartir avec votre clé privée. Il y a peu de place pour l'erreur ici, car une petite quantité de non-aléatoire peut compromettre un protocole cryptographique entier comme la génération de clés.

Tandis que les problèmes avec les implémentations naïves de générateurs de nombres aléatoires ou les interférences physiques dans votre matériel permettent de bonnes discussions, la plupart des vulnérabilités dans l'actualité avec les générateurs de nombres aléatoires, comme le problème Debian que vous avez mentionné n'est pas dû à ces problèmes. Les plus gros problèmes que j'ai vus à plusieurs reprises sont les développeurs qui pensent qu'ils ont une bonne source d'entropie pour amorcer le générateur de nombres aléatoires alors qu'ils ne le font pas, ce qui permet par erreur de découvrir et d'exploiter l'état du générateur aléatoire, ou le manque de tests rigoureux. du générateur de nombres aléatoires lui-même. La NSA n'a pas besoin de backdoor votre génération de clé si vous êtes l'un des 0,75% des clients TLS utilisant des clés à faible entropie. En résumé, les développeurs ignorent les quelques avertissements, voire aucun, et supposent que leur RNG fonctionnera dans n'importe quelle application.

Qu'est-ce que l'entropie et où en obtenir?

Puisque tous les programmes informatiques produisent les mêmes sorties étant donné les mêmes entrées, elles doivent lire à partir d'une source d'entropie (ou de données imprévisibles) dans le système d'exploitation ou le matériel. De nos jours, nous avons des choses comme la commande RdRand qui peuvent générer des dizaines ou des centaines de Mo d'entropie par seconde. Cependant, les appareils avec des générateurs de nombres aléatoires matériels comme le Ferranti Mark 1 en 1951 ou le Intel 82802 Firmware Hub en 1999 étaient l'exception plutôt que la règle jusqu'aux années 2010.

Donc, historiquement, les générateurs de nombres aléatoires reposent sur des sources d'entropie relativement lentes comme les entrées humaines ou les synchronisations de l'ordinateur, et les systèmes hérités peuvent avoir presque aucune fonction intégrée avec de bonnes sources d'entropie disponibles. / Dev / random de Linux, par exemple, peut utiliser l'heure de démarrage, la synchronisation des périphériques d'entrée humains, les synchronisations du disque, les synchronisations IRQ et même la modification du pool d'entropie par d'autres threads

À bien des égards, les générateurs de nombres aléatoires sont fragiles parce que ces méthodes standard pour obtenir l'entropie ne sont pas infaillibles. Tout ce qui rend ces sources d'entropie prévisibles ou limitées compromettra votre RNG, par exemple:

• Le bogue Debian que vous avez noté n'utilisait que l'identifiant de processus pour l'entropie.
• Si vous utilisez un système d'exploitation pré-configuré sans tête qui génère des clés au démarrage, de nombreuses sources d'entropie de Linux pourraient être prévisibles. source
• L'architecture de cryptographie Java d'Android s'est avérée nécessiter une initialisation explicite à partir d'une bonne source d'entropie sur certains appareils.
• Générer des nombres aléatoires trop rapidement sous Linux épuisera le pool d'entropie plus rapidement qu'il ne peut être reconstitué, conduisant à des nombres moins aléatoires.

Comprendre l'état et l'absence de réensemencement

Souvent, les RNG n'obtiennent pas de nouvelle entropie à chaque appel de fonction comme le fait / dev / random. Parfois, vous ne pouvez pas obtenir assez d'entropie assez rapidement, ou vous ne faites pas entièrement confiance à la source d'entropie. Au lieu de cela, le RNG est amorcé avec une source d'entropie connue, puis produit des valeurs indépendantes à partir de cette graine. Cependant, lorsque quelqu'un découvre l'état interne du générateur, les choses se passent mal, ce qui conduit à tout, du clonage de cartes à puce à la triche d'une machine à sous à Vegas.

Une attaque par débordement de tampon ou une attaque similaire peut révéler l'état du générateur de nombres aléatoires. L'apprentissage de l'état peut également être possible avec une attaque par force brute, en particulier si l'algorithme est connu et réversible, peut être calculé rapidement ou si un texte en clair est connu. C'était le cas pour les problèmes avec Windows XP, la bibliothèque Dropbear SSH, XorShift128 + dans Chrome et l ' algorithme Messerne twister, parmi tant d'autres.

Exiger une atténuation avancée pour ces attaques d'état connu rend le RNG fragile. La meilleure façon d'atténuer les attaques à l'état connu est de ne pas utiliser d'algorithme vulnérable (comme la plupart des CSRNG). Cette question explique également plus en détail ce qui rend un bon RNG sécurisé. Cependant, même les CSRNG ont parfois aussi des faiblesses (par exemple, la vulnérabilité RNG dans le noyau Linux 2.6.10). Par conséquent, la défense en profondeur nécessite des atténuations telles que l'utilisation d'états séparés pour les générateurs de nombres aléatoires (peut-être un par utilisateur), l'actualisation fréquente de la graine et des protections contre les attaques de canaux secondaires et les débordements de tampon.

Rejeter le blâme entre les développeurs et les utilisateurs

Souvent, ces RNG sont fragiles en raison d'une mauvaise communication des limitations entre les développeurs de bibliothèques ou les créateurs de systèmes d'exploitation qui ne peuvent pas concevoir un système infaillible et les utilisateurs qui attendent un. Linux, par exemple, oblige les utilisateurs à choisir entre une latence élevée / dev / random et potentiellement une faible entropie / dev / urandom. Autre exemple, PHP avant la version 5.3 n'avait pas de support pour les PRNG forts dans Windows via des interfaces telles que mcrypt_create_iv (), et avant la version 7.0 n'avait pas un bon CSPRNG intégré.

Difficulté de détection

Il y a un point de discussion populaire lors de la discussion des nombres aléatoires qui, pour un nombre vraiment aléatoire, chaque possibilité est également probable et il y a un nombre infini de modèles potentiels. Alors, comment pouvez-vous vraiment regarder une séquence et dire qu'elle n'est pas aléatoire? (Dilbert pertinent)

En réalité, la détection de motifs dans des nombres aléatoires est un domaine mature, bien qu'imparfait, et la question de savoir si le non-aléatoire peut être détecté a été abordée depuis M.G. Article de Kendall et B. Babington-Smith de 1938. Vous pouvez démontrer que certains types de modèles ne sont pas beaucoup plus susceptibles d’apparaître que le hasard. Par exemple, je peux vérifier si le chiffre 1 est plus courant que les autres chiffres, avec des seuils déterminés par un test du chi carré. Tant que ces modèles testés sont au moins probables à distance et que vous vérifiez un ensemble suffisamment long de nombres générés, la probabilité d'un faux positif est faible. Bien que certains problèmes cachés avec certains générateurs de nombres aléatoires puissent ne pas être détectés pendant des années, si vous avez effectué une analyse cryptographique de base et appliqué des tests de qualité industrielle comme indiqué dans cette question, vous Je ne peux pas vous tromper.

Cependant, les concepteurs peuvent aussi sous-estimer leurs attaquants (comment étiez-vous censé prédire que les gens procéderaient à une rétro-ingénierie et chronométreraient votre machine à sous?). Pire encore, parfois le générateur de nombres aléatoires ou la génération d'entropie n'est jamais inspecté par un expert, et seul le résultat de l'utilisation du RNG est examiné, comme lorsque les signatures du micrologiciel PS3 étaient signées avec une sortie «aléatoire» constante.

En fin de compte, le problème ici est similaire à celui d'une grande partie de la cybersécurité: vous avez un ensemble très complexe de protocoles, d'exigences et d'appareils pour les nombres aléatoires. Comme toujours, si vous ne comprenez pas la complexité, vous êtes vulnérable à un attaquant qui le comprend.