OVH Cloud OVH Cloud

MD5 compromis ?

40 réponses
Avatar
Guillaume Gielly
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 ?

--
Guillaume Gielly

10 réponses

1 2 3 4
Avatar
Paul Gaborit
Ca peut relancer aussi le concept du mélange de deux fonctions de
hachage différentes, mais je ne sais pas d'un point de vue théorique
quelle est vraiment la solidité de ce type de méthode.



À (at) Thu, 19 Aug 2004 14:41:40 +0000 (UTC),
(Thomas Pornin) écrivait (wrote):
D'un point de vue théorique, on a beaucoup de mal à bien définir ce que
ça veut dire, que deux fonctions de hachage sont "différentes".


À supposer que SHA-1 "tombe" comme vient de le faire MD5, que penser d'une
double signature (en attendant mieux) ? Par exemple, serait-il possible de
créer deux fichiers ayant *à* *la* *fois* les mêms signatures MD5 et SHA-1 ?

--
Paul Gaborit - <http://www.enstimac.fr/~gaborit/>


Avatar
Grindipo
Thomas Pornin :
D'un point de vue théorique, on a beaucoup de mal à bien définir ce que
ça veut dire, que deux fonctions de hachage sont "différentes".
Remarque : j'avance des idées, interrompez quand je dis faux ;)

A propos de la théorie, j'ai l'impression que l'attaque sur md5 n'est pas de
force brute. Donc on a exploité une astuce algorithmique, une faiblesse
théorique.
Ne serait-il pas possible d'adosser la robustesse d'une fonction de hash à
un résultat théorique ? L'idéal serait que le cassage de cette fonction est
NP-complet. Ce n'est pas comme ça que RSA fonctionne ? (casser RSA revient à
décomposer un nombre en facteurs premiers, problème réputé difficile)

Il est effectivement temps de réfléchir ;)

Grindipo

Avatar
Damien Wyart
* (Thomas Pornin) in fr.misc.cryptologie:
En bref, je n'ai personnellement rien de mieux à proposer que SHA-1
pour le moment. Le mieux serait que SHA-1 tienne une dizaine d'années
de plus, qu'on ait le temps de s'assurer que SHA-256 est bon, et de se
mettre à conseiller d'utiliser SHA-256.


Que penser des fonctions Whirlpool (recommandée par le rapport européen
Nessie) et de RIPEMD-160 et TIGER-192 (présentes dans la version de
développement de gnupg) ? Sont-elles elle aussi trop récente pour avoir
vraiment un avis fiable à leur propos ?

--
DW

Avatar
Jean-Marc Desperrier
Paul Gaborit wrote:
À supposer que SHA-1 "tombe" comme vient de le faire MD5, que penser d'une
double signature (en attendant mieux) ? Par exemple, serait-il possible de
créer deux fichiers ayant *à* *la* *fois* les mêms signatures MD5 et SHA-1 ?


Oui, c'est ce que je voulais dire par mélange.

Y-a-t-il des analyses vraiment sérieuse de ce genre de truc ?
Est-ce possible d'analyser sérieusement, comme l'évoque Pornin ?(que
veut dire différent ?)

Avatar
Francois Grieu
sur fr.comp.securité, Jean-Marie Delapierre dit:

les conséquences (des récentes attaques sur MD5, MD4, SHA-0.. sont)
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.



Relativisons.


D'abord l'algorithme de hash le plus utilisé, et de loin, pour signer des
documents, c'est SHA-1, pas MD5. SHA-1 reste sur pour l'instant.


MD5 reste encore assez utilisé pour les certificats SSL (de https
par exemple), mais dans ce contexte les récentes attaques ont peu de
portée. En effet ces attaques permettent de trouver des collisions,
mais:

- les hashs (donc certificats) EXISTANTS utilisant MD5 ne sont pas
attaquables par quelque technique de collision que ce soit (il faut
une attaque de type [seconde] préimage);

- la pratique existante chez, par exemple, Verisign, quand ils émettent
(encore) un certificat avec MD5, est de mettre de l'aléa au début
du certificat, ce qui également rend inopérante toute attaque par
collision;

- certains (par exemple au moins un utilisateur de OpenSSL postant
des challenges sur nos forums, il se reconnaitra) ne prennent
pas cette précaution; ils sont donc vulnérables à une attaque
connue, en 2^65 calculs MD5 (certe d'un coût de l'ordre de 10^5 euro
à monter), dès lors qu'ils acceptent de signer un certificat pour une
clé publique qu'ils n'ont pas généré; eh bien ces imprudents sont
apparemment plutôt à l'abris de la nouvelle attaque, qui ne permet PAS
(au contraire de la force brute) de choisir des contenus distincts
au début des données.


MD5 est très utilisé dans HMAC-MD5, mais là aussi les attaques par
collision ne sont pas à craindre.


