La faille de sécurité OpenSSL+Debian m'a motivé à lancer un projet que j'avais en tête depuis quelques temps : écrire une bibliothèque haut niveau pour gérer les nombres pseudo-aléatoires.
http://haypo.hachoir.org/trac/wiki/hasard
Ma motivation est que l'API C, srand() et rand(), est difficile à utiliser et peu de gens l'utilisent correctement. L'idée est donc de créer des fonctions qui empêchent les erreurs courantes : utilisation d'une faille entropie pour initialiser le générateur (typiquement time(NULL), voir getpid() et getppid()), utilisation de rand()%nombre pour générer un nombre dans l'intervalle [0; nombre-1].
J'ai donc écrit des fonctions pour générer des booleans, des entiers dans un intervalle, des nombres flottants et des octets aléatoires. La bibliothèque hasard supporte de nombreux générateurs (Mersenne Twister, ISAAC, Park-Miller, RANDU, ...) pour générer des nombres, et divers générateurs pour initialiser la graine (/dev/urandom et /dev/random pour l'instant). Par défaut c'est Mersenne Twister qui est utilisé avec /dev/urandom.
Pour faciliter l'intégration dans des biblitohèques et projets existants, la licence choisie est la licence BSD. La bibliothèque est écrite en C et un binding Python est disponible (tests/hasard.py). Le code est encore en développement et mériterait d'être relu. J'ai écrit divers tests pour mesurer l'entropie, tester les algorithmes, lancer le programme ENT (calcule divers statistiques sur les nombres), etc.
Pour la suite, il faudrait améliorer la portabilité (pour l'instant, hasard vise surtout Linux) en implémentant d'autres générateurs matériels : code pour Windows, EGD, instruction Intel "XSTORE RNG", etc. Des tests doivent être fait sur processeur 64 bits et/ou big endian. Voir le fichier README pour les autres idées de développement.
Journal Sortie de la bibliothèque Hasard version 0.2
31
mai
2008
# À quoi ça sert…
Posté par Sylvain Sauvage . Évalué à 10.
Il y a déjà http://www.gnu.org/software/gsl/ , qui a des bindings ruby, ocaml, s-lang, octave, python, etc., qui est bien testée, qui possède tout un tas de générateurs, qui permet tout un tas de distributions, qui est portable…
Il y a aussi http://www.boost.org/doc/libs/release/libs/random pour le C++, mêmes avantages que GSL.
Et il y en a d’autres, comme http://sprng.cs.fsu.edu/ ou bien plusieurs petites bibliothèques qui offrent des générateurs aléatoires (cf. apt-cache search random lib ou équivalent).
[^] # Re: À quoi ça sert…
Posté par khivapia . Évalué à 3.
En revanche, il est vrai que pour un usage cryptographique (à peu près le seul où il y a vraiment besoin d'aléas non prévisible) c'est délicat de tout réimplémenter de façon sûre et rapide.
[^] # Re: À quoi ça sert…
Posté par Victor STINNER (site web personnel) . Évalué à 8.
Je pense donc récupérer les meilleurs morceaux d'OpenSSL, libgcrypt, et autres (ex: GSL) pour faire une bibliothèque dédiée. Puis en suite, propose à ces projets de réutiliser mon code. Le but serait de concentrer les efforts pour obtenir un code de meilleur qualité que du code que chacun écrit dans son coin.
Maintenant, peut-être qu'effectivement il existe déjà une bibliothèque comme celle que j'essaye d'écrire, mais je ne suis pas au courant. Je vais voir les URLs que tu as postée, merci :-)
[^] # Re: À quoi ça sert…
Posté par Victor STINNER (site web personnel) . Évalué à 10.
Côté positif, GSL a de nombreuses fonctions pour lire et restaurer l'état d'un générateur. C'est très intéressant. J'avais commencé à coder ça dans libhasard, mais je n'ai pas réussi à me décider sur la manière de le faire. GSL a également plus d'algorithmes : ranlux, ranlxs, cmrg, mrg, taus, gfsr4, bsd, libc5, glibc2, 3 variantes de Mersenne Twister, ... Maintenant, je pense que je pourrai toujours rajouter des algorithmes après, mais je veux surtout une base solide ;-)
[^] # Re: À quoi ça sert…
Posté par fa224718524 . Évalué à 4.
http://www.gnu.org/software/gsl/manual/html_node/Random-numb(...)
La doc est limpide. Pour faire du Monte Carlo, ta remarque ne me parait pas pertinente. Il faut juste pouvoir générer des "run" avec une suite -différente-, le moins "pseudo" possible.
[^] # Re: À quoi ça sert…
Posté par fa224718524 . Évalué à 1.
Cher Victor c'est une mauvaise réponse! Si tu avais posé la question, je t'aurais dit que la GSL existait et que le CERN la vérifié :
http://lcgapp.cern.ch/project/cls/work-packages/mathlibs/ind(...)
http://seal.cern.ch/documents/mathlib/thesis_marte.pdf
cf. "Tests and validation of random number generators (see technical student report)"
Si OpenSSL ne la connaît pas, c'est normal c'est pas le même champ d'application (scope). La cryptologie utilise un PRNG uniforme. La GSL from Los Alamos (disneyland pour les militants de Greenpeace) est fait pour les scientifiques et permet de générer des distributions.
Voilà de quoi potasser sur le sujet.
Je suppose que ENT est un outil dédié à la prédiction du cours des actions d'Autodesk. Au passage l'histoire de la naissance du géant fait en LaTeX est une curiosité mémorable! Sacré Bacula! La pompe à fric procure la sécurité des données ...
p.s. : The etymology of the word "hazard" comes from French "hasard", from Old Spanish "azar", from Arabic "al-zahr" wich means the die. Example "hazardous area". Soit un nom pertinant pour un virus, make ...
[^] # Hasard != Hazard
Posté par Zenitram (site web personnel) . Évalué à 5.
Hasard (français, "Randomness" en anglais) != Hazard (anglais, "Risque" en français)
http://www.cnrtl.fr/definition/Hasard
http://fr.wikipedia.org/wiki/Hasard
On n'est au 21e siècle, pas a 13è siècle, l'origine peut dater du 13è siècle, ça n'empêche pas que le mot a évolué depuis dans notre langue... Pour ne rien avoir à faire avec l'idée d'un virus.
[^] # Re: Hasard != Hazard
Posté par fa224718524 . Évalué à 0.
[^] # Re: Hasard != Hazard
Posté par Victor STINNER (site web personnel) . Évalué à 2.
[^] # Re: Hasard != Hazard
Posté par BAud (site web personnel) . Évalué à 4.
[^] # Re: Hasard != Hazard
Posté par liberforce (site web personnel) . Évalué à 3.
[^] # Re: À quoi ça sert…
Posté par Victor STINNER (site web personnel) . Évalué à 3.
Je suppose que ENT est un outil dédié à la prédiction du cours des actions d'Autodesk.
Euh, est-ce que signifie qu'ENT n'est pas fiable ? Si tu as d'autres propositions, je suis preneur. Je pense que je vais utiliser Diehard(er) et ses copains. Là j'ai pris ENT car c'est le premier auquel j'ai pensé et qu'il est simple à utiliser.
Au passage l'histoire de la naissance du géant fait en LaTeX est une curiosité mémorable! Sacré Bacula! La pompe à fric procure la sécurité des données ...
Rien compris. C'est qui/quoi le géant fait en LaTeX ?
[^] # Re: À quoi ça sert…
Posté par Sylvain Sauvage . Évalué à 7.
Gare aux licences…
Puis en suite, propose à ces projets de réutiliser mon code.
< mauvais esprit >Ouais, je pompes le code puis je le rends… < / >
Le but serait de concentrer les efforts pour obtenir un code de meilleur qualité que du code que chacun écrit dans son coin.
Mon avis serait que participer à GSL (p.ex.) pour améliorer la partie Aléa serait un meilleur remède aux deux maux que sont la « mauvaise » qualité du code et le « chacun écrit dans son coin » (en fait, je ne vois pas en quoi le fait que ce soit toi qui écrive fasse que ce soit moins « dans son coin », et, même si c’est censé être repris plus tard, pourquoi les auteurs de GSL (toujours p.ex.) ne participeraient pas. D’autre part, à la base, je n’ai pas vraiment l’impression que GSL soit « écrit dans son coin » ou par des non-spécialistes.)
Et, de là, de discuter avec GSL pour « sortir » (ou « désolidariser ») la partie Aléa (et, possiblement, de se rendre compte que ça n’a pas vraiment de sens parce que cette partie utilise d’autres parties de base de la GSL et, qu’au final, tout mettre ensemble n’est pas si gênant (ou pas)).
En fait, j’ai l’impression que beaucoup refont leur petite fonction dans leur coin pour les raisons suivantes :
— pourquoi chercher ailleurs ?
— je n’ai pas besoin de grand-chose, une bidouille suffira ;
— c’est un problème simple / connu / vieux, je suis capable de le faire ;
— le syndrome « pas inventé ici, donc on n’a pas confiance » ;
— le syndrome « ouh là la, mais c’est un canon pour écraser un moustique cette bibliothèque ».
Et, toi-même, tu ne connais pas ce qui existe, donc tu ne t’en sers pas, donc tu as réinventé la roue comme les autres, ou tu veux le faire, et tu trouves que ce qui existe est trop gros…
Ça vaudrait aussi pour Boost : pourquoi refont-ils ce que GSL fait ? Boost est aussi moins complet que GSL…
En fait, je crois qu’ils diraient — et c’est peut-être un indice sur la difficulté de la faisabilité de la séparation de la partie aléa du reste de la GSL —, les générateurs sont liés aux types (int, float…) et, en plus, Boost fait du vrai C++ et veut intégrer tout ça à ses templates…
Sinon, pour info, libgsl.so.0 fait moins de 2 Mio en x86_64 (idem pour le paquet -dev avec tous les .h et le .a). Ce qui n’est pas énorme pour tout ce qu’il y a dedans.
Enfin bon, chacun fait ce qui lui plaît, hein.
[^] # Re: À quoi ça sert…
Posté par fa224718524 . Évalué à 5.
----------
Project Background
The project was conceived in 1996 by Dr M. Galassi and Dr J. Theiler of Los Alamos National Laboratory.
They were joined by other physicists who also felt that the licenses of existing libraries were hindering scientific cooperation.
Most of the library has been written by a relatively small number of people with backgrounds in computational physics in order to provide a consistent and reasonably-designed framework.
----------
C'est pour ça que c'est du C avec une fonction pour le type float, double => optimisation maximale du temps de calcule.
Boost est fait pour les adorateurs du code bloat. C'est pas la même problématique.
Leur but était de réimplémenter en C et libre de droit tout un tas de codes FORTRAN qui traînaient sur les sites académiques.
Discuter avec GSL n'a pas de sens, cette bibliothèque a été conçu aux petits oignons pour simuler des processus physiques, pas pour crypter.
À chaque usage son outil. Point barre. Tu peux l'utiliser pour en faire ce que tu veux, mais tu ne changeras pas une ligne de codes dedans. La partie générateur de nombres est ultra-critique et sert de base à pleins d'algorithmes fournis par la bibliothèque.
[^] # Re: À quoi ça sert…
Posté par Sarcastic . Évalué à 4.
[^] # Re: À quoi ça sert…
Posté par Sylvain Sauvage . Évalué à 2.
[^] # Re: À quoi ça sert…
Posté par Sarcastic . Évalué à 6.
Dans tous les cas, Hasard n'est pas inutile.
# Mersenne twister
Posté par Batchyx . Évalué à 3.
[^] # Re: Mersenne twister
Posté par khivapia . Évalué à 6.
1) l'algorithme utilisé (Mersenne-Twister ou autres)
2) une suite de quelques nombres générés par l'algorithme
pour savoir retrouver l'état interne du générateur et donc être capable de prédire les nombres suivants.
C'est pour ça que les recommandations pour un usage cryptographique imposent d'ajouter en plus un "retraitement" de l'aléas généré. C'est-à-dire, appliquer une fonction de hachage sur la sortie permet d'empêcher l'utilisateur d'avoir accès à la sortie brute de l'algorithme et donc de pouvoir le prédire.
Ensuite il y a des subtilités, genre parfois il vaut mieux ne prendre que quelques bits de la sortie de la fonction de hachage, etc...
Voir http://www.ssi.gouv.fr/site_documents/politiqueproduit/Mecan(...) pour plus de précisions.
# initialisation
Posté par beb . Évalué à 5.
[^] # Re: initialisation
Posté par Yusei (Mastodon) . Évalué à 6.
(Disclaimer: je ne sais pas si c'est la faille principale, c'est juste la plus évidente. C'est pour ça qu'en général on rajoute au moins le pid au résultat de time, mais le pid est aussi public si on a un accès local à la machine.)
[^] # Re: initialisation
Posté par ckyl . Évalué à 3.
Il faut différencier les CSPRNG des PRNG. Initialiser correctement un PRNG on s'en fou puisqu'on peut assez facilement trouver l'état interne, et donc tout les états suivants, du générateur à partir de sa sortie. De mémoire pour un mersenne twister c'est dans les 8Ko.
Au passage si quelqu'un à des références sur des PRNG parallèles (voir une jolie implémentation en java) ça m'intéresse. J'ai pas réussi a mettre la main sur des versions distribuées (sans contention après l'initialisation) et prouvées. La ce serait une contribution intéressante.
[^] # Re: initialisation
Posté par Victor STINNER (site web personnel) . Évalué à 4.
Effectivement, il y a globalement deux usages des générateurs de nombres pseudo-aléatoires : les simulations et la sécurité. Je ne connais pas trop les besoins en simulation, je dirai que l'algorithme doit être rapide. Tandis qu'en sécurité, on recherche un générateur le plus fidèle possible à un générateur réellement aléatoire, tant pis s'il est lent (ex: /dev/urandom vs /dev/random).
OpenSSL et libgcrypt ont d'excellents générateur pour la sécurité, mais n'utilisent pas de base commune de code. C'est dommage car un bug impactant les deux bibliothèques ne sera pas forcément corrigé dans les deux. De même niveau fonctionnalité, si on rajoute une nouvelle source d'entropie dans l'une, l'autre ne saura pas l'exploiter.
Mon idée serait donc de concentrer les efforts pour factoriser le code et donc avoir un maximum de sources d'entropie, beaucoup d'algorithme, et surtout un code bien testé. Pourquoi ne pas réutiliser GSL (ou autre) ? Je pense que le problème est qu' « on » n'a pas envie de tirer une grosse dépendance juste pour un sous-ensemble d'une bibliothèque. Maintenant si Hasard devient aussi gros qu'OpenSSL ou GSL, retour à la case départ :-) La licence BSD et un code écrit en C avec de nombreux bindings pourrait aider à l'intégration dans les autres projets.
Au sujet de ma phrase « Je pense donc récupérer les meilleurs morceaux d'OpenSSL, libgcrypt, et autres (ex: GSL) pour faire une bibliothèque dédiée. Puis en suite, propose à ces projets de réutiliser mon code. », je me suis mal exprimé. Le but est de permettre à OpenSSL d'utiliser les meilleurs bouts de libgcrypt, et inversement !
Bien sûr, il y a des problèmes de licence. J'ai contacté l'auteur de Mersenne Twister pour savoir si je peux utiliser la licence BSD et il m'a dit pas de problème. ISAAC est aussi compatible BSD (c'est dans le domaine public !). Pour RANDU, Park-Miller et drand48, je n'ai finalement réutiliser que des constantes, et je pense qu'elles sont dans le domaine public vu combien elles sont répendues.
Niveau sécurité, Hasard n'est pas prêt pour générer des clés SSH ou certificat X.509. Les algorithmes implémentés ne sont pas sûrs et le code n'est pas assez testé. J'ai implémenté les algorithmes libres trouvés sur Internet. D'autres viendront plus tard. C'était un peu une preuve de concept pour savoir si ça peut intéresser du monde. J'aimerai -si possible- réunir le meilleur des deux mondes, simulation et sécurité, pour factoriser les efforts.
[^] # Re: initialisation
Posté par ckyl . Évalué à 4.
Et bien évidement pour tes objectifs GSL t'es totalement inutile. Pour le côté simulation il y a déjà des lib qui sont reconnues et auditées donc pas trop de besoins (sauf pour les générateurs parallèle).
Après il faut voir si il y a vraiment un besoin pour les CSPRNG et se borner a ça. Mais la il vaut mieux avoir du manpower compétent en cryptographie. Peux tu prouver que la façon dont tu initialises les PRNG ne les affaibli pas (théoriquement et implémentation) ? La faille d'OpenSSL^wDebian c'était une ligne commentée d'un code fait par des experts et modifiée par un maintainer...
[^] # Re: initialisation
Posté par rewind (Mastodon) . Évalué à 5.
Victor: je crois qu'il n'y a pas de place pour ton projet, parce que comme dit précédemment, soit tu te focalises sur les générateurs pour la sécurité et alors il te faut des armes mathématiques pour comprendre ce que tu fais ainsi que des armes informatiques pour bien le faire (et OpenSSL le fera mieux que toi). Soit tu te focalises sur les générateurs pour le reste du monde mais là, tu vas te casser la tête pour rien vu que pour le reste du monde, rand() ou même un Mersenne Twister (qui va être dans la stdlibc++) suffise amplement.
[^] # Re: initialisation
Posté par wismerhill . Évalué à 4.
Heu, c'est le contraire, /dev/urandom c'est la version rapide et /dev/random c'est la version qui attend de récupérer suffisamment d'entropie pour générer les octets suivants.
[^] # Re: initialisation
Posté par khivapia . Évalué à 3.
Euh, ce n'est pas tout à fait vrai ça : si c'est vrai pour la génération de clefs asymétriques (qu'on ne fait pas tous les jours), pour les serveurs de signatures, les protocoles SSL, etc. où on utilise beaucoup de nombres aléatoires à usage unique (nonces ou clefs de session), la vitesse du générateur pseudo-aléatoire commence à avoir une influence importante.
# GSL est vraiment pas mal
Posté par Amine Mokhtari . Évalué à 3.
Par expérience je me demande si tu as conscience Victor à ce que tu t'attaques. Non pas pour te démoraliser ou autres choses, mais j'ai l'impression que tu as une vision simpliste sur laquelle tu t'attaques.
Récemment je me suis posé la même question que toi. J’avais besoin de faire quelques simulations pour valider quelques travaux de recherches (dans le domaine des bases de données). J’avais besoin d'un volume important de données non corrélé (sinon très très peu).
Il est vrai que pour qlq'un qui recherche un générateur de nombre aléatoire, le premier réflexe est d'utiliser Rand() qu'on a par défaut sous c (et C++) dans différentes bibliothèques (glibc entre autres). Mais des qu'on cherche qlq chose de plus sophistiquée on n'a pas systématiquement le reflète de ce dire qu'il y' a forcement une bibliothèque pour cela. Je me disais avec une naïfté qui n'a pour égale que mon... ; que c'était qlq chose de ne pas si compliqué que sa. Mais rapidement j'ai déchanté. Car un bon générateur, bien implémenté doit vérifier certaines propriétés mathématiques (non corrélation, périodicité grande, etc.). Les labiraintes théoriques ont eu raison de ma volonté. Surtout au niveau de la validation d'une implémentation.
Puis je suis tombé sur GSL. Et je dois dire qu'elle est très bien foutue (conception très factorisée en autres).
Donc, je n'aurais qu'une chose à dire à Victor. Ta démarche est louable, mais tu as le choix entre une contribution intégré à GSL qui sera directement utile à une communauté déjà établie. Ou la grande traversée nécessitant environ une décennie pour avoir une bibliothèque mature et reconnue.
[^] # Re: GSL est vraiment pas mal
Posté par wismerhill . Évalué à 2.
J'ai pas l'habitude de coder en C, mais pour de grand volumes de données mon premier réflexe aurait plutôt été /dev/random (pas urandom dans ton cas puisque tu parle de données non corrélée). Un petit coup de dd et tu as la quantité de données que tu veux.
[^] # Re: GSL est vraiment pas mal
Posté par ckyl . Évalué à 2.
Cela dit tu n'as jamais fait de dd avec /dev/random comme source apparemment. Autrement tu saurais comment il se comporte quand le noyau est a cours d'entropie :-)
[^] # Re: GSL est vraiment pas mal
Posté par Sarcastic . Évalué à 4.
# dd if=/dev/random of=/dev/null
0+140 records in
2+0 records out
1024 bytes (1.0 kB) copied, 497.191 s, 0.0 kB/s
Alors, la quantité que tu veux, oui. Mais uniquement si tu as beaucoup beaucoup de temps.
[^] # Re: GSL est vraiment pas mal
Posté par Amine Mokhtari . Évalué à 1.
enfin bon. on peut en débattre encore et encore.
# Une faille ?
Posté par barmic . Évalué à 2.
Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
[^] # Re: Une faille ?
Posté par Victor STINNER (site web personnel) . Évalué à 4.
http://www.random.org/analysis/dilbert.jpg
[^] # Re: Une faille ?
Posté par Sylvain Sauvage . Évalué à 4.
(indice : un dé donne (1, 2, 3, 4, 5, 6), soit (0, 1, 2, 3, 0, 1) avec un %4.)
[^] # Re: Une faille ?
Posté par Cédric Chevalier (site web personnel) . Évalué à 2.
"If you want to generate a random integer between 1 and 10, you should always do it by using high-order bits, as inj = 1 + (int) (10.0 * (rand() / (RAND_MAX + 1.0)));
and never by anything resembling
j = 1 + (rand() % 10); (which uses lower-order bits)."
Mais ceci n'est vrai que pour les anciennes implantations de rand. Donc, maintenant, dans la vraie vie, le modulo est suffisant pour les applications utilisant rand, qui n'ont de toute façon pas forcément besoin d'une forte source d'aléas.
Ensuite, concernant l'exemple du dé, j'aimerai connaitre un processus déterminister qui fait mieux que le modulo pour la répartition :) D'ailleurs, si RAND_MAX est un multiple de 4, tout se passe bien !
[^] # Re: Une faille ?
Posté par TeXitoi (site web personnel) . Évalué à 2.
int rand4(void) { int d; while ((d = dice()) > 4) ; return d; }Cette fonction fini presque surement en un temp infini.[^] # Re: Une faille ?
Posté par Cédric Chevalier (site web personnel) . Évalué à 3.
Je me limitais à un tir de dé, mais c'est vrai que ta solution est belle. Puis j"ai toujours été fan de ce genre de fonctions qui terminent avec probabilité 1 sans qu'on puisse en dire plus :).
[^] # Re: Une faille ?
Posté par khivapia . Évalué à 2.
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.