MD5 compromis ?

Guillaume Gielly wrote in message
<4123ae85$0$20690$626a14ce@news.free.fr>:

Si j'ai bien compris, ils ont réussi à trouver input2 telle que
md5(input1) == md5(input2) == hash.

En effet. Plus exactement :

cigaes@aimlin ~ $ recode base64..data <<EOF | md5sum
0THdAsXm7sRpPZoGmK/5XC/KtYcSRn6rQARYPrj7f4lVrTQGCfSzAoPkiIMlcUFaCFEl6PfNyZ/Z
Hb3ygDc8W5YLHdHcQXuc5NiX9FplVdU1c5rH8Ov9DDAp8WbRCbGPdSd/eTDVXOsi6K26ecwVXO10
y91fxdNtsZsK2DXMp+M EOF
a4c0d35c95a63a805915367dcfe6b751 -
cigaes@aimlin ~ $ recode base64..data <<EOF | md5sum
0THdAsXm7sRpPZoGmK/5XC/KtQcSRn6rQARYPrj7f4lVrTQGCfSzAoPkiIMl8UFaCFEl6PfNyZ/Z
Hb1ygDc8W5YLHdHcQXuc5NiX9FplVdU1c5pH8Ov9DDAp8WbRCbGPdSd/eTDVXOsi6K26eUwVXO10
y91fxdNtsZsKWDXMp+M EOF
a4c0d35c95a63a805915367dcfe6b751 -

(pour ceux qui ne parlent pas le shell couramment : les deux données
écrites en base64 entre la ligne de commande et la ligne EOF ont le
même MD5 a4c0d35c95a63a805915367dcfe6b751.

Maintenant si input1 doit avoir une forme spécifique ou que input2 se
dérive de input1 facile, les conséquences sont minimes, non ?

À ce que des cryptographes disent, beaucoup de protocoles ne subissent
pas d'impact à cause de ça. En particulier, _a priori_, pas de souci
pour TLS, ni pour PGP. Cependant, des propriétés de MD5 font que cette
attaque est généralisable. À voir au cas par cas.

https://www.devnullteam.org/~pmz/sha-collision.txt


Si j'ai bien compris, ils ont réussi à trouver input2 telle que
md5(input1) == md5(input2) == hash.
En fait, ils ont choisi eux-mêmes input1 et input2 en toute liberté. C'est

encore plus simple (hum, hum ! )

Maintenant si input1 doit avoir une forme spécifique ou que input2 se
dérive de input1 facile, les conséquences sont minimes, non ?
J'ai aussi l'impression que c'est une attaque assez faible. Mais ce qui

compte le plus pour moi c'est que c'est un premier coup de canif à la
fonction de hash. Donc elle commence à sentir le souffre. Elle reste
gentille, mais je ne lui confierait plus mes enfants ;)

Grindipo

Le Wed, 18 Aug 2004 21:17:06 +0000, Guillaume Gielly a écrit :

https://www.devnullteam.org/~pmz/sha-collision.txt

On notera pour ceux qui on du mal à lire que ce papier parle de collision
dans SHA-0, pas dans MD5. Celui qui parle de collision dans MD5, c'est
celui-ci :

http://eprint.iacr.org/2004/199.pdf

Voir un thread très récent de fr.misc.cryptologie pour plus de détails.


--

pour commencer la mandrake est pas male du tout
De là à dire que c'est une distrib de gonzesses...

-+- AG in Guide du Fmblien Assassin : "Même pas male" -+-

A propos des collisions md5, un fil s'est ouvert sur fr.misc.cryptologie.
Les contributions y sont plus nombreuses à ce sujet qu'ici.

Grindipo

"Guillaume Gielly" a écrit

Si j'ai bien compris, ils ont réussi à trouver input2 telle que
md5(input1) == md5(input2) == hash.

Yep.
Ce qui est un peu moins clair c'est le mode de construction de ces input1 et
input2.
Il y a un thread concernant ces collisions sur fr.misc.cryptologie.

Maintenant si input1 doit avoir une forme spécifique ou que input2 se
dérive de input1 facile, les conséquences sont minimes, non ?

