Pourquoi les sels rendent-ils les attaques de dictionnaire «impossibles»?

Mise à jour: S’il vous plaît noter que je ne demande pas ce qu’est un sel, ce qu’est une table arc-en-ciel, ce qu’est une attaque par dictionnaire ou quel est le but d’un sel. J’interroge: Si vous connaissez les utilisateurs de sel et de hash, n’est-ce pas assez facile de calculer leur mot de passe?

Je comprends le processus et je l’implémente moi-même dans certains de mes projets.

s = random salt storedPassword = sha1(password + s) 

Dans la firebase database que vous stockez:

 username | hashed_password | salt 

Chaque mise en œuvre de salage que j’ai vue ajoute le sel soit à la fin du mot de passe, soit au début:

 hashed_Password = sha1(s + password ) hashed_Password = sha1(password + s) 

Par conséquent, une attaque par dictionnaire d’un pirate informatique qui vaut son sel (ha ha) ne ferait qu’exécuter chaque mot-clé contre les sels stockés dans les combinaisons communes énumérées ci-dessus.

La mise en œuvre décrite ci-dessus ajoute-t-elle simplement une étape supplémentaire pour le pirate informatique, sans résoudre le problème sous-jacent? Quelles alternatives existe-t-il pour contourner ce problème, ou est-ce que je comprends mal le problème?

La seule chose que je peux penser à faire est d’avoir un algorithme de fusion secrète qui lie le sel et le mot de passe ensemble, ou ajoute d’autres champs utilisateur au processus de hachage, ce qui signifie que le pirate doit avoir access à la firebase database eux pour une attaque de dictionnaire se révéler fructueuse. (Mise à jour, comme indiqué dans les commentaires, il est préférable de supposer que le pirate a access à toutes vos informations, donc ce n’est probablement pas la meilleure).

Permettez-moi de vous donner un exemple de la manière dont je propose qu’un pirate informatique pirate une firebase database utilisateur avec une liste de mots de passe et de hachages:

Données de notre firebase database piratée:

 RawPassword (not stored) | Hashed | Salt -------------------------------------------------------- letmein WEFLS... WEFOJFOFO... 

Dictionnaire de mots de passe commun:

  Common Password -------------- letmein 12345 ... 

Pour chaque enregistrement d’utilisateur, bouclez les mots de passe courants et hachez-les:

 for each user in hacked_DB salt = users_salt hashed_pw = users_hashed_password for each common_password testhash = sha1(common_password + salt) if testhash = hashed_pw then //Match! Users password = common_password //Lets visit the webpage and login now. end if next next 

J’espère que cela illustre bien mon propos.

Compte tenu de 10 000 mots de passe courants et de 10 000 enregistrements d’utilisateur, il faudrait calculer 100 000 000 de hachages pour découvrir autant de mots de passe d’utilisateurs que possible. Cela peut prendre quelques heures, mais ce n’est pas vraiment un problème.

Mise à jour sur la théorie de la fissuration

Nous supposerons que nous sums un hébergeur corrompu, qui a access à une firebase database de hachages et de sels SHA1, ainsi que votre algorithme pour les mélanger. La firebase database contient 10 000 enregistrements d’utilisateurs.

Ce site prétend pouvoir calculer 2 300 000 000 SHA1 par seconde en utilisant le GPU. (Dans la réalité, la situation sera probablement plus lente, mais pour le moment, nous utiliserons ce chiffre).

(((95 ^ 4) / 2300000000) / 2) * 10000 = 177 secondes

Étant donné une gamme complète de 95 caractères ASCII imprimables, avec une longueur maximale de 4 caractères, divisée par le taux de calcul (variable), divisé par 2 (en supposant que le temps moyen pour découvrir le mot de passe nécessitera 50% des permutations) les utilisateurs prendraient 177 secondes pour calculer tous les mots de passe des utilisateurs dont la longueur est <= 4.

Ajuster un peu pour le réalisme.

(((36 ^ 7) / 1000000000) / 2) * 10000 = 2 jours

En supposant l’absence de sensibilité à la casse, avec une longueur de mot de passe <= 7, uniquement des caractères alphanumériques, il faudrait 4 jours pour résoudre 10 000 enregistrements utilisateur et j'ai réduit de moitié la vitesse de l'algorithme.

Il est important de reconnaître qu’il s’agit d’une attaque par force brute linéaire, tous les calculs étant indépendants les uns des autres, c’est donc une tâche parfaite pour plusieurs systèmes à résoudre. (IE facile à configurer 2 ordinateurs exécutant des attaques à des fins différentes, ce qui ferait la moitié du temps d’exécution).

