Bcrypt

Auteurs : Antoine Petetin et Florian Sebire

Introduction

Le nombre de pirates ne cesse d'augmenter ces dernières années. En 2017, une faille a été trouvée sur le protocole le plus répandu pour la sécurité des mots de passe wifi, à savoir le WPA 2. En octobre 2018, le réseau social Facebook s'est fait piraté 5 millions de comptes en Europe. Aujourd'hui, tous les sites possèdent un système d'authentification. Les utilisateurs doivent se connecter avec un mot de passe, plus ou moins complexe en fonction des règles imposées sur le site. La robustesse d'un mot de passe face aux différentes attaques joue un rôle essentielle dans la sécurisation de nos données. Un mot de passe est qualifié de "faible" s'il est facilement attaquable. Il existe plein d'algorithme pour chiffrer les mots de passe (MD5, SHA1, ...).

Quelques définitions

Fonction de hachage

Une fonction de hachage transforme une donnée en entrée de taille quelconque en une donnée de sortie de taille fixe. Une fonction de hachage cryptographique va permettre de lier un clair à son empreinte. Pour que cette fonction soit efficace, il ne faudrait pas (en théorie) pouvoir retrouver le clair à partir du haché. Pour cela, cette fonction doit être aussi injective que possible.

• Les fonction de hachage sont des fonctions à sens unique ( on ne peut pas à partie d'une empreinte retrouver le chaîne de caractère initial )
• La fonction est le plus injective possible ( à partir d'une image on a au plus un seul antécédent )

Empreinte

Une empreinte est le résultat d'une fonction de hachage sur un clair. Une empreinte est aussi appelée une hash value, un hash code, un digest ou encore un hash.

Processus d'authentification sur un site web

L'identification d'un utilisateur sur un site est assez classique. La plupart du temps, les mots de passe ne sont pas stockés en clair dans la base de donnée du site. On stocke le haché d'un mot de passe clair. Ainsi, un hacker qui arriverait à accéder à la base de données ne verrait que les empreintes du clair, et ne pourrait pas en déduire le clair à partir de ce dernier (si le chiffrement respecte le secret parfait).

Le procédé est le suivant :

1. L'utilisateur saisit son identifiant et son mot de passe (le clair).
2. Ce mot de passe est envoyé au serveur qui va hacher le mot de passe grâce à une fonction de hachage.
3. Le serveur va ensuite ensuite comparer le haché du mot de passe donné et le haché stocké dans la base de données du site.
4. Si les 2 hachés correspondent alors, l’utilisateur est authentifié.

Attaques possibles

Il existe des attaques pour retrouver le mot de passe en clair à partir du haché. On utiliser le fait que la fonction de hachage soit injective.

L'attaque brute force

Il s'agit de l'attaque la plus simple, mais aussi la plus longue. On va essayer de trouver le bon haché en testant l'ensemble des clairs possibles pour un alphabet donné. Généralement, les hackers utilisent des fichiers textes appelés dictionnaire, qui contient cet ensemble.

Fonction BrutForce(dictionnaire : Liste de string, hache: string) : string
Début
    var i = 0;
    Tant que i < dictionnaire.taille
    Faire
        Si h(dictionnaire.get(i)) == hache
            Retourner dictionnaire.get(i);
    i = i + 1;
    Fin Tant que
Retourner "";
Fin

Des variantes de cet algorithme existent, tel que chercher aléatoirement un clair dans la liste plutôt que de parcourir toutes la liste.

L'attaque avec une table arc-en-ciel

Cette attaque repose sur un compromis temps/mémoire. Le principe est de calculer un tableau de taille M x N d'indices qui correspondent à différents hachés. Au lieu de stocker toutes les correspondances clair --> hash, on stocke généralement que le premier et le dernier élément de la chaine. Plus M et N sont grands, plus on va couvrir l'ensemble des clairs.

Premièrement, on génère un nombre aussi aléatoire que possible, puis on passe d'indice en indices N fois. On répète ce processus M fois.

Ce type d'attaque est rendu inefficace par l'ajout d'un seul combiné à la fonction de hachage. En effet si deux utilisateurs ont le même mot de passe leur empreinte sera différente.

L'attaque par collisions

L'attaque par collisions utilise, comme les attaques présentées précédemment, le fait que la fonction de hachage n'est pas tout à fait injective.

Le principe est de trouver plusieurs clairs qui donneraient un même haché. A partir de ces résultats, le hacker en déduit des règles sur la fonction de hachage.

Cette attaque se découpe en 2 variantes :

• L'attaque classique

On essaye au hasard 2 clairs distincts dans notre ensemble de clairs qui donnent le même haché. $(x,y)\in L,x\neq y,h(x)=h(y)$

• L'attaque avec préfixes choisis

Dans cette variante, on ne fait plus une comparaison avec des mots complets. On prend deux préfixes A et B disincts, et on cherche deux suffixes C et D pour lesquels $h(A.B)=h(C.D)$ où "." est la concaténation. Ainsi, les couples $(A,B,C,D)$ nous donnent plus d'indices sur la fonction de hachage comparé à une comparaison de deux clairs simples.

Complexifier le déchiffrement avec le salage

Le problème des fonctions de hachage usuelles est qu'elles sont injectives (ou presque). Le principe du salage est d'ajouter une information supplémentaire au chiffrement. On va concaténer le clair avec une chaine de caractères avant de chiffrer. Cette chaine est soit statique (pas très efficace), ou bien aléatoire.

Le salage aléatoire réduit l'efficacité de l'attaque par dictionnaire (surtout si le dictionnaire ne contient qu'un ensemble restreint de mots, comme les mots de la langue française par exemple). Elle ralentit l'attaque avec une table arc-en-ciel.

La condition de l'efficacité du salage est que le sel ne doit pas être connu de l'attaquant.

Bcrypt

Qu'est-ce que Bcrypt ?

Bcrypt est une fonction de hachage, créé par Niels Provos et David Mazières, et basée sur l'algorithme de chiffrement symétrique Blowfish : b pour Blowfish et crypt pour le nom de la fonction de hachage utilisé par le système de mot de passe UNIX.

Elle est utilisé dans certaines distribution Linux. Cette fonction est implémentée dans différents langage pour les développeurs comme PHP, C, C++, C#, Java ...

Les étapes du chiffrement

1. Génération des sous-clés avec la fonction eksblowfish (pour Expensive Key Schedule Blowfish)

Comme nous l'avons dit précédemment, Bcrypt s'appuie sur l'algorithme Blowfish. La première étape de l'algorithme Bcrypt consiste à générer la clé qui va permettre le chiffrement du texte clair. Cet algorithme fait partie des algorithmes de "préparation de clés". Le principe est de partir d'une graine, puis construire petit à petit la clé finale à partir de sous-clés.

Cette fonction prend 3 paramètres :

• cost Le coût souhaité de l'algorithme (Nombre entre 4 et 31). Il s'agit du logarithme binaire du nombre d'itérations de l'algorithme.
• salt Le sel qui correspond à une chaîne de caractère (Tableau de 16 octets)
• key le mot de passe que l'on souhaite hacher (Chaîne de caractères sur 1 à 72 octets)

EksBlowfishSetup(cost, salt, key)
    state $\gets$ InitState()
    state $\gets$ ExpandKey(state, salt, key)
    repeat (2cost)
        state $\gets$ ExpandKey(state, 0, key)
        state $\gets$ ExpandKey(state, 0, salt)
    return state

2. Chiffrement avec une partie des sous-clés

bcrypt(plainText, cost, salt)
   state $\gets$ EksBlowfishSetup(cost, salt, plainText)  
   //Encrypt le texte clair 64 fois
   //Repeatedly encrypt state with the text "OrpheanBeholderScryDoubt" 64 times
   ctext $\gets$ "OrpheanBeholderScryDoubt"  //24 bytes ==> three 64-bit blocks
   repeat (64)
      ctext $\gets$ EncryptECB(state, ctext) //encrypt utilise l'algorithme Blowfish en mode ECB

   //plainText sur 24 octets comme résulat du hash
   return Concatenate(cost, salt, ctext)

Après avoir généré l'état des sous-clés, on prend la chaîne de caractères plainText qu'on va encrypter 64 fois en utilisant eksblowfish en EBC Mode avec l'état de la phase précédente.

Le résultat est ensuite préfixé par $2a$, $2y$, ou $2b$ suivant la version de bcrypt utilisé.

Fonction EncryptECB :

Blowfish est basé sur un schéma de Feistel avec 16 tours. Un réseau de Feistel est subdivisé en plusieurs tours ou étages. Dans sa version équilibrée, le réseau traite les données en deux parties de taille identique. À chaque tour, les deux blocs sont échangés puis un des blocs est combiné avec une version transformée de l'autre bloc. Notre état a la même structure que l'état généré par Blowfish. Il contient un tableau P de 18 cases. Chaque ligne représente 32 bits (une case du tableau P). L'algorithme gère deux ensembles de clés : les 18 entrées du tableau P et les quatre S-Boxes de 256 éléments chacune. Une entrée du tableau P est utilisée à chaque tour. Arrivé au tour final, la moitié du bloc de donnée subit un XOR avec un des deux éléments restants dans le tableau P.

Le schéma ci-dessous montre la F-fonction de Blowfish. Elle sépare une entrée de 32 bits (une case du tableau P) en quatre morceaux de 8 bits et les utilise comme entrées pour accéder aux S-Boxes. Chaque S-Box accepte un mot de 8 bits en entrée et produit une sortie de 32 bits.

Les sorties sont additionnées avec une somme modulo $2^{32}$ et l'algorithme effectue un XOR entre les deux sous-totaux pour produire la sortie finale de 32 bits.

Les particularités de Bcrypt

Pourquoi utiliser Bcrypt par rapport à d'autres fonctions de hachage ?

L'intérêt par rapport à d'autre fonction de hachage comme md5 ou sha1 est que l’algorithme utilisé est lent ce qui dissuade les attaques par brute force ou avec une table arc-en-ciel.

Bcrypt est une fonction adaptative dans le sens où on peut préciser le nombre d'itérations. Plus le nombre d'itérations est important, plus le hachage est lent. Ceci est notamment utile au vu de l'évolution des CPU et GPU sachant que la taille des mots de passe reste constante. En effet les humains ont besoin de pourvoir d'avoir un mot de passe pas trop long afin de pouvoir facilement le retenir.

Quel coût choisir pour bcrypt ?

Telle est la question que chaque développeur doit se poser s'il veut utiliser bcrypt. En effet, le coût aussi connu sous le nom de "force de travail". Il doit d'être suffisamment grand pour que bcrypt soit le plus lent possible sans affecter l'expérience utilisateur.

Bcrypt en pratique

Temps de chiffrement par rapport au coût

Voici un graphique représentant le temps de chiffrement de Bcrypt en fonction du coût passé en paramètre avec une implémentation en Node.js avec un MacBook Pro :

• Processor: 2.8 GHz Intel Core i7
• Memory: 16 GB 2133 MHz LPDDR3
• Graphics: Radeon Pro 555 2048 MB, Intel HD Graphics 630 1536 MB

Voici les valeurs utilisés pour générer le graphique :

bcrypt | cost: 10, time to hash: 65.683ms
bcrypt | cost: 11, time to hash: 129.227ms
bcrypt | cost: 12, time to hash: 254.624ms
bcrypt | cost: 13, time to hash: 511.969ms
bcrypt | cost: 14, time to hash: 1015.073ms
bcrypt | cost: 15, time to hash: 2043.034ms
bcrypt | cost: 16, time to hash: 4088.721ms
bcrypt | cost: 17, time to hash: 8162.788ms
bcrypt | cost: 18, time to hash: 16315.459ms
bcrypt | cost: 19, time to hash: 32682.622ms
bcrypt | cost: 20, time to hash: 66779.182ms

Utiliser bcrypt avec PHP

La fonction PHP utilise par défaut l'algorithme Bcrypt pour hacher les mots de passes :

 string password_hash ( string $password , int $algo [, array $options ] )

Le coût par défaut définit dans password_hash est de 10.

Vous pouvez spécifier dans les options le coût comme ceci :

$options = [
    'cost' => 12,
];
echo password_hash("rasmuslerdorf", PASSWORD_BCRYPT, $options);

L'idéal est de mettre un coût suffisamment pour que le serveur qui hébergera votre application PHP mette au moins 50 ms pour hacher un mot de passe avec bcrypt.

Pour ce faire vous pouvez ce petit bout de code qui vous permet de trouver le coût adéquat :

<?php 
$timeTarget = 0.05; // 50 millisecondes
$cost = 8;
do {
    $cost++;
    $start = microtime(true);
    password_hash("test", PASSWORD_BCRYPT, ["cost" => $cost]);
    $end = microtime(true);
} while (($end - $start) < $timeTarget); 
echo "Valeur de 'cost' la plus appropriée : " . $cost;

Que se passe-t-il si la base de données est piratée ?

Les différentes parties de l'empreinte bcrypt

En général, l'empreinte bcrypt est stocké dans une seule colonne en base de données.

Si un pirate récupère l'ensemble des hash bcrypt, il peut par exemple essayer de faire une attaque avec des tables arc-en-ciel mais il devrait générer autant de table arc-en-ciel qu'il y a de sel différents et il devra utiliser le même coût pour hacher des chaînes de caractères ce qui sera très long pour générer ce genre de table.

Sources

http://www.lefigaro.fr/secteur/high-tech/2018/10/02/32001-20181002ARTFIG00121-piratage-de-facebook-5-millions-de-comptes-concernes-en-europe.php

https://www.zdnet.fr/actualites/faille-majeure-dans-wpa2-wi-fi-que-faire-qui-est-concerne-maj-39858724.htm

https://en.wikipedia.org/wiki/Bcrypt

https://medium.com/@danboterhoven/why-you-should-use-bcrypt-to-hash-passwords-af330100b861

https://en.wikipedia.org/wiki/Hash_function

https://fr.wikipedia.org/wiki/Attaque_de_collisions

https://en.wikipedia.org/wiki/Blowfish_(cipher)

https://fr.wikipedia.org/wiki/Salage_(cryptographie)

https://auth0.com/blog/hashing-in-action-understanding-bcrypt/

https://www.commonlounge.com/discussion/d95616beecc148daaa23f35178691c35

https://fr.wikipedia.org/wiki/S-Box

https://fr.wikipedia.org/wiki/Key_schedule