Combien de temps faut-il pour forcer un hachage SHA-512 salé ? (sel fourni)

Question

Voici un algorithme en Java :

public String getHash(String password, String salt) throws Exception {
    String input = password + salt;
    MessageDigest md = MessageDigest.getInstance(SHA-512);
    byte[] out = md.digest(input.getBytes());
    return HexEncoder.toHex(out);
}

Supposons que le sel soit connu. Je veux connaître le temps nécessaire à la force brute lorsque le mot de passe est un mot du dictionnaire et également lorsqu'il ne l'est pas.

Answer 1

Dans votre cas, casser l'algorithme de hachage est équivalent à trouver une collision dans l'algorithme de hachage. Cela signifie que vous n'avez pas besoin de trouver le mot de passe lui-même (qui serait une attaque par préimage ), il suffit de trouver une sortie de la fonction de hachage qui est égale au hachage d'un mot de passe valide (d'où le terme "collision"). Trouver une collision en utilisant une attaque d'anniversaire prend O(2^(n/2)) temps, où n est la longueur de sortie de la fonction de hachage en bits.

SHA-2 a une taille de sortie de 512 bits, donc trouver une collision prendrait O(2^256) temps. Étant donné qu'il n'y a pas d'attaques intelligentes sur l'algorithme lui-même (actuellement, aucune n'est connue pour la famille de hachage SHA-2), c'est ce qu'il faut pour casser l'algorithme.

Pour avoir une idée de ce que 2^256 signifie réellement : on pense actuellement que le nombre d'atomes dans l'univers (entier !!!) est d'environ 10^80, soit environ 2^266. En supposant une entrée de 32 octets (ce qui est raisonnable dans votre cas - 20 octets de sel + 12 octets de mot de passe) ma machine prend ~0,22s (~2^-2s) pour 65536 (=2^16) calculs. Donc 2^256 calculs seraient effectués en 2^240 * 2^16 calculs qui prendraient

2^240 * 2^-2 = 2^238 ~ 10^72s ~ 3,17 * 10^64 years

Même appeler ça des millions d'années est ridicule. Et ça ne s'améliore pas beaucoup avec le matériel le plus rapide de la planète qui calcule des milliers de hachages en parallèle. Aucune technologie humaine ne sera capable de transformer ce nombre en quelque chose d'acceptable.

Donc, oubliez le forçage brutal de SHA-256 ici. Votre prochaine question concernait les mots du dictionnaire. Pour récupérer de tels mots de passe faibles tables arc-en-ciel étaient utilisés traditionnellement. Une table arc-en-ciel est généralement une table de valeurs de hachage pré-calculées, l'idée étant que si vous étiez capable de pré-calculer et de stocker chaque hachage possible avec son entrée, il vous faudrait O(1) pour rechercher un hachage donné et récupérer une pré-image valide pour celui-ci. Bien entendu, cela n'est pas possible dans la pratique, car aucun dispositif de stockage ne peut conserver une telle quantité de données. Ce dilemme est connu sous le nom de compromis mémoire-temps . Comme vous ne pouvez stocker qu'un nombre limité de valeurs, les tables arc-en-ciel typiques comprennent une forme de chaînage de hachage avec des fonctions de réduction intermédiaires (ceci est expliqué en détail dans l'article de Wikipedia) pour gagner de l'espace en renonçant à un gain de temps.

Les sels étaient une contre-mesure pour rendre ces tables arc-en-ciel infaisables. Pour décourager les attaquants de précalculer une table pour un sel spécifique, il est recommandé d'appliquer des valeurs de sel par utilisateur. Cependant, étant donné que les utilisateurs n'utilisent pas de mots de passe sûrs et complètement aléatoires, il est toujours surprenant de constater le succès que l'on peut obtenir si le sel est connu et que l'on se contente d'itérer sur un grand dictionnaire de mots de passe courants dans un simple schéma d'essais et d'erreurs. La relation entre le langage naturel et le caractère aléatoire s'exprime comme suit entropie . Les choix de mots de passe typiques sont généralement de faible entropie, alors que des valeurs totalement aléatoires contiendraient un maximum d'entropie.

La faible entropie des mots de passe typiques fait qu'il y a une chance relativement élevée que l'un de vos utilisateurs utilise un mot de passe provenant d'une base de données relativement petite de mots de passe courants. Si vous les recherchez sur Google, vous finirez par trouver des liens torrent pour de telles bases de données de mots de passe, souvent de l'ordre du gigaoctet. Le succès d'un tel outil est généralement de l'ordre de quelques minutes à quelques jours si l'attaquant n'est soumis à aucune restriction.

C'est pourquoi, en règle générale, le hachage et le salage ne suffisent pas, il faut également installer d'autres mécanismes de sécurité. Vous devriez utiliser une méthode de réduction de l'entropie ralentie artificiellement, comme PBKDF2, décrite dans le document suivant PKCS#5 et vous devriez imposer une période d'attente pour un utilisateur donné avant qu'il ne puisse réessayer de saisir son mot de passe. Un bon schéma est de commencer par 0,5s et de doubler ce temps pour chaque tentative échouée. Dans la plupart des cas, les utilisateurs ne le remarquent pas et n'échouent pas plus de trois fois en moyenne. Mais cela ralentira considérablement toute personne extérieure malveillante qui tenterait d'attaquer votre application.

Answer 2

Je veux connaître le temps nécessaire à la force brute lorsque le mot de passe est un mot du dictionnaire et également lorsqu'il ne l'est pas.

Mot de passe dictionnaire

Chiffre approximatif il y a environ 1 000 000 de mots anglais, et si un pirate peut calculer environ 10 000 hachages SHA-512 par seconde ( mettre à jour : voir le commentaire de CodesInChaos, cette estimation est très basse), 1.000.000 / 10.000 = 100 secondes . Il faut donc un peu plus d'une minute pour craquer un mot de passe dictionnaire d'un seul mot pour un seul utilisateur. Si l'utilisateur concatène deux mots du dictionnaire, vous êtes dans la zone de quelques jours, mais encore très possible si l'attaquant est suffisamment soigneux. Plus que ça et ça commence à devenir difficile.

Mot de passe aléatoire

Si le mot de passe est une séquence vraiment aléatoire de caractères alphanumériques, en majuscules et en minuscules, alors le nombre de mots de passe possibles de longueur N est de 60^N (il y a 60 caractères possibles). Nous ferons le calcul dans l'autre sens cette fois-ci ; nous demanderons : Quelle longueur de mot de passe pourrions-nous craquer en un temps donné ? Il suffit d'utiliser cette formule :

N = Log60(t * 10,000) où t est le temps passé à calculer les hachages en secondes (en supposant à nouveau 10 000 hachages par seconde).

1 minute:    3.2
5 minute:    3.6
30 minutes:  4.1
2 hours:     4.4
3 days:      5.2

Donc, en trois jours, nous serons capables de craquer le mot de passe s'il comporte 5 caractères.

Tout ceci est très approximatif, mais vous voyez l'idée. Mise à jour : voir le commentaire ci-dessous, il est en fait possible de craquer des mots de passe beaucoup plus longs que celui-ci.

Qu'est-ce qui se passe ici ?

Clarifions certaines idées fausses :

• Le sel ne rend pas le calcul des hachages plus lent. cela signifie simplement qu'ils doivent craquer le mot de passe de chaque utilisateur individuellement, et les tables de hachage pré-calculées (mot à la mode) : tables arc-en-ciel ) sont rendus complètement inutiles. Si vous n'avez pas de table de hachage pré-calculée, et que vous ne craquez qu'un seul hachage de mot de passe, le salage ne fait aucune différence.

• SHA-512 n'est pas conçu pour être difficile à forcer. . De meilleurs algorithmes de hachage comme BCrypt, PBKDF2 ou SCrypt peuvent être configurés pour prendre beaucoup plus de temps à calculer, et un ordinateur moyen pourrait n'être capable de calculer que 10 à 20 hachages par seconde. Lire Cette excellente réponse sur le hachage de mot de passe si vous ne l'avez pas déjà fait.

• mise à jour : Comme indiqué dans le commentaire de CodesInChaos, même les mots de passe à forte entropie (environ 10 caractères) peuvent être forcés si l'on utilise le bon matériel pour calculer les hachages SHA-512.

---

Notes sur la réponse acceptée :

La réponse acceptée à partir de Septembre 2014 est incorrect et dangereusement incorrect :

Dans votre cas, casser l'algorithme de hachage est équivalent à trouver une collision dans l'algorithme de hachage. Cela signifie que vous n'avez pas besoin de trouver le mot de passe lui-même (ce qui serait une attaque préimage)... Trouver une collision en utilisant une attaque par anniversaire prend O(2^n/2) temps, où n est la longueur de sortie de la fonction de hachage en bits.

L'attaque d'anniversaire est complètement hors sujet pour craquer un hachage donné. Et c'est en fait un exemple parfait d'une attaque de préimage . Cette formule et les deux paragraphes suivants donnent des valeurs dangereusement élevées et totalement dénuées de sens pour un temps d'attaque. Comme démontré ci-dessus il est parfaitement possible de craquer des mots de passe à dictionnaire salé en quelques minutes .

La faible entropie des mots de passe typiques fait qu'il y a une chance relativement élevée que l'un de vos utilisateurs utilise un mot de passe provenant d'une base de données relativement petite de mots de passe courants...

C'est pourquoi, en général, le hachage et le salage seuls ne suffisent pas, il faut également installer d'autres mécanismes de sécurité. Vous devriez utiliser une méthode qui ralentit artificiellement l'entropie, comme le PBKDF2 décrit dans le PKCS#5...

Oui, veuillez utiliser un algorithme qui est lent à calculer, mais qu'est-ce qui "augmente l'entropie" ? Mettre un mot de passe à faible entropie dans un hash n'augmente pas l'entropie. Cela devrait préserver L'entropie, mais vous ne pouvez pas améliorer un mauvais mot de passe avec un hachage, ça ne marche pas comme ça. Un mot de passe faible passé au crible de PBKDF2 reste un mot de passe faible.

Answer 3

Il n'y a pas de réponse unique à cette question car il y a trop de variables, mais SHA2 n'est pas encore vraiment craqué (voir : Durée de vie des fonctions de hachage cryptographiques ), c'est donc toujours un bon algorithme à utiliser pour stocker les mots de passe. L'utilisation de sel est bonne car elle empêche les attaques provenant de attaques par dictionnaire ou des tables arc-en-ciel. L'importance d'un sel est qu'il doit être unique pour chaque mot de passe. Vous pouvez utiliser un format tel que [sel 128 bits][hachage 512 bits du mot de passe] pour stocker les mots de passe hachés.

La seule façon viable d'attaquer est de calculer des hachages pour différentes possibilités de mot de passe et de trouver finalement le bon en faisant correspondre les hachages.

Pour donner une idée du nombre de hachages qui peuvent être effectués en une seconde, je pense que le bitcoin est un bon exemple. Bitcoin utilise SHA256 et, pour faire court, plus vous générez de hachages, plus vous obtenez de bitcoins (que vous pouvez échanger contre de l'argent réel). Les gens sont donc motivés pour utiliser les GPU à cette fin. Vous pouvez voir dans l'aperçu du matériel qu'une carte graphique moyenne qui ne coûte que 150 dollars peut calculer plus de 200 millions de hachages/s. Plus votre mot de passe est long et complexe, plus le temps de calcul sera long. En calculant à 200M/s, pour essayer toutes les possibilités pour un alphanumérique de 8 caractères (majuscules, minuscules, chiffres), cela prendra environ 300 heures. Le temps réel sera très probablement inférieur si le mot de passe est quelque chose d'éligible ou un mot anglais commun.

Comme c'est le cas pour tout ce qui concerne la sécurité, il faut l'examiner dans son contexte. Quelle est la motivation de l'attaquant ? Quel est le type d'application ? Le fait de disposer d'un hachage avec un sel aléatoire pour chacun d'entre eux offre une assez bonne protection contre les cas où des milliers de mots de passe sont compromis.

Une chose que vous pouvez faire est d'ajouter une protection supplémentaire contre la force brute en ralentissement de la procédure de hachage. Comme vous ne hacherez les mots de passe qu'une seule fois, et que l'attaquant devra le faire plusieurs fois, cela joue en votre faveur. La méthode typique consiste à prendre une valeur, à la hacher, à prendre la sortie, à la hacher à nouveau et ainsi de suite pour un nombre fixe d'itérations. Vous pouvez essayer quelque chose comme 1 000 ou 10 000 itérations par exemple. L'attaquant aura ainsi beaucoup plus de mal à trouver chaque mot de passe.

Answer 4

Et si j'avais un moyen de mélanger le sel avec le mot de passe d'une manière qui fasse du mot de passe la clé pour trouver le sel avant qu'un attaquant puisse commencer à faire quelque chose avec le mot de passe haché ?

Dans la fonction hash_password, le mot de passe sera haché de manière conventionnelle, puis le sel sera mélangé à la chaîne de mots de passe salée en fonction des valeurs numériques des caractères et de la somme de tous les caractères numériques. Bien sûr, le sel est généré de manière aléatoire.

La fonction compare_password utilisera le mot de passe pour inverser ce processus, ce qui donnera le sel utilisé pour hacher le mot de passe en premier lieu. Avec le sel trouvé, le mot de passe peut être comparé avec le mot de passe salé.

cette idée devrait rendre très difficile la recherche du sel pour générer la rainbow table. en gros : si vous avez le mot de passe, vous pouvez déverrouiller et entrer, si vous n'avez pas le mot de passe, la chaîne de mots de passe hachée est complètement inutile puisque vous ne connaissez pas le sel (qui est aussi aléatoire).

Bien sûr, si quelqu'un avait accès à votre base de données ET à votre code source, ce processus serait inutile, mais pourrait ajouter un poids supplémentaire.

J'espère apprendre ce que vous pensez !

function hash_password($password, $salt = null) {
if (is_null($salt)) {
    $hash = "";
    $count = mt_rand(1, 100);
    for ($i = 0; $i < $count; $i++) {
        $hash .= substr(crypt(mt_rand(1, 9999999999)), 0, mt_rand(0, 13));
    }
    $salt = crypt($hash, '$2a$10$' . $hash . '$');
}
$saltedPassword = crypt($password, '$2a$10$' . $salt . '$');
$sumord = strlen($password);
$sumnr = 1;
while (true) {
    if (strlen($salt) <= 0)
        break;
    for ($i = 0; $i < strlen($password); $i++) {
        if (strlen($salt) <= 0)
            break;
        $ord = ord($password[$i]);
        $sumord += $ord;
        if (ctype_digit($password[$i]))
            $sumnr += $password[$i];
        $key = $sumnr * $sumord;
        $position = $key % 60;
        $group = ($sumord % 2) ? 3 : 2;
        if (strlen($salt) < $group)
            $group = strlen($salt);
        if ($key % 2) {
            $saltedPassword = substr($saltedPassword, 0, $position) . substr($salt, 0, $group) . substr($saltedPassword, $position);
            $salt = substr($salt, $group, strlen($salt));
        } else {
            $saltedPassword1 = substr($saltedPassword, 0, strlen($saltedPassword) - $position);
            $saltedPassword = $saltedPassword1 . substr($salt, strlen($salt) - $group, strlen($salt)) . substr($saltedPassword, strlen($saltedPassword1));
            $salt = substr($salt, 0, strlen($salt) - $group);
        }
    }
}
return $saltedPassword;
}

function compare_password($password, $saltedPassword) {
$sumord = strlen($password);
$sumnr = 1;
$decoders = array();
$salt = 60;
while (true) {
    if ($salt <= 0)
        break;
    for ($i = 0; $i < strlen($password); $i++) {
        if ($salt <= 0)
            break;
        $ord = ord($password[$i]);
        $sumord += $ord;
        if (ctype_digit($password[$i]))
            $sumnr += $password[$i];
        $key = $sumnr * $sumord;
        $position = $key % 60;
        $group = ($sumord % 2) ? 3 : 2;
        if ($salt < $group)
            $group = strlen($salt);
        $decoders[] = array("ord" => $ord, "sumord" => $sumord, "sumnr" => $sumnr, "group" => $group, "key" => $key);
        $salt = $salt - $group;
    }
}
$decoders = array_reverse($decoders);
$salt = "";
$unsaltedPassword = $saltedPassword;
foreach ($decoders as $decoder) {
    if (strlen($salt) >= 60)
        break;
    $position = $decoder['key'] % 60;
    if ($decoder['key'] % 2) {
        $salt = substr($unsaltedPassword, $position, $decoder['group']) . $salt;
        $unsaltedPassword = substr($unsaltedPassword, 0, $position) . substr($unsaltedPassword, $position + $decoder['group']);
    } else {
        $salt .= substr($unsaltedPassword, strlen($unsaltedPassword) - ($position + $decoder['group']), $decoder['group']);
        $unsaltedPassword = substr($unsaltedPassword, 0, strlen($unsaltedPassword) - ($position + $decoder['group'])) . substr($unsaltedPassword, (strlen($unsaltedPassword) - $position));
    }
}
return $saltedPassword == hash_password($password, $salt);
}

Answer 5

Je suis pratiquement sûr qu'un sel unique pour chaque hachage/mot de passe est la méthode la plus sûre.

Je suis allé plus loin le sel est un UDID qui est stocké, crypté par un autre UDID secret.

De plus, le hachage est effectué avec un nombre d'itérations aléatoire compris entre 50 000 et 100 000.

Le hachage et le sel sont également inversés x nombre d'itérations.

Le nombre d'itérations est également stocké crypté par l'UDID secret.

Je pense avoir raison en disant que c'est une méthode sûre et rapide.

Il y aurait d'autres vulnérabilités à craindre à ce stade.