Ces attaques sont donc une très grande nouvelle, mais pas la fin
du commerce électronique. Par contre, la chute de SHA-1, ou une attaque
de type [seconde] préimage contre MD5, ou même une attaque de type
collision sur MD5 permettant de choisir le début des messages, ou
de ne devoir imposer que quelques bits au lieu de 1024, ce serait
nettement plus gênant.


Ah mon avis, une des pires conséquence réelle de ces attques est qu'il
devient extrèmement facile de faire deux exécutables qui ont le même
hash MD5, mais font deux choses très différentes et que l'on a choisi.

Et aussi, il y a l'impact médiatico/marketing: une aubaine
pour les journaleux et les vendeurs de machins de sécurité, qui vont
pouvoir vendre leur soupe; ça va en pisser de l'article sensationnel
et du remplacement de parc !


François Grieu

Avatar
Francois Grieu
Jean-Marie Delapierre a écrit:

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.


Plusieurs objections:

- les attaques récemment publiées cassent MD5, pas SHA-1, qui reste
sur pour l'instant, et est le plus utilisé pour signer des documents

- MD5 est encore pas mal utilisé dans les certificats SSL (il
est en perte de vitesse au profit de SHA-1), mais dans ce contexte
l'attaque, dans son état actuel, n'est PAS très dangereuse.
En effet, la meilleur pratique de ceux qui font (encore) des
certificats avec MD5 (ex. Verisign) est de mettre de l'aléa au
début des certificats avant de les signer, ce qui tue toute
attaque de type collision.
Noter tout de même que certains (au moins certaines instances de
OpenSSL) ne prennent pas cette précaution; ils sont donc vulnérables
à une attaque connue, par la force brute, en 2^65 calculs MD5
environ (une légère variante de ce que faisait www.md5crk.com).
Eh bien même ces imprudents semblent à l'abris de la nouvelle attaque,
d'extrème justesse, car elle ne permet PAS de choisir des contenus
différents pour le début des messages en collison.

François Grieu

Avatar
Francois Grieu
Jean-Marie Delapierre dit:

les conséquences sont minimes, non ?


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.



Relativisons.


D'abord l'algorithme de hash le plus utilisé, et de loin, pour signer des
documents, c'est SHA-1, pas MD5. SHA-1 reste sur pour l'instant.


MD5 reste encore assez utilisé pour les certificats SSL (de https
par exemple), mais dans ce contexte les récentes attaques ont peu de
portée. En effet ces attaques permettent de trouver des collisions,
mais:

- les hashs (donc certificats) EXISTANTS utilisant MD5 ne sont pas
attaquable par quelque technique de collision que ce soit (il faut
une attaque de type [seconde] préimage);

- la pratique existante chez, par exemple, Verisign, quand ils émettent
(encore) un certificat avec MD5, est de mettre de l'aléa au début
du certificat, ce qui également rend inopérante toute attaque par
collision;

- certains (par exemple au moins un utilisateur de OpenSSL postant
des challenges sur nos forums, il se reconnaitra) ne prennent
pas cette précaution; ils sont donc vulnérables à une attaque
connue, en 2^65 calculs MD5 (certe d'un coût de l'ordre de 10^5 euro
à monter), dès lors qu'ils acceptent de signer un certificat pour une
clé publique qu'ils n'ont pas généré; eh bien ces imprudents sont
apparemment assez à l'abris de la nouvelle attaque, qui ne permet PAS
(au contraire de la force brute) de choisir des contenus distincts
au début des données.


MD5 est très utilisé dans HMAC-MD5, mais là aussi les attaques par
collision ne sont pas à craindre.


Ces attaques sont donc une très grande nouvelle, mais pas la fin
du commerce électronique. Par contre, la chute de SHA-1, ou une attaque
de type [seconde] préimage contre MD5, ou même une attaque de type
collision sur MD5 permettant de choisir le début des messages, ou
de ne devoir imposer que quelques bits au lieu de 1024, ce serait
nettement plus gênant.


Ah mon avis, une des pires conséquence réelle de ces attques est qu'il
devient extrèmement facile de faire deux exécutables qui ont le même
hash MD5, mais font deux choses très différentes et que l'on a choisi.

Et aussi, il y a l'impact médiatico/marketing: une aubaine
pour les journaleux et les vendeurs de machins de sécurité, qui vont
pouvoir vendre leur soupe; ça va en pisser de l'article et de l'upgrade !

[Je devrais peut-être pas cracher tant dans la soupe: je vends mes
services comme expert..]


François Grieu


Avatar
Francois Grieu
In article <cg2e74$1vrh$,
(Thomas Pornin) wrote:

je n'ai personnellement rien de mieux à proposer que SHA-1
pour le moment.



Je hasarde un bricolage compatible avec SHA-1 dans les contextes
où augmenter le coût de calcul est possible, et où le message
reste un peu inférieur à la limite (2^61 octets) de SHA-1;
je baptise ça "Double SHA-1":

