bcrypt

bcrypt est une fonction de hachage de mot de passe conçue par Niels Provos et David Mazières, basée sur le chiffrement Blowfish et présentée à USENIX en 1999. En plus d'incorporer un sel pour se protéger contre les attaques de table arc-en-ciel , bcrypt est une fonction adaptative : au fil du temps, le nombre d'itérations peut être augmenté pour la rendre plus lente, de sorte qu'elle reste résistante aux attaques de recherche par force brute même avec une puissance de calcul croissante.

La fonction bcrypt est l' algorithme de hachage de mot de passe par défaut pour OpenBSD , et était la valeur par défaut pour certaines distributions Linux telles que SUSE Linux .

Il existe des implémentations de bcrypt en C , C++ , C# , Embarcadero Delphi , Elixir , Go , Java , JavaScript , Perl , PHP , Ruby , Python , Rust , Zig et d'autres langages.

Blowfish est un chiffrement par blocs remarquable pour sa phase de configuration de clé coûteuse. Il démarre avec des sous-clés dans un état standard, puis utilise cet état pour effectuer un chiffrement par bloc en utilisant une partie de la clé, et utilise le résultat de ce chiffrement (qui est plus précis au niveau du hachage) pour remplacer certaines des sous-clés. Il utilise ensuite cet état modifié pour chiffrer une autre partie de la clé, et utilise le résultat pour remplacer davantage de sous-clés. Il procède de cette manière, en utilisant un état progressivement modifié pour hacher la clé et remplacer des bits d'état, jusqu'à ce que toutes les sous-clés aient été définies.

Provos et Mazières en ont profité et l'ont poussé plus loin. Ils ont développé un nouvel algorithme de configuration de clé pour Blowfish, baptisant le chiffrement résultant « Eksblowfish » (« programme de clé coûteux Blowfish »). La configuration de la clé commence par une forme modifiée de la configuration de clé standard Blowfish, dans laquelle le sel et le mot de passe sont utilisés pour définir toutes les sous-clés. Il y a ensuite un certain nombre de tours dans lesquels l'algorithme de clé standard Blowfish est appliqué, en utilisant alternativement le sel et le mot de passe comme clé, chaque tour commençant par l'état de la sous-clé du tour précédent. En théorie, ce n'est pas plus puissant que le programme de clé standard Blowfish, mais le nombre de tours de changement de clé est configurable ; ce processus peut donc être rendu arbitrairement lent, ce qui permet de dissuader les attaques par force brute sur le hachage ou le sel.

L'entrée de la fonction bcrypt est la chaîne de mot de passe (jusqu'à 72 octets), un coût numérique et une valeur de sel de 16 octets (128 bits). Le sel est généralement une valeur aléatoire. La fonction bcrypt utilise ces entrées pour calculer un hachage de 24 octets (192 bits). La sortie finale de la fonction bcrypt est une chaîne de la forme :

$2<a/b/x/y>$[coût]$[sel de 22 caractères][hachage de 31 caractères] 

Par exemple, avec le mot de passe d'entrée abc123xyz, le coût 12et un sel aléatoire, la sortie de bcrypt est la chaîne

$2a$12$R9h/cIPz0gi.URNNX3kh2OPST9/PgBkqquzi.Ss7KIUgO2t0jWMUW \__/\/ \____________________/\_____________________________/ Alg Coût Sel Hash 

Où:

• $2a$: L'identifiant de l'algorithme de hachage (bcrypt)
• 12:Coût d'entrée (2 ¹² soit 4096 tours)
• R9h/cIPz0gi.URNNX3kh2O:Un codage en base 64 du sel d'entrée
• PST9/PgBkqquzi.Ss7KIUgO2t0jWMUW:Un codage en base 64 des 23 premiers octets du hachage de 24 octets calculé

L'encodage en base 64 dans bcrypt utilise la table ./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789, qui diffère de l'encodage RFC 4648 Base64 .

$2$ (1999)

La spécification bcrypt originale définissait un préfixe de $2$. Cela suit le format Modular Crypt Format utilisé lors du stockage des mots de passe dans le fichier de mots de passe OpenBSD :

• $1$:Cryptage basé sur MD5 ('md5crypt')
• $2$:Crypte basée sur Blowfish ('bcrypt')
• $sha1$:Cryptage basé sur SHA-1 ('sha1crypt')
• $5$:Cryptage basé sur SHA-256 (« sha256crypt »)
• $6$:Cryptage basé sur SHA-512 (« sha512crypt »)

$2a$

La spécification d'origine ne définissait pas comment gérer les caractères non-ASCII, ni comment gérer un terminateur nul. La spécification a été révisée pour spécifier que lors du hachage de chaînes :

