Blog Haypo

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.

voyages-sncf.com

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.

Sites web SNCF alternatifs

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).

Agences SNCF

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%.

Horaires des trains sur les sites étrangers

• bahn.fr (Allemagne) : site de la Deutsche Bahn simple, efficace et disponible dans trois langues (allemand, français et anglais). Il demande juste de préciser son âge pour calculer le prix du billet.
• sbb.ch (Suisse) : site des Chemins de fer fédéraux suisses disponible en quatre langues (français, allemand, italien et anglais). La page d'accueil est très sobre et n'affiche qu'un moteur de recherche.

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 ».

Pour finir

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.

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.

Nouveautés de Fusil 1.0

Entre la version 0.9.1 et la 1.0, la liste des changements est longue, mais voici les plus importants :

• Fusil exécute maintenant les processus fils sous un autre utilisateur UNIX (fusil) pour éviter qu'il supprime vos fichiers ou tue vos processus !
• Création d'un script replay.py pour pouvoir rejouer une session. Il permet de rejouer une session dans gdb, Valgrind ou gdb.py.
• Possibilité de créer un fichier de configuration (~/.config/fusil.conf) pour modifier de nombreuses options (ex: désactiver le débogueur)
• Renomme le dossier d'une session avec le type d'erreur pour pouvoir regrouper les sessions similaires (ex: « invalid_read-null », « div_by_zero », « timeout », etc.).
• Chaque fuzzer est un programme qui a ses propres options en ligne de commande : utilisez l'option --help pour obtenir l'aide de chaque fuzzer
• Création de fusil-vlc : teste le lecteur multimédia VLC
• Création de fusil-zzuf : réutilise la bibliothèque zzuf de Sam Hocevar. Contrairement aux outils Fusil, zzuf mute les fichiers en mémoire, ce qui est plus rapide et permet de travailler avec de très gros fichier (plusieurs giga-octets).
• Support de Python 3000 avec le script de conversion conv_python3.0.sh qui utilise le programme 2to3 puis applique quelques patchs supplémentaires
• Support minimal de Windows

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.

Article dans le magazine MISC

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.

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) !

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.

Lire la suite

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é !

Utilisations des PRNG

Cas où les PRNG empêchent qu'un espion puisse lire ou injecter des données dans un canal de communication (connexion réseau) :

• L'établissement d'une connexion SSL (https dans firefox) ou SSH utilise un PRNG pour générer des clés de session
• La sécurité du protocole TCP repose sur un PRNG

Cas où un PRNG sert à prouver l'identité d'une personne :

• Création d'un mot de passe (ex: programme pwgen) ou d'une clé SSH utilisés pour l'authentification
• Création d'un certificat X.509 (ex: identité d'un serveur avec https)
• Création de clés GPG (courriels)
• etc.

Attaquer la graine

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 :

• Dans la faille OpenSSL Debian, la valeur réelle de N était 15 : ce qui donne seulement 32.768 graines différentes
• DSA-152-1 l2tpd -- missing random seed : la graine était tout simplement constante...

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).

Reconstruire l'état interne

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).

Biais dans un générateur

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).

Porte dérobée dans un générateur

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.

Limiter l'effet d'une attaque dans le temps

Casser un PRNG permet de :

• Calculer les nombres précédemment générés (passé)
• Calculer les nombres qui vont être générés (futur)

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.

Tiens, les spammeurs français ont découverts la génération automatique de phrases, ça donne de drôles de choses :

• Votre Penis Atteindre Vos Genoux Et Votre Menton!
• Atteindre L'autre Cote Du Monde Avec Mon Piquer!
• Vous Vous Sentirez Lui au Coeur de Votre Chatte!
• Votre Amie Peut Sauter! Plus! Plus forte!
• Agiter Les Nuages De Votre Front! Il Fait Doux Vous!

Tout ça, c'est du charabia...

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 :

• 2008 : Présentation de Fusil le fuzzer aux RMLL
• 2008 : Présentation de PyPy et de Python 3000 à Pycon FR
• 2007 : Divers présentations sur la programmation Python (style du code, gestion des exceptions et des erreurs, écriture d'un module, les tests) aux Journées Python Francophones
• 2005 : Atelier sécurité sur PHP et SQL
• 2005 : Atelier sécurité sur le langage C

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.

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 ;-)).

Fuzzer 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.

Rapports de bugs Python 2.6

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.

Publication de Fusil 0.9

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.

Fuzzing de PyPy

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.

Classement des interprètes Python

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.

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.

Complétion avancée

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 !

Ignorer les doublons dans l'historique

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.