Dans le cas du hachage récursif d’un mot de passe 1000 fois pour rendre cette tâche plus coûteuse en calcul:

(((36 ^ 7) / 1 000 000 000) / 2) * 1000 secondes = 10,8839117 heures

Cela représente une longueur maximale de 7 caractères alphanumériques, à une vitesse inférieure à la moitié de celle indiquée pour un utilisateur .

Le hachage récursif 1 000 fois bloque efficacement une attaque globale, mais les attaques ciblées sur les données utilisateur sont toujours vulnérables.

Oui, il ne vous faut que 3 jours pour sha1 (salt | password). C’est pourquoi de bons algorithmes de stockage de mots de passe utilisent un hachage à 1000 itérations: il vous faudra 8 ans.

Il n’arrête pas les attaques par dictionnaire.

Ce qu’il fait est d’arrêter quelqu’un qui parvient à obtenir une copie de votre fichier de mot de passe d’utiliser une table arc- en -ciel pour déterminer quels sont les mots de passe des hachages.

Finalement, il peut être forcé par la force, cependant. La réponse à cette question est de forcer vos utilisateurs à ne pas utiliser les mots du dictionnaire comme mots de passe (exigences minimales d’au moins un chiffre ou caractère spécial, par exemple).

Mise à jour :

J’aurais dû le mentionner plus tôt, mais certains systèmes de mots de passe (la plupart?) Utilisent un sel différent pour chaque mot de passe, probablement stocké avec le mot de passe lui-même. Cela rend inutile une seule table arc-en-ciel. C’est ainsi que fonctionne la bibliothèque de cryptes UNIX, et les systèmes d’exploitation de type UNIX modernes ont étendu cette bibliothèque avec de nouveaux algorithmes de hachage.

Je sais pertinemment que la prise en charge de SHA-256 et SHA-512 a été ajoutée dans les nouvelles versions de GNU crypt.

Pour être plus précis, une attaque par dictionnaire , c’est-à-dire une attaque où tous les mots d’une liste exhaustive sont essayés, n’est pas “impossible”, mais peu pratique : chaque bit de sel double la quantité de stockage et de calcul requirejse .

Ceci est différent des attaques par dictionnaire pré-calculées comme les attaques impliquant des tables arc-en-ciel, peu importe que le sel soit secret ou non.

Exemple: avec un sel de 64 bits (soit 8 octets), vous devez vérifier 2 64 combinaisons de mots de passe supplémentaires dans votre attaque par dictionnaire. Avec un dictionnaire contenant 200 000 mots, vous devrez faire

200 000 * 2 64 = 3,69 * 10 24

tests dans le pire des cas – au lieu de 200 000 tests sans sel.

Un avantage supplémentaire de l’utilisation de salt est qu’un attaquant ne peut pas pré-calculer les hachages de mots de passe de son dictionnaire. Cela prendrait simplement trop de temps et / ou d’espace.

Mettre à jour

Votre mise à jour suppose qu’un attaquant connaît déjà le sel (ou l’a volé). C’est bien sûr une situation différente. Cependant, il n’est pas possible pour l’attaquant d’utiliser une table arc-en-ciel pré-calculée. Ce qui compte ici, c’est la vitesse de la fonction de hachage. Pour rendre une attaque impraticable, la fonction de hachage doit être lente. MD5 ou SHA ne sont pas de bons candidats car ils sont conçus pour être rapides, les meilleurs candidats pour les algorithmes de hachage sont Blowfish ou certaines de ses variantes.

Mise à jour 2

Une bonne lecture sur la question de la sécurisation de vos mots de passe en général (allant bien au-delà de la question initiale mais toujours intéressante):

Assez avec les tables Rainbow: ce que vous devez savoir sur les schémas de mots de passe sécurisés

Corollaire de l’article: Utilisez des hachages salés créés avec bcrypt (basé sur Blowfish) ou Eksblowfish qui vous permettent d’utiliser un temps de configuration configurable pour ralentir le hachage.

Un dictionnaire est une structure où les valeurs sont indexées par des clés. Dans le cas d’une attaque par dictionnaire pré-calculée, chaque clé est un hachage et la valeur correspondante est un mot de passe qui entraîne le hachage. Avec un dictionnaire pré-calculé en main, un attaquant peut “instantanément” rechercher un mot de passe qui produira le hachage nécessaire pour se connecter.

Avec le sel, l’espace requirejs pour stocker le dictionnaire augmente rapidement… si rapidement que la tentative de pré-calcul d’un dictionnaire de mots de passe devient rapidement inutile.

Les meilleurs sels sont choisis au hasard parmi un générateur de nombres aléatoires cryptographiques. Huit octets sont une taille pratique et plus de 16 octets ne servent à rien.


