A quoi sert ce groupe si l'annonce d'un truc de ce genre met plusieurs
jours pour y arriver ? Tss.
Une collision a été trouvé sur SHA-0 en utilisant un algo de Antoine
Joux (une amélioration de ses résultats de 98 avec Chabaud qui utilise
aussi une technique de Biham et Chen sur les "neutral bit") :
http://www.mail-archive.com/cryptography@metzdowd.com/msg02554.html
Valeur de haché commune :
c9f160777d4086fe8095fba58b7e20c228a4006b
Il suffit de faire "openssl sha file.bin" sur un fichier binaire dont le
contenu est l'un de deux précédent pour reproduire le résultat.
Rapellons que SHA-0 est la première version de l'algorythme SHA, qui a
été précipitament retiré par le NSA suite à la découverte d'une
faiblesse que le NSA n'a jamais publié.
L'attaque a pris environ 80 000 heures CPU sur le système TERA NOVA (256
Intel-Itanium2 de BULL SA, installé au labo TERA TECH du CEA DAM).
La complexité de l'attaque est estimé à 2^51.
Apparement, ce système n'est pas listé dans le top 500 des
super-ordinateurs de 2004.
Ou bien s'agit-il en fait de l'ordinateur de Bull classé 227ème dont la
description ressemble fortement ?
La collision est sur une variante de md5 dont le vecteur d'initialisation est inversé.
Non. Les messages sont pas dans leur ordre habituel, mais le vecteur est absolument standard. Le md5 des deux fichiers de 1024 bits dont le contenu en hexa est:
Ca dépend. Quelle version du papier as-tu? Dans celle datée du 16 août, les vecteurs sont effectivement inversés. Dans la version révisée du 17 août, ce sont les bons.
Ah tout s'explique, j'ai la version 17 Août. Je reviens juste de vacance, mais je vois que tout le monde n'a pas chômé !
François Grieu
Erwann ABALEA <erwann@abalea.com> dit
On Tue, 17 Aug 2004, Francois Grieu wrote:
Jean-Marc Desperrier <jmdesp@alussinan.org> dit:
La collision est sur une variante de md5 dont le vecteur
d'initialisation est inversé.
Non. Les messages sont pas dans leur ordre habituel, mais
le vecteur est absolument standard. Le md5 des deux fichiers
de 1024 bits dont le contenu en hexa est:
Ca dépend. Quelle version du papier as-tu? Dans celle datée du 16 août,
les vecteurs sont effectivement inversés. Dans la version révisée du 17
août, ce sont les bons.
Ah tout s'explique, j'ai la version 17 Août.
Je reviens juste de vacance, mais je vois que tout le monde n'a pas chômé !
La collision est sur une variante de md5 dont le vecteur d'initialisation est inversé.
Non. Les messages sont pas dans leur ordre habituel, mais le vecteur est absolument standard. Le md5 des deux fichiers de 1024 bits dont le contenu en hexa est:
Ca dépend. Quelle version du papier as-tu? Dans celle datée du 16 août, les vecteurs sont effectivement inversés. Dans la version révisée du 17 août, ce sont les bons.
Ah tout s'explique, j'ai la version 17 Août. Je reviens juste de vacance, mais je vois que tout le monde n'a pas chômé !
François Grieu
Xavier Roche
Je n'ai pas encore compris ce que signifiait dans leur papier (http://eprint.iacr.org/2004/199.pdf) "Moreover, our attack works for any given initial value.". Initial value de quoi ? Apparamment l'attaque marche si on a le message original (et donc aussi son md5 original) d'une taille définie ? On attend les précisions avec impatience et les détails de leur attaque.
Ps: Un exemple (http://www.trash.net/~roman/weiteres/collision.tar.gz) de deux collisions sur le "vrai" md5 (exceptionnellement ici, les fichiers étant petits):
begin 600 hash1 MT3'=`L7F[L1I/9H&F*_Y7"_*M8<21GZK0`18/KC[?XE5K30&"?2S`H/DB(,E M<4%:"%$EZ/?-R9_9';WR@#<6Y8+'='<07N<Y-B7]%IE5=4U<YK'.O]##`I F6;1";&/=2=_>3#57.LBZ*VZ><P57.UTR]U?Q=-ML9L*V#7,I^,` ` end
begin 600 hash2 MT3'=`L7F[L1I/9H&F*_Y7"_*M0<21GZK0`18/KC[?XE5K30&"?2S`H/DB(,E M4%:"%$EZ/?-R9_9';UR@#<6Y8+'='<07N<Y-B7]%IE5=4U<YI'.O]##`I F6;1";&/=2=_>3#57.LBZ*VZ>4P57.UTR]U?Q=-ML9L*6#7,I^,` ` end
Je n'ai pas encore compris ce que signifiait dans leur papier
(http://eprint.iacr.org/2004/199.pdf) "Moreover,
our attack works for any given initial value.". Initial value de quoi ?
Apparamment l'attaque marche si on a le message original (et donc aussi
son md5 original) d'une taille définie ? On attend les précisions avec
impatience et les détails de leur attaque.
Ps: Un exemple (http://www.trash.net/~roman/weiteres/collision.tar.gz)
de deux collisions sur le "vrai" md5 (exceptionnellement ici, les
fichiers étant petits):
begin 600 hash1
MT3'=`L7F[L1I/9H&F*_Y7"_*M8<21GZK0`18/KC[?XE5K30&"?2S`H/DB(,E
M<4%:"%$EZ/?-R9_9';WR@#<6Y8+'='<07N<Y-B7]%IE5=4U<YK'.O]##`I
F6;1";&/=2=_>3#57.LBZ*VZ><P57.UTR]U?Q=-ML9L*V#7,I^,`
`
end
begin 600 hash2
MT3'=`L7F[L1I/9H&F*_Y7"_*M0<21GZK0`18/KC[?XE5K30&"?2S`H/DB(,E
M4%:"%$EZ/?-R9_9';UR@#<6Y8+'='<07N<Y-B7]%IE5=4U<YI'.O]##`I
F6;1";&/=2=_>3#57.LBZ*VZ>4P57.UTR]U?Q=-ML9L*6#7,I^,`
`
end
Je n'ai pas encore compris ce que signifiait dans leur papier (http://eprint.iacr.org/2004/199.pdf) "Moreover, our attack works for any given initial value.". Initial value de quoi ? Apparamment l'attaque marche si on a le message original (et donc aussi son md5 original) d'une taille définie ? On attend les précisions avec impatience et les détails de leur attaque.
Ps: Un exemple (http://www.trash.net/~roman/weiteres/collision.tar.gz) de deux collisions sur le "vrai" md5 (exceptionnellement ici, les fichiers étant petits):
begin 600 hash1 MT3'=`L7F[L1I/9H&F*_Y7"_*M8<21GZK0`18/KC[?XE5K30&"?2S`H/DB(,E M<4%:"%$EZ/?-R9_9';WR@#<6Y8+'='<07N<Y-B7]%IE5=4U<YK'.O]##`I F6;1";&/=2=_>3#57.LBZ*VZ><P57.UTR]U?Q=-ML9L*V#7,I^,` ` end
begin 600 hash2 MT3'=`L7F[L1I/9H&F*_Y7"_*M0<21GZK0`18/KC[?XE5K30&"?2S`H/DB(,E M4%:"%$EZ/?-R9_9';UR@#<6Y8+'='<07N<Y-B7]%IE5=4U<YI'.O]##`I F6;1";&/=2=_>3#57.LBZ*VZ>4P57.UTR]U?Q=-ML9L*6#7,I^,` ` end
pornin
According to Erwan David :
Par contre certains (Thomas Pornin ?) avaient comparé la probabilité de collision et celle de recevoir une météorite. Il semblerait que cela *aussi* soit arrivé... (http://fr.news.yahoo.com/040818/202/40h38.html)
Certes, certes. Mais il me semble bien avoir toujours pris les précautions oratoires d'usage, c'est-à-dire un genre de "sauf si on trouve une attaque spécifique à MD5, utilisant sa structure interne". Ce qui est le cas ici.
--Thomas Pornin
According to Erwan David <erwan@rail.eu.org>:
Par contre certains (Thomas Pornin ?) avaient comparé la probabilité
de collision et celle de recevoir une météorite. Il semblerait que
cela *aussi* soit arrivé... (http://fr.news.yahoo.com/040818/202/40h38.html)
Certes, certes. Mais il me semble bien avoir toujours pris les
précautions oratoires d'usage, c'est-à-dire un genre de "sauf si on
trouve une attaque spécifique à MD5, utilisant sa structure interne".
Ce qui est le cas ici.
Par contre certains (Thomas Pornin ?) avaient comparé la probabilité de collision et celle de recevoir une météorite. Il semblerait que cela *aussi* soit arrivé... (http://fr.news.yahoo.com/040818/202/40h38.html)
Certes, certes. Mais il me semble bien avoir toujours pris les précautions oratoires d'usage, c'est-à-dire un genre de "sauf si on trouve une attaque spécifique à MD5, utilisant sa structure interne". Ce qui est le cas ici.
--Thomas Pornin
pornin
According to Xavier Roche :
Je n'ai pas encore compris ce que signifiait dans leur papier (http://eprint.iacr.org/2004/199.pdf) "Moreover, our attack works for any given initial value.". Initial value de quoi ?
MD5 fonctionne par applications successives d'une "fonction de compression" sur une valeur de 128 bits, en utilisant à chaque application un bloc de 512 bits de données comme "clé". Au tout début, il faut une valeur de 128 bits conventionnelle, dite "initial value (IV)", spécifiée dans la RFC. C'est cette valeur que les auteurs avaient initialement mal recopiée, avec cette histoire d'ordre des octets.
Ce qu'ils veulent dire, c'est que leur attaque marche quelque soit la valeur qu'on fixe pour cette IV, donc notamment celle de la RFC qui caractérise MD5. Ils doivent néanmoins _connaître_ cette valeur pour travailler, ce qui fait que pour le moment, l'attaque n'est pas applicable à HMAC-MD5, l'algorithme de contrôle d'intégrité utilisant MD5 en interne (dans un montage un peu compliqué avec une clé secrète). Je précise ça, parce que TLS/SSL (donc HTTPS) utilise HMAC-MD5 (ou HMAC-SHA1, suivant ce que savent faire le client et le serveur). En bref, TLS/SSL (et donc HTTPS) n'est pas cassé par cette attaque.
(M'enfin bon, depuis le temps qu'on répète que SHA-1 c'est mieux que MD5...)
--Thomas Pornin
According to Xavier Roche <xroche@free.fr.NOSPAM.invalid>:
Je n'ai pas encore compris ce que signifiait dans leur papier
(http://eprint.iacr.org/2004/199.pdf) "Moreover,
our attack works for any given initial value.". Initial value de quoi ?
MD5 fonctionne par applications successives d'une "fonction de
compression" sur une valeur de 128 bits, en utilisant à chaque
application un bloc de 512 bits de données comme "clé". Au tout début,
il faut une valeur de 128 bits conventionnelle, dite "initial value
(IV)", spécifiée dans la RFC. C'est cette valeur que les auteurs avaient
initialement mal recopiée, avec cette histoire d'ordre des octets.
Ce qu'ils veulent dire, c'est que leur attaque marche quelque soit
la valeur qu'on fixe pour cette IV, donc notamment celle de la RFC
qui caractérise MD5. Ils doivent néanmoins _connaître_ cette valeur
pour travailler, ce qui fait que pour le moment, l'attaque n'est pas
applicable à HMAC-MD5, l'algorithme de contrôle d'intégrité utilisant
MD5 en interne (dans un montage un peu compliqué avec une clé secrète).
Je précise ça, parce que TLS/SSL (donc HTTPS) utilise HMAC-MD5 (ou
HMAC-SHA1, suivant ce que savent faire le client et le serveur). En
bref, TLS/SSL (et donc HTTPS) n'est pas cassé par cette attaque.
(M'enfin bon, depuis le temps qu'on répète que SHA-1 c'est mieux que
MD5...)
Je n'ai pas encore compris ce que signifiait dans leur papier (http://eprint.iacr.org/2004/199.pdf) "Moreover, our attack works for any given initial value.". Initial value de quoi ?
MD5 fonctionne par applications successives d'une "fonction de compression" sur une valeur de 128 bits, en utilisant à chaque application un bloc de 512 bits de données comme "clé". Au tout début, il faut une valeur de 128 bits conventionnelle, dite "initial value (IV)", spécifiée dans la RFC. C'est cette valeur que les auteurs avaient initialement mal recopiée, avec cette histoire d'ordre des octets.
Ce qu'ils veulent dire, c'est que leur attaque marche quelque soit la valeur qu'on fixe pour cette IV, donc notamment celle de la RFC qui caractérise MD5. Ils doivent néanmoins _connaître_ cette valeur pour travailler, ce qui fait que pour le moment, l'attaque n'est pas applicable à HMAC-MD5, l'algorithme de contrôle d'intégrité utilisant MD5 en interne (dans un montage un peu compliqué avec une clé secrète). Je précise ça, parce que TLS/SSL (donc HTTPS) utilise HMAC-MD5 (ou HMAC-SHA1, suivant ce que savent faire le client et le serveur). En bref, TLS/SSL (et donc HTTPS) n'est pas cassé par cette attaque.
(M'enfin bon, depuis le temps qu'on répète que SHA-1 c'est mieux que MD5...)
--Thomas Pornin
Jean-Marc Desperrier
Erwann ABALEA wrote:
Le papier http://eprint.iacr.org/2004/199.pdf a été révisé. Les formules ne sont pas plus claires, les messages sont toujours du little-endian, et les hash fournis ne sont pas ceux calculés. Mais la collision fonctionne sur le vrai MD5.
J'ai trouvé un début de commentaire sur la nature de l'attaque :
It seems to be a straightforward differential cryptanalysis attack, so one wonders why no-one else came up with it. The attack on Haval takes about 64 tries. On MD4, about 4 tries. RIPE-MD, about 2 hours (but can improve it). SHA-0 about 2^40 (1000 times better than Joux).
Bien que non cité dans l'article, RIPE-MD-160 est certainement lui aussi en grand péril. L'algo est fortement semblable à celui du RIPE-MD-128, juste étendu, et le SHA-0 démontre que les tailles de 160 bits peuvent être cassés par cette technique.
Erwann ABALEA wrote:
Le papier http://eprint.iacr.org/2004/199.pdf a été révisé. Les formules
ne sont pas plus claires, les messages sont toujours du little-endian, et
les hash fournis ne sont pas ceux calculés. Mais la collision fonctionne
sur le vrai MD5.
J'ai trouvé un début de commentaire sur la nature de l'attaque :
It seems to be a straightforward differential cryptanalysis attack, so
one wonders why no-one else came up with it. The attack on Haval takes
about 64 tries. On MD4, about 4 tries. RIPE-MD, about 2 hours (but can
improve it). SHA-0 about 2^40 (1000 times better than Joux).
Bien que non cité dans l'article, RIPE-MD-160 est certainement lui aussi
en grand péril.
L'algo est fortement semblable à celui du RIPE-MD-128, juste étendu, et
le SHA-0 démontre que les tailles de 160 bits peuvent être cassés par
cette technique.
Le papier http://eprint.iacr.org/2004/199.pdf a été révisé. Les formules ne sont pas plus claires, les messages sont toujours du little-endian, et les hash fournis ne sont pas ceux calculés. Mais la collision fonctionne sur le vrai MD5.
J'ai trouvé un début de commentaire sur la nature de l'attaque :
It seems to be a straightforward differential cryptanalysis attack, so one wonders why no-one else came up with it. The attack on Haval takes about 64 tries. On MD4, about 4 tries. RIPE-MD, about 2 hours (but can improve it). SHA-0 about 2^40 (1000 times better than Joux).
Bien que non cité dans l'article, RIPE-MD-160 est certainement lui aussi en grand péril. L'algo est fortement semblable à celui du RIPE-MD-128, juste étendu, et le SHA-0 démontre que les tailles de 160 bits peuvent être cassés par cette technique.
Francois Grieu
Dans l'article <cfv5kh$dpf$, (Thomas Pornin) dit:
According to Xavier Roche :
Je n'ai pas encore compris ce que signifiait dans leur papier (http://eprint.iacr.org/2004/199.pdf) "Moreover, our attack works for any given initial value.". Initial value de quoi ?
MD5 fonctionne par applications successives d'une "fonction de compression" sur une valeur de 128 bits, en utilisant à chaque application un bloc de 512 bits de données comme "clé". Au tout début, il faut une valeur de 128 bits conventionnelle, dite "initial value (IV)", spécifiée dans la RFC. C'est cette valeur que les auteurs avaient initialement mal recopiée, avec cette histoire d'ordre des octets.
Ce qu'ils veulent dire, c'est que leur attaque marche quelque soit la valeur qu'on fixe pour cette IV, donc notamment celle de la RFC qui caractérise MD5.
Oui. Conséquences:
- En insérant 1024 bits qu'ils choisissent dans n'importe quel message que l'on leur impose (ainsi que l'endroit de l'insertion à un alignement de 512 bits près), les auteurs peuvent produire des messages distincts dont les hash MD5 sont identiques.
- En doublant la longeur de l'insertion, les auteurs peuvent doubler le nombre de messages distincts, tous en collision.
- Les auteurs peuvent construire des exécutables win32 ou autre, en collision, dont ils choisisent les comportements complètement distincts.
Noter que, en l'état, c'est légèrement moins puissant (mais beaucoup plus rapide) que la recherche de collision par la force brute, laquelle permet en outre (moyennant un doublement du travail) de produire des messages dont les débuts sont imposés mais DISTINCTS (et qui a besoin de choisir de l'ordre de 10 fois moins de bits).
Pour cette raison, je ne vois pas que l'attaque EN L'ETAT soit applicable à la fraude aux certificats SSL possible par la force brute [*] même si l'autorité de certification commet l'erreur d'autoriser l'usage de MD5 et de laisser le début du certificat entièrement prévisible.
François Grieu
[*] consistant à ce que l'attaquant soumette une requète de certification spécialement construite, puis transforme le certificat légitimement obtenu en un autre, différent mais utilisable pour se représenter comme une entité cible. <http://google.fr/groups?threadm=fgrieu-35E934.07012424052004%40individual.net>
Dans l'article <cfv5kh$dpf$2@biggoron.nerim.net>,
pornin@nerim.net (Thomas Pornin) dit:
According to Xavier Roche <xroche@free.fr.NOSPAM.invalid>:
Je n'ai pas encore compris ce que signifiait dans leur papier
(http://eprint.iacr.org/2004/199.pdf) "Moreover,
our attack works for any given initial value.". Initial value de quoi ?
MD5 fonctionne par applications successives d'une "fonction de
compression" sur une valeur de 128 bits, en utilisant à chaque
application un bloc de 512 bits de données comme "clé". Au tout début,
il faut une valeur de 128 bits conventionnelle, dite "initial value
(IV)", spécifiée dans la RFC. C'est cette valeur que les auteurs avaient
initialement mal recopiée, avec cette histoire d'ordre des octets.
Ce qu'ils veulent dire, c'est que leur attaque marche quelque soit
la valeur qu'on fixe pour cette IV, donc notamment celle de la RFC
qui caractérise MD5.
Oui. Conséquences:
- En insérant 1024 bits qu'ils choisissent dans n'importe quel message
que l'on leur impose (ainsi que l'endroit de l'insertion à un
alignement de 512 bits près), les auteurs peuvent produire des
messages distincts dont les hash MD5 sont identiques.
- En doublant la longeur de l'insertion, les auteurs peuvent doubler
le nombre de messages distincts, tous en collision.
- Les auteurs peuvent construire des exécutables win32 ou autre,
en collision, dont ils choisisent les comportements complètement
distincts.
Noter que, en l'état, c'est légèrement moins puissant (mais beaucoup plus
rapide) que la recherche de collision par la force brute, laquelle permet
en outre (moyennant un doublement du travail) de produire des messages
dont les débuts sont imposés mais DISTINCTS (et qui a besoin de choisir
de l'ordre de 10 fois moins de bits).
Pour cette raison, je ne vois pas que l'attaque EN L'ETAT soit applicable
à la fraude aux certificats SSL possible par la force brute [*]
même si l'autorité de certification commet l'erreur d'autoriser
l'usage de MD5 et de laisser le début du certificat entièrement
prévisible.
François Grieu
[*] consistant à ce que l'attaquant soumette une requète de
certification spécialement construite, puis transforme le certificat
légitimement obtenu en un autre, différent mais utilisable pour se
représenter comme une entité cible.
<http://google.fr/groups?threadm=fgrieu-35E934.07012424052004%40individual.net>
Je n'ai pas encore compris ce que signifiait dans leur papier (http://eprint.iacr.org/2004/199.pdf) "Moreover, our attack works for any given initial value.". Initial value de quoi ?
MD5 fonctionne par applications successives d'une "fonction de compression" sur une valeur de 128 bits, en utilisant à chaque application un bloc de 512 bits de données comme "clé". Au tout début, il faut une valeur de 128 bits conventionnelle, dite "initial value (IV)", spécifiée dans la RFC. C'est cette valeur que les auteurs avaient initialement mal recopiée, avec cette histoire d'ordre des octets.
Ce qu'ils veulent dire, c'est que leur attaque marche quelque soit la valeur qu'on fixe pour cette IV, donc notamment celle de la RFC qui caractérise MD5.
Oui. Conséquences:
- En insérant 1024 bits qu'ils choisissent dans n'importe quel message que l'on leur impose (ainsi que l'endroit de l'insertion à un alignement de 512 bits près), les auteurs peuvent produire des messages distincts dont les hash MD5 sont identiques.
- En doublant la longeur de l'insertion, les auteurs peuvent doubler le nombre de messages distincts, tous en collision.
- Les auteurs peuvent construire des exécutables win32 ou autre, en collision, dont ils choisisent les comportements complètement distincts.
Noter que, en l'état, c'est légèrement moins puissant (mais beaucoup plus rapide) que la recherche de collision par la force brute, laquelle permet en outre (moyennant un doublement du travail) de produire des messages dont les débuts sont imposés mais DISTINCTS (et qui a besoin de choisir de l'ordre de 10 fois moins de bits).
Pour cette raison, je ne vois pas que l'attaque EN L'ETAT soit applicable à la fraude aux certificats SSL possible par la force brute [*] même si l'autorité de certification commet l'erreur d'autoriser l'usage de MD5 et de laisser le début du certificat entièrement prévisible.
François Grieu
[*] consistant à ce que l'attaquant soumette une requète de certification spécialement construite, puis transforme le certificat légitimement obtenu en un autre, différent mais utilisable pour se représenter comme une entité cible. <http://google.fr/groups?threadm=fgrieu-35E934.07012424052004%40individual.net>
Quisquater
Jean-Marc Desperrier wrote:
A quoi sert ce groupe si l'annonce d'un truc de ce genre met plusieurs jours pour y arriver ? Tss.
Parce que c'est la semaine de la conférence CRYPTO et que la plupart des (bons :-) cryptographes y sont :-)
En passant, il y a bien d'autres collisions : voir les titres de la rump session d'hier soir (qui était webcasté, mais c'était durant la muit pour l'Europe). http://www.iacr.org/conferences/crypto2004/C04RumpAgenda.pdf et surtout le preprint http://eprint.iacr.org/2004/199/
Comme vient de le dire Eli Biham durant la présentation de son papier "SHA-1 is not yet broken" "SHA-1 n'est pas encore cassé".
Mais cela va un peu s'exciter dans les chaumières sécurisées : qui utilise encore MD5 ?
Une collision a été trouvé sur SHA-0 en utilisant un algo de Antoine Joux (une amélioration de ses résultats de 98 avec Chabaud qui utilise aussi une technique de Biham et Chen sur les "neutral bit") : http://www.mail-archive.com//msg02554.html
Valeur de haché commune : c9f160777d4086fe8095fba58b7e20c228a4006b
Il suffit de faire "openssl sha file.bin" sur un fichier binaire dont le contenu est l'un de deux précédent pour reproduire le résultat.
Rapellons que SHA-0 est la première version de l'algorythme SHA, qui a été précipitament retiré par le NSA suite à la découverte d'une faiblesse que le NSA n'a jamais publié.
L'attaque a pris environ 80 000 heures CPU sur le système TERA NOVA (256 Intel-Itanium2 de BULL SA, installé au labo TERA TECH du CEA DAM). La complexité de l'attaque est estimé à 2^51.
Apparement, ce système n'est pas listé dans le top 500 des super-ordinateurs de 2004. Ou bien s'agit-il en fait de l'ordinateur de Bull classé 227ème dont la description ressemble fortement ?
Jean-Marc Desperrier wrote:
A quoi sert ce groupe si l'annonce d'un truc de ce genre met plusieurs
jours pour y arriver ? Tss.
Parce que c'est la semaine de la conférence CRYPTO et
que la plupart des (bons :-) cryptographes y sont :-)
En passant, il y a bien d'autres collisions :
voir les titres de la rump session d'hier soir
(qui était webcasté, mais c'était durant la muit pour
l'Europe).
http://www.iacr.org/conferences/crypto2004/C04RumpAgenda.pdf
et surtout le preprint
http://eprint.iacr.org/2004/199/
Comme vient de le dire Eli Biham durant la présentation de
son papier
"SHA-1 is not yet broken"
"SHA-1 n'est pas encore cassé".
Mais cela va un peu s'exciter dans les chaumières sécurisées :
qui utilise encore MD5 ?
Une collision a été trouvé sur SHA-0 en utilisant un algo de Antoine
Joux (une amélioration de ses résultats de 98 avec Chabaud qui utilise
aussi une technique de Biham et Chen sur les "neutral bit") :
http://www.mail-archive.com/cryptography@metzdowd.com/msg02554.html
Valeur de haché commune :
c9f160777d4086fe8095fba58b7e20c228a4006b
Il suffit de faire "openssl sha file.bin" sur un fichier binaire dont le
contenu est l'un de deux précédent pour reproduire le résultat.
Rapellons que SHA-0 est la première version de l'algorythme SHA, qui a
été précipitament retiré par le NSA suite à la découverte d'une
faiblesse que le NSA n'a jamais publié.
L'attaque a pris environ 80 000 heures CPU sur le système TERA NOVA (256
Intel-Itanium2 de BULL SA, installé au labo TERA TECH du CEA DAM).
La complexité de l'attaque est estimé à 2^51.
Apparement, ce système n'est pas listé dans le top 500 des
super-ordinateurs de 2004.
Ou bien s'agit-il en fait de l'ordinateur de Bull classé 227ème dont la
description ressemble fortement ?
A quoi sert ce groupe si l'annonce d'un truc de ce genre met plusieurs jours pour y arriver ? Tss.
Parce que c'est la semaine de la conférence CRYPTO et que la plupart des (bons :-) cryptographes y sont :-)
En passant, il y a bien d'autres collisions : voir les titres de la rump session d'hier soir (qui était webcasté, mais c'était durant la muit pour l'Europe). http://www.iacr.org/conferences/crypto2004/C04RumpAgenda.pdf et surtout le preprint http://eprint.iacr.org/2004/199/
Comme vient de le dire Eli Biham durant la présentation de son papier "SHA-1 is not yet broken" "SHA-1 n'est pas encore cassé".
Mais cela va un peu s'exciter dans les chaumières sécurisées : qui utilise encore MD5 ?
Une collision a été trouvé sur SHA-0 en utilisant un algo de Antoine Joux (une amélioration de ses résultats de 98 avec Chabaud qui utilise aussi une technique de Biham et Chen sur les "neutral bit") : http://www.mail-archive.com//msg02554.html
Valeur de haché commune : c9f160777d4086fe8095fba58b7e20c228a4006b
Il suffit de faire "openssl sha file.bin" sur un fichier binaire dont le contenu est l'un de deux précédent pour reproduire le résultat.
Rapellons que SHA-0 est la première version de l'algorythme SHA, qui a été précipitament retiré par le NSA suite à la découverte d'une faiblesse que le NSA n'a jamais publié.
L'attaque a pris environ 80 000 heures CPU sur le système TERA NOVA (256 Intel-Itanium2 de BULL SA, installé au labo TERA TECH du CEA DAM). La complexité de l'attaque est estimé à 2^51.
Apparement, ce système n'est pas listé dans le top 500 des super-ordinateurs de 2004. Ou bien s'agit-il en fait de l'ordinateur de Bull classé 227ème dont la description ressemble fortement ?
Quisquater
Concernant la probabilité de recevoir une météorite voir http://www.lemonde.fr/web/dh/0,@2-3208,39-23450327,0.html
Ce n'est vraiment pas le jour :-).
Thomas Pornin wrote:
According to Erwan David :
Par contre certains (Thomas Pornin ?) avaient comparé la probabilité de collision et celle de recevoir une météorite. Il semblerait que cela *aussi* soit arrivé... (http://fr.news.yahoo.com/040818/202/40h38.html)
Certes, certes. Mais il me semble bien avoir toujours pris les précautions oratoires d'usage, c'est-à-dire un genre de "sauf si on trouve une attaque spécifique à MD5, utilisant sa structure interne". Ce qui est le cas ici.
--Thomas Pornin
Concernant la probabilité de recevoir une météorite
voir
http://www.lemonde.fr/web/dh/0,14-0@14-0@2-3208,39-23450327,0.html
Ce n'est vraiment pas le jour :-).
Thomas Pornin wrote:
According to Erwan David <erwan@rail.eu.org>:
Par contre certains (Thomas Pornin ?) avaient comparé la probabilité
de collision et celle de recevoir une météorite. Il semblerait que
cela *aussi* soit arrivé... (http://fr.news.yahoo.com/040818/202/40h38.html)
Certes, certes. Mais il me semble bien avoir toujours pris les
précautions oratoires d'usage, c'est-à-dire un genre de "sauf si on
trouve une attaque spécifique à MD5, utilisant sa structure interne".
Ce qui est le cas ici.
Concernant la probabilité de recevoir une météorite voir http://www.lemonde.fr/web/dh/0,@2-3208,39-23450327,0.html
Ce n'est vraiment pas le jour :-).
Thomas Pornin wrote:
According to Erwan David :
Par contre certains (Thomas Pornin ?) avaient comparé la probabilité de collision et celle de recevoir une météorite. Il semblerait que cela *aussi* soit arrivé... (http://fr.news.yahoo.com/040818/202/40h38.html)
Certes, certes. Mais il me semble bien avoir toujours pris les précautions oratoires d'usage, c'est-à-dire un genre de "sauf si on trouve une attaque spécifique à MD5, utilisant sa structure interne". Ce qui est le cas ici.
--Thomas Pornin
Roland
Mais on est d'accord, cette attaque ne permet pas de fabriquer un message m2 qui aurait le même hash qu'un message m1 imposé.
Leur attaque conduit à découvrir deux puis plusieurs messages a priori quelconques qui ont le même hash.
Pouvez vous confirmer, les spécialistes ? Merci
Francois Grieu wrote:
Dans l'article <cfv5kh$dpf$, (Thomas Pornin) dit:
According to Xavier Roche :
Je n'ai pas encore compris ce que signifiait dans leur papier (http://eprint.iacr.org/2004/199.pdf) "Moreover, our attack works for any given initial value.". Initial value de quoi ?
MD5 fonctionne par applications successives d'une "fonction de compression" sur une valeur de 128 bits, en utilisant à chaque application un bloc de 512 bits de données comme "clé". Au tout début, il faut une valeur de 128 bits conventionnelle, dite "initial value (IV)", spécifiée dans la RFC. C'est cette valeur que les auteurs avaient initialement mal recopiée, avec cette histoire d'ordre des octets.
Ce qu'ils veulent dire, c'est que leur attaque marche quelque soit la valeur qu'on fixe pour cette IV, donc notamment celle de la RFC qui caractérise MD5.
Oui. Conséquences:
- En insérant 1024 bits qu'ils choisissent dans n'importe quel message que l'on leur impose (ainsi que l'endroit de l'insertion à un alignement de 512 bits près), les auteurs peuvent produire des messages distincts dont les hash MD5 sont identiques.
- En doublant la longeur de l'insertion, les auteurs peuvent doubler le nombre de messages distincts, tous en collision.
- Les auteurs peuvent construire des exécutables win32 ou autre, en collision, dont ils choisisent les comportements complètement distincts.
Noter que, en l'état, c'est légèrement moins puissant (mais beaucoup plus rapide) que la recherche de collision par la force brute, laquelle permet en outre (moyennant un doublement du travail) de produire des messages dont les débuts sont imposés mais DISTINCTS (et qui a besoin de choisir de l'ordre de 10 fois moins de bits).
Pour cette raison, je ne vois pas que l'attaque EN L'ETAT soit applicable à la fraude aux certificats SSL possible par la force brute [*] même si l'autorité de certification commet l'erreur d'autoriser l'usage de MD5 et de laisser le début du certificat entièrement prévisible.
François Grieu
[*] consistant à ce que l'attaquant soumette une requète de certification spécialement construite, puis transforme le certificat légitimement obtenu en un autre, différent mais utilisable pour se représenter comme une entité cible. <http://google.fr/groups?threadm=fgrieu-35E934.07012424052004%40individual.net>
Mais on est d'accord, cette attaque ne permet pas de fabriquer un
message m2 qui aurait le même hash qu'un message m1 imposé.
Leur attaque conduit à découvrir deux puis plusieurs messages a priori
quelconques qui ont le même hash.
Pouvez vous confirmer, les spécialistes ?
Merci
Francois Grieu wrote:
Dans l'article <cfv5kh$dpf$2@biggoron.nerim.net>,
pornin@nerim.net (Thomas Pornin) dit:
According to Xavier Roche <xroche@free.fr.NOSPAM.invalid>:
Je n'ai pas encore compris ce que signifiait dans leur papier
(http://eprint.iacr.org/2004/199.pdf) "Moreover,
our attack works for any given initial value.". Initial value de quoi ?
MD5 fonctionne par applications successives d'une "fonction de
compression" sur une valeur de 128 bits, en utilisant à chaque
application un bloc de 512 bits de données comme "clé". Au tout début,
il faut une valeur de 128 bits conventionnelle, dite "initial value
(IV)", spécifiée dans la RFC. C'est cette valeur que les auteurs avaient
initialement mal recopiée, avec cette histoire d'ordre des octets.
Ce qu'ils veulent dire, c'est que leur attaque marche quelque soit
la valeur qu'on fixe pour cette IV, donc notamment celle de la RFC
qui caractérise MD5.
Oui. Conséquences:
- En insérant 1024 bits qu'ils choisissent dans n'importe quel message
que l'on leur impose (ainsi que l'endroit de l'insertion à un
alignement de 512 bits près), les auteurs peuvent produire des
messages distincts dont les hash MD5 sont identiques.
- En doublant la longeur de l'insertion, les auteurs peuvent doubler
le nombre de messages distincts, tous en collision.
- Les auteurs peuvent construire des exécutables win32 ou autre,
en collision, dont ils choisisent les comportements complètement
distincts.
Noter que, en l'état, c'est légèrement moins puissant (mais beaucoup plus
rapide) que la recherche de collision par la force brute, laquelle permet
en outre (moyennant un doublement du travail) de produire des messages
dont les débuts sont imposés mais DISTINCTS (et qui a besoin de choisir
de l'ordre de 10 fois moins de bits).
Pour cette raison, je ne vois pas que l'attaque EN L'ETAT soit applicable
à la fraude aux certificats SSL possible par la force brute [*]
même si l'autorité de certification commet l'erreur d'autoriser
l'usage de MD5 et de laisser le début du certificat entièrement
prévisible.
François Grieu
[*] consistant à ce que l'attaquant soumette une requète de
certification spécialement construite, puis transforme le certificat
légitimement obtenu en un autre, différent mais utilisable pour se
représenter comme une entité cible.
<http://google.fr/groups?threadm=fgrieu-35E934.07012424052004%40individual.net>
Mais on est d'accord, cette attaque ne permet pas de fabriquer un message m2 qui aurait le même hash qu'un message m1 imposé.
Leur attaque conduit à découvrir deux puis plusieurs messages a priori quelconques qui ont le même hash.
Pouvez vous confirmer, les spécialistes ? Merci
Francois Grieu wrote:
Dans l'article <cfv5kh$dpf$, (Thomas Pornin) dit:
According to Xavier Roche :
Je n'ai pas encore compris ce que signifiait dans leur papier (http://eprint.iacr.org/2004/199.pdf) "Moreover, our attack works for any given initial value.". Initial value de quoi ?
MD5 fonctionne par applications successives d'une "fonction de compression" sur une valeur de 128 bits, en utilisant à chaque application un bloc de 512 bits de données comme "clé". Au tout début, il faut une valeur de 128 bits conventionnelle, dite "initial value (IV)", spécifiée dans la RFC. C'est cette valeur que les auteurs avaient initialement mal recopiée, avec cette histoire d'ordre des octets.
Ce qu'ils veulent dire, c'est que leur attaque marche quelque soit la valeur qu'on fixe pour cette IV, donc notamment celle de la RFC qui caractérise MD5.
Oui. Conséquences:
- En insérant 1024 bits qu'ils choisissent dans n'importe quel message que l'on leur impose (ainsi que l'endroit de l'insertion à un alignement de 512 bits près), les auteurs peuvent produire des messages distincts dont les hash MD5 sont identiques.
- En doublant la longeur de l'insertion, les auteurs peuvent doubler le nombre de messages distincts, tous en collision.
- Les auteurs peuvent construire des exécutables win32 ou autre, en collision, dont ils choisisent les comportements complètement distincts.
Noter que, en l'état, c'est légèrement moins puissant (mais beaucoup plus rapide) que la recherche de collision par la force brute, laquelle permet en outre (moyennant un doublement du travail) de produire des messages dont les débuts sont imposés mais DISTINCTS (et qui a besoin de choisir de l'ordre de 10 fois moins de bits).
Pour cette raison, je ne vois pas que l'attaque EN L'ETAT soit applicable à la fraude aux certificats SSL possible par la force brute [*] même si l'autorité de certification commet l'erreur d'autoriser l'usage de MD5 et de laisser le début du certificat entièrement prévisible.
François Grieu
[*] consistant à ce que l'attaquant soumette une requète de certification spécialement construite, puis transforme le certificat légitimement obtenu en un autre, différent mais utilisable pour se représenter comme une entité cible. <http://google.fr/groups?threadm=fgrieu-35E934.07012424052004%40individual.net>
Grindipo
Rolanda demandé :
Mais on est d'accord, cette attaque ne permet pas de fabriquer un message m2 qui aurait le même hash qu'un message m1 imposé. Pour l'instant, on laisse le choix des deux messages aux attaquants.
Leur attaque conduit à découvrir deux puis plusieurs messages a priori quelconques qui ont le même hash. Même si c'est "plus facile" d'obtenir une collision que de trouver un jumeau
à un message choisi, ça pose quand même des problèmes de sécurité. En construisant une collision et en faisant "certifier" l'un des messages par son hash, l'autre sera aussi "certifié" sans avoir été examiné (mouais, je n'ai pas été bien clair)
Pouvez vous confirmer, les spécialistes ? Ah, zut je ne suis pas spécialiste. On va alors considérer que ce n'est
qu'une opinion ;)
Une question : les collisions sur md5, c'est tout nouveau ? Quand ont-elles été trouvées ?
Grindipo
Rolanda demandé :
Mais on est d'accord, cette attaque ne permet pas de fabriquer un
message m2 qui aurait le même hash qu'un message m1 imposé.
Pour l'instant, on laisse le choix des deux messages aux attaquants.
Leur attaque conduit à découvrir deux puis plusieurs messages a priori
quelconques qui ont le même hash.
Même si c'est "plus facile" d'obtenir une collision que de trouver un jumeau
à un message choisi, ça pose quand même des problèmes de sécurité.
En construisant une collision et en faisant "certifier" l'un des messages
par son hash, l'autre sera aussi "certifié" sans avoir été examiné (mouais,
je n'ai pas été bien clair)
Pouvez vous confirmer, les spécialistes ?
Ah, zut je ne suis pas spécialiste. On va alors considérer que ce n'est
qu'une opinion ;)
Une question : les collisions sur md5, c'est tout nouveau ? Quand ont-elles
été trouvées ?
Mais on est d'accord, cette attaque ne permet pas de fabriquer un message m2 qui aurait le même hash qu'un message m1 imposé. Pour l'instant, on laisse le choix des deux messages aux attaquants.
Leur attaque conduit à découvrir deux puis plusieurs messages a priori quelconques qui ont le même hash. Même si c'est "plus facile" d'obtenir une collision que de trouver un jumeau
à un message choisi, ça pose quand même des problèmes de sécurité. En construisant une collision et en faisant "certifier" l'un des messages par son hash, l'autre sera aussi "certifié" sans avoir été examiné (mouais, je n'ai pas été bien clair)
Pouvez vous confirmer, les spécialistes ? Ah, zut je ne suis pas spécialiste. On va alors considérer que ce n'est
qu'une opinion ;)
Une question : les collisions sur md5, c'est tout nouveau ? Quand ont-elles été trouvées ?