Utiliser most plutôt que less pour lire du texte

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

Activer les couleurs

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'

Tailles de fichier avec des unités humaines

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.

Passer en mode verbeux

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'

Personnaliser l'invite

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 !

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 ».

Option -i pour demander confirmation

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'

Option -C de bash

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 » :-)

Configurer l'historique

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 !).

Exigences vis à vis d'un générateur de nombres pseudo-aléatoires

Les générateurs de nombres pseudo-aléatoires sont utilisés principalement à deux fins :

• Simulation : simulation physique, jeux vidéos, etc.
• Sécurité : générer un secret pour garantir la confidentialité

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.

Générateur biaisé

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 !

Inverser un générateur congruentiel linéraire

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).

Solutions

Pour rééquilibrer la distribution d'un générateur, on peut l'améliorer en utilisant différrentes techniques :

• Utiliser la parité du flux
• Utiliser le mapping de transition (technique de Von Neumann)
• Utiliser la transformée de Fourier discrète (ou une transformation de Fourrier rapide, FFT)
• Utiliser la compression (en zappant les entêtes et autres parties « fixes »)

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 !

Suite au bug OpenSSL de Debian, je me suis à nouveau intéressé de près aux générateurs de nombres pseudo-aléatoires (PRNG). J'ai commencé à écrire la bibliothèque Hasard qui contient plusieurs algorithmes pour générer des nombres et des fonctions de haut niveau : int(min, max), bool(), bytes(size), etc.

Outils ENT et Dieharder

J'ai utilisé le programme ENT pour tester la qualité des algorithmes. ENT utilise :

• Test d'entropie,
• Test du χ²,
• Estimation de PI par la méthode de Monte-Carlo avec calcul de l'erreur en pourcentage
• Calcul de la moyenne arithmétique : (x1+x2+...+xn) / n. La valeur parfaite est 255 / 2 = 127,5.
• Coefficient de corrélation en série (?)

