y a-t-il un moyen d'inverser un hachage sans tables arc-en-ciel? [dupliquer]

possibilité de dupliquer:

md5 décodé. Comment ils le font?

cette page suggère qu'un algorithme de hachage comme md5() et sha1() peut être inversé à cause de l'énorme puissance de traitement que nous avons aujourd'hui. À ce moment-là, je pensais que ce n'était possible qu'avec des tables arc-en-ciel. Avais-je tort?

dans les tableaux Arc-En-Ciel est-ce la seule façon d'y aller, comment quelqu'un pourrait inverser un hash qui a été fait avec un sel?

6
demandé sur Community 2011-09-23 06:22:37

6 réponses

Eh bien, cette question en général est un double de cette Question . Cependant, pour répondre à vos questions exactes:

à ce point je pensais que c'était seulement possible avec des Tables arc-en-ciel. Avais-je tort?

Techniquement, oui, vous avez tort. Aucune fonction de hachage n'est irrécouvrable, étant donné la puissance de traitement suffisante. Le point clé, c'est la puissance de traitement qu'il faut, ce qui dans la plupart des cas est loin en plus que vous pouvez imaginer. La raison en est que le nombre de valeurs possibles augmente exponentiellement à chaque étape du cycle de hachage. Pour MD5, chaque étape (il y en a 64) multiplierait le nombre de possibilités par 10^77 (beaucoup de zéros). Donc, pour inverser avec succès un MD5, vous devez essayer un vraiment grand nombre de permutations possibles (un calcul de retour-de-l'enveloppe montre quelque part sur l'ordre de 10^4932 essais). Avec le super ordinateur le plus rapide de tous les temps créé aujourd'hui (environ 8 petaflops, ou 8x10^15 opérations à virgule flottante par seconde), vous regardez environ 10^4908 années pour l'Inverser. Ce qui est d'ailleurs 2.5x10^4898 fois l'âge de l'univers en ce moment. Vraiment, c'est un nombre énorme qui est au-delà de notre capacité humaine à comprendre...

et c'est la meilleure situation possible.

donc techniquement il est possible de revenir en arrière. Mais pratiquement, il n'est pas.

dans le cas où les tables arc-en-ciel est la seule façon d'aller, comment quelqu'un pourrait inverser un hash qui a été faite avec un sel?

