Aller au contenu | Aller au menu | Aller à la recherche
mardi 11 novembre 2008
Par haypo, mardi 11 novembre 2008 à 16:00 :: Humeur
Suite au décès prématuré de mon ordinateur portable (un Compaq de 2003), je me suis décidé à acheter un ordinateur de bureau monté moi-même. Tout fonctionne sous Ubuntu en 64 bits, et je suis agréablement surpris de la réactivité de la bête.
mercredi 5 novembre 2008
Par haypo, mercredi 5 novembre 2008 à 13:09 :: Programmation
When you're not allowed to commit in a svn repository, it's sometimes difficult to write an huge patch or to maintain an old patch. If the svn is updated while you're working on your patch (or after you wrote your patch), it will be difficult to update your patch. The main problem is that a patch has no reference to the revision number of the patched files. Your patch may apply to svn rev 67001 but not on svn trunk (rev 67103).
That's why I want to try git to be able to easily update a patch to the svn trunk. This article is a quick tutorial to setup your local git repository using git-svn.
samedi 11 octobre 2008
Par haypo, samedi 11 octobre 2008 à 01:48 :: Logiciel libre
Après avoir pas mal utilisé Ubuntu pendant plusieurs années, j'ai décidé de réinstaller Debian Sid sur mon portable histoire de voir si je sais encore m'en servir.
Une fois que j'ai compris que le lecteur de CD était mort (j'ai cramé 3 CDR pour m'en rendre compte), je me suis essayé à l'installation par clé USB.
J'ai choisi de n'installer aucun paquet, c'est-à-dire avoir l'installation la plus minimaliste possible histoire de contrôler ce qui est installé sur ma machine. Les commandes qui suivent permettent d'installer certaines catégories de logiciels.
deb http://debian.revolsys.fr/debian/ sid main contrib non-free deb http://www.debian-multimedia.org sid main
apt-get install less vim
apt-get install kde kdm kde-i18n-fr kde-style-polyester yakuake
Pour partager souris et clavier entre mes deux ordinateurs :
apt-get install synergy
apt-get install mozilla-noscript iceweasel iceweasel-l10n-fr flashplugin-nonfree
apt-get install alsa-utils mplayer
Certains préféreront vlc, xine ou encore totem.
apt-get install ssh-askpass-fullscreen keychain
apt-get install nmap netcat
apt-get install gcc make autoconf automake libtool fakeroot
apt-get install manpages-dev manpages-fr subversion exuberant-ctags meld
apt-get install gdb strace ltrace lsof
apt-get install pyflakes pylint pychecker
apt-get install openoffice.org openoffice.org-l10n-fr ttf-mscorefonts-installer
Utilisez DicOOo pour installer des dictionnaires français plus complets
apt-get install network-manager-kde
Firmware pour mon chipset Intel 3945 :
apt-get install firmware-iwlwifi
Cet article concis et fouilli me servira de notes au cas où je réinstalle la machine. J'espère que vous découvrerez de chouettes paquets parmis ceux que j'ai listé. C'est enfin le moment tant attendu pour placer cette URL : Debian Package of the Day.
mardi 23 septembre 2008
Par haypo, mardi 23 septembre 2008 à 22:50 :: Humeur
Aujourd'hui, un collègue m'a demandé quel était le meilleur moyen d'acheter un billet de TGV sur Internet. Bien que j'effectue régulièrement des aller-retours Strasbourg-Paris en TGV, je ne connais pas LA solution idéale. Néanmoins je connais quelques astuces.
Le site de référence pour acheter des billets de train en France est voyages-sncf.com. Accessoirement, il semble que ça soit le seul site Internet permettant d'acheter des billets SNCF en ligne. C'est également le pire site Internet que je connaisse : bugs d'affichage avec mon navigateur (Konqueror) empêchant parfois de naviguer dans le site, indisponibilités régulières (parfois pendant plusieurs heures), difficultés pour trouver le bon train (absence de réponse ou réponses aberrantes), formulaires compliqués (choix du train et achat en ligne), etc.
Ce site existe depuis 2000 et est géré par le Groupe Voyages-sncf.com (VSC, AVSC et VSCT). Le site utiliserait Oracle sous Solaris, et les bornes (en gare) sont sous Windows XP. Le groupe VSC emploie plus de 260 personnes.
Il existe une version allégée de voyages-sncf : voyages-sncf.mobi, version destinée aux téléphones mobiles mais utilisable sur un ordinateur. Je ne l'ai jamais utilisé pour acheter un billet, mais il semble beaucoup plus simple. Notez l'absence de publicité !
Il existe également tgv.com qui propose des informations sur les trains TGV. On peut rechercher des horaires ou acheter un billet, mais on est fatalement redirigé sur voyages-sncf.com.
Bah tiens, il existe aussi ter-sncf.com, peut-être enfin un site SNCF simple pour trouver des horaires ? Mis à part un petit bug (il me demande de choisir entre la gare et la commune de Sélestat, or c'est la même chose), l'affichage des résultats est propre et la navigation dans les horaires suivantes / précédentes est agréable. Il n'est pas possible d'acheter de billet en ligne. En même temps, pas besoin de réserver pour un TER.
Il existe aussi les sites d'information sncf.com (informations générales sur la SNCF) et infolignes.com (état actuel et prévisions du trafic).
Il existe aussi des agences SNCF dans les centres villes (dans les grandes villes en tout cas) qui évitent d'aller en gare pour acheter des billets. À Paris, j'avais également vu des bornes (les gros trucs jaunes) en super-marché (Monoprix), mais leur disponibilité est loin du 100%.
Ce qui me choque aussi bien sur bahn.de ou sbb.ch, c'est la vitesse à laquelle apparaissent les résultats d'une recherche. Ils n'ont besoin que d'une seconde alors que voyages-sncf.com prend environ cinq secondes pendant lesquelles il nous impose une publicité ! D'ailleurs, la navigation sur voyages-sncf.com est lente de manière générale, pas uniquement lors d'une recherche. Il faut s'armer de patience pour « modifier tous les souhaits ».
Un ami m'a parlé du site trocdesprems.com qui permet de revendre ou d'acheter des billets Prems (non échangeables ni remboursables). Je n'ai jamais acheté de billet sur ce site, mais je suis sûr qu'on peut y faire de bonnes affaires.
dimanche 21 septembre 2008
Par haypo, dimanche 21 septembre 2008 à 19:36 :: Fuzzing
Après 3 versions béta, le projet Fusil est enfin sorti en version 1.0 ! La version 1.0beta3 a été annoncée dans un journal linuxfr, et sur les listes de diffusions Full Disclosure et Pen test.
Entre la version 0.9.1 et la 1.0, la liste des changements est longue, mais voici les plus importants :
Fusil fonctionne sous Linux, FreeBSD et Windows. Il nécessite Python 2.4, supporte CPython et PyPy. Des paquets Debian, Mandriva, et d'autres distributions Linux sont disponibles.
J'ai écrit l'article « Pratique du fuzzing avec Fusil » dans le dernier numéro du magazine MISC (#39). L'article fait parti du dossier dédié au fuzzing.
D'ailleurs, j'ai bien aimé aimé l'article sur Sulley (fuzzer similaire à Fusil) de Gabriel Campana et Laurent Butti (deux dingues de fuzzing qui vous envoyent des exploits noyaux par le wifi !). J'y ai appris qu'ils ont réutilisé python-ptrace (binding Python de ptrace) pour porter Sulley sous Linux.
jeudi 11 septembre 2008
Par haypo, jeudi 11 septembre 2008 à 13:23 :: Humour
Alors que je recherchais une liste des numéro de commit pour lesquels il faut payer son coup (exemples : 1000, 1664, 5000), je suis tombé sur une liste des phobies sur Wikipédia. J'apprend qu'il existe la triskaidékaphobie, peur du nombre 13, et l'hexakosioihexekontahexaphobie, la peur du nombre 666. Alors comme ça il existe des avions sans place numéro 13, j'avais jamais fait attention :-) Photo des boutons d'un ascenseur sans étage 4 ni 13 :
J'avais aussi lu que les appartements numéro 13 se vendent moins bien, en y réfléchissant, ça se comprend. Ça me rappelle un article sur l'absence de quatrième étage : c'est la tetraphobie, peur du nombre 4 venue de Chine où la prononciation du nombre 4 (四) sonne comme le mot « mort » (死). Un bande dessinée sur ces phobies :
(lire la BD en grand format : 600x720 pixels)
Bon, avec tout ça, je ne suis pas avancé pour savoir si je dois ou non payer mon coup pour le commit numéro 2175 ;-) Je devrais peut-être le décomposer en nombre premiers pour voir, ou alors séparer chaque chiffre et en calculer la somme modulo 17, ou .... euh, je vais arrêter ça tout de suite avant de finir en tuant ma copine (histoire de placer une référence au chouette film « 23 » avec Jim Carrey) !
vendredi 22 août 2008
Par haypo, vendredi 22 août 2008 à 01:08 :: Python
Python est un langage interprété par une machine virtuelle appelée CPython. Dumoins, CPython est l'implémentation de référence, il en existe d'autres moins répendues (PyPy, Jython, IronPython, etc.). Pour ceux qui ne le savent pas encore, CPython est écrit en langage C. Lorsque CPython plante (« Fatal error: ... », erreur de segmentation ou autre), il est difficile de connaître les raisons du plantage. Ce billet devrait vous éclairer un peu si vous en êtes arrivé à passer par gdb pour déboguer Python.
lundi 18 août 2008
Par haypo, lundi 18 août 2008 à 13:45 :: Sécurité informatique
Je commence doucement à comprendre comment fonctionnent les générateurs de nombres pseudo-aléatoires (PRNG) et à voir quel est leur impact dans la sécurité informatique. En bref : la sécurité repose sur eux, trouver une faille dans le générateur revient à compromettre la sécurité !
Cas où les PRNG empêchent qu'un espion puisse lire ou injecter des données dans un canal de communication (connexion réseau) :
Cas où un PRNG sert à prouver l'identité d'une personne :
La graine est un nombre de N bits utilisé pour construire l'état interne (M bits) du PRNG. N est souvent plus petit que M. Exemple : time(NULL), 32 bits voir beaucoup moins, est utilisé pour construire l'état interne de l'algorithme Mersenne Twister (20.000 bits). Il est plus facile de deviner N bits que M (32 vs 20.000 dans le cas de Mersenne Twister), c'est donc la première cible.
Obtenir la graine permet de reconstruire l'état interne initial complet.
Cas réel :
Une graine basée uniquement que sur time(NULL), getpid() et getppid() ne peut être utilisée dans un contexte de sécurité. Il faut utiliser de vraies sources d'entropies (ex: /dev/random sous Linux).
Si un attaquant arrive à obtenir suffisamment de bits générés par le PRNG, il pourra reconstruire l'état interne du PRNG. Dans le cas de Mersenne Twister, il suffit de 19.937 bits (ou 624 nombres de 32 bits) pour reconstruire l'état interne complet.
Pour éviter qu'un attaquant puisse reconstruire l'état interne du PRNG à partir de bits générés, on peut utiliser une fonction de hachage (ex: SHA-1) sur sa sortie. Un attaquant devra inverser la fonction SHA-1 pour obtenir l'état interne (ce qui est possible mais très coûteux).
Pour générer un nombre pseudo-aléatoires dans un intervalle, un mauvais PRNG va produire certaines valeurs plus fréquemment. En connaissant le biais, l'attaquant peut gagner du temps en testant ces valeurs en priorité.
Un bon PRNG donne une distribution uniforme : chaque nombre doit sortir avec une probabilité identique. Assurez-vous que le PRNG passe tous les tests statistiques connus (ex: Mersenne Twister ne passe pas tous les tests de Dieharder).
Il a été prouvé (lire Des Trappes dans les Clés) qu'il est possible de construire un PRNG valide (passant tous les tests statistiques) possédant une porte dérobée. Son auteur peut alors calculer les nombres générés sans pour autant connaître la graine. En pratique, l'attaquant devra toujours effectuer une recherche par force brute, mais avec un coût très inférieur au coût classique de recherche exhaustive (ex: 2^32 au lieu de 2^256).
La porte dérobée peut être introduite au niveau algorithmique (ex: On the Possibility of a Back Door in the NIST SP800-90 Dual EC PRNG) ou bien dans une implémentation.
Casser un PRNG permet de :
L'opération de regénération de la graine, appelée reseed, limite la portée d'une attaque. Cette opération peut se faire après avoir généré N bits (ex: générer 1000 mots de passe) ou alors une fois que le pool d'entropie a atteint un certain seuil (dépend des générateurs matériels et non plus de la quantité de bits pseudo-aléatoires générés). Un pirate n'aura donc pas accès à tous les mots passe (certificats ou autre) précédents et suivants, mais seulement une partie.
Appeler reseed après chaque nombre généré est une très mauvaise idée si la graine est de mauvaise qualité. Exemple : appeler srand(time(NULL)) après chaque appel à rand() va avoir pour conséquence de générer plusieurs fois le même nombre durant la même seconde. Il est primordial d'utiliser une source ayant une excellente entropie.
Pour en savoir plus : Random number generator attack.
dimanche 17 août 2008
Par haypo, dimanche 17 août 2008 à 17:16 :: Humour
Tiens, les spammeurs français ont découverts la génération automatique de phrases, ça donne de drôles de choses :
Tout ça, c'est du charabia...
jeudi 14 août 2008
Par haypo, jeudi 14 août 2008 à 13:52 :: Programmation
Histoire de ne pas les perdre, j'ai mis en ligne les différentes présentations que j'ai données depuis 2005 : voir toutes mes présentations. Vous y trouverez les supports (diaporamas) des présentations, si possible l'enregistrement vidéo, et les documents utilisés (pour les ateliers). Présentations archivées :
Les présentation sont au format Beamer ou S5. Je suis déçu d'avoir perdu les traces de mes ateliers XHTML/CSS et sur Gimp que j'avais donné à mon école (UTBM). Tant pis.
dimanche 13 juillet 2008
Par haypo, dimanche 13 juillet 2008 à 23:54 :: Informatique
Je suis devant mes ordinateurs de 8h jusqu'à plus de 16h certains jour. Mon poste de travail est donc critique. Je vous invite pour une petite visite, voir l'antre depuis lequel je télétravaille.
Bien sûr, j'ai tout rangé pour la photo :-) La chaise avec dossier en cuir est rigide et s'incline quand je me penche en arrière. Les pieds du bureau sont dans les coins, donc en pratique, j'ai énormément d'espace pour les jambes. L'imprimante dans un coin est une imprimante laser noir et blanc : HP LaserJet 2015. Elle est parfaitement compatible Linux, imprime la première page en 8,5 secondes et les suivantes suivent immédiatement. La machine à café, Magimix de Nespresso, n'est pas compatible Linux mais produit un excellent café :-)
J'utilise deux écrans en 1280x1024 pixels côte à côte, chacun branché sur un ordinateur différent : un portable (écran au fond en jaune) et un fixe (fond bleu). C'est des écrans LCD 17 pouces que je trouve agréables. Je n'ai pas réellement noté de différence avec un écran CRT... mis à part l'encombrement : les écrans prennent juste 5 cm en profondeur, ce qui laisse toute la place à mes bras.
Grâce à Synergy, je n'utilise qu'un seul couple clavier-souris pour les deux ordinateurs. Il suffit de passer le curseur de la souris sur le bord de l'écran pour changer de machine. Le copier-coller fonctionne dans les deux sens, même quand j'utilise Windows sur une des machines. Le clavier est un Logitech UltraX : sensisble, silencieux et assez lourd pour être stable. Je voulais essayer un clavier « plat » et j'en suis plutôt satisfait, c'est agréable.
Ma souris n'est pas une souris mais une trackball : Logitech Cordless Optical TrackMan. Ce périphérique épouse la forme de la main. C'est beaucoup plus reposant qu'une souris, les muscles sont moins contractés.
J'ai toujours une souris (secondaire) dans un coin pour Gimp ou quand la trackball m'énerve. Effectivement, une trackball est moins précise qu'une souris, en particulier pour cliquer sur une zone de 10x10 pixels ou moins. Exemples : fermer une fenêtre en cliquant sur la croix, case à cocher dans un formulaire web, sélectionner une ligne de texte dans une page web ou document PDF, etc. Je redécouvre l'ergonomie par la pratique :-)
Pour finir, la déco. En face, un poster de Gilles Tran (Main Street (West)), à côté une peinture de Dalí (Une femme à la fenêtre), et à gauche un poster de Gaston dessiné par Franquin ramené du musée de la bande dessinée de Bruxelles :
Fin de la visite, n'oubliez pas le guide (laissez un commentaire ;-)).
mercredi 9 juillet 2008
Par haypo, mercredi 9 juillet 2008 à 13:18 :: Python
Suite à ma conférence sur l'assurance qualité et fuzzing aux RMLL, je me suis remis à jouer avec mon fuzzer Fusil. Dans le TGV retour, 8h quand même pour rentrer à Strasbourg, j'ai écrit un fuzzer pour le langage Python. L'idée est de récupérer la liste des fonctions, classes et méthodes d'une module, et les appeler/instancier avec un nombre d'arguments aléatoires de type aléatoire. Comme je m'y attendais, une fois le fuzzer python écrit, CPython 2.5 a rapidement planté : erreur de segmentation dans le module imageop.
Pour écrire un rapport de bug correct, j'ai reproduit les bugs avec la version trunk (futur CPython 2.6) compilée avec l'option pydebug et... mince, ça plante plus : le bug imageop est déjà corrigé. J'ai donc amélioré le fuzzer pour qu'il ne teste non plus uniquement un seul module, mais toute une liste de modules (j'ai noté ceux écrits en langage C), et j'ai rajouté d'autres types d'argument (nombre flottant, objet, unicode, etc.). Voilà CPython qui plante, ouf, l'honneur du fuzzing est sauf :-) J'ai alors rapporté une quinzaine de bugs (cherchez les bugs rapportés entre le 6 et le 9 juillet), à chaque fois accompagné d'un patch et d'un exemple pour reproduire le crash. Deux patchs sont déjà appliqués.
Pour fêter ce succès, j'ai publié la version 0.9 de Fusil. Cette nouvelle version contient le nouveau fuzzer pour Python, peut s'exécuter dans l'interprète Python PyPy, gère mieux le logging (sortie plus concise mais contient le nombre de crash et un fichier project.log est conservé dans le dossier du projet), et l'outil IncrMangle est plus rapide et précis.
Enfin, j'ai fuzzé un peu PyPy, mais le seul vrai bug que j'ai trouvé est dans un module que j'ai écrit (module pwd écrit avec ctypes) ! Par contre, Carl (cfbolz sur le salon IRC #pypy du serveur Freenode) a trouvé d'autres bugs dans PyPy en utilisant Fusil.
Pour résumer, vu les résultats face aux tests de fuzzing, on peut classer la qualité des interprètes Python comme ceci : CPython 2.5 < CPython trunk << PyPy où << veut dire très supérieur. Effectivement, je n'ai trouvé qu'un seul bug PyPy après une nuit de fuzzing contre une quinzaine dans CPython rapidement détectés.
jeudi 19 juin 2008
Par haypo, jeudi 19 juin 2008 à 00:46 :: Logiciel libre
En dehors des raccourcis claviers que j'avais déjà abordé, il existe énormément d'astuces pour améliorer la ligne de commande sous Linux. En voici quelques unes pour gagner encore plus de temps avec la ligne de commande.
La touche TAB sert à compléter automatiquement les commandes. C'est diablement efficace, mais bash peut faire mieux ! En chargeant /etc/bash_completion, la complétion dépendra du programme utilisé. « kpdf <tab><tab> » n'affichera que les fichiers PDF (et les répertoires). « apt-get install python-<tab><tab> » affiche les paquets Debian installables dont le nom débute par « python- ». Pour l'activer la complétion avancée, ajoutez dans votre ~/.bashrc :
source /etc/bash_completion
Le chargement de bash sera plus long, mais vous serez beaucoup efficace avec votre ligne de commande !
Par défaut, bash conserve toutes les commandes tapées. J'ai présenté dans mon billet précédent la variable d'environnement HISTIGNORE pour ignorer certains commandes. Pour ne pas sauver un commande saisie plusieurs fois, utilisez :
export HISTCONTROL=ignoredups
Rappel : CTRL+r permet de rechercher une commande déjà tapée en en saisissant quelques lettres.
Pour lire un fichier texte, il existe le programme more qui n'est pas très pratique. Le programme less est mieux : il permet de revenir en arrière, rechercher du texte, etc. Il existe encore mieux ! most utilise des couleurs (meilleur rendu des pages de manuel), permet de découper l'écran en plusieurs vues indépendentes, etc. Lisez l'aide intégrée pour les détails. Installez-le avec « apt-get install most » et choisissez-le par défaut en ajoutant dans votre fichier de configuration ~/.bashrc :
export PAGER=most
Plusieurs programmes permettent d'afficher des couleurs mais ne le font pas par défaut pour des raisons de compatibilité avec les anciens terminaux. Activez les couleurs avec :
alias ls='ls --color=auto' alias grep='grep --color' alias egrep='egrep --color'
L'option « -h » permet d'afficher les tailles avec des unités plus facilement compréhensibles par un humain (19 Ko, 367 Mo, 1 Go, ...) :
alias du='du -h' alias df='df -h'
La commande ls supporte également l'option.
Par défaut, les programmes sont silencieux : ils ne disent pas ce qu'ils font. Or c'est pratique pour vérifier qu'on a bien fait ce qu'on voulait. Aliases pour activer le mode verbeux :
alias ln='ln -v' alias cp='cp -v' alias mv='mv -v' alias rm='rm -v'
L'invite est le court texte invitant à saisir une commande, du style « haypo@marge:~$ ». C'est la variable d'environnement PS1 qui contient l'expression pour générer cette invite. « \u » est remplacé par le nom d'utilisateur, « \h » le nom de la machine, « \w » le répertoire de travail, etc.
Je n'aime pas du tout avoir une invite qui contient le répertoire de travail car l'invite prend rapidement toute la largeur de l'écran. J'utilise donc une invite qui ne contient que le nom de la machine :
export PS1='\h$ '
C'est rudimentaire mais efficace. La commande « pwd » me sert à me rappeler où je suis quand je me perd ;-)
Voilà, j'espère que je vous ai appris des trucs, n'hésitez pas à m'en apprendre d'autres en déposant un commentaire !
Par haypo, jeudi 19 juin 2008 à 00:06 :: Logiciel libre
L’erreur est humaine, mais pour provoquer une vraie catastrophe, il faut un ordinateur.
Quand on passe trop de temps dans la ligne de commande, on a tendance à oublier qu'on manipule des documents importants et qu'au détour d'une commande on peut les éradiquer à tout jamais ! Voici quelques astuces pour limiter la casse : lignes à ajouter dans votre configuration « ~/.bashrc ».
Alias qui rajoutent l'option -i sur les opérations dangereuses :
alias ln="ln -i -v" alias cp='cp -i -v' alias mv='mv -i -v' alias rm='rm -i'
Vous pouvez également utiliser l'option -k de tar pour éviter d'écraser les fichiers existant :
alias tar='tar -k'
Bash possède une option -C pour interdire les redirections vers un fichier existant :
set -C
Exemple au pif : ça arrive qu'on tape « echo "user:password:" >/etc/passwd » alors qu'on voulait écrire « >>/etc/passwd » :-)
Bash permet de ne pas mettre une commande dans l'historique (touche haut ou CTRL + r) avec la variable HISTIGNORE :
# Ignore commands like: # >konsole&< # any command starting with a space (eg. " sudo touch /tmp/x") # >bg< # >fg< # >exit< # >svn revert*< # >hg revert*< # >*rm *< (eg. "svn rm file", "rm -rf dir", ...) # >tee *< export HISTIGNORE='*&: *:[bf]g:exit:*>|*:history*:svn revert*:hg revert*:*rm *:tee *'
Du coup, si vous tapez une commande que vous savez délicate, précédez la d'une espace pour éviter qu'elle soit sauvée (merci acatout pour l'astuce !).
mardi 10 juin 2008
Par haypo, mardi 10 juin 2008 à 00:00 :: Sécurité informatique
Les générateurs de nombres pseudo-aléatoires sont utilisés principalement à deux fins :
Dans les deux domaines, la qualité du générateur est importante. Si un générateur est biaisé, c'est-à-dire que la distribution n'est pas équitable entre les différentes valeurs possibles, le résultat de la simulation sera invalide (ou bien simplement imprécis) et la confidentialité peut être comprise. Par contre, la simulation privilégie la vitesse du générateur. Alors que pour la sécurité on se donne les moyens pour qu'il soit difficile de deviner les nombres précédemment générés et les prochains nombres générés (quitte à ce que le générateur soit plus lent), ce qui revient à deviner quel est l'état interne du générateur étant donné qu'un algorithme est déterministe.
Reprenons l'exemple de RANDU, un générateur biaisé (les bits de poids faible sont peu aléatoires). Si on utilise 1 + rand() % 6 pour simuler un lancé de dé, on va obtenir une suite du genre :
1, 3, 1, 5, 3, 3, 1, 5, ...
Les faces 2, 4 et 6 ne sont jamais tirées !
Il est possible de deviner l'état interne d'un générateur congruentiel linéraire (LCG) en ne connaissant qu'un seul nombre généré. L'algorithme RANDU est :
x(n+1) = (x(n) * 65539) % 2147483648
Avec x(0) : graine du générateur. On peut exécuter le générateur à l'envers en calculant :
y(n+1) = (y(n) / 65539) % 2147483648
Sachant que diviser revient à multiplier par l'inverse, x / 65539 <=> x * (1 / 65539), on va calculer l'inverse 65539 modulo 2147483648 avec le théorème des restes chinois. En pratique, on utilise l'identité de Bezout. Fonction Python qui calcule les coefficients u et v tels quel a · u + b · v = 1 :
def bezout(a, b):
u0 = 1; u1 = 0
v0 = 0; v1 = 1
while 1:
q = a // b
r = a % b
u0, u1 = u1, u0 - q*u1
v0, v1 = v1, v0 - q*v1
if r != 0:
a = b
b = r
else:
break
return (u0, v0)
On calcule alors bezout(65539, 2147483648) = (477211307, -14564), ce qui donne :
65539 · 477211307 - 2147483648 · 14564 = 1
et
(477211307 * 65539) % 2147483648 = 1
Finalement, y(n+1) = (y(n) * 477211307) % 2147483648.
Exemple :
x(0) = 42 x(1) = 2752638 x(2) = 16515450 x(3) = 74318958
On utilisant x(3), on va pouvoir générer les nombres précédents :
y(0) = 74318958 y(1) = 16515450 y(2) = 2752638 y(3) = 42
On a donc réussi à retrouver les nombres précédents jusqu'à la graine (42). Même si le générateur ne délivre que quelques bits de son état interne (ex: rand() = x(n) & 0xffff), on peut retrouver l'état interne en utilisant une recherche exhaustive (si on dispose de quelques nombres successifs).
Pour rééquilibrer la distribution d'un générateur, on peut l'améliorer en utilisant différrentes techniques :
Lire la RFC 1750 pour les sources et les détails sur ces techniques.
Pour empêcher qu'un pirate arrive à deviner l'état interne du générateur, on peut rajouter une fonction de hachage sur la sortie du générateur (ex: MD5, SHA-1, ...). Il est toujours possible d'inverser la fonction de hachage, mais c'est beaucoup plus difficile !