Générer des nombres aléatoires avec Hasard 0.9.6

Posté par (page perso) . Modéré par Mouns.
Tags :
36
10
juil.
2009
Sécurité
Générer des nombres aléatoires avec un ordinateur (déterministe par définition) est un problème complexe. Il est facile d'introduire un biais par une maladresse. On a vu de nombreuses failles au fil des années, un exemple récent étant la faille introduite dans la version Debian d'OpenSSL (mai 2008).

Chaque système d'exploitation propose des périphériques et API différentes, et il existe diverses bibliothèques tierces, pour générer des nombres aléatoires. La bibliothèque Hasard propose une API simple, portable et haut niveau, pour limiter les erreurs d'un développeur, tout en réutilisant les briques existantes (ex: bibliothèques OpenSSL et gcrypt).

La version 0.9.6 supporte Linux, FreeBSD, Mac OS X et Windows, et devrait fonctionner sur n'importe quel système d'exploitation disposant des périphériques /dev/urandom et /dev/random. La bibliothèque Hasard est écrite en C, propose un binding Python, et est distribué sous licence BSD. Une API simple :

Hasard propose, par exemple, une fonction hasard_ulong() pour générer un nombre dans une intervalle choisi par l'utilisateur garantissant une distribution uniforme. La bibliothèque standard C n'offre par de telle fonction, ce qui oblige chaque développeur à réimplementer une telle fonction. Et souvent ces réimplementations sont boguées (non uniformes).

Hasard s'occupe également d'initialiser le générateur de nombres avec une entropie de bonne qualité (typiquement /dev/urandom), plutôt qu'à partir du temps ou du numéro de processus.

Lisez le document Common errors qui présente en détail les problèmes qu'Hasard tente de résoudre.

Simulation ou sécurité ? Utilisez les profils !

Il existe deux principales utilisations des générateurs de nombres aléatoires : les simulations physiques (les jeu vidéos en étant un cas particulier) et la sécurité. Pour les simulations, un bon générateur doit être rapide et avoir une distribution uniforme. Pour la sécurité, même si l'attaquant est capable de contrôler la source d'entropie et/ou obtenir l'état interne du générateur, il ne doit pas être capable de prédire les précédents nombres ou prochains nombres générés.

Hasard offre plusieurs profils pour répondre aux différentes utilisations :
  • @fast : générateur rapide destiné aux simulations
  • @secure_blocking : générateur sûr (bloquant) pouvant être utilisé pour générer des certificats
  • @secure_nonblocking : compromis entre la vitesse et la sécurité, générateur sûr mais non bloquant, pouvant être utilisé pour générer des mots de passe, identifiants de session et vecteurs d'initialisation.

Il existe également les profils @hardware et @test, réservés à des utilisations spéciales.

Le profil @fast utilise le générateur Mersenne Twister. Les profils @secure_blocking et @secure_nonblocking utilisent les bibliothèques OpenSSL et gcrypt, et les périphériques /dev/urandom et /dev/random. Consultez Hasard profile list pour les détails.

Vous pouvez également vous passer des profils en spécifiant directement les générateurs : un générateur pour générer des nombres (rng) et un pour initialiser la graine du premier (seed). Hasard en contient un grand nombre. Les générateurs peu fiables sont dans une seconde bibliothèque (hasardweak), pouvant être utile pour des raisons de compatibilité.

Tests et outils :

Hasard est régulièrement testé par une grande campagne de tests pour détecter les erreurs d'implémentation. Il est également possible d'utiliser les programmes TestU01 (le meilleur et plus complet), dieharder ou encore ENT, pour mesurer la qualité d'un générateur donné.

D'autres programmes sont disponibles dans le sous-dossier python/. Voyez par exemple le document Visualise random numbers using images pour tracer des images démontrant rapidement la faible qualité des générateurs congruentiels linéaires (générateurs les plus courants et malheureusement les plus mauvais).

Journaux des précédentes versions :