Le sel fait beaucoup plus que simplement «rendre le travail d’un attaquant plus irritant». Il élimine toute une classe d’attaque, à savoir l’utilisation de dictionnaires précalculés.

Un autre élément est nécessaire pour sécuriser complètement les mots de passe, à savoir “renforcer les clés”. Un tour de SHA-1 n’est pas suffisant: un algorithme de hachage sécurisé des mots de passe devrait être très lent sur le plan des calculs.

De nombreuses personnes utilisent PBKDF2, une fonction de dérivation de clé, qui renvoie des résultats à la fonction de hachage des milliers de fois. L’algorithme “bcrypt” est similaire, utilisant une dérivation de clé itérative lente.

Lorsque l’opération de hachage est très lente, une table précalculée devient de plus en plus souhaitable pour un attaquant. Mais le bon sel défait cette approche.


commentaires

Voici les commentaires que j’ai faits sur la question.


Sans salt, un attaquant n’utiliserait pas la méthode décrite dans “Update 2”. Il ferait simplement une recherche dans une table pré-calculée et obtiendrait le mot de passe en temps O (1) ou O (log n) (n étant le nombre de mots de passe candidats). Salt est ce qui l’empêche et l’oblige à utiliser l’approche O (n) indiquée dans la «Mise à jour 2».

Une fois réduit à une attaque O (n), nous devons tenir compte de la durée de chaque tentative. Le renforcement des clés peut prendre chaque seconde de la boucle, ce qui signifie que le temps nécessaire pour tester 10k mots de passe sur 10k utilisateurs va de 3 jours à 3 ans … et avec seulement 10k mots de passe, vous risquez de ne pas craquer mots de passe à cette époque.

Vous devez considérer qu’un attaquant va utiliser les outils les plus rapides possibles, pas PHP, donc des milliers d’itérations, plutôt que 100, seraient un bon paramètre pour le renforcement des clés. Il faut une fraction de seconde pour calculer le hash pour un seul mot de passe.

Le renforcement des clés fait partie des algorithmes standard de dérivation de clés PBKDF1 et PBKDF2, de PKCS # 5, qui constituent d’excellents algorithmes d’obfuscation de mots de passe (la “clé dérivée” est le “hash”).

Beaucoup d’utilisateurs sur StackOverflow se réfèrent à cet article car il s’agissait d’une réponse à la publication de Jeff Atwood sur les dangers des tables arc-en-ciel. Ce n’est pas mon article préféré, mais il discute de ces concepts plus en détail.


Bien sûr, vous supposez que l’attaquant a tout: salt, hash, nom d’utilisateur. Supposons que l’attaquant est un employé de la société d’hébergement corrompu qui a vidé la table des utilisateurs sur votre site de fans myprettypony.com. Il essaie de récupérer ces mots de passe, car il va se retourner et voir si vos fans de poney ont utilisé le même mot de passe sur leurs comptes citibank.com.

Avec un schéma de mot de passe bien conçu, il sera impossible à ce type de récupérer des mots de passe.

Le but du salage est d’empêcher l’amortissement de l’effort de l’attaquant.

Sans sel, une seule table d’entrées de mot de passe de hachage précalculées (par exemple MD5 de toutes les chaînes alphanumériques de 5 caractères, faciles à trouver en ligne) peut être utilisée sur chaque utilisateur dans chaque firebase database du monde.

Avec un sel spécifique au site, l’attaquant doit calculer lui-même la table et peut ensuite l’utiliser sur tous les utilisateurs du site.

Avec un sel par utilisateur, l’attaquant doit déployer cet effort pour chaque utilisateur séparément.

Bien sûr, cela ne protège pas beaucoup les mots de passe très faibles d’un dictionnaire, mais protège les mots de passe raisonnablement forts contre cet amortissement.

De plus, un autre point important en utilisant un sel spécifique à USER évite la détection de deux utilisateurs avec le mot de passe SAME. C’est pourquoi le hash est souvent le hash (salt + username + password)

Si vous essayez de garder le secret du hachage, l’attaquant ne peut pas non plus vérifier les hachages.

Edit- vient de remarquer que le point principal a été fait dans un commentaire ci-dessus.

Les sels sont mis en œuvre pour prévenir les attaques à l’arc-en-ciel. Une table arc-en-ciel est une liste de hachages pré-calculés, ce qui rend la traduction d’un hachage plus simple. Vous devez comprendre que le salage n’est pas efficace en tant que moyen de prévention moderne permettant de déchiffrer un mot de passe à moins d’avoir un outil de hachage moderne.