• la chaîne doit être codée en UTF-8
• le terminateur nul doit être inclus

Avec ce changement, la version a été modifiée en $2a$

$2x$, $2y$ (juin 2011)

En juin 2011, un bug a été découvert dans crypt_blowfish , une implémentation PHP de bcrypt. Il gérait mal les caractères avec le 8e bit défini. Ils ont suggéré que les administrateurs système mettent à jour leur base de données de mots de passe existante, en remplaçant $2a$par $2x$, pour indiquer que ces hachages sont mauvais (et doivent utiliser l'ancien algorithme cassé). Ils ont également suggéré l'idée de faire émettre crypt_blowfish$2y$ pour les hachages générés par l'algorithme corrigé.

Personne d'autre, y compris Canonical et OpenBSD, n'a adopté l'idée du 2x/2y. Ce changement de marqueur de version était limité à crypt_blowfish .

2 milliards de dollars (février 2014)

Un bug a été découvert dans l'implémentation OpenBSD de bcrypt. Il utilisait une valeur non signée de 8 bits pour contenir la longueur du mot de passe. Pour les mots de passe de plus de 255 octets, au lieu d'être tronqué à 72 octets, le mot de passe était tronqué à la plus petite valeur entre 72 et la longueur modulo 256. Par exemple, un mot de passe de 260 octets serait tronqué à 4 octets plutôt qu'à 72 octets.

bcrypt a été créé pour OpenBSD. Lorsqu'ils ont eu un bug dans leur bibliothèque, ils ont décidé d'augmenter le numéro de version.

La fonction bcrypt ci-dessous crypte le texte « OrpheanBeholderScryDoubt » 64 fois à l'aide de Blowfish . Dans bcrypt, la fonction de configuration de clé Blowfish habituelle est remplacée par une fonction de configuration de clé coûteuse (EksBlowfishSetup) :

Fonction bcrypt  Entrée : coût : Nombre (4..31)  log 2 (Itérations). ex. 12 ==> 2 12 = 4 096 itérations sel : tableau d'octets (16 octets)  sel aléatoire mot de passe : tableau d'octets (1..72 octets)  Mot de passe codé en UTF-8 
Sortie : hash : tableau d'octets (24 octets) // Initialiser l'état Blowfish avec un algorithme de configuration de clé coûteux 
// P : tableau de 18 sous-clés (UInt32[18]) 
// S : quatre boîtes de substitution (S-boxes), S 0 ... S 3 . Chaque S-box fait 1 024 octets (UInt32[256]) 
P , S ← EksBlowfishSetup( password , salt , cost ) //Crypter à plusieurs reprises le texte "OrpheanBeholderScryDoubt" 64 fois 
ctext ← "OrpheanBeholderScryDoubt"
 //24 octets ==> trois blocs de 64 bits 
se répètent (64) ctext ← EncryptECB( P , S , ctext ) //crypter à l'aide de Blowfish standard en mode ECB

// Le ctext de 24 octets est le hachage du mot de passe résultant

L'algorithme bcrypt dépend fortement de son algorithme de configuration de clé « Eksblowfish », qui fonctionne comme suit :

Fonction EksBlowfishSetup  Entrée : mot de passe : tableau d'octets (1..72 octets)  mot de passe codé en UTF-8 sel : tableau d'octets (16 octets)  coût du sel aléatoire : nombre (4..31)  log 2 (itérations). par exemple 12 ==> 2 12 = 4 096 itérations 
Sortie : P : tableau d'UInt32  tableau de 18 sous-clés par tour S 1 ..S 4 : tableau d'UInt32  tableau de quatre SBox ; chaque SBox est de 256 UInt32 ( c'est-à-dire que chaque SBox est de 1 Ko)
//Initialiser P (sous-clés) et S (boîtes de substitution) avec les chiffres hexadécimaux de pi 
P , S ← InitialState() //Permuter P et S en fonction du mot de passe et du sel 
P , S ← ExpandKey( P , S , password , salt ) //Il s'agit de la partie « coûteuse » de la « configuration de clé coûteuse ». 
//Sinon, la configuration de la clé est identique à Blowfish. 
repeat (2 cost ) P , S ← ExpandKey( P , S , password, 0) P , S ← ExpandKey( P , S , salt, 0) retour
 P , S

InitialState fonctionne comme dans l'algorithme Blowfish original, en remplissant les entrées du tableau P et de la boîte S avec la partie fractionnaire en hexadécimal.

La fonction ExpandKey effectue les opérations suivantes :

Fonction ExpandKey  Entrée : P : tableau de UInt32  Tableau de 18 sous-clés S 1 ..S 4 : UInt32[1024]  Quatre SBox de 1 Ko mot de passe : tableau d'octets (1..72 octets)  Mot de passe codé en UTF-8 sel : Byte[16]  sel aléatoire 
Sortie : P : tableau de UInt32  Tableau de 18 sous-clés par tour S 1 ..S 4 : UInt32[1024]  Quatre SBox de 1 Ko
//Mélanger le mot de passe dans le tableau de sous-clés P 
pour
 n ← 1 à 18 faire P n ← P n 
xor 
password [32(n-1)..32n-1] //traiter le mot de passe comme cyclique
//Traitez le sel de 128 bits comme deux moitiés de 64 bits (la taille du bloc Blowfish). saltHalf[0] ← salt [0..63] //64 bits inférieurs de sel saltHalf[1] ← salt [64..127] //64 bits supérieurs de sel
//Initialiser un tampon de 8 octets (64 bits) avec tous les zéros. bloc ← 0 // Mélanger l'état interne dans des boîtes P 
pour
 n ← 1 à 9 do // xor 
bloc 64 bits avec un demi- 
bloc de sel 64 bits ← bloc xor saltHalf [(n-1) mod 2] // chaque itération alternant entre saltHalf [0] et saltHalf [1]
//crypter le bloc en utilisant la planification de clé actuelle 
block ← Encrypt( P , S , block ) P 2n ← bloc [0..31] // 32 bits inférieurs du bloc P 2n+1 ← bloc [32..63] // 32 bits supérieurs du bloc
//Mélanger l'état chiffré dans les boîtes S internes de l'état 
pour
 i ← 1 à 4 faire 
pour
 n ← 0 à 127 faire
 block ← Encrypt( state , block 
xor
 saltHalf [(n-1) mod 2]) //comme ci-dessus S i [2n] ← block [0..31] //32 bits inférieurs S i [2n+1] ← block [32..63] //32 bits supérieurs 
renvoient
 l'état

Par conséquent, il est identique au programme de clés Blowfish standard, car tous les XOR avec une valeur de sel entièrement nulle sont inefficaces. est similaire, mais utilise le sel comme une clé de 128 bits. ExpandKey(state, 0, key)ExpandKey(state, 0, salt)

De nombreuses implémentations de bcrypt tronquent le mot de passe aux 72 premiers octets, suivant l'implémentation d'OpenBSD.

L'algorithme mathématique lui-même nécessite une initialisation avec 18 sous-clés de 32 bits (équivalent à 72 octets/octets). La spécification originale de bcrypt n'impose aucune méthode particulière pour mapper les mots de passe textuels de l'espace utilisateur en valeurs numériques pour l'algorithme. Un bref commentaire dans le texte mentionne, mais n'impose pas, la possibilité d'utiliser simplement la valeur codée ASCII d'une chaîne de caractères : « Enfin, l'argument clé est une clé de chiffrement secrète, qui peut être un mot de passe choisi par l'utilisateur jusqu'à 56 octets (y compris un octet zéro de fin lorsque la clé est une chaîne ASCII). »

Notez que la citation ci-dessus mentionne des mots de passe « jusqu'à 56 octets » même si l'algorithme lui-même utilise une valeur initiale de 72 octets. Bien que Provos et Mazières n'indiquent pas la raison de la restriction plus courte, ils ont peut-être été motivés par la déclaration suivante de la spécification originale de Blowfish de Bruce Schneier , « La limite de 448 [bits] sur la taille de la clé garantit que [ sic ] chaque bit de chaque sous-clé dépend de chaque bit de la clé. »

Les implémentations ont varié dans leur approche de conversion des mots de passe en valeurs numériques initiales, y compris parfois en réduisant la force des mots de passe contenant des caractères non ASCII.

Il est important de noter que bcrypt n'est pas une fonction de dérivation de clé (KDF) . Par exemple, bcrypt ne peut pas être utilisé pour dériver une clé de 512 bits à partir d'un mot de passe. En même temps, des algorithmes comme pbkdf2 , scrypt et argon2 sont des fonctions de dérivation de clé basées sur un mot de passe, où la sortie est ensuite utilisée à des fins de hachage de mot de passe plutôt que simplement de dérivation de clé.

Le hachage du mot de passe doit généralement être terminé en moins de 1 000 ms. Dans ce scénario, bcrypt est plus puissant que pbkdf2, scrypt et argon2.

• PBKDF2 : pbkdf2 est plus faible que bcrypt. L'algorithme de hachage SHA2 couramment utilisé n'est pas gourmand en mémoire. SHA2 est conçu pour être extrêmement léger afin de pouvoir fonctionner sur des appareils légers (par exemple des cartes à puce). Cela signifie que PBKDF2 est très faible pour le stockage de mots de passe, car le matériel de hachage SHA-2 de base capable d'effectuer des milliards de hachages par seconde est facilement disponible.
• scrypt : scrypt est plus faible que bcrypt pour les besoins en mémoire inférieurs à 4 Mo. scrypt nécessite environ 1000 fois la mémoire de bcrypt pour atteindre un niveau de défense comparable contre les attaques basées sur le GPU (pour le stockage des mots de passe).
• argon2 : bcrypt est plus léger qu'Argon2. Cela peut poser un problème pour certaines applications Web où l'utilisation d'Argon2 nécessiterait de réduire les paramètres de sécurité à un niveau inacceptable afin de rester performant. Plus précisément, Argon2 est moins sécurisé que bcrypt pour des temps d'exécution inférieurs à 1 seconde (c'est-à-dire pour l'authentification par mot de passe commun). Argon2 n'égale ni ne dépasse la force de bcrypt jusqu'à ce qu'il dépasse des temps d'exécution d'environ 1000 ms. Cela peut ne pas convenir au hachage de mot de passe, mais est parfaitement acceptable pour la dérivation de clés. Dans certains cas, Argon2 est recommandé par rapport à bcrypt, si les paramètres de sécurité sont suffisamment élevés.
• pufferfish2 est une évolution de bcrypt qui utilise une empreinte mémoire réglable (comme scrypt et argon2), plutôt que l'empreinte mémoire fixe de 4 Ko de bcrypt. Similaire à scrypt ou argon2, pufferfish2 gagne en difficulté en utilisant plus de mémoire. Contrairement à scrypt et argon2, pufferfish2 ne fonctionne que dans le cache L2 d'un cœur de processeur. Alors que scrypt et argon2 gagnent leur dureté de mémoire en accédant aléatoirement à beaucoup de RAM, pufferfish2 se limite au seul cache L2 dédié disponible pour un cœur de processeur. Cela le rend encore plus difficile à implémenter dans du matériel personnalisé que scrypt et argon2. L'empreinte mémoire idéale de pufferfish2 est la taille du cache disponible pour un cœur (par exemple 1,25 Mo pour Intel Alder Lake ). Cela rend pufferfish2 beaucoup plus résistant au GPU ou à l'ASIC.

bcrypt a une longueur de mot de passe maximale de 72 octets. Ce maximum provient de la première opération de la fonction ExpandKey qui utilise XOR sur les 18 sous-clés de 4 octets (P) avec le mot de passe :

P 1 ..P 18 ← P 1 ..P 18 mot de passe xorOctets 

Le mot de passe (codé en UTF-8) est répété jusqu'à ce qu'il atteigne 72 octets. Par exemple, un mot de passe de :

correct horse battery staple␀ (29 octets)

Est répété jusqu'à ce qu'il corresponde aux 72 octets des 18 sous-clés P par tour :

correct horse battery staple␀correct horse battery staple␀correct horse (72 octets)

Dans le pire des cas, un mot de passe est limité à 18 caractères, alors que chaque caractère nécessite 4 octets de codage UTF-8. Par exemple :

𐑜𐑝𐑟𐑥𐑷𐑻𐑽𐑾𐑿𐑿𐑰𐑩𐑛𐑙𐑘𐑙𐑒𐑔 (18 caractères, 72 octets)

En 2024, un service d'authentification unique d' Okta, Inc. a annoncé une vulnérabilité due au mot de passe concaténé après le nom d'utilisateur et la paire hachée avec bcrypt, ce qui a pour résultat que le mot de passe est ignoré pour les connexions avec un nom d'utilisateur suffisamment long .

L'algorithme bcrypt consiste à crypter de manière répétée le texte de 24 octets :

OrpheanBeholderScryDoubt (24 octets)

Cela génère 24 octets de texte chiffré, par exemple :

85 20 af 9f 03 3d b3 8c 08 5f d2 5e 2d aa 5e 84 a2 b9 61 d2 f1 29 c9 a4 (24 octets)

L'implémentation canonique d'OpenBSD tronque ceci à 23 octets :

85 20 af 9f 03 3d b3 8c 08 5f d2 5e 2d aa 5e 84 a2 b9 61 d2 f1 29 c9 (23 octets)

On ne sait pas pourquoi l'implémentation canonique supprime 8 bits du hachage de mot de passe résultant.

Ces 23 octets deviennent 31 caractères lorsqu'ils sont codés en radix-64 :

fQAtluK7q2uGV7HcJYncfII3WbJvIai (31 caractères)

L'encodage utilisé par l'implémentation canonique d'OpenBSD utilise le même alphabet Base64 que crypt , qui est ./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789. Cela signifie que l'encodage n'est pas compatible avec la RFC 4648 plus courante .