The SHAttered attack is 100,000 faster than the brute force attack that relies on the birthday paradox.
Je n'ai d'abord pas compris comment il était possible de réussir en n'étant que 100000 fois plus rapide.
Un SHA1 a une longueur de 160 bits. Avec le paradoxe des anniversaires, on peut espérer en force brute trouver une collision en à peu près 280 hashes (une bonne approximation est de prendre la racine carrée du nombre de possibilités). Donc ça revient à tester toutes les combinaisons d'une variable de 80 bits. Infaisable.
Mais même 100000 fois plus rapide, ça ne fait gagner que ~17 bits (ln(100000)/ln(2)) :
$ echo'l(100000)/l(2)'| bc -l
16.60964047443681173951
Donc ça fait quand même plus de 263. C'est toujours infaisable.
Mais ils précisent :
This attack required over 9,223,372,036,854,775,808 SHA1 computations.
Ce nombre est exactement 263.
Donc ils ont calculé presque 264 hashes. C'est dingue, je pensais qu'il était matériellement impossible de calculer n'importe quelle fonction pour toutes les valeurs possibles d'une variable de 64 bits.
Je vais donc revoir mes règles de pouce approximant la frontière entre le possible et l'impossible à la hausse.
PS : comment écrire 264 en markdown sur linuxfr sans manger l'espace ou mettre en exposant le caractère qui suit ?
Voici ce que j'ai essayé :
2^64. donne 264.
2^64^. donne 264.
2^{64}^. donne 2{64}.
2^64 hashes. donne 264 hashes.
2^64 h. donne 264 h. ← ça fonctionne, mais ce n'est pas ce que je veux écrire.
...
EDIT : Pour 2^64 hashes., le problème ne se produit que lors de la prévisualisation, une fois posté, ça fonctionne ;-)
Il y a d'autres différences entre la prévisualisation et la version postée, par exemple 2^{64}^..
# Every single 64 bits possible value...
Posté par ®om (site web personnel) . En réponse au journal Et paf, le SHA-1 !. Évalué à 10. Dernière modification le 23 février 2017 à 23:19.
http://shattered.io/
Je n'ai d'abord pas compris comment il était possible de réussir en n'étant que 100000 fois plus rapide.
Un SHA1 a une longueur de 160 bits. Avec le paradoxe des anniversaires, on peut espérer en force brute trouver une collision en à peu près 280 hashes (une bonne approximation est de prendre la racine carrée du nombre de possibilités). Donc ça revient à tester toutes les combinaisons d'une variable de 80 bits. Infaisable.
Mais même 100000 fois plus rapide, ça ne fait gagner que ~17 bits (ln(100000)/ln(2)) :
Donc ça fait quand même plus de 263. C'est toujours infaisable.
Mais ils précisent :
Ce nombre est exactement 263.
Donc ils ont calculé presque 264 hashes. C'est dingue, je pensais qu'il était matériellement impossible de calculer n'importe quelle fonction pour toutes les valeurs possibles d'une variable de 64 bits.
Je vais donc revoir mes règles de pouce approximant la frontière entre le possible et l'impossible à la hausse.
PS : comment écrire 264 en markdown sur linuxfr sans manger l'espace ou mettre en exposant le caractère qui suit ?
Voici ce que j'ai essayé :
2^64.donne 264.2^64^.donne 264.2^{64}^.donne 2{64}.2^64 hashes.donne 264 hashes.2^64 h.donne 264 h. ← ça fonctionne, mais ce n'est pas ce que je veux écrire.EDIT : Pour
2^64 hashes., le problème ne se produit que lors de la prévisualisation, une fois posté, ça fonctionne ;-)Il y a d'autres différences entre la prévisualisation et la version postée, par exemple
2^{64}^..blog.rom1v.com