[gull] Collision md5

[Frederic Schutz]

Quoting Daniel Cordey <dc at mjt.ch>:

> On Friday 20 August 2004 08:38, Marc SCHAEFER wrote:
> 
> > Entre trouver deux chaînes qui donnent le même MD5' et une modification
> > d'une chaîne donnée qui donne toujours le même MD5 il y a encore un pas
> > à faire.
> 
> Oui, il faut au moins s'appeler Gulliver :-) En effet, j'avoue que, sans
> etre un specialiste du cryptage, je vois mal comment on peut arriver a la 
> deuxieme situation.

Il y a un type d'attaque dont la complexite se situe entre les deux attaques
que decrit Marc ci-dessus. L'idee est la suivante: je cree 2 fichiers de la
forme

Fichier 1: [ texte 1 ][random data 1]
Fichier 2: [ texte 2 ][random data 2]

"Random data" peut etre insere p.ex. dans une image, etc. Maintenant, je
cherche une paire de random data 1 et 2 qui me donnent la meme empreinte
MD5 pour les 2 fichiers. C'est clairement plus complique que la premiere
attaque citee par Marc (car une partie de la chaine est fixee), mais plus
simple que la deuxieme (car je n'ai pas un des fichiers qui est fixe, et
je peux jouer sur les random data dans les deux cas).

Une fois que j'ai trouve mes fichiers, toute tentative de verification du
fichier 1 basee sur une empreinte MD5 ne detecterait pas si le fichier 2
etait inseree a la place.

En pratique, c'est plus complique que les attaques qui ont ete decrites
jusqu'a present sur MD5, ca ne marche pas avec GPG (qui ajoute du padding
aleatoire dans tous les cas avant de calculer l'empreinte et empeche donc
de choisir a l'avance le resultat du MD5), mais on pourrait imaginer que
ca pourrait etre utilise contre un systeme de verification d'integrite de
fichiers par exemple.

Frederic