[Erylanor]

Salut les cocos,

(rappel : une fonction de hachage est une fonction qui transforme un message de taille quelconque en un message de taille fixe. Le principe est qu'il est facile de fabriquer le hash d'une donnée, mais il est très difficile de reconstruire le message à partir du hash)

Le Sha-1 a fait son temps car tout comme le MD5, cette fonction de hachage n'est plus sécurisée. Le Sha-1 est une fonction de hachage cryptographique de la NSA sur 160 bits, et depuis déjà quelques années, on remettait en cause la fiabilité de cette fonction. Le 23 février 2017, google à annoncé avoir trouvé une collision (c'est-à dire deux données ont le même résultat par la fonction de hachage).
Les conséquences sont que le Sha-1 va être progressivement remplacé par d'autres fonctions plus sécurisées, comme le Sha-2 ou Sha-3 (très originaux comme noms). En outre, chrome n'accepte plus les certificats Sha-1 et firefox a prévu de les arrêter fin 2017.

Pourquoi c'est pas bien une collision ?
Parce que l'on peut faire des attaques en partant d'une collision. Un exemple sera plus parlant qu'un long discours :
M crée deux documents d1 et d2 ayant le même hash (c'est une collision). M envoie le document d1 à A, qui accepte et signe le hash et envoie la signature à M. M attache la signature de d1 à d2, et envoie le d2 à B. B croit alors que A a signé le document, alors que ce n'est pas vrai.

Il y a un exemple de deux pdf ayant le même Sha-1 mais étant différents : https://shattered.it

Tchüs,
Ryl

[harvey]

J'aurais bien dit "le petit sha est mort", mais la vanne a été faite 12 000 fois depuis 2005...

[lovenunu]

google à annoncé avoir trouvé une collision

Je me trompe surement (je suis pas très fort en hash), mais si on essaye d'obtenir tous les sha-1 (donc des nombres de 160 bits) de toutes les valeurs possibles de 168 bits, il y aura obligatoirement des valeurs avec les mêmes signature non ?

La "force" d'un algo de hash n'est-il pas la difficulté de calculer une valeur possible à partir d'un hash ?

[pixis]

Du coup il suffit de calculer le condensat de toutes les valeurs possibles de 160 bits + une valeur.

Je rappelle seulement que ça fait la bagatelle de 10^48 condensats à calculer, soit mille milliards de milliards de milliards de milliards de milliards de valeurs. Alors oui, il "suffit" de tous les calculer. Mais c'est là que le bât blesse, ça prend du temps... 

Ensuite, un bon algo de hachage est un algo qui a le moins de collisions possible (tout en cherchant à avoir une emprunte la plus petite possible), qui doit être le plus homogène possible, et qui produit une emprunte complètement différente lorsqu'un seul bit est changé en entrée. Le but étant de minimiser le risque de collision, ainsi que rendre la recherche de collisions difficile.

Donc la "force" d'un algo de hachage, c'est de rendre la recherche de collision difficile, de ce que j'ai compris (et lu)

[harvey]

google à annoncé avoir trouvé une collision

Je me trompe surement (je suis pas très fort en hash), mais si on essaye d'obtenir tous les sha-1 (donc des nombres de 160 bits) de toutes les valeurs possibles de 168 bits, il y aura obligatoirement des valeurs avec les mêmes signature non ?

La "force" d'un algo de hash n'est-il pas l'impossibilité de calculer une valeur possible à partir d'un hash ?

En fait, il y a une très bonne probabilité d'obtenir une collision avec 2^80 hashes environ (et en général avec 2^(N/2) pour un espace de 2^N). C'est un compromis temps-mémoire, l'inconvénient par rapport au brute-force est qu'il faut aussi stocker environ 2^80 hashes en mémoire. Voir "attaque des anniversaires".
Ce qui est intéressant, c'est la comparaison entre l'efficacité de l'attaque et celle des anniversaires, qui fonctionne avec n'importe quelle fonction. SHAttered utilise 2^63 calculs de sha1, soit "seulement" 2^17 fois moins que l'attaque théorique. Si la puissance globale des ordinateurs continue d'augmenter, il se peut en effet que l'attaque des anniversaires devienne praticable pour sha1 (raison pour laquelle les fonctions plus récentes ont un espace plus grand).


La nécessité d'avoir une fonction de hachage résistante aux collisions dépend du cadre dans lequel on l'utilise. Quand il s'agit d'authentifier des données, c'est très important. Cf. https://fr.wikipedia.org/wiki/R%C3%A9sistance_aux_collisions , notamment:

dans certains systèmes de signature numérique, une autorité atteste de l'authenticité d'un document en publiant une signature à clé publique sur une valeur de hachage du document ; s'il est possible de produire deux documents avec la même valeur de hachage, un attaquant pourrait obtenir d'une autorité une attestation d'authenticité sur un document, et ensuite prétendre que l'autorité a attesté de l'authenticité d'un autre document

Certaines attaques informatiques requièrent une collision. On fait authentifier un "bon" document, puis on utilise un document malicieux avec la même signature en le faisant passer pour le premier (c'est ce qu'explique Erylanor).

[Erylanor]

En fait, il y a une très bonne probabilité d'obtenir une collision avec 2^80 hashes environ (et en général avec 2^(N/2) pour un espace de 2^N). C'est un compromis temps-mémoire, l'inconvénient par rapport au brute-force est qu'il faut aussi stocker environ 2^80 hashes en mémoire. Voir "attaque des anniversaires".

Pour continuer sur cette lancée, je dirais qu'on parle d'attaque sur une fonction de hashage (hachage ?) dès que l'on a moyen de trouver une collision en moins que 2^(n/2) (l'attaque la plus naïve). Par exemple, sur le Sha-1, Wang Xiaoyun (après avoir trouvé une collision sur le Sha-0) avait trouvé en 2005 une attaque en 2^68. C'est beaucoup mieux que le 2^80 (=2^(n/2)), mais c'est compliqué à mettre en pratique (surtout avec la puissance de calcul de 2005), mais ça explique que le Sha-1 était déjà à l'agonie même si on avait pas trouvé de collision.
Mais en effet, avec SHAttered en 2^63, on a fini par trouver une collision.

