Intrigués par la rapidité avec laquelle une attaque par table arc-en-ciel (Rainbow table) permet de cracker l’empreinte (hash) d’un mot de passe, j’ai décidé de me plonger dans le sujet pour en savoir plus et comprendre « le truc ». Voici un petit résumé de mon voyage au pays des Rainbow tables.

Tout d’abord commençons par le commencement…

Méthode numéro 1 - La force brute

Toutes les fonctions de hachage communément utilisées sont telles qu’il n’existe pas de fonction inverse. Pour cracker une empreinte (hash), l’idée la plus simple est donc de prendre tous les mots de passes possibles, de calculer pour chacun son empreinte, et de la comparer à l’empreinte que l’on veut cracker. Si les deux empreintes sont identiques, on a trouvé le mot de passe, sinon on continue.

Empreinte recherchée : a7df33

aaaa => hachage => 6d8c33…Non, ce n’est pas celui que l’on recherche. Au suivant !
aaab => hachage => 54cd12…Au suivant !
aaac => hachage => af5a94…Au suivant !
aaad => hachage => a7df33…Gagné !! le mot de passe est « aaad »

Le problème avec cette méthode c’est que ca peut vite s’avérer assez long. Sur un PC moderne, il faut 8 à 10 jours de calcul en moyenne pour casser un mot de passe de 8 caractères alphanumérique (minuscules uniquement).

Méthode numéro 2 - Dictionnaire d’empreintes

Comme toujours en informatique, on peut aller plus vite, au prix d’une plus grande consommation mémoire. En effet, pourquoi ne pas calculer l’empreinte de tous les mots de passe possibles, puis stocker le tout dans un fichier ? Ensuite, pour cracker une empreinte, il suffit de chercher dans le fichier l’empreinte et de lire le mot de passe associé.

Empreinte recherchée: a7df33
Dictionnaire:

Le problème dans ce cas, c’est la taille du fichier. Une empreinte SHA-1 est composée de 20 octets, donc le fichier contenant les empreintes de tous les mots de passe de 8 caractères alphanumériques (minuscules uniquement) pèse déjà 50.000 Go, soit 100 disques durs de 500 Go !! Comptez 2000 disques de 500 Go pour stocker le dictionnaire des empreintes des mots de passe de 8 caractères alphanumériques (minuscules et majuscules).

Méthode numéro 3 - Rainbow tables

Les tables arc-en-ciel essayent de concilier taille de fichier et temps de calcul raisonnable.
Une attaque par Rainbow table (table arc-en ciel) se déroule en 2 étapes. Il faut tout d’abord générer une table, puis cracker une ou plusieurs empreintes à l’aide de cette table.

Génération de la table

Toute l’astuce des Rainbow tables consiste à calculer à partir d’une empreinte, un mot de passe. Attention, pas LE mot de passe qui correspond à l’empreinte (une telle fonction n’existe pas), mais UN mot de passe. On dit que l’on réduit l’empreinte. La seule chose que l’on demande à cette fonction de réduction c’est d’être cohérente, c’est-à-dire de toujours retourner le même mot de passe quand on lui donne la même empreinte en paramètre.

Le principe de génération d’une Rainbow table est donc le suivant: On part d’un mot de passe, on calcule son empreinte puis on calcule un nouveau mot de passe à partir de l’empreinte, on calcule l’empreinte de ce mot de passe, et on répète l’opération un certain nombre de fois. Ensuite on stocke dans la table le mot de passe initial et l’empreinte finale.

Puis on recommence le processus. On choisit un nouveau mot de passe, et on construit une nouvelle chaine.

Voilà ! Nous venons de générer une Rainbow table contenant 2 lignes où chaque ligne représente une chaine de 4 mots de passe (chaine de longueur 4).

Utilisation de la table pour cracker des empreintes

Voyons maintenant comment utiliser cette Rainbow table pour cracker des empreintes.