Alors disons que nous travaillons avec SHA1, profitant des récents exploits découverts avec cet algo, et disons que nous avons un ordinateur fonctionnant à 1 000 000 de hachages / seconde, il faudrait 5,3 millions de millions d’années pour trouver une collision , alors oui php peut travailler 300 par seconde, gros coup, n’a pas d’importance. La raison en est que si quelqu’un a pris la peine de générer toutes les expressions de dictionnaire courantes (2 ^ 160 personnes, bienvenue aux exploits de l’ère 2007).

Donc, voici une firebase database réelle, avec 2 utilisateurs que j’utilise à des fins de test et d’administration.

 RegistrationTime UserName UserPass 1280185359.365591 briang a50b63e927b3aebfc20cd783e0fc5321b0e5e8b5 1281546174.065087 test 5872548f2abfef8cb729cac14bc979462798d023 

En fait, le programme de salaison est votre sha1 (heure d’enregistrement + nom d’utilisateur). Allez-y, dites-moi mon mot de passe, ce sont de vrais mots de passe en production. Vous pouvez même vous asseoir et hacher une liste de mots en php. Devenir fou.

Je ne suis pas fou, je sais juste que c’est sécurisé. Pour le plaisir, le mot de passe du test est test . sha1(sha1(1281546174.065087 + test) + test) = 5872548f2abfef8cb729cac14bc979462798d023

Vous devez générer une table arc-en-ciel complète avec 27662aee8eee1cb5ab4917b09bdba31d091ab732 uniquement pour cet utilisateur. Cela signifie que je peux réellement laisser mes mots de passe ne pas être tous compromis par une seule table arc-en-ciel, le pirate doit générer une table arc-en-ciel pour 27662aee8eee1cb5ab4917b09bdba31d091ab732 pour le test et encore f3f7735311217529f2e020468004a2aa5b3dee7f pour briang. Rappelez-vous les 5,3 millions de millions d’années pour tous les hachages. Pensez à la taille de stockage des seuls 2 ^ 80 hachages (c’est-à-dire plus de 20 yottaoctets ), cela ne va pas arriver.

Ne confondez pas le salage comme moyen de créer un hash que vous ne pouvez jamais décoder, c’est un moyen d’empêcher une table arc-en-ciel de traduire tous vos mots de passe utilisateur. C’est impossible à ce niveau de technologie.

L’idée derrière l’attaque de dictionnaire est que vous prenez un hachage et trouvez le mot de passe à partir duquel ce hachage a été calculé, sans calcul de hachage. Maintenant, faites la même chose avec le mot de passe salé – vous ne pouvez pas.

Ne pas utiliser un sel rend la recherche par mot de passe aussi simple que la recherche dans la firebase database. L’ajout d’un sel permet à l’attaquant d’effectuer le calcul du hachage de tous les mots de passe possibles (même pour l’attachement au dictionnaire, cela augmente considérablement le temps d’attaque).

En termes simples: sans salage, chaque mot de passe candidat ne doit être haché qu’une seule fois pour le comparer à tous les utilisateurs, n’importe où dans l’univers connu (collection de bases de données compromises), dont le mot de passe est le même. Avec le salage, si le nombre de valeurs de sel possibles dépasse sensiblement le nombre d’utilisateurs dans “l’univers connu”, chaque mot de passe candidat doit être haché séparément pour chaque utilisateur contre lequel il sera testé.

Le simple fait de saler n’empêche pas un hachage d’attaque (force brute ou dictionnaire), cela ne fait que le rendre plus difficile; L’attaquant devra soit trouver l’algorithme de salage (qui, s’il est correctement implémenté, utilisera plus d’itérations) ou forcer l’algo, ce qui, à moins d’être très simple, est presque impossible. Le salage élimine aussi presque complètement la possibilité de consulter les tables arc-en-ciel …

Salt rend les attaques sur table Rainbow beaucoup plus difficiles, car cela rend le hachage d’un mot de passe unique beaucoup plus difficile. Imaginez que vous ayez un horrible mot de passe pour le numéro 1. Une attaque par table arc-en-ciel pourrait le casser immédiatement.

Imaginez maintenant que chaque mot de passe dans la firebase database est salé avec une longue valeur aléatoire de nombreux caractères aléatoires. Maintenant, votre mot de passe “1” est stocké dans la firebase database sous la forme d’un hachage de 1 plus un groupe de caractères aléatoires (le sel). Dans cet exemple, la table arc-en-ciel doit contenir

Donc en supposant que votre sel est quelque chose de sûr et aléatoire, disons ()% ISLDGHASKLU ( % #% #, la table arc-en-ciel du pirate devrait avoir une entrée pour 1 * ()% ISLDGHASKLU (*% #% #. même ce simple mot de passe n’est plus pratique.