SHA-1 est tombé

On Mon Aug 22 2005 at 10:57, MiF wrote:

Encore les chinois :-(
http://www.theregister.co.uk/2005/08/19/sha-1_attack/

Non, il n'est pas encore tombé. Il reste aussi sûr qu'un hash de 128
bits qui serait parfait. On verra bien ce que l'avenir réserve...

--
http://arboi.da.ru/
PGP key ID : 0x0BBABA91 - 0x1320924F0BBABA91
Fingerprint: 1048 B09B EEAF 20AA F645 2E1A 1320 924F 0BBA BA91

Il faut quand même relativiser. C'est une attaque qui permet de générer une
collision à partir d'entrées aléatoires. Ce qui est beaucoup plus facile que
de trouver une collision à partir d'une entrée donnée. Or c'est cela qui est
nécessaire pour compromettre la sécurité d'un cryptosystème reposant sur
SHA-1.

JL.

JL wrote on 27/08/2005 18:54:

Il faut quand même relativiser. C'est une attaque qui permet de générer
une collision à partir d'entrées aléatoires. Ce qui est beaucoup plus
facile que de trouver une collision à partir d'une entrée donnée. Or
c'est cela qui est nécessaire pour compromettre la sécurité d'un
cryptosystème reposant sur SHA-1.

dans cet esprit, diriez-vous qu'il existe un risque objectif pour un
hash calculé sur, disons, une dizaine de kilo-octets de données
disposant d'une "certaine liberté d'entropie".

je pense par exemple une image où on peut jouer à volonté sur des points
tant que l'aspect général ne parait pas modifié - j'entends bien sur
substituer une image à hash connu par une autre différente qui serait
ajustée pour produire le même hash.

merci pour tout estimation qualitative du risque.

Sylvain.

Dans l'article <4310a51b$0$17244$8fcfb975@news.wanadoo.fr>,
Sylvain <noSpam@mail.net> demande

une estimation qualitative (..) du risque objectif pour
un hash calculé sur, disons, une dizaine de kilo-octets
de données disposant d'une "certaine liberté d'entropie".

Il faut bien comprendre que les attaques de Xiaoyun Wang
et ses sollègues contre MD5 et SHA-1 ne permettent PAS
de produire UN message ayant un hash arbitrairement imposé;
ni d'exhiber UN second message ayant le même hash qu'un
autre message arbitrairement imposé. Ceci quelque soit
le contenu et le format des messages, image ou pas, et la
"liberté d'entropie".

Ces attaques permettent de produire DEUX messages
distincts ayant le même hash, y compris si l'essentiel
du message est arbitrairement imposé, quand les 2
conditions suivantes sont réunies:

1) l'attaquant est libre de choisir une (ou des)
courte(s) section(s) du message (de l'ordre de 128
octets chacune) qui sera la seule (ou seront les seules)
où diffèreront les deux messages (l'emplacement de la ou
des sections dans le message peut être imposé à
l'attaquant, dans ce cas la taille de section augmente
de moitié)

2) l'attaquant connais au préalable le reste du message,
sauf éventuellement dans la portion qui suit la dernière
section (même si ce qui suit la dernière section change,
la collision se produit encore).

Pour MD5, le coût de l'attaque est très faible; pour
SHA-1, il serait environ 2^63 rounds, contre 2^80
pour la force brute.

Il convient toutefois de noter que l'attaque par la
force brute admet une extension simple à des messages
où l'attaquant est libre de choisir l'essentiel du
message, moyennant seulement un doublement du coût.
Ce n'est pas le cas dans la nouvelle attaque, qui par
conséquent est non applicable dans de nombreux cas
réels où la force brute le serait, par exemple la
certification X509 quand le début du certificat est
prévisible.

je pense par exemple à une image où on peut jouer à
volonté sur des points tant que l'aspect général ne
parait pas modifié

Transposées dans le contexte de messages codant une
image, les attaques de Xiaoyun Wang et ses sollègues
permettent de produire DEUX messages distincts ayant
le même hash et astreints à produire des images de
même apparence; ou ayant l'apparence d'une image
arbitrairement imposée; voire même ayant l'apparence
de deux images distinctes arbitrairement imposées.