la chose est que personne a besoin pour l'Inverser. Ils ont juste besoin de trouver une collision. Fondamentalement, une collision est deux entrées qui conduisent à la même sortie. Donc si hash(a) = x et hash(b) = x , a et b sont les collisions de chacun d'autres. Donc, tout ce que nous avons à faire est de trouver une collision (qui le croit ou non est plus facile que de trouver l'entrée exacte, puisqu'il y a techniquement un nombre infini d'entrées qui peuvent donner une sortie particulière). Avec l'entrée de la taille des mots de passe, typiquement la collision est le mot de passe original.

la façon la plus facile de trouver cette collision est avec une liste précomputée de hash (généralement appelé une table arc-en-ciel). Fondamentalement, tout ce que vous devez faire est alors regarder le hachage de la table pour voir si l'original est là. Si oui, vous êtes fait (facile).

Les sels

sont généralement ajoutés pour combattre les tables arc-en-ciel. C'est parce que si l'utilisateur entre 1234 comme mot de passe, et vous utilisez abcdefghijklmnop comme sel, l'original serait 1234abcdefgjhijklmnop , qui est beaucoup moins susceptible d'apparaître dans une table arc-en-ciel. Ainsi l'ajout d'un sel fort protégera contre précalculé tables arc-en-ciel.

Force Brute

cependant, il y a une préoccupation importante si vous faites simplement hash(pass + salt) . Il n'est pas sensible aux tables arc-en-ciel prédéfinies, mais il est sensible au forçage Brutal. La raison en est que les fonctions de hachage cryptographique (comme sha1, md5, sha256, etc.) sont conçues pour être rapides. Leur rôle traditionnel est en Signature , donc ils ont besoin d'être rapide pour être utile. Toutefois, dans le mot de passe de stockage c'est la faiblesse. Avec les GPU modernes, un attaquant pourrait forcer (juste essayer chaque permutation de mot de passe possible) un simple hachage avec du sel en quelques heures (pour plus de détails, voir mon post de blog à ce sujet)...

La meilleure prévention

La meilleure prévention a deux caractéristiques:

  1. il n'est pas facile de pré-calculer un tableau de valeurs (un arc-en-ciel de la table)

  2. ce n'est pas rapide de hacher une seule valeur (pas facile de forcer).

il s'avère qu'il y a une façon simple de le faire en utilisant une fonction de hachage. Il suffit d'itérer sur elle et de faire la sortie dépend d'un grand nombre de fonctions de hachage: 

var result = password + salt;
for (var i = 0; i < 10000000; i++) {
    result = hash(result + salt);
}

la clé est qu'en le rendant artificiellement lent et en utilisant un sel, vous le rendez résistant à la précomputation et au forçage Brutal.

comme il s'avère, il ya 2 algorithmes standard qui le font (bien, utiliser les principes).

le meilleur est Blowfish hash (bcrypt) qui n'utilise pas vraiment une fonction primitive de hachage, mais utilise le cycle de dérivation clé du chiffre de Blowfish. Il est disponible en PHP via crypt() . Pour l'utiliser: 

$hash = crypt($password, 'a$' . $salt . '$');

et de le vérifier avec 

$hash == crypt($password, $hash);

l'autre méthode (qui est légèrement moins préférée) est PBKDF2 . Pour le programmer en PHP: 

function pbkdf2($hashFunc, $password, $salt, $iterations, $length = 32) {
    $size   = strlen(hash($hashFunc, '', true));
    $len    = ceil($length / $size);
    $result = '';
    for ($i = 1; $i <= $len; $i++) {
        $tmp = hash_hmac($hashFunc, $salt . pack('N', $i), $password, true);
        $res = $tmp;
        for ($j = 1; $j < $iterations; $j++) {
            $tmp  = hash_hmac($hashFunc, $tmp, $password, true);
            $res ^= $tmp;
        }
        $result .= $res;
    }
    return substr($result, 0, $length);
}

Note:

aucun de ceux-ci ne protégera un utilisateur contre un très mot de passe faible. S'ils entrent un mot du dictionnaire, ou un mot de passe commun, il est encore probable qu'un attaquant sera en mesure de le craquer. Ils ajouteront toutefois à la défense contre les mots de passe de force modérée...

un peu plus de lecture:

15
répondu ircmaxell 2017-05-23 12:32:23

une table arc-en-ciel est" juste " une grande table de valeurs de hash précomputées avec une certaine ruse pour stocker seulement une petite partie de la table et encore être en mesure de rechercher toutes les valeurs. En détail, une table arc-en-ciel qui peut "inverser" N valeurs possibles (i.e. il ya N hash sorties pour lesquelles la table donnera une entrée correspondante) prend du temps environ 1.7*n pour construire -- donc la construction de la table est en fait plus lent que" juste "essayer le N entrées et voir si on correspond à la sortie de hachage donnée. L'avantage de la table est quand vous avez plusieurs sorties de hachage pour lesquelles vous voulez trouver une entrée correspondante.

2
répondu Thomas Pornin 2011-09-24 01:49:41

peut-être pourriez-vous utiliser l'attaque suivante, en adoptant, la technique utilisée pour faire le hachage est un simple calcul.

par exemple, si le calcul est effectué avec un hachage modulaire en 100, nous avons:

exemple d'entrée: Huit milliard trois cent soixante dix neuf million cinq cent quarante sept mille trois cent soixante dix huit Sortie de hachage: 78

une formule générale pour la valeur de hachage 78 serait 78 +100*k (K appartenant à des entiers). Ainsi, on pourrait essayer toutes les séquences possibles. Notez que cela réduit la recherche espace de 100% à 1% dans ce cas, le module 100. S'il était possible d'établir un pressentiment que ce nombre était de 10 chiffres, nous pourrions rendre la recherche encore plus réduit de 78 +100 k (10^7<=k< 10^8).

une autre façon serait de peupler une base de données avec un certain nombre de vraiment grand de hashs et leurs entrées, puis la recherche dans cette base de données.

j'espère avoir aidé un peu.

2
répondu GarouDan 2011-10-05 19:02:44

techniquement, aucun algorithme de hachage standard n'est réversible! ainsi, une fois que vous obtenez le hachage d'un message, il ne devrait y avoir aucun moyen d'obtenir le message original hors de sa chaîne de hachage. La seule façon pour les gens de la craquer, c'est d'utiliser la force brute. La force brutale est la chose la plus stupide que vous pouvez faire, en essayant toutes les clés possibles! Cela explique pourquoi l'une des caractéristiques d'un algorithme cryptographique sécurisé est d'avoir un grand espace de clé. Mais si vous utilisez le processus, dans certains cas, il peut être pratique, c'est quoi exactement arc-en-ciel les tableaux.

une table arc-en-ciel est une table prédéfinie pour toutes les combinaisons possibles jusqu'à une certaine longueur. Cela signifie que vous créez toutes les combinaisons possibles de caractères (majuscules et minuscules), nombres et caractères spéciaux jusqu'à une certaine longueur. Pour autant que je sache, la table arc-en-ciel la plus complète peut briser le hachage des chaînes jusqu'à 10 caractères qui comprennent des nombres, des majuscules et des caractères spéciaux, donc si vous avez une chaîne plus longue que qu'il ne devrait pas y avoir de problème de sécurité à briser le hachage lui-même. comme vous pouvez voir ici la taille de la table qui peut casser Vista mots de passe jusqu'à 8 caractères est plus de 100 Go et ce nombre augmente de façon exponentielle ce qui rend un peu impossible d'aller plus loin que 10 ou 12 caractères.

tant que votre chaîne n'est pas facile à deviner, assez longue et qu'elle contient des lettres majuscules, des chiffres et des caractères spéciaux, il n'y a pas lieu de s'inquiéter :)

