This article is also available in English.
Le contexte
Vous êtes sûrement au courant du fait qu’un pirate a réussi à voler une liste de 6,5 millions de mots de passe à LinkedIn récemment. En pratique, ces mots de passe n’étaient pas lisibles en clair : il s’agit d’un hash SHA-1 des mots de passe. Toutefois, l’algorithme avait été utilisé de manière un peu légère, car sans sel.
Pour expliquer en deux minutes, le principe d’un hash est de transformer un mot en un autre sans qu’il y ait possibilité mathématique de le retrouver. Ainsi, le hash de “password” est par exemple “5baa61e4c9b93f3f0682250b6cf8331b7ee68fd8”, et il n’existe pas de moyen théorique de retrouver “password” à partir de ce nombre.
Ceci est intéressant pour les mots de passe, car c’est censé garantir que, si on stocke le hash, même un administrateur ne peut pas en déduire votre mot de passe. Par contre, lorsqu’une application reçoit une tentative de connexion, elle est capable de dire si le mot de passe envoyé est le bon car, si c’est le cas, il aura le même hash que celui qui est stocké dans sa base de données. A l’inverse, un léger changement dans le mot de passe proposé provoquera un grand changement dans le hash calculé, et l’application saura alors que le mot de passe n’est pas correct. Cette grande instabilité est importante, car elle permet de rendre statistiquement impossible de modifier petit à petit des tentatives pour approcher d’un hash voulu : si on change ne serait-ce qu’un caractère, le hash s’en trouve tout retourné, et il n’y a donc aucune chance qu’on puisse approcher le bon mot par tâtonnements.
Voila pour la théorie. Dans la pratique, le mécanisme de hash pose un problème, à savoir que comme “password” donne toujours un hash de “5baa61e4c9b93f3f0682250b6cf8331b7ee68fd8” (et c’est heureux sinon nous ne pourrions pas nous en servir pour valider les mots de passe), cela veut dire qu’il est possible de pré-calculer des dictionnaires de hash sur des mots de passe “courants”, et de comparer ensuite directement les hash, pour en déduire le mot de passe utilisé.
La contre-mesure pour ceci est d’utiliser ce qu’on appelle un “sel”. “Saler l’algorithme de hash” consiste à ajouter du “bruit” connu autour du mot de passe à hasher. Ainsi, au lieu de calculer le hash de “password”, on calculerait par exemple celui de “PréfIXE32password67coucou”, qui a beaucoup moins de chance de se trouver dans un dictionnaire de hash, car il s’agit pour le moins d’un mot de passe peu courant. Pour ce qui est de la validation des mots de passe, pas de problème, car on sait qu’avant de comparer le hash, il faut toujours entourer la tentative avec “PréFIXE32” et “67coucou”.
La boulette de LinkedIn a été de ne pas saler leur algorithme de hash SHA-1 (en tout cas à une époque, dont ce fichier date). Du coup, quand le fichier en question a fuité, n’importe qui a pu y trouver des hash de mots de passe connus, comme ceux de “password”, “123456”, etc.
L’hypothèse à valider
Evidemment, ceci est une erreur de la part de LinkedIn. C’est bien gentil d’expliquer que leur équipe contient des experts de la sécurité (http://blog.linkedin.com/2012/06/09/an-update-on-taking-steps-to-protect-our-members/), si c’est pour oublier de saler leur algo de hash – ce qu’un informaticien qui s’intéresse un tant soit peu à la sécurité sait – ce n’est pas la peine de faire trop de pub…
Pourtant, je fais l’hypothèse qu’un sel, appliqué de manière unique à tous les hash découverts dans le fichier, n’aurait en fait pas changé grand chose à la situation.
En effet, dans un tel fichier avec 6.5 millions de mots de passe, il y a toutes les chances de trouver bon nombre de mots de passe “traditionnels” comme “password”, “123456”, etc. Du coup, si le mécanisme de hash est commun, il suffit de lancer une attaque de force brute sur le mécanisme de sel, tout en restreignant à ces quelques mots de passe cible, pour retrouver celui-ci. Cela prend évidemment du temps en plus, mais mon hypothèse est que cela ne fait que multiplier par deux le temps nécessaire, et non pas par le nombre de chaînes possibles. En bref, avec des unités de temps relatives :
Je vous propose de me suivre dans cet article à rallonge, qui relate mes différentes expérimentations sur cette hypothèse. Le code est en C#, mais vous n’aurez pas de mal à retrouver sa signification même si vous êtes habitués à d’autres langages.
Trouver les fichiers
Avant de commencer à pouvoir jouer avec, il s’agit de trouver le fichier avec les fameux hash. Le lien original ne fonctionne plus :
Mais en suivant un peu les conversations sur https://news.ycombinator.com/item?id=4073309, on retrouve rapidement la trace d’une copie… Il doit y en avoir quelques milliers dans le monde, j’imagine. Du coup, j’avoue ne pas voir l’intérêt de bloquer le premier lien. A la rigueur, ça ne fait qu’encourager la consommation disque pour rien, puisque de toute façon, on le retrouve en deux temps trois mouvements.
Bref, nous voici sur un autre site pour récupérer le fichier :
20 minutes de téléchargement plus tard, on jette un œil dans le fichier, et ça semble être le bon, avec une partie des hash dont le début est remplacé par cinq caractères “0”, caractéristique abondamment discutée sur http://dropsafe.crypticide.com/article/7235.
Ensuite, on récupère un fichier de mots de passe retrouvé sur DazzlePod, et on commence par faire un petit test rapide sur de façon à vérifier qu’on a bien les “grands standards” :
[TestMethod]
public void PresenceMotsDePasseSimplesDansFichierReference()
{
List<string> mots = new List<string>() { "password", "123456", "superman" };
string ligne;
int motsTrouves = 0;
int nbLignesAnalysees = 0;
using (StreamReader lecteur = new StreamReader(@"D:\Projets\Brèche LinkedIn SHA1\passwords.txt"))
{
while ((ligne = lecteur.ReadLine()) != null)
{
nbLignesAnalysees++;
if (mots.Contains(ligne))
motsTrouves++;
if (motsTrouves == mots.Count)
break;
}
}
Assert.AreEqual(mots.Count, motsTrouves);
}
Ce fichier contient un peu plus de deux millions de mots de passe, qui ont du être moissonnés je ne sais comment, mais qui correspondent à des cas réels. Quoi qu’il en soit, on retrouve bien dedans nos mots de passe les plus courants, comme testés ci-dessus. Nous allons nous en servir pour mener une attaque ciblée sur les hash du fichier LinkedIn.
Rechercher les hash SHA-1 par force brute
L’étape suivante consiste à regarder si on retrouve les SHA-1 de ces mots de passe :
[TestMethod]
public void PresenceSHA1ReduitDeMotsDePasseSimples()
{
List<string> mots = new List<string>() { "password", "123456", "superman" };
SHA1 moteur = SHA1CryptoServiceProvider.Create();
List<string> hashes = mots.ConvertAll(m => BitConverter.ToString(
moteur.ComputeHash(Encoding.UTF8.GetBytes(m))).ToLower().Replace("-", string.Empty));
string ligne;
int hashesTrouves = 0;
int nbLignesAnalysees = 0;
using (StreamReader lecteur = new StreamReader(@"D:\Projets\Brèche LinkedIn SHA1\SHA1.txt"))
{
while ((ligne = lecteur.ReadLine()) != null)
{
nbLignesAnalysees++;
if (hashes.Contains(ligne))
hashesTrouves++;
if (hashesTrouves == mots.Count)
break;
}
}
Assert.AreEqual(hashes.Count, hashesTrouves); // Plante : on ne trouve rien
}
On ne les trouve pas en direct, mais c’est là qu’interviennent les 00000 en préfixe, et si on les rajoute, pas de problème, on fait carton plein (je ne montre ci-dessous que le code modifié par rapport au listing précédent) :
List<string> hashes = mots.ConvertAll(m => string.Concat("00000", BitConverter.ToString(
moteur.ComputeHash(Encoding.UTF8.GetBytes(m))).ToLower().Replace("-", string.Empty).Substring(5)));
Du coup, on peut passer aux choses plus sérieuses en croisant le contenu complet des fichiers, de façon à moissonner tous les mots de passe “simples” dans le fichier fuité de LinkedIn. Pour réaliser ceci, on travaille évidemment par force brute. Et quand je dis “brute”, c’est vraiment au pied de la lettre, à savoir que je me contente de bêtement boucler, sans optimisation aucune. Dans la pratique, une personne mal intentionnée se servirait d’outils beaucoup plus sophistiqués comme John The Ripper (surtout qu’une extension destinée à la manipulation des hash en provenance de LinkedIn, avec les 00000 en préfixes, est spécialement sortie).
Le temps de taper ces quelques lignes, ce code pas du tout optimisé (sur une bonne bécane, toutefois : Xeon, beaucoup de RAM, SSD) a trouvé une vingtaine de mots de passe :
A priori, en laissant tourner toute une nuit, on devrait donc retrouver suffisamment d’instances pour pouvoir mener le reste de nos expériences avec une étendue statistiquement suffisante. Le code est donc modifié pour plutôt ressortir les résultats dans un fichier CSV :
[TestClass]
public class TestHashes
{
private SHA1 moteur = SHA1CryptoServiceProvider.Create();
private string CalculerHashReduit(string motDePasse)
{
return string.Concat("00000", BitConverter.ToString(
moteur.ComputeHash(Encoding.UTF8.GetBytes(motDePasse))).ToLower()
.Replace("-", string.Empty).Substring(5));
}
[TestMethod]
public void RechercheMotsDePasseUsuelsDansFichierFuiteLinkedInVersionToutEnMemoire()
{
string fichierSortie = Path.Combine(@"D:\Projets\Brèche LinkedIn SHA1", DateTime.Now.ToString("yyyy-MM-dd-hh-mm-ss"));
string[] tableau = File.ReadAllLines(@"D:\Projets\Brèche LinkedIn SHA1\SHA1.txt");
List<string> hashes = new List<string>(tableau);
string ligne;
int index = 0;
Stopwatch chrono = Stopwatch.StartNew();
using (StreamReader lecteur = new StreamReader(@"D:\Projets\Brèche LinkedIn SHA1\passwords.txt"))
{
while ((ligne = lecteur.ReadLine()) != null)
{
index++;
string hash = CalculerHashReduit(ligne);
if (hashes.Contains(hash))
{
Debug.WriteLine(string.Format("{0} trouvé sous le hash {1} - {2} / 2 151 220 - {3}",
ligne, hash, index, chrono.Elapsed));
File.AppendAllText(fichierSortie, string.Concat(ligne, Environment.NewLine));
}
}
}
}
}
Ensuite, il ne reste plus qu’à attendre. Un peu moins de 24 heures plus tard, les résultats sont les suivants :
42 799 hash ont été trouvés dans le fichier LinkedIn, sur 412 116 mots de passe testés parmi les 2 151 220 que contient le dictionnaire de mots de passe.
Passage à la vitesse supérieure
Bon, c’est bien sympa, tout ça, mais je ne vais pas laisser ma bécane allumée pendant trois jours juste pour me faire un corpus de mots de passe dans le but de tester une hypothèse sur la présence du sel ! Et 40 000 mots de passe, c’est déjà pas mal, mais j’aimerais bien travailler sur tout ce que je peux retrouver pour valider au mieux mon hypothèse. Du coup, je modifie le code pour utiliser la puissance de mes huit cœurs, et ça va pousser un peu plus 
.
Le code pour mettre ceci en place est le suivant :
[TestClass]
public class TestSHA1Breach
{
private List<string> hashes;
private string identifiant;
private string repSortie;
[TestMethod]
public void TestParallelBreachSHA1LinkedIn()
{
identifiant = DateTime.Now.ToString("yyyy-MM-dd-hh-mm-ss");
repSortie = string.Concat(@"D:\Projets\Brèche LinkedIn SHA1\ParallelResults-", identifiant);
Directory.CreateDirectory(repSortie);
string[] tableau = File.ReadAllLines(@"D:\Projets\Brèche LinkedIn SHA1\SHA1.txt");
hashes = new List<string>(tableau);
using (StreamReader lecteur = new StreamReader(@"D:\Projets\Brèche LinkedIn SHA1\passwords - Copie.txt"))
{
List<Task> taches = new List<Task>();
int limite = 1000;
string ligne;
List<string> mots = new List<string>();
while ((ligne = lecteur.ReadLine()) != null && limite-- >= 0)
{
mots.Add(ligne);
if (mots.Count == 100)
{
Task t = new Task(new Action<object>(Traitement), new List<string>(mots));
taches.Add(t);
t.Start();
mots.Clear();
}
}
foreach (Task t in taches)
t.Wait();
string fichierComplet = Path.Combine(@"D:\Projets\Brèche LinkedIn SHA1",
string.Concat("parallel-", identifiant));
foreach (string fichier in Directory.GetFiles(repSortie))
File.AppendAllLines(fichierComplet, File.ReadAllLines(fichier));
Directory.Delete(repSortie, true);
}
}
// On pourrait aussi faire avec des BlockingCollection, mais l'avantage des fichiers est que si le test
// plante en cours de route pour un lock mal géré ou quelque chose du genre, on ne perd pas tous les résultats.
//private BlockingCollection<string> Resultats = new BlockingCollection<string>();
private void Traitement(object mots)
{
SHA1 moteur = SHA1CryptoServiceProvider.Create();
List<string> Resultats = new List<string>();
foreach (string mot in mots as List<string>)
{
string hash = string.Concat("00000", BitConverter.ToString(
moteur.ComputeHash(Encoding.UTF8.GetBytes(mot))).ToLower()
.Replace("-", string.Empty).Substring(5));
if (hashes.Contains(hash))
{
Debug.WriteLine(string.Format("{0} trouvé sous le hash {1}", mot, hash));
Resultats.Add(mot);
}
}
string fichierSortie = Path.Combine(repSortie, Guid.NewGuid().ToString());
File.AppendAllLines(fichierSortie, Resultats.ToArray());
}
}
Je ne rentre pas dans les détails, mais ce code va à peu près huit fois plus vite que le précédent, car il utilise à pleine puissance les huit cœurs CPU de ma machine. On pourrait aller encore plus vite en utilisant du GPGPU, mais ça serait pas mal de boulot, et là, les estimations sont que le calcul durera en gros 15 heures, donc ça ne vaut pas le coup. Encore une fois, si le but était juste de cracker le plus vite possible le maximum de mots de passe, on utiliserait John The Ripper, qui d’ailleurs a un plugin pour fonctionner en OpenCL. Avec les possibilités du cloud, il est même quasi-sûr qu’il existe déjà des outils pour utiliser la puissance ponctuelle énorme d’une telle architecture de façon à gagner encore un ou deux ordres de grandeur dans la performance de la méthode par force brute.
Au final, on obtient bien notre fichier avec tous les mots de passe dont les hash ont été retrouvés dans le fichier fuité de LinkedIn. Sur 6,5 millions de hash, cette méthode nous a permis de retrouver 600 000 mots de passe, ce qui est déjà pas mal, sachant que pour certains très simples, le nombre de duplications doit être très important. Le tout a mis finalement 18 heures au lieu des 15 estimées…
On passe aux choses sérieuses
L’étape suivante nous rapproche enfin de l’hypothèse à tester. Jusqu’à maintenant, nous avons juste moissonné de l’information pour tester cette hypothèse. Maintenant, nous allons nous servir des mots de passe trouvés comme d’un nouveau corpus pour les études suivantes. Pour cela, nous créons un fichier de hash des mots de passe, mais cette fois-ci avec un sel, et nous allons vérifier si la connaissance statistiques de mots de passe “traditionnels” nous permet effectivement de réaliser une attaque de force brute non pas sur les mots de passe, mais sur le sel utilisé.
Pour faire le test, je vais utiliser le sel que je propose en TD à mes étudiants, à savoir préfixer le mot de passe par “zorglub”. Je recalcule donc mon fichier de hash avec ce sel, et nous allons tester si la méthode statistique proposée permet d’accélérer l’attaque du sel par force brute.
Pour cela, à chaque hypothèse de sel, nous ne testerons que les 25 mots de passe qui sont les plus utilisés (voir http://splashdata.com/splashid/worst-passwords/index.htm) :
- password
- 123456
- 12345678
- qwerty
- abc123
- monkey
- 1234567
- letmein
- trustno1
- dragon
- baseball
- 111111
- iloveyou
- master
- sunshine
- ashley
- bailey
- passw0rd
- shadow
- 123123
- 654321
- superman
- qazwsx
- michael
- football
L’idée est donc de boucler sur des hypothèses de sel, de calculer les hash de ces 25 mots de passe, et de regarder si l’un d’entre eux au moins est dans le fichier de hash cible. Si c’est le cas, il y a des chances qu’on ait trouvé notre sel, et nous pouvons donc revenir à une attaque par force brute hors-sel, dont nous avons montré plus haut l’efficacité, même sur des gros volumes à analyser.
La fréquence des premiers mots de passe est telle que nous pourrions nous contenter de quelques mots de passe seulement. Pour mes tests, je vais même commencer avec un seul, à savoir “password”. En fait (et c’est là la faille d’utiliser un même sel sur un ensemble de plusieurs millions de mots de passe), le corpus est tellement grand qu’on est quasiment assuré de tomber sur au moins un mot de passe égal à cette valeur “traditionnelle”. Le code est le suivant :
[TestClass]
public class TestAttaqueSel
{
private List<string> hashes;
[TestMethod]
public void TestParallelRechercheSel()
{
string sel = "zorglub";
int limite = int.MaxValue;
// Préparation du fichier des hash selon le sel choisi
string fichierMotsDePasseLinkedInObtenusParForceBrute = Path.Combine(
@"D:\Projets\Brèche LinkedIn SHA1",
"FichierObtenuSansParallelisme.txt");
string fichierHashCible = Path.Combine(
@"D:\Projets\Brèche LinkedIn SHA1",
"FichierHashesSelEnCours.txt");
SHA1 moteur = SHA1CryptoServiceProvider.Create();
using (StreamReader lecteur = new StreamReader(fichierMotsDePasseLinkedInObtenusParForceBrute))
using (StreamWriter scribe = new StreamWriter(fichierHashCible))
{
string ligne;
while ((ligne = lecteur.ReadLine()) != null)
{
scribe.WriteLine(BitConverter.ToString(moteur.ComputeHash(
Encoding.UTF8.GetBytes(string.Concat(sel, ligne)))));
}
}
// Stockage de toutes ces valeurs en mémoire pour aller plus vite dans nos recherches
hashes = new List<string>(File.ReadAllLines(fichierHashCible));
// On lance des tâches de traitement de recherche pour toutes les hypothèses de sel. Comme hypothèses de sel,
// on part sur la plus simple en premier, à savoir que le sel est un préfixe, et qu'il a des chances d'être
// un mot courant. On repart donc d'un dictionnaire des mots de passe les plus utilisés. Si cela ne suffit pas,
// on ferait ensuite la même analyse avec un suffixe, les deux, etc. Il est évident que dans ces cas, les temps
// augmentent, mais le but est justement de faire voir qu'un simple sel n'apporte pas la sécurité imaginée,
// et qu'il faut justement un mécanisme de sel complexe, ou en tout cas non unique, pour augmenter ce temps
// à des valeurs suffisamment dissuasives.
List<Task> taches = new List<Task>();
using (StreamReader lecteur = new StreamReader(@"D:\Projets\Brèche LinkedIn SHA1\passwords.txt"))
{
string ligne;
List<string> hypotheses = new List<string>();
while ((ligne = lecteur.ReadLine()) != null && limite-- >= 0)
{
hypotheses.Add(ligne);
if (hypotheses.Count == 100)
{
Task t = new Task(new Action<object>(Traitement), new List<string>(hypotheses));
taches.Add(t);
t.Start();
hypotheses.Clear();
}
}
}
foreach (Task t in taches)
t.Wait();
}
private void Traitement(object hypotheses)
{
// Le traitement de chaque hypothèse de sel consiste à regarder si, en appliquant ce sel sur "password",
// on obtient un hash présent dans le fichier cible. Si c'est le cas, il y a statistiquement de bonnes
// chances pour qu'on ait trouvé le hash. Et si ce n'est pas le cas, on trouvera rapidement car on a alors
// trouvé une combinaison de sel et de mot de passe connue. Il suffit alors de déplacer le curseur sur les
// caractères de la chaîne en testant les autres décomposition jusqu'à trouver la bonne.
SHA1 moteur = SHA1CryptoServiceProvider.Create();
List<string> Resultats = new List<string>();
foreach (string hypothese in hypotheses as List<string>)
{
string hash = BitConverter.ToString(moteur.ComputeHash(
Encoding.UTF8.GetBytes(string.Concat(hypothese, "password"))));
if (hashes.Contains(hash))
{
Debug.WriteLine(string.Format("Il y a de bonnes chances pour que {0} soit le sel", hypothese));
File.AppendAllText(string.Concat(
@"D:\Projets\Brèche LinkedIn SHA1\ResultatRechercheSel-",
DateTime.Now.ToString("yyyy-MM-dd-hh-mm-ss")), hypothese);
Environment.Exit(0);
}
}
}
}
La toute première vague d’hypothèses pour le sel, pour une attaque en force brute, est bien sûr de repartir directement sur les valeurs en provenance du dictionnaire de mots de passe et de s’en servir comme sel de type préfixe. Ensuite, on passerait au sel de suffixe, à la composition des deux, à l’ajout de symboles supplémentaires, etc.
Résultats
Cette première approche nous ressort le sel par force brute en à peine quelques minutes. Il se trouve que le préfixe choisi faisait partie du dictionnaire de mot de passe, et a donc été trouvé dès la 1 698 685 ème tentative.
Première attaque en force brute d’un sel simple sur le fichier de 6.5 millions de hash : solution trouvée en 4 minutes !
Nous pourrions bien sûr rendre le sel plus complexe, comme “Zorglub64” en préfixe et “Batman28” en suffixe, mais il y aurait quelque chose d’artificiel à adapter l’algorithme en fonction de ce qu’on recherche.
Surtout, ce que nous souhaitions démontrer l’est déjà avec cet exemple : à partir du moment où on a de bonnes chances de connaitre un des mots de passe et qu’on dispose d’un corpus de hash assez grand, utiliser un sel, s’il est unique pour tous les hash, ne sert pas à grand chose, car au lieu de démultiplier les cas de recherche, il ne fait qu’ajouter une étape de force brute. Dans ces cas statistiques limites, on pourra donc au mieux multiplier par deux le temps d’attaque, ce qui est bien évidemment insuffisant.
Pour résumer
Un petit tableau résumant la situation :
Bref, si vous exposez un grand nombre de hash et que certains mots de passe sont de mauvaise qualité (par exemple parmi les 25 plus utilisés), et ce même si leur proportion est infime, un sel simple ne vous apportera que très peu de sécurité supplémentaire.
Toute l’idée est que le volume de données, au lieu de nous retarder dans les calculs, nous donne au contraire plus de chances de valider l’hypothèse du sel. La conclusion de tout ceci est qu’un sel ne devrait pas être unique pour des gros volumes, sinon il perd de son efficacité.
La solution
Autant la démonstration est complexe, autant la solution est relativement simple : il ne faut pas utiliser un seul et même sel de hash pour des grands volumes de mots de passe. Du coup, on peut imaginer d’utiliser un sel variable (par exemple basé sur un hash de la date de création du mot de passe), voire même une variable exogène, comme par exemple un identifiant unique de compte (mais surtout pas le login : la seule chose qui a évité une catastrophe à LinkedIn était justement que les logins n’étaient pas présents dans ce même fichier de hash de mots de passe).
Voici une proposition de notation sur vingt des différents modes d’utilisation d’un sel (le mot de passe à hasher est en vert, et le sel en gris) :
Pas de 20/20, car aucune méthode n’est infaillible. Même le mécanisme de cryptographie SHA-1 n’est pas exempt de tout risque : des algorithmes de génération de collisions ont été trouvés qui sont suffisamment rapides pour représenter un risque (http://people.csail.mit.edu/yiqun/SHA1AttackProceedingVersion.pdf, ou pour quelque chose de plus facile à lire, http://www.rsa.com/rsalabs/node.asp?id=2927). Si vous utilisez les hash dans le cas d’une fourniture de signature numérique, il peut être intéressant de passer à une méthode plus moderne (SHA-256, par exemple).
Attention à ne pas tomber dans le piège de la fausse sécurité avec des méthodes exotiques comme inverser les lettres du mot de passe, etc. Quoi qu’on fasse, ces méthodes sont prédictibles par quelqu’un avec un peu d’imagination et les personnes mal-intentionnées en ont malheureusement beaucoup. Une fois une liste de ces méthodes inclue dans un outil, c’en sera fait d’elles…