L'effet sur les images du changement dans le message
dépend énormément du codage retenu pour l'image,
mais doit être considéré comme limitant très peu la
portée de l'attaque. Même pour pour un codage
complètement "brut de pixel", il n'y aura que
quelques pixels différents (avec les codages usuels:
pixels très différents mais peu nombreux) et cela
reste peu ou pas perceptible (l'attaquant peut agir
dans un coin, ou dans une petite zone très bruitée).
Pour d'autres codages, il est souvent possible à
l'adversaire de produire des fichiers comprenant des
sections de fichier non visualisées (commentaires,
zone au delà de la fin de l'expression du contenu de
l'image) et alors les images visualisées peuvent être
exactement identiques entre elles et/ou à l'original
imposé. Pour d'autres formats encore, il est possible
de mettre deux images arbitraires dans un même fichier
et que la section modifiée provoque l'affichage de
l'une ou de l'autre (format postscript, code
exécutable..)

Une conséquence de la faible latitude dont dispose
l'attaquant pour choisir les sections modifiées est
que, dans un codage "brut de pixel", les deux images
seront très proches; dans un format type postscript,
que le message devra être d'une taille suffisante
à la description des deux images.


François Grieu

Dans l'article <4310a51b$0$17244$8fcfb975@news.wanadoo.fr>,
Sylvain demande

une estimation qualitative (..) du risque objectif pour
un hash calculé sur, disons, une dizaine de kilo-octets
de données disposant d'une "certaine liberté d'entropie".

Il faut bien comprendre que les attaques de Xiaoyun Wang
et ses sollègues contre MD5 et SHA-1 ne permettent PAS
de produire UN message ayant un hash arbitrairement imposé;
ni d'exhiber UN second message ayant le même hash qu'un
autre message arbitrairement imposé. Ceci quelque soit
le contenu et le format des messages, image ou pas.

Ces attaques produisent DEUX messages distincts ayant le
même hash, y compris si l'essentiel du message est
arbitrairement imposé, quand les 2 conditions suivantes
sont réunies:

1) l'attaquant est libre de choisir une (ou des)
courte(s) section(s) du message (de l'ordre de 128
octets chacune) dans les DEUX messages, section
qui sera la seule (ou seront les seules) où diffèreront
les deux messages (l'emplacement de la ou des sections
dans le message peut être imposé à l'attaquant, dans ce
cas la taille de section augmente de moitié)

2) l'attaquant connais au préalable le reste du message,
sauf éventuellement dans la portion qui suit la dernière
section (même si ce qui suit la dernière section change,
la collision se produit encore).

Pour MD5, le coût de l'attaque est très faible; pour
SHA-1, il serait environ 2^63 rounds, contre 2^80
pour la force brute.

Il convient toutefois de noter que l'attaque par la
force brute admet une extension simple à des messages
où l'attaquant est libre de choisir l'essentiel du
message, moyennant seulement un doublement du coût.
Ce n'est pas le cas dans la nouvelle attaque, qui par
conséquent est non applicable dans de nombreux cas
réels où la force brute le serait, par exemple la
certification X509 quand le début du certificat est
prévisible.

Je pense par exemple à une image où on peut jouer à
volonté sur des points tant que l'aspect général ne
parait pas modifié - j'entends bien sur substituer
une image à hash connu par une autre différente qui
serait ajustée pour produire le même hash.

Eh bien non, cela n'est pas possible du tout avec
cette attaque (voir ci-dessous); l'attaquant doit
produire les DEUX messages.

Transposées dans le contexte de messages codant une
image, les attaques de Xiaoyun Wang et ses sollègues
permettent "seulement" de produire DEUX messages
distincts ayant le même hash et astreints à produire
des images de même apparence; ou ayant l'apparence
d'une image arbitrairement imposée; voire parfois
même ayant l'apparence de deux images distinctes
arbitrairement imposées, ce qui peut alors avoir une
conséquence pratique.

L'effet sur les images du changement dans le message
dépend énormément du codage retenu pour l'image, mais
doit être considéré comme ne limitant pas vraiment
la portée de l'attaque. Même pour pour un codage
complètement "brut de pixel", il n'y aura que quelques
pixels différents (avec un codage où 3 octets
consécutifs codent un pixel, l'attaquant doit choisir
un cinquantaine de pixels consécutifs, et il y en a
encore beaucoup moins qui diffèrent entre les deux
images). Cela reste peu ou pas perceptible (l'attaquant
peut agir dans un coin, ou dans une petite zone très
bruitée).
Pour d'autres codages, il est souvent possible à
l'adversaire de produire des fichiers comprenant des
sections de fichier non visualisées (commentaires,
zone au delà de la fin de l'expression du contenu de
l'image) et alors les images visualisées peuvent être
exactement identiques entre elles et/ou à l'original
imposé. Pour d'autres formats encore, il est possible
de mettre deux images arbitraires dans un même fichier
et que la section modifiée provoque l'affichage de
l'une ou de l'autre (format postscript, code
exécutable..)

Une conséquence de la faible latitude dont dispose
l'attaquant pour choisir les sections modifiées est
que, dans un codage "brut de pixel", les deux images
seront très proches; dans un codage type "postscript",
que le message devra être d'une taille suffisante pour
la description des deux images.


François Grieu

Francois Grieu wrote on 28/08/2005 14:25:

Bonjour François,

merci pour ces éléments de réponse.

Il faut bien comprendre que les attaques de Xiaoyun Wang
et ses sollègues contre MD5 et SHA-1 ne permettent PAS
de produire UN message ayant un hash arbitrairement imposé
[...]
Ces attaques permettent de produire DEUX messages
distincts ayant le même hash [...], quand les 2
conditions suivantes sont réunies:

1) l'attaquant est libre de choisir une (ou des)
courte(s) section(s) du message (de l'ordre de 128
octets chacune) qui sera la seule (ou seront les seules)
où diffèreront les deux messages [...]