1
répondu Tohid 2011-10-07 18:13:33

premièrement, en général, il n'est pas possible d ' "inverser" une fonction de hachage cryptographique. En effet, ces fonctions prennent généralement beaucoup plus de données d'entrée qu'elles n'en produisent.

par exemple, MD5 prend 512 bits d'entrée (64 octets) et produit 128 bits de sortie (16 octets). Ainsi, il n'est tout simplement pas assez d'informations dans l'entrée de reconstruire la sortie. En fait, il y aura environ 2^384 (un vraiment grand nombre) d'entrées différentes qui ont exactement le même résultat de hachage.

au lieu de cela les cryptographes parlent de trois différents types d'attaques sur les hachures:

  • première preimage attaque: étant donné une valeur de hachage h, trouver tout message m tel que hash(m) = h
  • deuxième preimage attaque: étant donné un message fixe m1, trouver un autre message m2 tels que hash(m1) = hash(m2)
  • collision attack: trouver deux messages m1 et m2 tels que hash (m1) = hash (m2)

maintenant de retour à cette activité" inversée". Lorsque vous voulez "casser un mot de passe MD5", ce que vous voulez vraiment faire est une première attaque de préimage: trouver n'importe quel "mot de passe" M tel que hash(m) correspond hash stocké H. En temps normal, cela prendrait de l'ordre de 2^128 suppositions à faire par la force brute (plus que tous les ordinateurs sur terre pourraient gérer en un siècle). Il existe des faiblesses connues dans le MD5 qui apportent ceci: jusqu'à ~2^123, ce qui est encore trop difficile pour être pratique.

mais parce que les mots de passe sont généralement des chaînes courtes de lettres et de nombres, il ya beaucoup moins de 2^128 mots de passe que les gens sont en fait probable à utiliser. Il y en a plus de 2^40 (soit environ un trillion). C'est encore beaucoup, mais pas tellement qu'il est impossible de tous les essayer si vous avez un an ou un peu ou beaucoup de PS3. Mais si tu savais que tu voulais casser un tas de mots de passe? Plutôt que de faire 2^40 conjectures à chaque fois, vous pouvez stocker les hachures de tous les mots de passe probables sur le disque pour une utilisation future. C'est (plus ou moins) ce qu'est une table arc-en-ciel: quelqu'un a déjà fait tout le travail de sorte que vous venez de chercher la réponse et sauter la plupart du travail.

vous avez raison. Maintenant vous êtes de retour à 2^40 conjectures et votre chambre pleine de PS3s à nouveau. Utiliser une meilleure fonction de hachage (comme SHA512 ou SKEIN) ne change pas vraiment cela parce qu'il ne change pas le nombre de mots de passe probables que vous devez essayer. Leçon: vous devez utiliser un mot de passe très difficile à deviner!

Ok, mais est-ce que MD5 et SHA1 ne sont pas encore considérés comme cassés? Oui, mais pas d'une manière qui importe vraiment ici (encore). Les nouvelles passionnantes dans ce domaine a été tout au sujet collision attacks , qui sont pertinents pour briser des parties de la sécurité SSL et des signatures numériques, mais ne sont pas pertinents pour briser les mots de passe stockés. Les cryptographes attendent ce travail pour conduire à des attaques encore mieux avant longtemps, donc ce n'est probablement pas une bonne idée d'utiliser MD5 ou SHA1 dans de nouveaux programmes, mais les programmes qui utilisent MD5/SHA1 + salting approprié pour le stockage de mot de passe sont encore très bien.

1
répondu mpm 2011-10-08 02:34:05

la force brute dont parle cette page est essentiellement la génération d'une table arc-en-ciel à la volée.

0
répondu Ignacio Vazquez-Abrams 2011-09-23 02:24:34