Pas vraiment non.
Dans le cas ou input2 se dérive facilement de input1 ça varie de la
catastrophe (on arrive assez facilement à faire un document "textuel" [1]) à
chiant (il faut savoir que certains binaires sont fournis avec un md5 signé
; si on peut trafiquer le binaire en gardant le md5 ça ne va pas être triste
pour certains contrôles, y compris par des outils qui proposent la
possibilité d'utiliser un seul système de hashage ).

Si c'est input1 qui doit avoir une forme spécifique ce n'est pas encore
critique [2] mais c'est très mauvais signe.

Au niveau de la sécurité informatique ça peut remettre en cause certains
schémas qui ... existerons encore d'ici quelques années, le temps de changer
de (mauvaises) habitudes :(

En tous cas, amha, c'est à suivre d'assez près.

Eric

PS : le doc : http://eprint.iacr.org/2004/199.pdf

[1] pour l'instant on semble loin du texte "brut" (ex ASCII ou
ISO-machin-truc) mais avec des formats comme word ou pdf on peut ajouter des
infos qui ne seront pas visibles mais qui servent dans le calcul du md5)

[2] Et encore, ça permet de se faire signer deux documents différents alors
que le signataire n'a signé qu'une fois!

--
L'invulnérable :
Je ne pense pas etre piratable, infectable par un trojen oui!
Vu sur fcs un jour de mars 2004.

"Nicolas George" <nicolas$george@salle-s.org>

Maintenant si input1 doit avoir une forme spécifique ou que input2 se
dérive de input1 facile, les conséquences sont minimes, non ?

À ce que des cryptographes disent, beaucoup de protocoles ne subissent
pas d'impact à cause de ça. En particulier, _a priori_, pas de souci
pour TLS, ni pour PGP. Cependant, des propriétés de MD5 font que cette
attaque est généralisable. À voir au cas par cas.

Il faut faire attention quand même. TLS n'utilise pas MD5 mais HMAC-MD5
(voir le post de Thomas Pornin sur fr.misc.cryptologie
<cfv5kh$dpf$2@biggoron.nerim.net>) et sa non
vulnérabilité dans ce cas n'implique pas que c'est MD5 qui n'est pas
attaquable en pratique).

On n'en est qu'à des effets d'annonce pour l'instant[1], sans attaque
sérieuse
immédiatement en vue[2]. Mais ça pousse quand même, je crois, a se tourner
vers les fonctions de hashages non concernées par cet article (SHA-1 et les
versions 256&co par exemple).

Eric

[1] tant que le processus d'obtention des messages n'est pas indiqué la
seule chose dont on est sur c'est que le gus a trouvé des collisions :)

[2] En particulier rien qui laisse imaginer qu'on puisse trouver un nouveau
message ayant le même hash qu'un message quelconque (c'est à dire non choisi
par l'attaquant).

--
L'invulnérable :
Je ne pense pas etre piratable, infectable par un trojen oui!
Vu sur fcs un jour de mars 2004.

"Grindipo" <grindipo@iaou.fr>

A propos des collisions md5, un fil s'est ouvert sur fr.misc.cryptologie.
Les contributions y sont plus nombreuses à ce sujet qu'ici.

Oui.
J'ai accepté le post alors que j'avais déjà connaissance de l'autre fil.

Les implications en sécurité sont, amha, assez immédiates si un jour on
casse une fonction de hashage courament utilisée pour que ça ait sa place
sur ce forum.

Je suggére qu'on évite ici les débats purement techniques
(fr.misc.cryptologie a les spécialistes pour ça :) ) et qu'on reste plus
informatifs et centrés sur les conséquences de sécurité ici.

Eric.

Co-modérateur de fr.comp.securite.

Bonjour,

On Thu, 18 Aug 2004, Eric Razny wrote:

"Grindipo" <grindipo@iaou.fr>

A propos des collisions md5, un fil s'est ouvert sur fr.misc.cryptologie.
Les contributions y sont plus nombreuses à ce sujet qu'ici.

Oui.
J'ai accepté le post alors que j'avais déjà connaissance de l'autre fil.

Les implications en sécurité sont, amha, assez immédiates si un jour on
casse une fonction de hashage courament utilisée pour que ça ait sa place
sur ce forum.