Commençons par le plus facile : essayons de cracker l’empreinte « 269c241b ». Cette empreinte figure directement dans la table, à la seconde ligne, et est associée avec le mot de passe « qwer ». On sait donc que le mot de passe qui correspond à cette empreinte est le 4ème de la chaine. Malheureusement, on ne l’a pas stocké dans la table. Nous allons donc régénérer la chaine comme lors de la création de la Rainbow table. On prend donc le mot de passe initial, on le fait passer dans la fonction de hachage, ce qui donne 05db7a98. Ensuite on fait passer cette empreinte dans la même fonction de réduction que celle qui a servit à générer la table. Elle retourne donc le 2ème mot de passe de la chaine (jufx ) que l’on hache puis réduit pour trouver le 3ème mot de passe (sgkj), que l’on hache puis réduit pour donner le 4ème mot de passe: « omhf ». Bingo ! Pour être sur de nous, on hache « omhf », ce qui donne « 26c241b ». Re-bingo !! Nous avons cracké l’empreinte « 26c241b » : le mot de passe est « omhf ».

Essayons maintenant de cracker l’empreinte « 9d4e1e23 » : Pas de chance cette fois, cette empreinte ne figure pas dans la table. La partie n’est pas perdue pour autant ! Essayons de calculer une autre empreinte à partir de « 9d4e1e23 » : Un appel à la fonction de réduction nous donne « swdv », qui si on le passe à la fonction de hachage renvoie « 4457806c ». Oh surprise… cette empreinte figure dans la table à la 1ère ligne. Prenons donc le mot de passe initial « aaaa », et comme pour le premier cas, reconstituons la chaine : 2 coups de hachage/réduction nous donnent le mot de passe « xccd » qui une fois passé au hachoir donne « 9d4e1e23 ». Mission accomplie. Le mot de passe correspondant à notre empreinte est « xccd ».

Un dernier pour la route : « 05db7a98 » :

1. L’empreinte ne figure pas dans la table. Passons au plan B
2. reduce(hash(05db7a98)) => 3caa59a1. Qui ne figure pas non plus dans la table. Recommençons.
3. reduce(hash(3caa59a1)) => a986fc2c. Encore perdu. Recommençons.
4. reduce(hash(a986fc2c)) => 269c241b. Qui figure sur dans la table, à la 1ère ligne. De plus comme nous avons tourné 3 fois pour trouver, et que la table contient des chaines de longueur 4, le mot de passe recherché est le 1er de la chaine.
5. hash(qwer) => 05db7a98. C’est gagné !

Pour stocker 100 millions de mots de passe, il suffit donc par exemple de générer une Rainbow table contenant 100.000 lignes avec des chaines de longueur 1.000. On stocke donc dans un fichier de 2 Mo une table qui pèserait 2 Go dans le cas d’un simple dictionnaire… si on a de la chance et pas de collision!
Tout cela est trop un peu trop simple…
Car en pratique, les fonctions de réductions provoquent des collisions. Une collision survient quand la fonction de réduction retourne le même mot de passe pour deux empreintes différentes. Cela survient forcement car il y a toujours plus d’empreintes possibles que de mots de passes possibles.

Reprenons l’exemple précédent et admettons que nous n’ayons pas eu de chance en ce début d’année 2008. Cela donnerait à peu près cela:

La collision se produit lors de la réduction de 05db7a98. La fonction retourne « xccd », comme pour l’empreinte 4a388ce4. Résultat : au lieu de contenir 8 mots de passe distincts, notre table n’en contient que 6. Nous avons des chaines qui sont dupliquées à partir de la collision (xccd => swdv).

Pour diminuer cet effet indésirable, les Rainbow Tables utilisent non pas une mais plusieurs fonctions de réduction. En fait, il y a une fonction de réduction différente par « colonne ». Voici donc le schéma de génération d’une Rainbow table :

Cette fois, si une collision se produit, on ne se retrouve pas avec des chaines dupliquées car même si la fonction de réduction 1 retourne « uibf » pour l’empreinte 05db7a98, en haut on passe ensuite à la fonction de réduction 3, et en bas à la fonction de réduction 2, et donc au lieu d’avoir la chaine dupliquée jusqu’à la fin, on a juste un mot de passe dupliqué.