2) l'attaquant connais au préalable le reste du message.

c'était ma compréhension - connaissant "l'état" du hash à un moment du
traitement on y sustitue des blocks différents des originaux qui
produiront le même digest final.

Transposées dans le contexte de messages codant une
image, les attaques de Xiaoyun Wang et ses sollègues
permettent de produire DEUX messages distincts ayant
le même hash et astreints à produire des images de
même apparence; ou ayant l'apparence d'une image
arbitrairement imposée; voire même ayant l'apparence
de deux images distinctes arbitrairement imposées.

ma question se place plus dans ce cas: on connait l'intégralité de
l'image d'origine et son hash, on souhaite la remplacer par une image
totalement différente (y compris si besoin en taille pour peu de garder
un ordre comparable) produisant le même hash.

les contraintes sur le codage de l'image se limiteront à un header court
(50 à 100 octets) (fixe en structure mais différent en données de celui
de l'original) et à un encodage JPG ou JP2 (choix indépendant de celui
de l'image d'origine).

est-ce ce problème se ramène à une attaque force brute ou est-ce que les
travaux de Xiaoyun Wang et ses collègues nous facilitent la tache ?

merci encore pour vos explications.
Sylvain.

Dans l'article <4311b53d$0$17248$8fcfb975@news.wanadoo.fr>,
Sylvain écrit:

ma question se place plus dans ce cas: on connait
l'intégralité de l'image d'origine et son hash,
on souhaite la remplacer par une image totalement
différente (y compris si besoin en taille pour peu
de garder un ordre comparable) produisant le même
hash.

On ne sait PAS le faire, ni par Xiaoyun Wang, ni par
une force brute plausible ! On peut produire deux
fichiers, l'un représentant l'image d'origine, l'autre
l'image totalement différente, et qui ont le même hash,
mais ce hash ne sera PAS celui du fichier de l'image
d'origine.

les contraintes sur le codage de l'image se limiteront à
un header court (50 à 100 octets) (fixe en structure mais
différent en données de celui de l'original) et à un
encodage JPG ou JP2 (choix indépendant de celui de
l'image d'origine).

La contrainte sur le codage de l'image pour pouvoir
utiliser Xiaoyun Wang, c'est que les deux fichiers,
qui diffèrent par quelques bits dans une section au
contenu fixé par l'attaque, affichent deux images
imposées et sans rapport. Avec du JPG ce n'est pas
trivial du tout, et je ne me hasarderais pas à parier
que c'est possible. Avec du EPS ou un programme
exécutable, c'est facile, au problème de compromis
qualité image / taille du message près.

est-ce que ce problème se ramène à une attaque force
brute ou est-ce que les travaux de Xiaoyun Wang et
ses collègues nous facilitent la tache ?

Si le signataire réalise lui-même l'acquisition de
l'image en un fichier, la meilleure attaque connue
est la force brute en 2^159 rounds de moyenne au moins.
Si le signataire accepte le fichier que vous lui
remettez (sans le modifier en son début de manière
imprévisible), deux cas se présentent:
- codage défavorable => force brute en 2^81 rounds de
moyenne environ
- codage favorable => Xiaoyun Wang en 2^69 parait-il
contre 2^80 rounds pour la force brute.

Conclusion pratique: avant de signer un message que l'on
a reçu d'un adversaire potentiel, et même si le message
a un contenu qui permet qu'il soit signé, il est prudent
de changer le début du message, de manière imprévisible.


François Grieu

Francois Grieu wrote on 28/08/2005 22:13:

Dans l'article <4311b53d$0$17248$8fcfb975@news.wanadoo.fr>,
Sylvain écrit:

ma question se place plus dans ce cas: on connait
l'intégralité de l'image d'origine et son hash,
on souhaite la remplacer par une image totalement
différente (y compris si besoin en taille pour peu
de garder un ordre comparable) produisant le même
hash.

On ne sait PAS le faire, ni par Xiaoyun Wang, ni par
une force brute plausible ! On peut produire deux
fichiers, l'un représentant l'image d'origine, l'autre
l'image totalement différente, et qui ont le même hash,
mais ce hash ne sera PAS celui du fichier de l'image
d'origine.

merci Françaois pour ces compléments, mais j'ai encore une doute sur ma
compréhension puisque vous indiquez que l'on peut produire "deux
fichiers qui ont le même hash" qui ne serait pas "le hash d'origine".

je comprends cela comme une possibilité de modifier l'image d'origine à
la volée en n'interférant pas ensuite son procédé de hash (puis
signature) mais en faisant en sorte que ces modifications permettent de
forger une image différente à hash identique.