Pour en savoir plus, vous pouvez également consulter les journaux annonçant les précédentes versions :
  • # Très intéressant

    Posté par (page perso) . Évalué à 8.

    Merci bien pour cette dépêche claire et détaillée.

    J'ai trouvé ton document sur les erreurs classiques très bien écrit et intéressant.

    Je n'ai pas l'usage de ta bibliothèque pour le moment, mais si un jour il faut que je génère des nombres aléatoires de qualité j'y penserai.

    Bonne continuation.
  • # Hum...

    Posté par . Évalué à 6.

    Plutôt que de savoir réutiliser OpenSSL, les performances de la librairie de pourraient-elles pas être améliorées, au moins sous Debian, en faisant un simple "return 9" ? (on est vendredi)
    • [^] # Re: Hum...

      Posté par . Évalué à 5.

      N'importe quoi: http://xkcd.com/221/
    • [^] # Re: Hum...

      Posté par (page perso) . Évalué à 7.

      Utilise "zero", "one" ou "counter". Le premier ne génère que des zéros, le second que des uns, et le dernier est un simple compteur :-p À force d'avoir la blague à chaque fois, je me demande si je ne vais pas prévoir le coup en ajoutant un générateur « Debian ».
      • [^] # Re: Hum...

        Posté par . Évalué à 4.

        Je vote oui pour une option 'debian' qui sorte toujours le code hexa des lettres D E B I A N de manière cyclique :)
        • [^] # Re: Hum...

          Posté par (page perso) . Évalué à 3.

          Oui, enfin gare aux bugs dans ces algorithmes, tu pourrais générer du hasard en sortant un cycle pas tout à fait parfait !
  • # .

    Posté par . Évalué à 7.

    Il faudrait peut etre parler de 'Hasard' aux développeurs de NSS : http://weblogs.asp.net/fbouma/archive/2009/07/09/the-firefox(...)
    • [^] # Re: .

      Posté par . Évalué à 7.

      Et le pire c'est quand tu regardes les bugs. Ils ont pas l'air de bien savoir pourquoi c'est encore la.

      En fait c'est utile sur Windows < 2000 ou le generateur de nombres aleatoires n'est pas forcement assez solide. Mais depuis, ils ont pas fait de tests pour savoir si ca apporte vraiment de l'entropie en plus que le generateur systeme.

      Et donc pour FF 3.5, ils ont "ameliore" du code qui fait doublon avec le generateur aleatoire fourni par le systeme, sans jamais se poser la question du pourquoi.

      Et c'est sense etre _le_ composant gerant la securite pour Mozilla. Ouch...
  • # Test / OpenSSL

    Posté par . Évalué à 3.

    Justement, dans le cas de l'affaire Debian / OpenSSL, est-ce qu'un outil comme Hasard aurait permis de déceler la faille plus tôt ?
    • [^] # Re: Test / OpenSSL

      Posté par (page perso) . Évalué à 5.

      Non pas du tout. Les nombres semblaient être aléatoires (en fait sortaient une série normale au sens mathématique du terme) mais deterministe en fonction du pid.
      En pratique, personne n'essaie de vérifier si un générateur risque de cracher deux fois la même série parce que l'échantillon normalement necessaire pour vérifier ça est énorme.
    • [^] # Re: Test / OpenSSL

      Posté par (page perso) . Évalué à 7.

      Hasard intègre de nombreux tests pour vérifier que N générateurs différents génèrent N suites différentes. En particulier, le programme python/test_hasard.py comporte les tests :
      * init : crée 10 (par défaut), 2^10 (option --slow) ou 2^20 (option --very-slow) générateurs différents et vérifie que les nombres générés sont différents
      * reseed : appelle la fonction reseed(), qui regénère la graîne d'un générateur, 10, 2^10 ou 2^20 fois en s'assurant que le générateur génère des suites différentes
      * fork_* (~17 tests) : vérifie qu'après un fork les deux générateurs (procesus parent et processus fils) génèrent des suites différentes

      J'avoue ne pas avoir testé la version OpenSSL mais je compte le faire. Je suppose que la suite "init" devrait trouver le bug très rapidement.

      Il y a une longue liste noire pour ces tests, car les générateurs faibles (dont l'état interne ou la graine font 32 bits ou moins) échouent rapidement. Le générateur libc_rand (fonction rand() de la libc) échoue par exemple après moins de 100.000 tests. Je viens de lancer le test "init" et j'ai obtenu une collision après 55094 essais. Ceci signifit qu'un attaquant a un espèce de recherche très restreint. Les générateurs utilisés dans Hasard utilisent un état interne et une graine d'au moins 128 bits. Consultez l'article suivant pour la théorie sur le risque de collision :
      http://fr.wikipedia.org/wiki/Paradoxe_des_anniversaires
      • [^] # Re: Test / OpenSSL

        Posté par (page perso) . Évalué à 4.

        Dans le cas de debian, le problème était sur le PID... Pour détecter cela, il faudrait lancer des tests sur n machines virtuelles vierges que l'on démarre puis lance le test dessus.

        Sur la version de debian, si tu lançais 10 générateurs, tu ne voyait pas le problème...

        Bref, il faut lancer dans ces cas là des tests sur un cluster (virtuel ou physique).
        • [^] # Re: Test / OpenSSL

          Posté par (page perso) . Évalué à 10.

          J'ai recompilé OpenSSL après avoir réintroduit le bug. Les tests d'Hasard 0.9.6 sont finalement insuffisant. Le test "init" réutilise le même processus, et on obtient donc des suites différentes. Par contre, j'ai modifié les tests fork_xxx pour forker N fois (1, 2^15 ou 2^20, selon les options --slow et --very-slow). Avec N=2^15, le bug OpenSSL est détecté (presque à la fin, vers ~32.100 essais).

          Vu que j'ai du écrire un test spécifique à ce bug, je me demande si demain on ne pourrait pas trouver un autre type de bug demandant également un test précis :-/
          • [^] # Re: Test / OpenSSL

            Posté par (page perso) . Évalué à 3.

            Ce qui prouve au moins une chose, que malgré la bourde du mainteneur debian, introduire un bogue dans ce genre de programme peut être très difficile à déceler. Il faut donc que ce genre de programme lié à la sécurité valide les critères suivants :

            - toujours faire auditer le code par des personnes extérieures

            - passer tous les tests des compilateurs (et équivalent : valgrind...) sans aucun warning

            - avoir un code très propre et bien documenté aux passages critiques

            - avoir une API simple et claire

            - avoir une batterie de test la plus large possible

            Malgré cela, on n'est pas à l'abris d'un bogue subtile. Pour revenir au cas d'openssl, le développeur debian a fait une bourde mais je le projet openssl ne passe pas non plus le genre de critère que je viens d'énoncer.
            • [^] # Re: Test / OpenSSL

              Posté par (page perso) . Évalué à 4.

              - toujours faire auditer le code par des personnes extérieures

              Il faut des personnes compétentes, en particulier pour ce bug : des personnes connaissant (très) bien les générateurs de nombres aléatoires... ce qui est très rare.

              - passer tous les tests des compilateurs (et équivalent : valgrind...) sans aucun warning

              AHEM. La faille a été introduite à cause d'un faux positif Valgrind...

              - avoir un code très propre et bien documenté aux passages critiques
              - avoir une API simple et claire


              L'API OpenSSL est très claire (pas juste l'API publique, l'API interne également).

              - avoir une batterie de test la plus large possible

              Le problème dans le cas de Debian OpenSSL est que le générateur était parfaitement aléatoire, il passe tous les tests, même les plus complets. Le problème était celui de la graine, et il semble qu'aucun outil ne teste la qualité de la graîne : s'assurer que N générateurs génèrent N suites différentes. Même s'il existe un tel outil, il faut que l'outil pense à exécuter chaque générateur dans un processus différent... Or pour des raisons pratiques, on va préférer tout faire dans le même processus.

              Le bug Debian OpenSSL est un cas très particulier et il n'existait pas de test pour détecter le bug. Maintenant, il faut espérer que l'histoire ne se répête pas.

              PS : Hasard contient un outil pour tester que N générateurs génèrent N suites différentes. Je parlais d'un test utilisant fork(). Et bien il semble que mon outil ait trouvé un (nouveau) bug, différent. fork() est encore un autre cas :-/
              • [^] # Re: Test / OpenSSL

                Posté par (page perso) . Évalué à 2.

                > des personnes connaissant (très) bien les générateurs de nombres aléatoires... ce qui
                > est très rare.

                C'est une problématique bien connu dans les labo de recherche. On travaille sur des domaines pointus et donc l'audit n'est pas facile. On tourne assez rapidement sur toujours les mêmes personnes.

                Sinon, je ne connais pas du tout OpenSSL sauf en tant que simple utilisateur lambda. Je vois juste que c'est un composant fondamental et qu'il y a régulièrement des bogues. En fait, je trouve dommage qu'OpenSSL et que GnuTLS ne soit pas plus interchangeable.

                Enfin, j'ai essayé de faire une liste de type checklist des bonnes pratiques pour ce genre de composant. Cette checklist est bien sur à améliorer.

                Concernant plus spécifiquement le code du bogue debian, je crois me souvenir que la ligne capitale qui a été retirée n'étais pas spécialement commentée et surtout, qu'il y avait un certain nombre d'appel du "même" type. C'est en ce sens la qu'il y a peut-être une amélioration à voir.
              • [^] # Re: Test / OpenSSL

                Posté par . Évalué à 2.

                AHEM. La faille a été introduite à cause d'un faux positif Valgrind...
                Parce que l'équipe d'openssl ne s'en était pas préoccupé...

                Ce qui est anormal c'est que c'est le dvp d'une distrib qui s'occupe de ça.
                • [^] # Re: Test / OpenSSL

                  Posté par (page perso) . Évalué à 1.

                  Parce que l'équipe d'openssl ne s'en était pas préoccupé...

                  Et?
                  Dans ce cas, on remonte le bug à l'équipe OpenSSL, qui va le prendre en compte ou refuser le patch.

                  Ce qui est anormal c'est que c'est le dvp d'une distrib qui s'occupe de ça.

                  Ce qui est anormal, c'est qu'un packageur se permette de modifier du code, et le mette dans une distrib.
                  J'entends souvent parler de logiciels qui sont "cassés" chez Debian/Ubuntu, parce que les packageurs s'amusent à modifier le code source qui n'a rien à voir avec le package, et ça gonfle pas mal de développeurs qui se prennent des mails "telle fonctionnalité ne marche pas", et après recherche longue, le développeur s'aperçoit que son code est bon, juste que le code packagé a introduit un bug non vu par le packageur.

                  Le bug OpenSSL a montré les limites de la façon de gérer de Debian, mais d'autres logiciels moins critiques subissent le même sort... Heureusement, l'impact est souvent juste de faire chier le développeur original.
                  Et ça n'a pas l'air prêt de changer chez Debian/Ubuntu! (ben oui, c'est peut-être l'effet de volume, mais mes lectures m'ont amené que sur des bug de packages en .deb)
                  • [^] # Re: Test / OpenSSL

                    Posté par . Évalué à 2.

                    Dans ce cas, on remonte le bug à l'équipe OpenSSL, qui va le prendre en compte ou refuser le patch.
                    Actuellement, l'équipe d'openssl avait accepté le patch. Mais bon on va pas refaire une nième fois l'histoire, surtout qu'à l'époque tout avait déjà été dis.

                    Ce que je disais dans le commentaire juste au dessus : c'est à l'équipe d'openssl d'offrir un truc clean, carré, propre pour éviter justement que ce genre de chose arrive.

                    Pas d'attendre que le boulot soit fait par quelqu'un qui n'est pas forcément aussi au fait que l'équipe de "base" d'open ssl (cela n'empeche pas d'accepter des patchs heins, et j'ai pas dis non plus que c'était facile).


                    Ce qui est anormal, c'est qu'un packageur se permette de modifier du code, et le mette dans une distrib.
                    Ce qui est anormal, c'est que des gens comme toi se permettent de juger le boulot de quelqu'un qui avait travaillé, et qui avait BIEN DEMANDER ce qu'il fallait demander à l'équipe d'open SSL.
                    De plus modifier le code et le mettre dans une distirb, c'est bel et bien le boulot du packageur (intégration toussa).
                    Si c'était juste faire un paquet binaire, ça ca peut se faire automatiquement.

                    Bref, plutôt que de vouloir casser du sucre sur debian de façon gratuite, et fausse, j'invite tout ceux qui sont intéressé par ce qui c'est réellement passé sur ce problème à voir les commentaires qui furent publié à l'épques.
                    Et les gens un tant soit peu ouvert d'esprit se rendront compte sans problème que cette "erreur" n'est nullement la faute exclusive de l'une ou de l'autre des parties, mais plutot d'une mauvaise compréhension entre les deux.


                    Le bug OpenSSL a montré les limites de la façon de gérer de Debian,
                    Nullement.
                    Le bug openssl a montré les limités de la façon de gérer d'openssl, des distribs et consors. Bref de la limite de l'opensource en général.
                    Red hat aurait très bien pu avoir ce problème .

                    Mais comme tu veux juste casser du sucre sur debian sans savoir de quoi tu parle, je vais pas te retenir plus longtemps. Débarasse toi de ton fiel.

                    Je dirais juste aux lecteurs : ne prenez surtout pas les propos de zenitram pour la véritée vrais (ni les miens par ailleurs) et relisez les commentaires qui furent sorties a cette époque et faites vous votre propre idée. (et mon petit doigt me dis que ce ne sera pas la tienne).

                    Ps, il y avait aussi un édito de misc sur ce bug, et bizarrement, ils n'accusaient pas le dvp debian de tous les mots. Mais je présume que les gens qui contribue à misc sont moins doués que zenitram...
                    • [^] # Re: Test / OpenSSL

                      Posté par (page perso) . Évalué à 3.

                      > ne prenez surtout pas les propos de zenitram pour la véritée

                      Tout a fait d'accord. Toutes les grosses distrib modifient le code des applications, donc dès qu'il y a modif, il y a risque. Il n'y a que ceux qui ne font rien qui ne casse rien.

                      On a déjà parlé de ce bogue ici, on va pas refaire encore une fois de l'anti-debian primaire... Je rappelle juste que Red-Hat et Novell se sont bien abstenus de tout commentaire négatif à l'époque.

                      Mon propos avait juste pour objectif d'aider Victor dans sa recherche du hasard.
              • [^] # Re: Test / OpenSSL

                Posté par . Évalué à 3.

                >> - passer tous les tests des compilateurs (et équivalent : valgrind...) sans aucun warning
                >
                >AHEM. La faille a été introduite à cause d'un faux positif Valgrind...

                Ce qui est le resultat de deux choses:
                - des commentaires insuffisants dans le code source expliquants pourquoi telle valeur n'est pas initialisee.

                - une gestion des patch 'mal foutue' de Debian qui devrait etre specialement prudent sur toute modification de composant de securite de base (la 'correction' n'ayant pas ete remontee suivant le mecanisme normal a l'equipe de SSH).

  • # Générateur matériel?

    Posté par . Évalué à 9.

    Qu'en est-il de l'implémentation au niveau matériel de générateurs aléatoires?

    Étant donné que les besoins en valeurs aléatoires sont somme toute assez courant (ne serait-ce que pour les jeux vidéos), pourquoi n'y a-t-il pas systématiquement, sur les cartes mères, une puce "bruiteuse" interrogeable via une instruction standardisée?

    Ça serait plus propre que de réinventer la roue à chaque fois, avec plus ou moins de succès..

    THIS IS JUST A PLACEHOLDER. YOU SHOULD NEVER SEE THIS STRING.

    • [^] # Re: Générateur matériel?

      Posté par . Évalué à 9.

      Ou un système mécanique comme celui-ci :

      http://www.blogeee.net/2009/05/27/un-jeteur-de-des-analogiqu(...)

      Il y a une vidéo en youtube (*) qui permet de voir comment ça marche...





      * : en flash, c'est mal je sais, mais je m'en fous, aujourd'hui c'est vendredi je fait ce que je veux
    • [^] # Re: Générateur matériel?

      Posté par (page perso) . Évalué à 7.

      Il existe des chipsets pour carte mère qui génèrent de l'entropie. Linux sait les utiliser et s'en sert pour /dev/random. Voir quelques informations par ici :
      http://bitbucket.org/haypo/hasard/src/tip/doc/linux_random.r(...)

      Si on ne dispose pas d'un tel chipset, il est également possible de générer de l'entropie avec un carte son, une carte wifi, une webcam, voir même une lavalamp (par contre, c'est breveté ça, si si !). J'ai des liens vers ce genre de projet sur la page d'accueil d'Hasard.

      Ça serait plus propre que de réinventer la roue à chaque fois, avec plus ou moins de succès.

      Les générateurs matériels ne servent pas aux simulations (ils sont bien trop lents), mais peuvent beaucoup aider pour la sécurité (ça permet de générer des certificats plus rapidement, car /dev/random est très lent sinon !).

      Enfin, il existe aussi le démon EGD (et quelques variantes) qui peut également servir à distribuer de l'entropie de tout le monde à partir de n'importe quelle source.
      • [^] # Re: Générateur matériel?

        Posté par (page perso) . Évalué à 5.

        J'ai lu qu'un des problèmes des générateurs matériels, c'est qu'ils ne sont pas forcément meilleurs qu'un bon générateur logiciel, voire bien moins bons quand ils ne sont pas chers (ils sont souvent biaisés).
      • [^] # Re: Générateur matériel?

        Posté par . Évalué à 2.

        Ou peut-être utiliser la température du CPU?

        Ceci dit, pourquoi ne pas utiliser uniquement cette source aléatoire 'forte' comme graîne d'une suite génératrice d'aléa software, donc rapide?
      • [^] # Re: Générateur matériel?

        Posté par (page perso) . Évalué à 6.

        les générateurs physiques ne servent jamais pour des simulations pour deux raisons:
        -les simulations n'ont jamais besoin de "vrai" hasard (sauf cas particuliers théoriques)
        -Dans la vraie vie lorsqu'une simulation foire ou donne des résultats incohérents, on est content de pouvoir recommencer l'experience avec les mêmes données. Avoir un générateur de nombre aléatoire entièrement deterministe, capable de cracher plusieurs fois de suite la même suite de milliards de nombres aléatoires à l'aide d'une simple petite graine, c'est très pratique.
        • [^] # Re: Générateur matériel?

          Posté par (page perso) . Évalué à 2.

          OK, refaire la même liste est très pratique mais il y a plein de cas ou on s'en fou. Par exemple pour marquer les paquets TCP/IP.

          Pourquoi ne pas introduire tous les x pas de temps, x aléatoire, la température du CPU dans la formule ? Cela rajouterais un aléa quasi imprévisible et éviterait même au "propriétaire" de rejouer la séquence.
    • [^] # Re: Générateur matériel?

      Posté par (page perso) . Évalué à 3.

      Je pense que le plus simple est de faire appel aux générateurs matériels chers et de bonne qualité qu'utilisent certainement les réseaux bancaires ou autres : un démon efficace et paresseux pourrait collecter du hasard auprès des serveurs HTTPS qui ne peuvent se permettre d'être de mauvaises sources d'entropie (gros sites tiers de confiance ou bancaires ... )
  • # Il manque un mot important

    Posté par . Évalué à 8.

    pseudo

    comme dans pseudo-aléatoire
  • # Dommage

    Posté par . Évalué à 3.

    Le fichier hasard.h contient des mots clés réservés en C++ (this et new) on ne peut donc pas l'utiliser direct dans un projet C++ (ou alors je ne connais pas l'astuce)

    Sinon exposer une API simple tout en permettant de configurer finement le moteur utilisé pour ceux qui le souhaitent j'aime bien ! Ça me fait penser au Ruby on Rails.

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.