De manière générale, l'utopie d'une fonction de hachage est qu'il n'y ait pas d'attaque plus efficace que celle des anniversaires (2^(n/2)).

[lovenunu]

En fait, il y a une très bonne probabilité d'obtenir une collision avec 2^80 hashes environ (et en général avec 2^(N/2) pour un espace de 2^N). C'est un compromis temps-mémoire, l'inconvénient par rapport au brute-force est qu'il faut aussi stocker environ 2^80 hashes en mémoire. Voir "attaque des anniversaires".
Ce qui est intéressant, c'est la comparaison entre l'efficacité de l'attaque et celle des anniversaires, qui fonctionne avec n'importe quelle fonction. SHAttered utilise 2^63 calculs de sha1, soit "seulement" 2^17 fois moins que l'attaque théorique. Si la puissance globale des ordinateurs continue d'augmenter, il se peut en effet que l'attaque des anniversaires devienne praticable pour sha1 (raison pour laquelle les fonctions plus récentes ont un espace plus grand).

Merci harvey pour ton explication, je ne connaissais pas l'attaque des anniversaires , mais du coup ce qui vient de se passer pour sha-1 devient plus clair.

De manière générale, l'utopie d'une fonction de hachage est qu'il n'y ait pas d'attaque plus efficace que celle des anniversaires (2^(n/2)).

Bon bah, au boulot

[Erylanor]

Tiens ça pourrait être cool de faire une épreuve (genre S03ncryp710n) avec le code d'une fonction de hashage en clair et où il faudrait trouver une collision (avec une attaque) pour valider.

EDIT : il faudrait peut-être que je regarde les épreuves de prog avant

[lovenunu]

Tiens ça pourrait être cool de faire une épreuve (genre S03ncryp710n) avec le code d'une fonction de hashage en clair et où il faudrait trouver une collision (avec une attaque) pour valider.

C'est marrant je crois qu'il existe déjà ce chall, mais pas en crypto :p

[harvey]

Il y a ThunderHash sur w3challs qui utilise ce principe (source).
Mais sur NC, je ne vois pas. Tu nous la ferais ?

[Stockage]

Il y a également Collision sur Pwnable qui part de la même idée.
+1 pour ce type d'épreuve sur NC, ça pourrait être fun

[the lsd]

Faut pas hésiter hein les gars

Enjoy

The lsd