En termes pratiques, le cassage du MD5 (puisque c'est bien de ça qu'on
cause, merci à Mr Blancher d'avoir présenté le bon lien) est assez brutal
(ces maudits chinois arrivent à fabriquer de nouvelles collisions assez
rapidement: 1h pour une collision partielle, plus quelques
secondes/minutes pour une vraie collision)..
Beaucoup d'archives sont protégées simplement par un MD5 (et même parfois
sans aucune signature), et je crois savoir que certains formats de fichier
acceptent que des octets 'en trop' se trouvent dans leurs fichiers: tar (à
la fin), zip (au début), sûrement d'autres... sans compter tous les
formats de fichiers qui acceptent sans broncher quelques octets de changés
au milieu de structures inutilisées (comme les commentaires dans un code
source, ou le paquet EXIF d'une image JPEG, ou les sections .comment ou
.debug* d'un binaire ELF, par exemple).

A noter que le lien fourni par l'OP présente une collision sur SHA-0, que
personne n'utilise, mais qui peut être un tremplin vers le SHA-1, qu'il
est préconisé d'utiliser en lieu et place de MD5 depuis ... 1996 (qui
utilise encore MD5 de nos jours, hein? ;) alors que lien fourni par Mr
Blancher (le 199.pdf) présente des collisions sur MD4, MD5, HAVAL-128
(tout le monde s'en fout), et RIPEMD (qui est plus utilisé dans sa version
-160, et qui pourrait peut-être bientôt tomber).

De tout ça, le plus utilisé est sans conteste MD5, on l'emploie toujours
un peu partout. Par exemple, une archive Java signée stocke généralement
un MD5 des fichiers qui la composent (dans le Manifest/).

On devrait en savoir plus dans quelques jours (le temps d'étudier comment
ont fait ces chinois). D'ici là, vacances :)

--
Erwann ABALEA <erwann@abalea.com> - RSA PGP Key ID: 0x2D0EABD5
-----
DM> J'arrive seulement sur ce groupe de discussion .Que faut il faire ?
Rien, il n'y a absolument rien d'autres à faire que taper son message en
répondant au groupe, ou pourquoi pas un nouveau message. Rien d'autres
-+- E in Guide du Neuneu Usenet - Mais oû ce qu'il est-il donc ? -+-

Le Wed, 18 Aug 2004 21:17:06 +0000, Guillaume Gielly a écrit :

https://www.devnullteam.org/~pmz/sha-collision.txt


Si j'ai bien compris, ils ont réussi à trouver input2 telle que
md5(input1) == md5(input2) == hash.

Maintenant si input1 doit avoir une forme spécifique ou que input2 se
dérive de input1 facile, les conséquences sont minimes, non ?

Bonjour,

Et bien non, les conséquences sont au contraire catastrophiques.
En effet, les algorithmes de hachage sont massivement utilisés dans les
mécanismes de signatures.
Si je sais créer input2 très voisin de input1, qu'est ce qui m'empèche
d'ajouter quelques 0 (à mon avantage bien sur) sur un document
commercial, quitte à introduire quelques fôtes d'orthographe par-ci
par-là ?. C'est la fin programmée, au moins pour quelques années, du
commerce électronique.

C'est tout le problème de ces algorithmes "faibles" dans lesquels les
faiblesses sont structurelles et dont la sécurité ne repose que sur le
fait que la méthode pour exploiter ces failles n'a pas encore été
découverte. Le cas de RSA est aussi intéressant ; quel que soit le
nombre de bits choisi, le deux nombres premiers à trouver sont là, à
portée de main dans leur produit. Ne serait-ce qu'en cherchant au hasard,
la probabilité de les trouver rapidement n'est pas nulle.

Le "drame", c'est que tous nos mécanismes de signature et que la plupart
de nos algorithmes de chiffrement (même si la clé de session est
symétrique) reposent sur ces algorithmes.

Cordialement.

Jean-Marie

Pour me répondre, remplacer "jm" par "jean-marie"

Le Thu, 19 Aug 2004 06:41:51 +0000, Erwann ABALEA a écrit :

Beaucoup d'archives sont protégées simplement par un MD5 (et même parfois
sans aucune signature)

Alors que tout le monde devrait savoir qu'un hash MD5 ne constitue en rien
une preuve d'intégrité de l'archives (au sens large) dans la mesure où
un pirate capable de modifier l'archive est aussi en mesure de
régénérer une somme MD5 adéquat, assurant à l'utilisateur qu'il a
bien la version vérolée en face de lui ;)))

La protection valable, c'est la signature cryptographique. On me dira que
ce procédé appelle une fonction de hashage, mais heureusement
les logiciels comme GnuPG ou GPG utilisent SHA-1 depuis longtemps. Fingers
crossed. N'empêche que je n'arrive pas à comprendre l'avantage que
certains trouvent à génèrer des sommes MD5, les coller dans un
fichier et puis signer ce fichier par rapport à signer directement les
archives...


--
tenir à bout de bras un câble ethernet qui traverse une salle de restau
pour pas qu'il tombe dans les tiramisu, pendant que d'autres parlent en
infrarouge, c'est bien la vraie vie, n'est-ce pas ?
-+- DA in Guide du Macounet Pervers : http://www.le-visconti.net/ -+-