ce point indique que dans le cas normal (on l'espère) où l'image
préalable n'a pas pu être "préparée", trouver une 2nd image à hash
identique a la difficulté habituelle.

ceci m'éclaire complétement sur les conditions d'application de la
"faiblesse".

est-ce que ce problème se ramène à une attaque force
brute ou est-ce que les travaux de Xiaoyun Wang et
ses collègues nous facilitent la tache ?

Si le signataire réalise lui-même l'acquisition de
l'image en un fichier, la meilleure attaque connue
est la force brute en 2^159 rounds de moyenne au moins.

j'ouvre la question - je m'interroge sur la "résistance" du hash au delà
de l'actualité Xiaoyun Wang.

on suppose ici une image non formattée pour faciliter une attaque
ultérieure et de 10 à 20 ko.

on souhaite une garantie (je ne dis pas conjecture ou spéculation) qu'il
restera pratiquement impossible de forger une autre image (en
s'autorisant toute modification d'aspect) qui produise le même hash et
ce sur une période de 5 ou 10 ans.

la question n'est donc pas liée à l'opération de signature - il existe
bien une signature ECDSA ou RSA d'un blob signed data contenant le hash
de l'image, générée une fois pour la période donnée - mais plus sur la
difficulté de substituer le message (l'image) qui n'est pas directement
inclut dans la signature, la question ne porte que sur d'éventuelles
collisions.

une variante à la question pourrait être: est-ce que SHA1 est suffisant
(indépendemment de l'actualité de la semaine) ou est-ce que SHA2-256
serait plus sage ?

merci pour vos éléments.
Sylvain.

Sylvain wrote on 28/08/2005 23:22:

la question n'est donc pas liée à l'opération de signature [...]

je veux dire que l'environnement de signature est sur - même si le
signataire ne réalise pas l'acquisition numérique de l'image, il est
digne de confiance et communique avec le signer de manière sécurisé.

Sylvain.

Dans l'article <43122b1d$0$27409$8fcfb975@news.wanadoo.fr>,
Sylvain <noSpam@mail.net> écrit:

je comprends cela comme une possibilité de modifier l'image d'origine à
la volée en n'interférant pas ensuite son procédé de hash (puis
signature) mais en faisant en sorte que ces modifications permettent de
forger une image différente à hash identique.

ce point indique que dans le cas normal (on l'espère) où l'image
préalable n'a pas pu être "préparée", trouver une 2nd image à hash
identique a la difficulté habituelle.

Je confirme ! Toute les attaques sont immensément aidées si l'adversaire
peut manipuler l'original; pour la force brute, on gagne en facteur
2^79 (à un cheval près); les attques récentes se placent dans ce
contexte.

on suppose ici une image non formattée pour faciliter une attaque
ultérieure et de 10 à 20 ko.

on souhaite une garantie (je ne dis pas conjecture ou spéculation)
qu'il restera pratiquement impossible de forger une autre image
(en s'autorisant toute modification d'aspect) qui produise le même
hash et ce sur une période de 5 ou 10 ans.

une variante à la question pourrait être: est-ce que SHA1 est suffisant
(indépendemment de l'actualité de la semaine) ou est-ce que SHA2-256
serait plus sage ?

Illustrons d'abord que la force brute n'est pas à craindre dès lors
que la préparation des messages hashés est digne de confiance.
Admettons que SHA-1 soit utilisé pour la signature de 2^32 photos
d'identitié (un big brother mondial), et que l'on attaque cela
avec 2^20 systèmes qui parviennent chacun à faire 2^24 essais par
seconde pendant 8 ans, soit en gros 2^28 secondes. Par la force brute,
la probabilibité de parvenir à trouver une collision est de
2^(32+20+24+28-160) = 2^-56; il est des milliards de fois plus
probable que la terre soit, pendant ces 8 ans, atteinte par
un asteroide la rendant impropre à notre espèce, que de voir
cette tentative d'attaque couronnée de succès.

Je ne sais pas comment prévoir combien pourraient gagner les
progrès théoriques qui pourraient venir. Mais je pense que le
big brother ci-dessus peut dormir sur ses deux oreilles que son
système ne sera pas cassé par une faiblesse de SHA-1 dans les
10 ans qui viennent.


François Grieu