Voilà donc d’où ces tables tirent leur nom de tables en arc-en-ciel

Evidemment dans le cas où on n’a vraiment pas de chance, on peut tomber sur une collision dans la même colonne. En pratique, ce cas n’arrive que peu fréquemment avec de longues chaines.

Si vous voulez aller encore un peu plus loin, vous pouvez regarder le code source d’un petit programme Java que j’ai écrit pour l’occasion qui génère des Rainbow tables pour casser les empreintes SHA-1 de mots de passe de 4 caractères alphanumériques (minuscules uniquement).

Télécharger la démo et les sources Java.

Grosse mise à jour de FlexSpy. La principale nouveauté de cette version 1.2, c’est la possibilité d’éditer les valeurs des propriétés et des styles des composants. J’ai également grandement amélioré l’affichage des valeurs des propriétés et des styles.

FlexSpy démo (right-click pour voir les sources)

Télécharger FlexSpy-1.2.zip (sources + swc)

Pour toute remarque concernant FlexSpy, n’hesitez pas à rajouter un commentaire à ce billet. Si vous rencontrez des bugs, ou bien voulez contribuer à ce projet, vous pouvez vous rendre sur la page dédié à FlexSpy sur Google code.

Pour ajouter FlexSpy à votre application:

1. Dezippez le contenu de FlexSpy-1.2.zip dans le répertoire de votre choix (ex: C:\work\FlexSpy)
2. Dans FlexBuilder, ouvrez la fenêtre de propriétés de votre projet (Project menu > Properties)
3. Dans la partie gauche de la fenêtre de propriétés, sélectionnez Flex Library Build Path, puis l’onglet Library path dans la partie droite
4. Cliquez sur le bouton Add SWC…
5. Sélectionnez le fichier FlexSpy.swc dans le répertoire que vous avez choisi à l’étape 1 (ex: C:\work\FlexSpy\bin\FlexSpy.swc) et cliquez sur OK pour fermer la fenêtre.
6. Ensuite, ajoutez un bouton qui appelle la méthode FlexSpy.show() dans votre application ainsi que l’import qui va bien… compilez votre projet et voilà ! Alternativement, vous pouvez également enregistrer un raccourcis clavier via la méthode FlexSpy.registerKey(…).

Il y a encore quelques mois, je pensais que stocker l’empreinte (hash) d’un mot de passe était à peu près suffisant pour lui garantir une certaine sécurité. Je pensais naïvement qu’un mot de passe haché avec un algorithme reconnu comme MD5 ou SHA-1 demandait plusieurs mois de calculs intensif pour être cracké. J’avais tort…

Retour en arrière pour bien comprendre. Le hachage d’un mot de passe consiste à passer une chaine de caractères au travers d’un algorithme qui va retourner un nombre: l’empreinte (hash) de cette chaine.

Les algorithmes utilisés pour calculer les empreintes, comme SHA-1, sont unidirectionnels (injectifs), c’est à dire qu’il n’y a pas de formule pour faire l’opposé de ce qu’ils font. En pratique, il faut plusieurs mois ou années de calculs pour trouver le mot de passe à partir de l’empreinte.

Les algorithmes sont également déterministes. C’est à dire qu’à chaque fois qu’on demande à un algorithme de hachage de calculer l’empreinte d’une chaine donnée (”motdepasse” par exemple), il retourne toujours la même valeur (940c0f…9bb813).

Enfin, ces algorithmes sont très susceptibles au changement: Une simple variation dans la valeur d’entrée et la valeur de sortie n’a plus rien à voir. Comparez par exemple, le résultat de SHA-1 sur la chaine “motdepassd”, pourtant très proche de “motdepasse”:

Donc, un site Web qui se respecte - lorsqu’un visiteur s’inscrit et donne son mot de passe - prend ce mot de passe et en calcule l’empreinte. C’est cette empreinte qui est stockée par le site (et pas le mot de passe lui-même!!). Ensuite lorsque ce visiteur revient et s’authentifie, il saisit son mot de passe, le site Web calcule l’empreinte du mot de passe saisi et compare cette empreinte avec celle qu’il a stockée. Si les deux empreintes sont identiques… bingo… l’utilisateur a saisi le bon mot de passe.

Mon monde était merveilleux, mes mots de passe quasiment inviolables… c’était il y a encore quelques mois. Et puis j’ai découvert l’existence des tables arc-en-ciel (Rainbow Tables). Vous avez besoin de trouver le mot de passe correspondant à l’empreinte “d93e1203d93058cdc255e072221091201466fc3f”? Pas de problème, allez sur le site http://passcracking.com/, entrez l’empreinte (sans les guillemets) et voyez le résultat s’afficher dans la seconde!!

En simplifiant à l’extrême les Rainbow Tables, ce sont simplement les précalculs de toutes les empreintes d’un jeu de caractère donnée. Il existe par exemple des Rainbow Tables pour les mots de passe de 4 à 8 caractères alphanumériques.

Supposons maintenant qu’une personne mal intentionnée accède à la base de donnée stockant les informations utilisateurs de votre site Web. Cette base contient les identifiants et empreintes des mots de passe de vos utilisateurs. L’attaquant peut donc procéder à une attaque par Rainbow Table en comparant toutes les empreintes de votre site avec celles contenues dans les Rainbow Tables. Il trouvera ainsi le mot de passe de tous vos utilisateurs qui ont utilisé un mot de passe composé de 4 a 8 caractères alphanumériques.

Pour se prémunir contre ce genre d’attaques, il suffit de rajouter du sel lors du calcul de l’empreinte. Kesako le sel? C’est simplement une chaine complémentaire qui sera combinée au mot de passe pour compliquer la tache des attaquants. Le premier avantage du sel, c’est que cela va allonger de manière artificielle la longueur du mot de passe. Ensuite, on met généralement des caractères exotiques dans le sel pour que les Rainbow Tables calculés sur des mots de passe ne contenant que des caractères alphanumériques ne marchent plus.

Enfin, pour éviter que l’attaquant ne génère une Rainbow Table avec tous les mots de passe contenant 6 à 8 caractères alphanumériques puis se terminant par notre sel, il faut que le sel soit dépendant de l’utilisateur… On va donc prendre comme sel, par exemple les 4 premières lettres de l’identifiant de l’utilisateur.

Ainsi on évitera que les mots de passe que l’on aura stockés ne soient trop facilement crackables via une attaque par Rainbow Tables.

Je me suis récemment enregistré auprès du site d’écoute musicale you.dj. Lors de l’enregistrement le site demande, comme il est de coutume de le faire, de fournir un nom d’utilisateur, un mot de passe et une adresse email. Je tape mon nom d’utilisateur, un mot de passe et hop je peux commencer à créer mes playlists et écouter la musique que j’aime.

Pourtant, quelques minutes plus tard, je recois le mail suivant:

Bienvenue sur You.dj,

You.dj est un lecteur de musique en ligne où vous pouvez écouter toutes les chansons que les membres envoient.
Vous pouvez vous aussi envoyer de la musique, pour cela, rendez-vous dans le lecteur de musique de You.dj, onglet ‘Envoyer ma musique’ et suivez ensuite les instructions.

Rappel de vos identifiants pour vous connectez à You.dj:
- identifiant : aranud1976
- mot de passe : motdepasse

Bonne écoute

Arg… mais pourquoi tu m’envoies mon mot de passe par mail en clair?  Est-ce que après avoir tapé le code de ma carte bleue au distributeur à billet, le distributeur affiche l’écran suivant?

Bienvenue à la BNP,

Vous avez demandé 50 euros.

Rappel du votre code de carte: 6791

Lorsque je confie un mot de passe à un site, je m’attend à ce qu’il en prenne soin. A savoir, qu’il ne le diffuse pas en clair sur internet (et tout le monde sait que les emails circulent en clair), mais également qu’il le stocke de manière sécurisé.

