Est-il possible d'obtenir le même sha1 hash? [dupliquer]

ce que vous décrivez s'appelle une collision . Les Collisions existent nécessairement, puisque SHA-1 Accepte beaucoup plus de messages distincts comme entrées qu'elle peut produire des sorties distinctes (SHA-1 peut manger n'importe quelle chaîne de bits jusqu'à 2^64 bits, mais ne produit que 160 bits; ainsi, au moins une valeur de sortie doit apparaître plusieurs fois). Cette observation est valable pour toute fonction avec une sortie plus petite que son entrée, que la fonction soit une "bonne" fonction de hachage ou non.

supposant que SHA-1 se comporte comme un "oracle aléatoire" (un objet conceptuel qui retourne essentiellement des valeurs aléatoires, avec la seule restriction qu'une fois qu'il a retourné la sortie v sur l'entrée m , il doit toujours par la suite retourner v sur l'entrée m ), puis la probabilité de collision, pour deux chaînes distinctes S1 et S2, devrait être 2^(-160). Toujours dans L'hypothèse de SHA-1 se comportant comme un oracle aléatoire, si vous collectez beaucoup de chaînes de saisie, alors vous commencerez à observer des collisions après avoir collecté environ 2^80 chaînes de ce type.

(C'est-à-dire 2^80 et non 2^160 parce que, avec 2^80 cordes vous pouvez faire environ 2^159 paires de cordes. Cela est souvent appelé le "paradoxe de l'anniversaire" parce qu'il vient comme une surprise pour la plupart des gens lorsqu'il est appliqué à des collisions le jour de l'anniversaire. Voir la page Wikipedia sur le sujet.)

maintenant, nous soupçonnons fortement que SHA-1 ne pas se comportent vraiment comme un oracle aléatoire, parce que l'approche de paradoxe d'anniversaire est l'algorithme de recherche de collision optimale pour un oracle aléatoire. Pourtant, il existe une attaque publiée qui devrait trouver une collision en environ 2^63 pas, donc 2^17 = 131072 fois plus rapide que l'algorithme de paradoxe d'anniversaire. Une telle attaque ne doit pas être faisable sur un véritable oracle aléatoire. Attention, cette attaque n'a pas été réellement terminée, il reste théorique (certaines personnes essayé, mais apparemment ne pouvait pas trouver assez de puissance CPU ) ( mise à jour: au début de 2017, quelqu'un fait calculer une collision SHA-1 avec la méthode mentionnée ci-dessus, et il a fonctionné exactement comme prévu). Pourtant, la théorie semble solide et il semble vraiment que SHA-1 n'est pas un oracle aléatoire. En conséquence, en ce qui concerne la probabilité de collision, tous les paris sont ouverts.

comme pour votre troisième question: pour une fonction avec une sortie n bit, alors il y a nécessairement des collisions si vous pouvez entrer plus de 2^ n messages distincts, c.-à-d. si la longueur maximale du message d'entrée est supérieure à n . Avec une limite m inférieure à n , la réponse n'est pas aussi facile. Si la fonction se comporte comme un oracle aléatoire, alors la probabilité de l' l'existence d'une collision diminue avec m , et non pas de façon linéaire, mais plutôt avec une coupure abrupte autour de m=n/2 . C'est la même analyse que le paradoxe d'anniversaire. Avec SHA-1, cela signifie que si m < 80 alors les chances sont qu'il n'y a pas de collision, tandis que m > 80 rend l'existence d'au moins une collision très probable (avec m > 160 cela devient une certitude).

Notez qu'il y a une différence entre "il existe une collision" et "vous trouverez une collision". Même si une collision doit exister, vous avez toujours votre 2^(-160) probabilité chaque fois que vous essayez. Ce que le paragraphe précédent signifie est qu'une telle probabilité est plutôt insignifiante si vous ne pouvez pas (conceptuellement) essayer 2^160 paires de chaînes, par exemple parce que vous vous limitez à des chaînes de moins de 80 bits.