==Phrack Inc.== Volume 0x0b, Issue 0x3b, Phile #0x0f of 0x12 |=--------=[ GENERATEURS CRYPTOGRAPHIQUES DE NOMBRES ALEATOIRES ]=-------=| |=-----------------------------------------------------------------------=| |=---------------=[ DrMungkee ]=---------------------=| ----| Introduction Chaque composant d'un cryptosystème est critique pour sa sécurité. Une seule erreur dans l'un pourrait faire tomber tous les autres. Les nombres aléatoires cryptographiques sont souvent utilisés comme clefs, padding, graines et vecteurs d'initialisation. Utiliser un bon GNA pour chacun de ces composants est essentiel. Il y a beaucoup de complications imposées par la prédictabilité des ordinateurs, mais il y a des moyens d'extraire les quelques bits sans se soucier de leur entropie, étant exponatiellement surpassée par redondance. L'angle de cet article couvre la conception, l'implémentation et l'analyse de GNA. Les GNA sujets à exploration seront NoiseSpunge, Intel RNG, le /dev/random de GNU/Linux, et Yarrow. ----[ Glossaire GNA - Générateur de nombres aléatoires [RNG] GNPA - Générateur de Nombres Pseudo-Aléatoires [PRNG] entropie - Information imprévisible redondance - Information prévisible ou probabiliste ----[ 1) Principes de conception des GNAs 1.0 ) Résume Toute une variété de facteurs entrent en jeu lors de la conception d'un GNA. Sa sortie doit être indiscernable du bruit blanc, il ne doit pas y avoir de moyen de prédire une quelonque de ses parties, et il ne peut y avoir aucun moyen de trouver les sorties précédentes ou futures de quelque sortie connue que ce soit. Si un GNA ne se conforme pas à ces critères, il n'est pas cryptographiquement sécurisé. Le mouvement de la souris est souvent utilisé comme entropie, mais si l'entropie est improprement interprétée par le GNA, il y a une redondance significatrice. Pour le démontrer, j'ai monitoré le mouvement de la souris à un intervalle de 100 millisecondes. Ces positions furent prises consécutivement alors que la souris était bougée [hectically] dans toutes les directions. Ces résultats parlent d'eux-mêmes : X-Position Y-Position 0000001011110101 0000000100101100 Seuls les 9 derniers bits de 0000001000000001 0000000100001110 chaque coordonnée 0000001101011111 0000001001101001 apparaissent au hasard. 0000001000100111 0000000111100100 0000001010101100 0000000011111110 0000000010000000 0000000111010011 0000001000111000 0000000100100111 0000000010001110 0000000100001111 0000000111010100 0000000011111000 0000000111100011 0000000100101010 La prochaine démonstration montre un rassemblement d'entropie plus réaliste en ne gardant que les 4 derniers bits significatifs des positions X et Y et en les XORisant avec un compteur haute-fréquence le monitorant à un intervalle au hasard : X Y Timer XORisé 1010 1001 00100110 01111111 0100 1100 00101010 00000110 0101 0010 01011111 01110101 1001 1100 10110000 11111100 0101 0100 11001110 11100010 0101 1100 01010000 01111100 1011 0000 01000100 00011100 0111 0111 00010111 00101000 0011 0101 01101011 01110110 0001 0001 11011000 11010001 Une bonne entropie est trouvée parce que 4 bits de chaque coordonnée représente un changement de 16 pixels dans chaque direction alors que supposer un mouvement de 65536 peut arriver dans toutes les directions. Le timer haute-résolution est bien utilisé parce que malgré qu'il soit complètement séquentiel, ses 8 derniers bits auront étés mis à jour très souvent durant quelques cycles d'horloge CPU, par conséquent rendant ces bits in-monitorable. Un XOR est utilisé pour combiner l'entropie des 2 sources car il a la très bonne propriété de fusoinner des nombres dans une voie qui préserve la dépendance de chaque bit. Les sources les plus communes d'entropie utilisées impliquent toutes l'interaction de l'utilisateur/utilisatrice ou des horloges à haute-fréquence d'une façon ou d'une autre. Un hybride des deux est toujours désirable. Les latences entre les événements déclenchés par l'utilisateur/utilisatrice (frappe au clavier, E/S disque, IRQs, clicks de souris) mesurés à haute-précision sont optimales à cause de la nature impredictible du comportement d'un(e) utilisateur/utilisatrice et du timing précis. Certaines sources peuvent sembler suffisamment aléatoire mais ne le sont pas dans les faits. Le trafic réseau est parfois utilisé mais cela n'est pas recommandé car il peut être monitoré et manipulé par une source extérieure. Un autre piège sont les horloges d'une précision à la millseconde : elles ne se mettent pas assez fréquemment à jour pour en faire bon usage. Un bon exemple d'imperfections de cueillette d'entropie est le Générateur de Nombres -pas-si-cryptographiquement-Aléatoire _cassé_ de Netscape. Netscape utilisait la date et l'heure avec ses process ID et ses process ID parents comme sa seule source d'entropie. Le process ID dans Win9x est une valeur habituellement au-dessous de 100 (incrémentée une fois pour chaque processus) qui est XORisé avec l'heure du jour où Windows fut demarré la première fois. Même si la fonction de hash aidait à générer une sortie qui parassait aléatoire, il est facile d'estimer les valeurs possibles pour l'entropie, de les hasher, et de prédire la sortie du GNA. Cela n'a pas d'importance que la sortie semble ou non aléatoire si la source est pauvre. 1.2) Estimations d'Entropie Evaluer la quantité de l'entropie recueillie ne devrait pas être trop regardé. Cela doit être fait pour empêcher le GNA de tenter de sortir plus d'entropie qu'il n'en a recueilli. Selon les paramètres du système, vous pouvez assigner des estimations de qualité à chacune de vos sources d'entropie. Par exemple, vous pouvez évaluer toute l'entropie générée par le clavier comme étant de taille 4 bits, sans faire attention à combien de bits d'entropie vous en avez collecté. Si le GNA est sur un serveur de données et utilise les E/S disques comme source d'entropie, il pourrait en dériver une estimation d'entropie proportionnelle au nombre d'utilisateurs accédant au disque pour empêcher l'accès séquentiel au disque de donner de l'entropie redondante. Les estimations d'entropie n'ont pas besoin d'être de la même taille que les entrées ou sorties de la collecte d'entropie.Elles repésentent une précaution de sûreté dans les caluls plus avancés. Il y a des méthodes alternatives pour estimer l'entropie. Vous pouvez dévier l'entropie d'une source pour qu'elle soit de meilleure qualité si la source n'a pas fourni d'entropie pendant une période excédant un certain intervalle. Vous pouvez accumuler de larges sommes d'entropie dans un tampon, le compresser, et dériver une estimation du taux de compression. Des tests statistiques comparant la dernière entropie entrée avec une large quantité d'entrées précédentes ne font pas grand-chose s'agissant de trouver la qualité de l'entrée courante, mais donnent au GNA une opportunité de rejeter les entrées qui augmentent la probabilité statistique du groupe d'entrée d'entropie. La meilleure approche à ceci est également un hybride. Une méthode d'estimation de qualité d'entropie n'est habituellement pas suffisante. Il y a des malgré tout des cas où une source d'entropie peut être supposée fournir une qualité consistante d'entropie. Dans ces cas, une taille fixée peut être assignée à toutes les entrée d'entropie en provenace de cette source, mais une analyse prudente devrait être faite avant que ne soit faite cette supposition. Il est plus sage de calculer de multiples estimations et supposer la plus petite valeur afin d'être plus précis. 1.3) Réserves d'Entropie Aucune source d'entropie ne devrait être supposée parfaite. Plus spécifiquement, dans un ordinateur, aucune source d'entropie ne devrait être supposée parfaite. C'est pourquoi l'entropie est collectée dans un tampon (réserve [pool] d'entropie) pour subir un traitement supplémentaire. Après que l'entropie ait été récupérée d'une source, elle est entrée dans un pool d'entropie. Le pool d'entropie doit faire plusieurs choses avec cette entrée. Il doit doit garder une trace de la somme de l'entropie contenue avec, mélanger la dernière entrée uniformément avec toutes les entrées précédentes contenues avec, et fournir un état au moins semblant aléatoire sans importance de la qualité de l'entropie entrée (les entrées modèles devraient toujours sembler aléatoire dans la réserve). Mélanger le contenu de la réserve d'entropie ne devrait ni sacrifier quelque entropie contenue que ce soit, ni être considéré ajoutant de l'entropie à son état. Si le mélange étand la réserve, l'estimation d'entropie de son contenu ne devrait pas changer. Seules les fonctions de collecte d'entropie son responsables d'augmenter l'entropie et s'en occuppent séparément. Les meilleurs candidats pour les fonctions de mélange sont les algorithmes de hash. Les algorithmes de hash devraient accepter n'importe quelle taille en entrée, et avoir une sortie de grande taille qui reflète la vitesse à laquelle l'entropie est collectée, et avoir une sortie non-déterministe. Pour préserver l'entropie collectée, la fonction de hash ne devrait pas prendre en entrée plus d'entropie que la taille de sa sortie. Ceci dit, si la fonction de hash sort 160 bits, il ne devrait pas être entré plus de 160 bits avant la sortie.si l'algorithme de hash est cryptographiquement sécurisé (ce qu'il devrait être) la sortie donnera le même compte d'entropie que l'entrée. Si la sortie est plus grande que l'entrée, alors l'état de la réserve ne peut être supposé avoir augmenté en entropie. Il y a plusieurs approches pour utiliser de grandes réserves d'entropie. Une approche implémente une réserve qui est hashée linéairement. Pour cette méthode, vous auriez besoin d'un tampon qui serait concaténé avec la dernière entrée d'entropie. Le hashage devrait être démarré à la fin du tampon. Le reste du tampon devrait être hashé, un morceau à la fois, en XORisant à chaque fois la sortie avec la sortie du hash du dernier bloc pour assurer que le pool entier est affecté par la dernière entrée, sans écrire par dessus une quelconque entropie précédente. Ceci n'est qu'une méthode d'exemple. Quelle que soit la procédure que vous choisissez, elle devra corresepondre à chaque critère mentionné dans les paragraphes précédents. Une autre approche pour maintenir une grande réserve d'entropie est d'utiliser de multiples contextes hashés qui sont utilisés pour affecter chacun des autres. Un usage commun est un pool qui contient de l'entropie non-manipulée. Une fois que cette réserve est pleine, elle est hashée et utilisée pour mettre chaque réserve à jour l'une l'autre, en hashant le contexte ou en XORisant. Ceci est fait en cascade pour autant de réserves que désiré, mais pour éviter de perdre la précédente entropie, certaines réserves ne devraient être mis à jour qu'après que sa réserve parente (celle qui l'a mise à jour) ait été mis à jour un certain nombre de fois. Par exemple, une fois que le premier pool hashé ait été mis à jour 8 fois, un second pool peut être mis à jour. Une fois que le second pool hashé ait été mis à jour 3 fois, il peut mettre à jour un troisième pool. Avec cette méthode, le troisième pool contient de l'entropie des 24 dernières mises à jour d'entropie. Ceci conserve moins d'entropie (limitée par la taille des contextes de hash) mais fournit une entropie de meilleure qualité. L'entropie est de meilleure qualité parce que la source de l'entropie contenue dans la troisème réserve est complètement dépendante de 24 entrées d'entropie. Entrer de l'entropie dans un pool est usuellement appelé mise à jour ou semance. Les pools d'entropie combinés avec la fonction de sortie par eux-mêmes sont en fait des GNPAs. Ce que fait un GNA est le traitement de la collecte d'entropie qui obtient de véritables graines aléatoires. Tant qu'une bonne entropie est entrée, le GNA aura une période (ou un modèle de sortie) infinie, contrairement aux GNPAs qui ont un point semi-fixé à partir duquel ils commenceront à répéter toutes les sorties précédentes dans le même ordre. [NDT : J'ai eu un cours à la fac' sur les Générateurs de Nombres Pseudo-Alétoires, si je retrouve le PDF je l'ajouterai dans les références] Les réserves d'entropie sont la clé pour empêcher toute sortie du GNA, future ou précédente, d'être prédite. Les attaques contre un GNA pour déterminer les sorties précédentes ou futures sont toutes basées sur la conaissance du pool d'entropie, des entrées d'entropie ou des sorties précédentes. La réserve devrait être conçue pour pour empêcher la conaissance de son état courant de quiconque compromettant ou toute ses sorties futures. Pour ceci, les réserves d'entropie devraient se soumettre à une modification drastique de temps à autre en effaçant tout ou partie de son entropie. Ceci est appelé re-semence. La re-semance devrait _toujours_ remplacer l'entropie qui est effacée avec de l'entropie fraîche avant de la faire sortir. Si l'entropie n'est pas remplacée, la réserve sera dans un état sévèrement fragile. Un GNA n'a pas besoin de re-semencer, mais s'il ne le fait pas, il doit y avoir de l'entropie ajoutée à un taux meilleur que la sortie du GNA. La re-semence ne devrait arriver qu'après que suffisemment d'entropie inutilisée ait été accumulée pour remplir une grande portion du pool, et l'estimation d'entropie devrait être ajustée à la taille estimée de l'entropie entrée. La re-semence ne devrait pas arriver très souvent, et seulement basée sur le nombre de bits sortis par le GNA et la taille du pool. Une estimation sûre sur la fréquence de re-semence d'un GNA serait après que 95% de la taille de l'entropie entrée ait été sortie. Cette estimation suppose que de l'entropie est ajoutée au pool au sein des sorties du GNA. Si ce n'est pas le cas, la re-semance devrait arriver plus souvent. Moins on entre d'entropie entre les sorties, plus il y a de chances qu'un attaquant ayant trouvé une sortie trouve la sortie précédente (ce qui peut être refait encascade après chaque sortie trouvée). 1.4) Fonctions de Sortie La sortie d'un GNA devrait être passée au travers d'une fonction à sens unique. La sortie d'une fonction à sens unique est dérivée de son entrée, mais cette entrée est non-dérivable par calcul d'ordinateur en partant de sa sortie [NDT : sous entendu : trop long]. Les focntions de hash à sens unques sont parfaites pour ceci. Des méthodes plus complexes compliquent en utilisant des portions de la réserve comme donnée-clef envoyées à un algorithme de cryptage symmétrique qui crypte une autre portion de la réserve et sort le texte crypté. L'expansion-compression est également une fonction à sens unique très efficace. Pour ceci vous pouvez utiliser des morceaux de la réserve comme graine pour un GNPA et générer plusieurss sorties (chacune de la taille de la graine du GNPA) et et tous les entrer ensuite dans une fonction de hash et en sortir le résultat. C'est efficace parce que plusieurs états intermédiaires (étendus) pourraint donner le même hash en sortie, mais un seul état initial (avant l'expansion) peut donner cet état intermédiaire. A chaque fois que le GNA donne une sortie, l'estimation de son entropie devrait être décrémentée par la taille de la sortie. Ceci est fait avec la supposition que que la sortie est entièrement constituée d'entropie. Parce que l'entropie de cette sortie est toujours dans la réserve, elle est à présent redondante et ne peut plus être supposée comme entropie (dans la réserve). Si la réserve fait 512 bits, et que que 160 bits d'entropie sont utilisés à chaque sortie, alors preque tout le hash d'entropie a été utilisé après 3 sorties et la réserve devrait être re-semancée. Il y a un problème possible presque inssurmontable qui se produit lors de l'implémentation des réserves d'entropie : il n'y a aucun moyen de déterminer quels bits d'entropie ont été sortis, et ceux qui ne l'ont pas été. Le meilleur moyen d'annuler les symtômes de ce problème est de rendre impossible de savoir quand l'entropie a été utilisée plus d'une fois en se basant sur la sortie du GNA. Lorsque qu'une sortie se produit, l'état de la réserve doit être permuté donc les sorties consécutives qans aucune entropie ajoutée ou re-semée ne donnera des sorties de GNA identiques. La permutation de l'état de la réserve doit être une fonction à sens unique et doit appliquer les mêmes concepts et critères que ceux utilisés dans la fonction de sortie. La taille de l'entropie de la réserve est toujours supposée être identique après la permutation tant que la procédure suit les critères. 1.5) Implémentation Tout l'effort fournit dans un GNA bien conçu est inutile s'il n'est pas implémenté proprement. Trois couches de l'implémentation seront couvertes : média, matériel/logiciel, et usage de la sortie. Chaque média de stockage et de communication représente un risque dans un état non-crypté. La liste suivante liste plusieurs degrés de risque assignés aux média de communication et de stockage. Les risques sont assignés comme ceci : 0 - aucun risque 1 - risque faible 2 - risque moyen 3 - risque important MEDIA RISQUE -------------------------------------- RAM 0 *& Disque dur 1 *& Mémoire partagée 1 *& Disques amovibles 2 LAN 2 & WAN 3 Le risque de tout média proprement crypté est 0. * Si le média de stockage est sur un ordinateur connecté à un réseau, le risque est augmenté de 1. & Si un accès physique est possible (ordinateur/LAN), le risque est augmenté de 1. Le risque le plus fort de chaque média devrait être considéré comme le risque de l'implémentation (lien le plus faible, au revoir !) [NDT :je puis assurer aux lecteurs/lectrices que ce texte n'a pas été écrit, ni traduit, par un fanatique de Laurence Boccholini sur le retour.] Un risque important n'est pas acceptable. Un risque moyen est acceptable, cela dépend de la valeur de la sortie du GNA (Qu'est que qui a de la valeur pour un attaquant ?). Un journal intime peut être facilement tenir si vous n'avez pas de squelettes dans votre placard. Les secrets industriels ne devraient utiliser que des GNAs de risque 0. Le risque acceptable est généralement à la charge du/de la programmeur/prgrammeuse, mais l'utilisateur devrait être conscient de son choix. Les GNAs matériels devraient être étanches à la falsification. Si une quelconque modification physique est tentée, le GNA devrait ne plus rien sortir.Cette précaustion évite la manipulation de l'état et le la sortie de la réserve d'entropie. Il ne devrait avoir aucun moyen de monitorer le GNA matériel au travers de fréquences, de radiation, de tension ou de toute autre émission générée par le GNA. N'importe laquelle de celles-ci pourrait être utilisée comme source d'information avec laquelle la réserve d'entropie ou la sortie du GNA pourraient être compromises. Pour éviter ceci, tous les GNA matériels devraient être blindé. Les implémentations logicielles peuvent être très astucieuses. Le reverse-engineering restera un problème jusqu'à ce que la signature digitale des fichiers exécutables sera implémentée au niveau du système d'exploitation. Avant cela, toute tentative au profit du/de la programmeur/programmeuse pour éviter le reverse-engineering du logiciel de GNA ne fera que retarder l'innévitable. IL est tojours très important le/la programmeur/programmeuse fasse attention en écrivant le logiciel d'avoir le plus petit facteur de risque possible (le classement tient compte du reverse-engineering du logiciel). //Ce qui suit s'applique aux GNAs séparés de l'application qui les appelle. Le GNA doit faire spécialement attention de s'assurer que seul un programe a accès aux sorties du GNA. La méthode par laquelle les données sont transférées depuis le GNA jusqu'au programme ne doit pas succomber à l'observation. Les sorties distingtes sont habituellement garanties par la fonction de sortie, mais parfois la sortie est copiée dans un tampon temporaire. Il serait peut-être possible de ruser un GNA en conservant de tampon, ou en le copiant autre part, fournissant une observation facile. Une solution rapide pour une application est de crypter la sortie du GNA et d'implémenter un [full key-esrow] entre le GNA et l'application appelante et être toujours vulnérable à un hack. L'espèce de _prévention_ qu'un(e) programmeur/programmeuse incorpore dans le logiciel ne sert que comme une barrière de sécurité routière, mais c'est souvent suffisant pour décourager 99,9% de ses utilisateurs de tenter de compromettre la sécurité. On ne peut pas faire grand-chose contre les 0,1% qui peuvent encore manipuler le logiciel parce qu'il y aura toujours un moyen de cracker les logiciels. 1.6) Analyse Il y a deux aspects important pour analyser un GNA : l'aléatoirité et la sécurité. Pour évaluer l'aléatoirité d'un GNA, on à habituellement recours à l'analyse statistique de l'entrée (traitement de la collecte d'entropie) et la sortie (fonction de sortie) du GNA. Pour évaluer sa sécurité, on chercherait des défauts dans sa collecte d'entropie, dans la réserve d'entropie, dans la fonction de mélange, et dans la fonction de sortie, qui autoriserait un(e) attaquant(e) à trouver les entrées passées, présentes ou futures par tout moyen possible.Il n'y a aucune garantie de l'efficacité d'aucun de ces aspects. La seule chose certaine est qu'une fois le GNA cassé, il est cassé ; avant cela, vous pouvez seulement spéculer. Il y a des tests spécifiques et disponibles sur Internet appropriés pour le test de l'aléatoirité des données. La plupart requièrent un grand échantillon de données stockées dans un fichier qour dériver des résultats significatifs. Une valeur probabiliste est obtenue au travers de l'analyse statistique de l'échantillon. Cette valeur est habituellement sous la forme de P, un nombre à virgule flottante entre 0 et 1. Les tests sont faits dans différantes tailles de blocs usuellement entre 8 et 32 bits. La précision de P varies d'un test à l'autre. Une valeur de P proche de 0,5 est ce qui est habituellement désiré. Lorsque P est proche de 0,5, la probabilité est à son milieu et il n'y a pas d'inclinaison vers 0 ou 1. Cela peut souvent arriver avec des données purement aléatoires. S'il était impossible d'obtenir une valeur proche de 0 ou 1, le GNA serait de toute façon troué. Ceci parce que lorsque les données sont complètement aléatoires, toutes les sorties sont à l'équiprobabilité. C'est la raison pour laquelle les sorties modelées sont possibles. Lorsque P n'est pas suffisamment satisfaisant, de nouveaux échantillons devraient être créés et testés. Si les autres échantillons donnent de mauvais P alors le GNA doit probablement avoir une sortie déterministe et ne devrait pas être utilisé. DieHard offre une armada de 15 tests qui utilisent des valeurs de P. Les autres tests décrits ici donnent un entier et sa cible. Plus l'entier est proche de sa cible mieux c'est. Un exemple de ceci est le Test Statitisque Universel Maurer. Le problème avec les tests statistques est que tout bon GNPA ou fonction de hash les passera facilement sans aucune entropie. Même si la sortie est non-déterministe le GNA n'est qu'un GNA s'il ne peut être prédit. Pour cette raison, l'entropie du GNA devrait aussi bien être non-déterministe. Sans que la source d'entropie ne puisse être garantit fonctionner proprement, il est il est prudent d'utiliser les mêmes tests sur l'entropie brute elle-même. En faisant ceci vous pouvez atteindre un niveau de confiance suffisant à propos de l'aléatoirité. Malgré tout, un gros speed-bump vous regarde droit dans les yeux lorsque vous tentez de le faire. L'entropie est souvent collectée à un pas très lent, rendat la collecte d'un échantillon suffisamment grand extrêmement fastidieux et dans certaine circonstances il peut ne même pas en valoir la peine. Que ce soit le cas ou pas, il est logique de scruter intelligemment les sources d'entropie, plutôt que de dépendre de tests statistiques (qui ne peuvent rien garantir) pour trouver des défauts (voir 1.1). Evaluer la sécurité d'un GNA est une tâche complexe avec des milieux infinis et une seule fin : un break. Les impairs sont toujours bien empilés contre un GNA. Pas d'importance n'a combien de provisions sont faites pour éviter les breaks, de nouvelles attaques émergeront toujours de ce GNA ou d'un autre. Tous les aspects du GNA doit être étudié avec attention, de la collecte d'entropie jusqu'à la délivrance de la sortie du GNA. Tous les composants devraient être testés individuellement et ensuite comme un groupe. Le tests incluent la possibilité d'un hack qui peut altérer ou monitrer la collecte d'entropuie et la cryptanalyse des fonctions de mélange et de sortie. La plupart des breaks sont découverts en conditions de laboratoire. Ceux-ci sont appelés breaks accadémiques et sont habituellement le résultat de mois (souvent d'années) de travail douloureux effectué par des cryptanalystes ayant des années d'expérience. La meilleure chose à faire est de le GNA concevoir avec attention du début à la fin avec la sécurité en tête. Comme les limites des mathématiques et de la cryptanalyse sont souvent atteintes en testant, les avancées en science pourraient [reak havoc] sur votre GNA. Par exemple, le scan Tempest pourrait être utilisé par un attaquant pour suivre les frappes au clavier et les positions de la souris. Des découvertes peuvent toujours être faites dans l'analyse du bruit blanc, éventuellement. Ces breaks sont habituellement trouvés par des étudiants et des professionnels qui ne cherchent qu'à rendre leurs connaissances disponibles avant que des dégâts se produisent. On ne peut pas faire grand-chose contre des attaques qui sont inconnues. Trouver rapidement un [fix] efficace et apprendre de ceci est ce qui est attendu des développeurs. Par chance, ces attaques n'émergent que très rarement, mais les choses changent à mesure que les recherches avancent. Seule l'analyse de la sécurité sera discutée dans la section 2 parce que tout a déjà été testé et a passé l'analyse d'aléatoirité. ----| 2 Description de GNAs spécifiques 2.1) Conception de NoiseSpunge Information Source : Uhhhh, je l'ai écrit. [NDT : l'auteur, pas moi, hein :)] 2.1.0) Résumé de NoiseSpunge NoiseSpunge fut spécialement écrit pour générer des clefs aléatoires aptes à la cryptographie forte. La collecte d'entropie pour une seule sortie (256 bits) requiert quelques secondes de mouvement de souris de la part de l'utilisateur/utilisatrice. Sa structure est complexe et chère en calcul. NoiseSpunge est fait pour être un composant dans un cryptosystème et, pour cette raison, on doit faire des considérations spéciales pour l'empêcher d'être un handicap. Le compromis dans cette implémentation est tel qu'il serait maladroit au possible si on avait régulièrement besoin de grandes quantités de données aléatoires parce que cela requièrerait une interaction utilisateur intense et consommerait trop de cycles CPU. 2.1.1) Collecte d'Entropie de NoiseSpunge Un GNPA est semé avec des zéros intitiaux. Ensuite le GNPA sort une valeur utilisée pour cacluler la taille de l'intervalle utilisé. Lorsque l'intervalle est déclenché, on vérifie le mouvement de la position de la souris. Si la souris a bougé depuis le dernier déclenchement, alors on demande la valeur de l'horloge haute-fréquence du PC. Les 4 derniers bites significatifs sont XORés avec les 4 derniers bits significatifs des coordonnées x et y de la souris. Un nouvel intervalle est ensuite calculé par le GNPA. Les 4 bits produits sont concaténés jusqu'à ce que 32 bits soient collectés et sorti. Les 32 bits sont concaténés dans un tampon d'entropie et également utilisés pour mettre à jour le GNPA qui met en place l'intervalle. Le traîtement est ensuite répété. Si la souris n'a pas bougé, un nouvel intervalle est mis en place et le traîtement se répète jusqu'à ce qu'elle ait bougé. Il y a également une fonction qui autorise le programmeur à entrer 32 bits d'entropie à la fois. Cette fonction est adéquate si il y a un appareil d'entropie matériel ou une autre source d'entropie connue sur un système particulier. Cependant, l'usage d'un autre GNA serait redondant s'il est bon, et inutile s'il est mauvais. 2.1.2) Estimation de l'Entropie de NoiseSpunge L'estimation d'entropie est linéaire. Le scénario du pire cas est supposé avec chaque entrée. Seuls 4 bits sont collectés pour chaque capture de souris. Aucune estimation plus avancée n'est faite parce qu'elle ne rapporterait que 4 bits ou plus. L'estimation d'entropie pour la fonction supplémentaire qui permet au programmeur de fournir sa propre entropie requiert que le programmeur garantisse que son entropie est de bonne qualité ; l'estimation de cette entrée d'entropie tombe entre ses mains. 2.1.3) Réserve d'Entropie de NoiseSpunge L'état interne comprends 762 bits. Il ya une graine de 256 bits, un hash primaire de 256 bits et un hash secondaire de 256 bits. Haval 256 bits est utilisée comme fonction de hashing. Lorsqu'un bloc de 32 bits d'entropie est ajouté, il est joint à un tampon de 256 bits. Une fois que le tampo est plein le hash primaire est mis à jour avec. La graine est XORée avec la sortie du hash primaire jusqu'à la huitième resemence du primaire. Dans ce cas, la sortie du hash primaire est mise en entrée dans le hash secondaire et son hash de sortie est permutée (voir ci-dessous) et remplace la graine. La permutation de graine est accomplie par une expension-compression. Des mots de 32 bits de la graine sont mangés comme graine aléatiore du GNPA et utilisés pour sortir deux mots de 32 bits. Les 512 bits de la sortie du GNPA sont tous hashés et remplacent la graine de la réserve. Après que tous les primaires ait étés resemés, un compteur KeyServe est incrémenté et limité à 8. KeyServe représente le nombre de groupe de 256 bits d'entropie qui ont étés ajoutés à l'état interne. Ce KeyServe est une ébauche d'estimation de lorsqu'il n'y a plus aucune raison d'ajouter de l'entropie dans la réserve et que le thread de collecte d'entropie peut être mis en pause (jusqu'à ce que le GNA sorte). 2.1.4) Fonction de Sortie de NoiseSpunge Il y a deux méthodes fournies pour la sortie du GNA : sûre et forcée. Une sortie sûre s'assure que le KeyServe n'est pas annulé et le décrémente après la sortie. Une sortie forcée ignore KeyServe. Pour sortir, la graine est copiée dans un tampon temporaire et est ensuite permutée. La nouvelle graine utilise une clef pour initialiser Rijndael (algorithme symmétrique à bloc). Le tampon temporaire est crypté avec Rijndael et est ensuite permuté avec une expension-compression (de la même manière que l'est la graine). Cela est répété en N rounds (choisis par le programmeur) et le tampon est ensuite sorti. 2.1.5) Analyse de NoiseSpunge [1] La lourde dépendance sur le mouvement de la souris peut_ priver_ d'entrée la réserve d'entropie si la souris n'est pas utilisée durant une grande période de temps. Cependant, un compteur empêche la sortie quand l'entropie est faible. [2] Le programmeur pourrait entrer de force de l'entropie de faible qualité et fragiliser l'état interne du GNA. [3] Il n'y a aucune provision sur les systèmes sans timers de haute résolution. [4] Même si l'état interne de la réserve est long de 762 bits, à n'importe quel état l'entropie est de 256 bits maximum (les autres bits ne sont seulement là que pour éviter le ratraçage et pour cacher la graine). Ceci rend ce GNA adéquat lorsqu'on a besoin de petites sommes de données aléatoires sécurisées. 2.2.) Conception du GNA de Intel Source d'Information : White Paper Générateurs de Nombres Aléatoire d'Intel *1 2.2.0) Résumé du GNA de Intel Le GNA d'Intel est un système répendu. Il est conçu pour fournir des données aléatoires de bonne qualité en grande quantité à tout logiciel qui le requiert. Sa moyenne de sortie est de 75 Kb/s (bits). Le Pilote de Sécurité Intel [Intel Security Driver] fournit un pont entre le middleware (CDSA, RSA-BSAFE et la CryptoAPI de Microsoft) qui donnera les nombres aléatoires aux applications le demandant, et le matériel. La partie matérielle est dans le chipset Intel 810, et sera dans le chipset 82802 Firmware Hub Device pour tous les chipsets 8xx futurs. (ATTENTION : ce ne sont que quelques-une de mes opinions ; prenez-les avec précaution) [with a grain of salt /* je capte pas trop l'expression :( */]. Intel a choisi de labeller avec éloquence son GNA comme un GNVA (Générateur de Nombres Vraiment Aléatoires), mais ils l'appellent GNA dans tout le reste de l'article. Techniquement il n'y a pas de différence fondamentale qui le mettrait à l'écart des autres bons GNAs, ; c'est un label pour la hype et qui n'a rien à voir avec sa capacité à produire des nombres aléatoires (GNA == GNVA & GNVA == GNA). Pour votre dose quotidienne de culture générale, voici ceci : "La sortie du GNA Intel a terminé sa validation post-conception par Cryptographic Research Inc. (CRI) et le test de Niveau 3 du Federal Information Processing (FIPS) pour l'aléatoirité statistique (FIPS 140-1)." . Je trouve rassurant qu'une compagnie (CRI) ait analysé et supporte ce GNA. Ce n'est pas quelque chose que l'on voit très souvent. D'un autre côté le FIPS 140-1 n'est qu'un autre générateur de hype. Après lecture du FIPS 140-1, on réalise qu'il n'a absolument RIEN à voir avec la qualité du GNA, mais hey ! Qui s'en soucie ? Microsoft semble penser que c'est suffisamment bon pour l'utiliser dans leur famille de produits de _haute_qualité_et_sécurité_, donc il doit être bon. Blague à part, malgré la puanteur [stench] de l'entreprise, ce GNa est bien conçu et empêchera les gaffes de beaucoup de GNA comme celui de Netscape. Je pense que c'est une étape dans la bonne direction. Plutôt que de laisser Joe, son cousin Timmy et les meilleurs amis de Timmy concevoir leurs propres GNAs, ils fournissent une bonne solution pour tout le monde sans avoir à tout faire comme l'a fait Netscape. 2.2.1) Collecte d'Entropie du GNA Intel Le Générateur de Nombres Aléatoires Intel est sur le point d'être intégré sur les cartes mères des PCs. Il y a 2 résistances et deux oscillateurs (l'un lent, l'autre rapide). La différence de tension entre les deux résistances est amplifiée pour recueillir le bruit thermal. Cette source de bruit est utilisée pour moduler l'horloge lente. Cette horloge à modulation variable est utilisée pour mettre en place les intervalles entre les mesures de l'horloge rapide. Lorsque l'intervalle est atteint la fréquence de l'horloge rapide est alors filtrée au travers de ce que Intel appelle le correcteur Von Neumann (brevet en instance). Le correcteur compense le parti-pris de l'horloge en faveur de rester dans des états de bit fixés (sans tenir compte de la modulation varible de l'horloge lente). Cela fonctionne en comparant des paires de bits et en ne sortant qu'un ou pas de bit ([1,0]=0; [0,1]=1; [0,0] ou [1,1] = pas de sortie). La sortie du correcteur est groupée en blocs de 32 bits et est envoyée au Pilote de Sécurité Intel [Intel Security Driver]. 2.2.2) Estimation de l'Entropie du GNA Intel Aucune estimation n'est faites pour quelques raisons. Du fait que la source d'entropie est basée sur le matériel, elle ne peut être manipulée sans être mise dans des températures très au-dessus ou au-dessous des conditions ambiantes raisonnables, ou que l'alimentation de l'ordinateur soit coupée (auquel cas la collecte d'entropie est soppée). Au-delà de ceci, toute l'entropie est collectée de la même manière et peut être supposée de qualité égale. 2.2.3) Réserve d'Entropie du GNA Intel Le Pilote de Sécurité Intel se charge du mélange de la sortie du GNA. La réserve est composée de 512 bits d'un contexte de hash SHA-1 divisé en deux états. Un hash de 80 bits du premier état est généré et ajouté à 32 bits d'entropie (provenant du matériel) et aux premiers 160 bits du premier état pour créer le second état. Lorsque d'autres 32 bits d'entropie sont générés, le second état devient le premier état et le même traitement est répété. 2.2.4) Fonction de sortie du GNA Intel Les derniers 16 bits du hash du premier état sont donnés au middleware. Le Pilote de Sécurité Intel s'assure que chasue sortie n'est expédié qu'une seule fois. Si désiré, le traîtement additionnel de la sortie devra être effectué par le programe qui a demandé les données aléatoires. 2.2.5) Analyse du GNA Intel [1] Le besoin d'implémenter le correcteur Von Neumann démontre les affinités du GNA pour les séquences répétitives. Un(e) attaquant(e) pourrait calculer quand les 1 ou les 0 sortent disproportionnellement en estimant son débit en bits/sec, mais ceci ne mène (actuellement) à aucune attaque faisable. [2] L'usage de middleware sous contract pourrait mener à des trous de sécurité. Avant d'utiliser le middleware d'une compagnie, vous devriez peut-être attendre quelques mois, juste pour voir si une brèche rapide est publiée. 2.3) Conception du /dev/random de Linux Source d'Information : code source de /dev/random *2 2.3.0) Résumé de /dev/random Linux fournit le character device /dev/random comme interface pour que les applications reçoivent des données aléatoires avec une bonne qualité d'entropie. Il fournit une réserve d'entropie de taille généreuse (512 octets) pour satisfaire le système d'exploitation et tous les logiciels fonctionnant au-dessus. Lorsque la qualité de l'entropie n'est pas nécessaire, un second character device /dev/urandom est donné en tant que GNPA pour éviter de vider inutilement la réserve d'entropie de /dev/random. 2.3.1) Collecte d'Entropie de /dev/random Des fonctions externes du kernel déclenchent l'ajout d'entropie dans la réserve. Les événements qui le déclenchent sont les frappes au clavier, les mouvements de la souris, et les IRQs. A chaque déclenchement, 32 bits d'un timer à haute-fréquence sont copiés, et d'autres 32 bits sont dérivés selon le type du déclencheur (soit les coordonnées de la souris, le code de la touche du clavier ou le numéro de l'IRQ). 2.3.2) Estimation de l'Entropie de /dev/random L'estimation d'entropie est calculée à l'aide de trois deltas. Delta1 est le temps écoulé depuis le dernier déclenchement du même type. Delta2 est la différence entre Delta1 et le Delta1 précédent. Delta3 est la différence entre Delta2 et le Delta2 précédent. Le plus petit des trois deltas est choisi comme Delta. Le dernier bit significatif de Delta est ignoré et les 12 bits suivants sont utilisés pour incrémenter le compteur d'entropie. 2.3.3) Réserve d'Entropie de /dev/random Ce GNA utilise une réserve d'entropie de 4096 bits. Avant l'entrée, un marqueur notant la position courante le long de la réserve est décrémenté par 2 mots de 32 bits. Si la position est 0, la position est enveloppée [wrapped around] derrière le dernier second mot de 32 bits. L'entropie est ajoutée dans deux mots de 32 bits : x & y. Une variable, j, détermine de combien de bits vers la gauche l'entropie devrait être rotatée. Avant que l'entropie ne soit ajoutée, j est incrémentée de 14 (7 si la réserve est à la position 0). L'entropie est rotatée de j. Selon la position courante le long de la réserve, y est XORé avec 5 autres portions fixées de la réserve. Les positions suivantes sont enveloppées depuis la position courantes : 103, 76, 51, 25, 1 (pour une réserve de 4096 bits) et x est XORé avec chaque mot suivant. x est déplacé de 3 bits vers la droite, XORé par une constante dans une table de 1x7 (0, 0x3b6e20c8, 0x76dc4190, 0x4db26158, 0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278) dont l'index est choisi par x ET 7 (du point de vue des bits, 3 bits). x XOR 7 est ensuite concaténé à la réserve en sautant un mot. y est déplacé de 3 bits vers la droite, XORé avec la table des constantes de la même façon que x et est ensuite copié dans le mot qui a été sauté dans la réserve. La réserve reste à cette position (position précédente - 2, la fin est peut-être enveloppée). 2.3.4) Fonction de sortie de /dev/random Lorsqu'on demande une sortie au GNA, le timer et le numbre d'octets demandé est ajouté à la réserve en tant qu'entropie. La réserve est ensuite hashée avec SHA-1 et les 2 premiers mots du hash sont mangés comme entropie dans la réserve ; ceci est répété 8 fois, mais à chaque fois les 2 mots suivants du hash sont mangés dans la réserve. La première moitié du hash final est ensuite XORée à sa seconde moitié pour produire la sortie. La sortie fait soit la taille demandée soit 20 octets (la moitié de la taille du hash) ; la plus petite de ces deux dernières est choisie. 2.3.5) Analyse du /dev/random de Linux [1] Le motoring et la prédiction de certains IRQs est possible dans un environnement réseau. [2] Il y a beaucoup de redondance dans les 16 plus petits bits ajoutés à l'entropie. Par exemple, lorsqu'une frappe au clavier se produit, une variable de 32 bits contient 16 bits provenant d'un timer de haute résolution, et les 16 plus petits bits sont 0-255 pour la frappe au clavier (256 et plus sont utilisés pour désigner les interruptions). Ceci laisse 8 bits de redondance pour chaque frappe au clavier. [3] Le temps écoulé depuis que le dernier bloc d'entropie a été ajouté n'a habituellement rien à voir avec la qualité de l'entropie, à moins que ce laps de temps soit très court. Ceci ne prend pas en compte les entrées d'entropie séquentielles comme les accès disque continus durant le déplavement d'un fichier. [4] Lorsqu'une sortie se produit, le mécanisme de mélange re-rentre beaucoup d'entropie hashée qui peut être de bonne qualité ou pas. Ces mots remis sont ajoutés au compteur d'entropie mais ne devraient pas. Il y a des bits d'entropie qui ont déjà été comptés. Après la sortie, 512 bits d'entropie sont redondamment entrés. Si cette estimation est précise, alors après 8 appels à la sortie il y a 4096 bits (la réserve entière) d'entropie de qualité indéfinissable. Dans ces circonstances, si aucune entropie n'est entrée en provenance de l'interaction avec l'utilisateur/utilisatrice, le GNA devient un GNPA. 2.4) Conception de Yarrow Sources d'Information : code source de Yarrow et White Papers *3, *4. 2.4.0) Résumé de Yarrow Yarrow a été conçu par Bruce Schneier, auteur de "Cryptographie Appliquée" et concepteur des algorithmes cryptographiques Blowfish et de Twofish, finaliste de AES. Yarrow est l'interprétation de Schneier de la conception propre d'un GNA et est accompagné d'un article détaillé décrivant son fonctionnement interne et son analyse (voir la seconde source d'information). C'est le résultat d'une longue recherche et c'est un standard des propriétés attendues pour un GNA sécurisé. Il est discuté ici par comparaison entre les GNA auxquels on fait généralement confiance et un qui a été conçu par un professionnel agerri. [NDT : "Cryptographie Appliquée" est à lire *absolument* pour celles et ceux qui s'intéressent à la crypto, probablement le meilleur livre jamais écrit dans ce domaine (avis personnel)] 2.4.1) Collecte d'Entropie de Yarrow Les ancres du système attendent un événement du clavier ou de la souris. Si une touche a été pressée, le temps écoulé depuis la dernière frappe au clavier est ajoutée dans un tableau. On fait la même chose lorsqu'un bouton de la souris est pressé. Si la souris a bougé, les coordonnées x et y sont ajoutées à un tableau d'événement de souris. Une fois qu'un tableau est plein il est passé à la fonction d'estimation d'entropie. 2.4.2) Estimation d'Entropie de Yarrow On passe à la fonction d'estimation d'entropie un nombre estimé de bits d'entropie choisi par le biais du/de la programmeur/programmeuse au travers de sa source. On peut décider que ce mouvement de souris ne réprésente que 4 bits d'entropie par mouvement, alors que la latence du clavier vaut 8 bits par frappe. Une autre mesure utilise un petit algorithme de compression et mesure la taille compressée. La troisième et dernière mesure est la moitié de la taille de l'échantillon [sample] de l'entropie. La plus petite de ces trois mesures incrémente l'estimation d'entropie. 2.4.3) Réserve d'Entropie de Yarrow Lorsque l'entropie est entrée, elle est mangée par une réserve rapide (contexte SHA-1) et une estimation d'entropie est mise à jour pour cette réserve. Une fois que la réserve a accumulé 100 bits d'entropie, la sortie du hash est mise dans la réserve lente et son estimation d'entropie est mise à jour. Lorsque la réserve lente a accumulé 160 bits d'entropie la sortie de son hash devient la clef courante. 2.4.4) Fonction de Sortie de Yarrow Lorsque la sortie est demandée, la clef courante (dérivée de la réserve lente) crypte un compteur (son nombre de bits est choisi par le/la programmeur/programmeuse) et sort le texte crypté ; le compteur est ensuite incrémenté. Après 10 sorties, le GNA resème la clef en la remplaçant par une autre sortie (forcée). La clef sera par la suite resemée soit lorsque la réserve lente aura accumulé 160 bits soit lorsque 10 sorties se seront produites. 2.4.5) Analyse de Yarrow [1] Le mouvement de la souris est en-soi très redondant, il y a un rang très limité de déplacement entre la dernière position et la position courante après que l'OS ait envoyé le message disant que la souris a bougé. La plupart des bits représentant la position de la souris ne changeront probablement pas et excluent [throw off] l'estimation d'entropie de ce GNA. [2] Même si l'état interne de la réserve est long de 320+n+k bits, il y a un maximum de 160 bits d'entropie pendant tous les états. "Yarrow-160, notre construction courante, est limité à au plus 160 bits de sécurité par la taille de ses réserves d'accumulation d'entropie." *4 ----| 3) Code source de NoiseSpunge Le code source suivant n'est simplement qu'un bref exemple. Faites ce que voulez avec ; même ce que vous faites avec votre langue et le [rubber] ... [NDT : "rubber" c'est le caoutchou, mais aussi la capote :>] ... Ca ne fait rien. Ca _NE_COMPILERA_PAS parce qu'environ 1 200 lignes ont été omises (qui consistent en Havaln Rijndael et le GNPA). Les codes sources de Haval et Rijndael sont facilement disponibles. N'importe quel GNPA fera l'affaire, mais assurez-vous qu'il fonctionne avec une entrée de 32 bits et que sa sortie a une période d'au mois 2^32 (4294967296). Je l'ai divisé en 3 morceaux : collecte d'entropie, réserve d'entropie, et fonctions de sortie. [COLLECTE D'ENTROPIE] Cette boucle doit se lancer dans un thread indépendant du thread principal de l'application. Pour les dépendences de l'OS, j'ai créé des fonctions dummy qui devraient être remplacées : int64 CounterFreq; //high-res counter's frequency/second int64 QueryCounter; //high-res counter's current value Delay(int ms); //1 milisecond precision delay int GetMouseX; //current mouse x coordinate int GetMouseY; // " y coordinate #define MOUSE_INTERVAL 10 { Prng_CTX PCtx; int x,y; unsigned long Block; unsigned long BitsGathered; int65 Interval,Frequency,ThisTime,LastTime; unsigned long BitsGathered=0; bool Idled=false; Frequency=CounterFreq; bool Terminated=false; //Set value to true to end the loop do { if (Idled==false) { Delay(MOUSE_INTERVAL); Idled=true; } ThisTime=QueryCounter; if ((ThisTime-LastTime)>Interval) { if ((x!=GetMouseX)&&(y!=GetMouseY) { x=mouse.cursorpos.x; y=mouse.cursorpos.y; Block|=((x^y^ThisTime)& 15)<>2)+MOUSE_INTERVAL) * Frequency)/1000; } LastTime=QueryCounter; Idled=false; } } while (Terminated==false); } [RESERVE D'ENTROPIE] #define SEED_SIZE 8 #define PRIMARY_RESEED 8 #define SECONDARY_RESEED 8 //paramètres #define MAX_KEY_RESERVE 8 #define KEY_BUILD_ROUNDS 16 typedef unsigned long Key256[SEED_SIZE]; Key256 Seed; Key256 EntropyBuffer; Haval_CTX PrimaryPool; Haval_CTX SecondaryPool; unsigned char PrimaryReseedCount; unsigned char EntropyCount; unsigned char KeyReserve; //FONCTIONS void NoiseSpungeInit { HavalInit(&PrimaryPool); HavalInit(&SecondaryPool); for (int i=0;i<8;i++) Seed[i]=0; EntropyCount=0; PrimaryReseedCount=0; KeyReserve=0; } void PermuteSeed { Key256 TempBuffer[2]; Prng_CTX PCtx; Haval_CTX HCtx; for (int i=0;i0) KeyReserve--; Return 1; } void ForcedGetKey(Key256 *Key) { Key256 TempSeed; Key256 TempBuffer[2]; Rijndael_CTX RCtx; Prng_CTX PCtx; Haval_CTX HCtx; for (int i=0;i0) KeyReserve--; } ----| 4) Références *1 Intel Random Number Generator White Paper http://developer.intel.com/design/security/rng/CRIwp.htm *2 /dev/random source code http://www.openpgp.net/random/ *3 Yarrow source code http://www.counterpane.com/Yarrow0.8.71.zip *4 Yarrow-160: Notes on the Design and Analysis of the Yarrow Cryptographic Pseudorandom Number Generator http://www.counterpane.com/yarrow-notes.html Traduit par [DegenereScience]DecereBrain, le 27/02/2004, 05:40 Greets to : Thibaut & Nathalie, Ophélie, qui supportent l'effort de guerre. Comme Dieu, le crou reconnaîtra les siens lors du Jugement Dernier. "Keep your friends close, but keep your ennemies closer" - Asian Dub Foundation, "Enemy of the enemy" (album "Enemy of the enemy", 2003)