DSHA-1(message) = SHA-1(message) XOR SHA-1(0#544|message)

où "0#544|" désigne l'insertion de 544 bits à 0 au début
du message (selon une notation déjà utilisée dans le contexte
des rares vecteurs de test de SHA-1 sur des chaines de bit).


Justification:

Faire le OU exclusif de deux hash sur le même texte est
une construction qui ne nécessite pas de stocker le message.

Insérer 512 bits à 0 revient à remplacer la valeur initiale
du hash, ce qui oblige à attaquer les deux SHA-1 en même temps,
et cela seul bloque net toutes les pistes d'attaque publiées.

Insérer 512 bits à 0 change aussi le padding final, ce qui est
une sécurité supplémentaire.

Insérer 512 bits à 0 ne coute en fait presque rien en calcul
(à partir du moment où l'on fait deux hash).

On a 544 = 512 + 32; insérer encore 32 bits à 0 coute assez
peu de temps de calcul, et disperse la position des différences
injectées, par surcroit de sécurité. Insérer de plus 16
(ou autres) bits à 0 aurait couté davantage de temps de calcul,
pour un bénéfice possible, mais pas facile à justifier.



Commentaires bienvenus !

François Grieu

Avatar
Jean-Marie Delapierre
Le Thu, 19 Aug 2004 18:51:03 +0000, Francois Grieu a écrit :

Jean-Marie Delapierre dit:

les conséquences sont minimes, non ?


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.



Relativisons.


D'abord l'algorithme de hash le plus utilisé, et de loin, pour signer des
documents, c'est SHA-1, pas MD5. SHA-1 reste sur pour l'instant.


MD5 reste encore assez utilisé pour les certificats SSL (de https
par exemple), mais dans ce contexte les récentes attaques ont peu de
portée. En effet ces attaques permettent de trouver des collisions,
mais:

- les hashs (donc certificats) EXISTANTS utilisant MD5 ne sont pas
attaquable par quelque technique de collision que ce soit (il faut
une attaque de type [seconde] préimage);

- la pratique existante chez, par exemple, Verisign, quand ils émettent
(encore) un certificat avec MD5, est de mettre de l'aléa au début
du certificat, ce qui également rend inopérante toute attaque par
collision;

- certains (par exemple au moins un utilisateur de OpenSSL postant
des challenges sur nos forums, il se reconnaitra) ne prennent
pas cette précaution; ils sont donc vulnérables à une attaque
connue, en 2^65 calculs MD5 (certe d'un coût de l'ordre de 10^5 euro
à monter), dès lors qu'ils acceptent de signer un certificat pour une
clé publique qu'ils n'ont pas généré; eh bien ces imprudents sont
apparemment assez à l'abris de la nouvelle attaque, qui ne permet PAS
(au contraire de la force brute) de choisir des contenus distincts
au début des données.


MD5 est très utilisé dans HMAC-MD5, mais là aussi les attaques par
collision ne sont pas à craindre.


Ces attaques sont donc une très grande nouvelle, mais pas la fin
du commerce électronique. Par contre, la chute de SHA-1, ou une attaque
de type [seconde] préimage contre MD5, ou même une attaque de type
collision sur MD5 permettant de choisir le début des messages, ou
de ne devoir imposer que quelques bits au lieu de 1024, ce serait
nettement plus gênant.


Ah mon avis, une des pires conséquence réelle de ces attques est qu'il
devient extrèmement facile de faire deux exécutables qui ont le même
hash MD5, mais font deux choses très différentes et que l'on a choisi.

Et aussi, il y a l'impact médiatico/marketing: une aubaine
pour les journaleux et les vendeurs de machins de sécurité, qui vont
pouvoir vendre leur soupe; ça va en pisser de l'article et de l'upgrade !

[Je devrais peut-être pas cracher tant dans la soupe: je vends mes
services comme expert..]


François Grieu


Bonsoir,

Je sais bien que l'attaque qui a été démontrée ne permet pas grand
chose, mais ce n'est qu'un début. Bien des chercheurs vont encore se
pencher sur le cas de ces algorithmes et je crains fort qu'un jour, l'un
d'entre eux trouve une vraie attaque qui marche. Et ce qui m'inquiète,
c'est que tout le commerce électronique, la fiscalité électronique,
le... électronique repose la dessus. Si l'irréversibilité des
algorithmes de hachage tombe (et j'ai bien compris que ce n'était pas le
cas cette fois-ci), c'est tout qui s'écroule ; et ça m'inquiète.

Cordialement.

Jean-Marie

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



Avatar
Michel Arboi
On Thu Aug 19 2004 at 11:58, Eric Razny wrote:

Accessoirement si tu tiens à ta clef privée je te conseille fortement de
signer le hashé d'un message que je te propose et non pas le message lui
même.


<souvenirs brumeux>
Il n'existe pas des fonctions de reformatage des données qui contrent
ces attaques, justement ?
Fonctions qui ne sont pas un hash...
</souvenirs brumeux>

1 2 3 4