Et la seule manière pour un site de stocker un mot de passe de manière sécurisé, c’est de ne pas le stocker du tout !! Cela veut dire qu’il faut stocker non pas le mot de passe mais une empreinte du mot de passe (hash en anglais). Si la fonction de hachage qui est utilisée pour calculer l’empreinte d’un mot de passe est correctement choisie et appliquée, alors retrouver le mot de passe est impossible car cela nécessiterait des calculs trop long (plusieurs milliers d’années).

Or certains site proposent de vous redonner votre mot de passe. Par exemple, ils vous demandent votre adresse email et vous expédient votre mot de passe à cette adresse. Ou bien ils vous demandent la réponse à une question qui vous a été posé lors de l’inscription (quel est le nom de jeune fille de votre mère) et vous révèlent votre mot de passe. Tous ces sites ne stockent donc pas l’empreinte du mot de passe mais le mot de passe lui même. Ils stockent donc votre mot de passe de manière non sécurisé.

Un site qui stocke une empreinte de votre mot de passe, peut donc au mieux vous générer un nouveau mot de passe en cas de perte de votre mot de passe. C’est heureusement ce que font la plupart des sites

Malheureusement, nous verrons dans le prochain billet que stocker l’empreinte du mot de passe n’est pas forcement suffisant.

Comme toute API qui se respecte, celle de Flex 2 réserve son lot de bizarreries. Cette semaine, j’ai eu besoin d’afficher un label cliquable. Et pour bien montrer à mes utilisateurs Web que ce label est cliquable, je voulais que le curseur en forme de main s’affiche lorsque la souris passe au dessus de ce label.

C’est le genre de truc qu’on fait des milliers de fois sans se poser de question en HTML:

<span style=”cursor:hand;cursor:pointer;text-decoration:underline” onclick=”alert(’Facile…’)”>Cliquer ici</span>

En Flex, l’équivalent se nomme useHandCursor. On s’attend donc à ce que le code suivant fonctionne:

<mx:Label text=”Cliquer ici” useHandCursor=”true”/>

Que nenni ! Rien nada. Pas de curseur en forme de main, rien. De deux choses l’une: Ou bien c’est un bug, mais dans ce cas comment se fait-il que personne n’ai trouvé ce bug aussi évident depuis la sortie de Flex 2 en 2006?… ou bien c’est un de ces cas où le design de l’API laisse à desirer et où changer la valeur de la propriété ne suffit pas. Encore faut-il trouver ce qui manque.

Et là, les gars de chez Adobe-Macromedia m’ont épaté:
Il faut modifier non pas UNE propriété…
non pas DEUX….
mais… TROIS !!!
Et, oui, c’est carrément trois propriétés qu’il faut changer pour voir apparaitre ce fameux curseur en forme de main.

Il faut donc dire à notre label, de montrer son curseur (useHandCursor=true), de se comporter comme un bouton (buttonMode=true) et enfin de ne pas déléguer les évènements de la souris à ses enfants (mouseChildren=false). On a connu plus intuitif !

Pour résumer voici le code MXML qu’il faut écrire pour voir notre curseur fétiche.

<mx:Label text=”Mais tu vas cliquer ici, oui !” useHandCursor=”true” buttonMode=”true” mouseChildren=”false” />

Selon Brad Abrams, un des pères de l’API de .NET, une API bien conçue est une API qui fait tomber le développeur dans la fosse du succès (The Pit of Success). Tel un marcheur qui essayerait de passer d’une vallée à une autre, et qui passera naturellement par le col plutôt que d’escalader le pic, une API bien conçue guide les développeurs dans la bonne direction, et leur rend la tache compliquées quand ils ne sont pas sur le bon chemin.

Dans le cas de useHandCursor, par exemple, je pense qu’il aurait été préférable de surcharger la propriété pour mettre à jour les 2 autres propriétés, ou au moins de l’indiquer clairement dans la documentation.

12/03/2008: Remplacé showHandCursor par useHandCursor.