ENT n'accepte en entrée que des fichiers contenant des octets (pseudo-)aléatoires. On ne peut donc pas tester la qualité d'un générateur de nombre flottants par exemple. Exemple de sortie (algorithme RANDU avec l'opérateur pow2(8)) :

Entropy = 6.000000 bits per byte.

Optimum compression would reduce the size
of this 262144 byte file by 25 percent.

Chi square distribution for 262144 samples is 786432.00, and randomly
would exceed this value 0.01 percent of the times.

Arithmetic mean value of data bytes is 126.0000 (127.5 = random).
Monte Carlo value for Pi is 2.999862669 (error 4.51 percent).
Serial correlation coefficient is 0.322338 (totally uncorrelated = 0.0).

Il existe également le programme Dieharder qui accepte en entrée des nombres de 32 bits non signés dans un fichier binaire ou un fichier texte. Il utilise des tests bien plus rigoureux, mais comme je ne sais pas les interpréter, je ne vais pas commenter.

Représentation visuelle

C'est pas très rigolo tout ça, alors voyons un peu des dessins et schémas qui permettent de distinguer le bon chasseur du mauvais chasseur. Image générée à partir des 8 bits de poids faible de l'algorithme RANDU :

Chaque pixel utilise une valeur du générateur comme couleur. On voit clairement que l'algorithme n'est pas du tout aléatoire ! Pour reproduire l'image :

$ cd tests
$ ./gen_files.py --rng=randu --op=pow2 --bits=8 randu.dat
$ ./draw_pil.py --width=300 --height=300 randu.dat

Une autre façon de représenter des nombres est d'utiliser un axe 2D avec x=random() et y=random() :

On voit qu'il existe très peu de combinaisons (x, y) : j'en dénombre 16. Pour reproduire cette image :

$ ./gnuplot.py randu.dat --point=2

La page web graphics présente d'autres images.

Script de tests de la bibliothèque Hasard

Le script gen_files.py génère un fichier au format texte plat qui contient les nombres générés par l'algorithme RANDU pour l'opérateur pow2(8) (génère un nombre dans l'intervalle [0; 255]). Lire file_format.rst pour voir le format de ce fichier. Le script file_info.py calcule l'entropie des nombres générés, la valeur maximale et la valeur minimale.

$ ./file_info.py randu.dat
Engine: randu
Seed: linux_urandom
Range: 0..255
Operation: pow2
Count: 262144
Minimum: 1
Maximum: 251
Entropy: quality=75.00%, value=6.0000/8.0000

On voit que seul 6 bits sur 8 sont réellement aléatoires (2 bits sont invariants) et que l'intervalle annoncé est incorrect : 0..255 versus 1..251.

J'aime bien l'algorithme RANDU car il est vraiment mauvais et il permet donc de tester l'outillage de test :-)

Pour la suite

Ma bibliothèque est encore en chantier. J'ai beaucoup travaillé sur l'outillage pour tester la sortie des algorithmes en comparant avec d'autres bibliothèques comme Python, PHP ou la libc. La version 0.2 n'inclut par encore ce travail, ça sera le cas pour la prochaine version 0.3 qui n'est pas encore publiée. En attendant, vous pouvez utiliser le dépôt Mercurial.

Je ne sais pas trop ce qu'Hasard va donner au final, mais en tout cas ça avance :-)

Comme l'année passée, je participe aux Journées Python Francophones organisées par l'AFPy à Paris (à la Cité des Sciences et de l'Industrie pour être exact). Contrairement aux conférences telle que Blackhat où l'entrée coûte plusieurs milliers d'euros, Pycon FR est entièrement gratuit !

Pour les gens qui ne peuvent pas se rendre à Paris ou qui sont déjà pris ce week-end là, aucun soucis ! Les conférences seront diffusées en direct sur Internet (ils ont pensé à tout). Elles seront très certainement disponibles en téléchargement un peu plus tard.

Au niveau du programme, je vous laisse le consulter vous même. Je donne une conférence sur l'interprète PyPy et une autre sur Python 3000. Il faudrait d'ailleurs que je commence à les préparer... Pour l'anecdote, j'ai deux collègues INL qui donnent des conférences (seb et misc) :-)

Pycon FR est aussi l'occasion de rencontrer des programmeurs Python et de discuter autour d'un café ou d'une bière. Alors, viendez !

Maintenant que j'ai écrit combien je suis indigné de la retouche photo, je vais vous présenter quelques outils de traitement d'image impressionnants :-)

Morphing de visage en 3D (1999)

• Auteurs : Volker Blanz, Thomas Vetter
• Utilisation : Changer l'expression du visage (ex: sourire ou non), la forme (ex: maigre ou gros), le type ethnique (couleur de la peau, forme des yeux, ...), etc.
• Site du projet
• Publication : A Morphable Model for the Synthesis of 3D Faces (juin 1999)
• Vidéo de démonstration : Morphing de visage en 3D

Exemple de modification du visage de Tom Hanks à partir d'une seule photo (1) :

Scale2x (2001)

• Auteur : Andrea Mazzoleni
• Utilisation : Agrandir 2 ou 4x la résolution (en pixels) d'anciens jeux de faible résolution (typiquement 320x200 pixels en 16 ou 256 couleurs)
• Site internet : Scale2x
• Démonstration : Scale2x, Scale4x

Exemple de l'algorithme Scale2x :

Interactive Digital Photomontage (2004)

• Auteurs : Aseem Agarwala, Mira Dontcheva, Maneesh Agrawala, Steven Drucker, Alex Colburn, Brian Curless, David Salesin, Michael Cohen
• Site Internet : Interactive Digital Photomontage
• Utilisations :
  • Créer une photo de famille où tout le monde souri à partir de plusieurs photos
  • Supprimer des personnes et objets pour créer une photo de paysage ou monument « propre »
  • Augmenter la profondeur de vue d'une photo macro (pris à quelques centimètres d'une plante ou animal)
  • Créer un panorama
  • Corriger l'éclairage d'un objet
• Publication : Interactive Digital Photomontage (mai 2004)

Exemple de montage tronqué et simplifié (j'ai apposé moi même les marques vertes et rouges pour mieux comprendre) pour créer une photo de famille où tout le monde est heureux :

GREYCstoration (2006)

• Auteur : David Tschumperlé
• Site internet
• Photos de démonstration
• Utilisations :
  • Supprimer le bruit d'une photo
  • Agrandir une photo ou un dessin
  • Supprimer de petits objets comme un grillage ou du texte incrusté dans une photo
• Publication : Fast Anisotropic Smoothing of Multi-Valued Images using Curvature-Preserving PDE's (juin 2006)

Exemple tronqué de la suppression de la cage d'un perroquet :

Seam Carving for Content-Aware Image Resizing (2007)

• Auteurs : Ariel Shamir et Shai Avidan
• Publication : Seam Carving for Content-Aware Image Resizing (août 2007)
• Vidéo de démonstration

Exemple de réduction de la hauteur d'une photo d'un port (j'ai réduit l'ensemble avec un redimensionnement cubique pour que ça tienne dans le blog) :

Je n'ai présenté que quelques outils que je connais. Il en existe sûrement d'autres encore plus puissant ! Bientôt Blade Runner sera la réalité...