Monthly Archives: janvier 2008

Qu’est-ce qu’un bon logiciel?

Voilà une question que je pose actuellement alors que je travaille sur un nouveau logiciel chez mon employeur actuel

Interrogez des utilisateurs et demandez-leur de vous citer un logiciel qu’ils aiment. Demandez-leur ensuite quelles sont les raisons qui les poussent à aimer ce logiciel. Voici quelques-unes des réponses que vous risquez d’avoir (dans le désordre):

  • Il répond à mon besoin.
  • Il fait ce que je lui demande.
  • Quand je lui demande quelque chose, il réagit rapidement
  • Il est facile à utiliser.
  • Il est beau / cool / à la mode / etc.
  • Je me sent à l’aise avec ce logiciel.
  • Il ne plante jamais.
  • Il est rapide à charger.
  • D’autres gens de mon entourage l’utilisent.

Notez que vos utilisateurs ne vous feront aucune de ces réponses:

  • Il est bien architecturé
  • Le code est bien écrit / bien documenté
  • Il est écrit en C# / Java / Ruby / Flex  / Eiffel / [Ajoutez ici votre langage favori]

Je vous propose de voir, tout au long de ces prochaines semaines, comment toutes ses réponses peuvent nous aider à construire de meilleurs logiciels.

Stocker des mots de passe en 2008

Suite à mon billet sur la salaison des mots de passe et sur les Rainbow tables, j’ai appris que calculer une empreinte de mot de passe avec un algorithme tel que SHA-1 ou MD5, même avec du sel, n’est plus très sûr.

le problème est que ces algorithmes de hachage ont été conçus dans le but d’être rapides car ils sont au cœurs de nombreux système cryptographiques. Ils ont également été conçus pour pouvoir tourner sur du matériel spécialisé. Le résultat c’est que mon PC pour calculer un peu plus d’un million d’empreintes SHA-1 par seconde, et presque deux millions par seconde avec MD5. Il existe également des circuits imprimés spécialisés qui peuvent calculer une centaine de millions d’empreintes SHA-1/MD5 par seconde, mettez-en 10.000 en parallèle et vous pouvez casser tout mot de passe de 1 à 10 caractères en une seule journée.

La conclusion, c’est qu’un algorithme rapide est exactement ce que l’on ne veut pas lorsqu’on calcule une empreinte de mot de passe. Utiliser un algorithme rapide comme SHA-1 ou MD5 pour calculer l’empreinte de mots de passe est aussi stupide que de ne pas mettre de sel avant de calculer l’empreinte. Ne le donc faites pas!

Utilisez un algorithme de hachage lent. Un tel algorithme demande énormément de temps pour calculer son empreinte, et n’est pas adapté pour tourner sur du matériel spécialisé. Il ne pourra donc jamais être cassé par des attaques par force brute.

L’état de l’art dans ce domaine aujourd’hui s’appelle BCrypt. Il a été mis au point en 1999 pour OpenBSD. Son principal avantage est que c’est vous, le programmeur, qui décidez combien de temps prend le calcul d’une empreinte. Mais attention, BCrypt est fait pour être lent. Sur mon PC, avec le réglage le plus rapide, le calcul d’une empreinte demande 2 msec, soit 500 empreintes par seconde. On est loin du million d’empreinte obtenu avec SHA-1 ou MD5. Avec le réglage par défaut, mon PC ne génère pas plus de 15 empreintes par seconde.

En conclusion, voici quelques règles à suivre pour stocker des mots de passe:

Règle numéro 1: Stockez l’empreinte des mot de passe, pas les mot de passe eux-même.

  • Ne stockez pas les mot de passe en clair
  • Ne stockez pas non plus une version cryptée des mot de passe. Les algorithmes de cryptage comme AES, DES, 3DES, BlowFish, RC4 ou RSA sont donc à bannir car ils sont réversibles par nature.

Règle numéro 2: Utilisez un algorithme de calcul d’empreinte si possible lent et éprouvé

Utilisez si possible BCrypt. Il est disponible pour Java, .NET, PHP, et bien d’autres langages encore.

Si vous ne pouvez vraiment pas, essayez d’utiliser SHA-512/384/256. Sinon SHA-1. En dernier recours MD5.

A savoir: MD5 a été cracké et SHA-1 n’est plus considéré comme sûr.

Règle numéro 3: Ajoutez du sel avant de calculer les empreintes.

  • Le sel ajouté doit avoir été calculé avec une fonction cryptographique de génération de nombre aléatoire. Il faut donc le stocker à coté de l’empreinte.
  • Le sel doit également être différent pour tous les utilisateurs (pour éviter les attaques sur un lot d’empreintes).
  • Le sel doit être suffisamment long (12 caractères ou 24 octects au minimum).

La bonne méthode est la suivante (en pseudo Java)

// Calcule l'empreinte d'un mot de passe
public String computePasswordHash(String password) {
// Génère un tableau aléatoire de 32 octets
byte[] salt = CryptographicRandomNumberGenerator.getBytes(32);

// Calcule l'empreinte du mot de passe en utilisant le sel généré (le sel est inclus dans l'empreinte retourné)
return hashPassword(password, salt);
}

// Verifie que le mot de passe fourni correspond à celui qui a servir à calculer l'empreinte fournie.
public boolean checkPassword(String text, String hash) {
// Récupère le sel contenu dans l'empreinte.
String[] hashAndSalt = String.split(hash, "$");
byte[] salt = Base64.decode(hashAndSalt[1]);

// Calcule l'empreinte du mot de passe fourni avec le sel récupéré ci-dessus.
String hashedText = hashPassword(text, salt);

// Regarde si les empreintes sont indentiques.
return hashedText.equals(hash);
}

private String hashPassword(String password, byte[] salt) {
byte[] pwd = password.getBytes("UTF-8");
byte[] saltedPwd = Array.join(pwd, salt);
byte[] hash = hashFunction(saltedPwd);
return Base64.encode(hash) + "$" + Base64.encode(salt);
}

Enfin sachez qu’il existe aujourd’hui une méthode pour ne plus avoir à stocker les mots de passe nommée SRP. Si vous pouvez l’utiliser, c’est encore mieux que de stocker les mots de passe.

Rainbow tables

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:

aaaa 6d8c33
aaab 54cd12
aaac af5a94
aaad a7df33
zzzz 8d6bc7

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.

Nombres de mots de passe de 8 caractères alphanumériques (26+26+10)^8 = 52^8 = 5×10^13
Nombres d’empreintes SHA-1 (160 bits) 2^160 = 10^4

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.