SHA-1 est tombé

Francois Grieu wrote on 29/08/2005 10:30:

[..] son système ne sera pas cassé par une
faiblesse de SHA-1 dans les 10 ans qui viennent.

grand merci pour toutes vos réponses.

Sylvain.

Francois Grieu wrote:

Ces attaques permettent de produire DEUX messages
distincts ayant le même hash, y compris si l'essentiel

Voilà. Donc en pratique la seule fonction du cryptosystème qui est
cassée c'est celle de non répudiation de la signature, par le
signataire lui-même.

Par exemple je signe un contrat dans lequel je m'engage à acheter des
bananes à 400 € la tonne, en me débrouillant pour que le dcument
signé contienne une partie non lisible dans laquelle je peux
positionner comme je veux 128 bits sans en modifier la signification
(ce qui est facile avec tous les formats de documents un peu riches
communs, comme word ou pdf).

Eh bien avec cette attaque je peux trouver un deuxième contrat,
identique pour un humain, si ce n'est qu'il mentionne cette fois le
prix de 200 € la tonne, et qui générera la même sign ature.

La contreparte croit donc avoir un contrat ferme à 400 €/t, ma is en
fait il ne tient que pour elle puisque je peux quand je veux exhiber la
version à 200 €/t et prétendre que c'est celle-là qu e j'ai signée
initialement. Donc concrètement cela me permet de répudier mon
contrat puisque personne ne pourra prouver lequel des deux j'ai
vraiment signé.

Le risque est donc assez limité puisqu'il suppose une volonté de
fraude de la part du signataire.

Le risque devient par contre beaucoup plus important si le signataire
est assez imprudent pour signer tel quel des données qu'on lui envoit.
Dans ce cas je peux faire signer ce même contrat à 400 €/ t par la
contrepartie, lui voler le texte initial de manière à ce qu'elle ne
puisse plus le produire, et exiger l'application du contrat à 200
€/t. Il suffit pour éviter cela que la contrepartie ne modifie ne
serais-ce qu'un bit au contrat avant de le signer pour que l'attaque
soit déjouée.

JL.

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).
[...]

Bonjour.

Un fichier Word pour Windows* pourrait il remplir les
conditions ci-dessus ?

Salutations

JPP

* avec plusieurs dizaines de ko dont on ignore largement
l'utilisation, et même l'utilité.

--
Enlevez le NO du spam et .invalid pour me répondre

"Dans les champs de l'observation, le hasard ne favorise que les esprits
préparés." Louis Pasteur

Dans l'article <431538e2$0$13837$636a15ce@news.free.fr>,
jpeps <jpeps.NOspam.box@online.fr.invalid> a écrit:

Un fichier Word pour Windows* pourrait il remplir les
conditions [qui permettent à l'attaque de Xiaoyun Wang
et se collègues de fonctionner]

Oui, le format de fichier Word convient pour faire deux
fichiers que Word accepte d'ouvrir, qui sont différents
(au sens de fichiers différents), et de même hash. Il
suffit d'avoir une zone de 190 octets environ
que l'on peut changer arbitrairement, ce n'est pas trop
difficile (il est facile de localiser de telles zones
inutilisées dans un document Word, et je crois bien
qu'il suffit d'ajouter des donées à la fin, et que Word
n'en fait rien !)

Il est par contre plus difficile de faire que Word
affiche et/ou imprime des choses différentes pour ces
fichiers différents, et surtout des choses où la
différence soit visible et fasse sens. Toutefois ce
n'est pas perdu, notemment grace aux macros que peut
contenir un doc Word, et/ou au fait qu'il peut contenir
du postscript (dans les images) je crois. Je ne sais
pas au juste si c'est possible, mais il faut faire comme
si cela l'était.

A nouveau: l'attaque ne permet PAS de produire un
document qui a la même signature qu'un autre document
arbitraire, word ou pas. L'attaque prépare les DEUX
documents différents qui ont le même hash.


François Grieu

Francois Grieu wrote:

Il est par contre plus difficile de faire que Word
affiche et/ou imprime des choses différentes pour ces
fichiers différents, et surtout des choses où la
différence soit visible et fasse sens. Toutefois ce
n'est pas perdu, notemment grace aux macros que peut
contenir un doc Word

Cependant les dites macro peuvent aussi se reposer sur la date ou autres
éléments externes variables pour faire des choses totalements
différentes pour un même document avec une signature donnée, ce qui
limite le scénario d'attaque vraiment novatrice grâce à cette collision.

En d'autre termes, si vous acceptez un document que des macro ou autre
élément qui le rendent dynamique, vous preniez déjà des risques avant.

Une question intéressante à ce sujet est de savoir quel est la
difficulté du calcul nécessaire pour retrouver l'autre moitié à partir
d'un bloc de donnée que l'on soupçonne très fort d'être la moitié d'une
des ces paires générant une collision, (en connaissant aussi le vecteur
d'initialisation qui correspond). Ce que l'on connait des ces paires me
donne l'impression qu'il y a des chances non négligeables que cette
opération soit "facile".

In article <dfh6el$3va$1@reader1.imaginet.fr>,
Jean-Marc Desperrier <jmdesp@alussinan.org> wrote:

En d'autre termes, si vous acceptez un document que des macro ou autre
élément qui le rendent dynamique, vous preniez déjà des risques avant.

Oui. D'ailleurs, avec les formats un peu complexes, il est
difficile d'être sur qu'il n'y a pas d'élément dynamique.
Par exemple, il est plausible qu'un document contienne une
image au format Postscript encapsulé, format qui peut contenir
un vrai programme, et donc qu'un même document s'imprime
de manière complètement différente selon le contexte (modèle
d'imprimante...)
[je ne sais pas si c'est possible avec Word, mais cela
l'est avec d'autres logiciels]

Autre exemple un peu limite: avec certains algoritmes de
sous-échantillonages d'images 'bitmap', on peut construire deux
bitsmaps qui, ré-échantillées à deux résolutions différentes,
donnent deux résultats entièrement arbitraires.

Conséquence: il ne faudrait signer que ce que l'on a entièrement
construit sois-même, ou examiné bit à bit.

François Grieu

Francois Grieu wrote:

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é)

128 octets, c'est pas largement suffisant pour inserer un shellcode
dans un programme?

<mavie>
ayant decouvert recement le systeme de package pkgsrc, j'ai eu la
surpise de voir qu'il verifie chaque pacakge avec 2 fonctions
de hachage (SHA1 et RMD160)
</mavie>

Je me suis pris a penser qu'on avait la affaire a un des rares cas
en cryptographie ou utiliser plusieurs systemes en meme temps
augmentait effectivement la securite (meme si la comparaison avec
le chainage de differents block-cypher est un peut tiree par les
cheuveux). Mais est-ce qu'il s'agit effectivement d'un plus
grande securite, ou juste une illusion? En admentant que les deux
fonctions de hachage utilises comportent des faiblesses connues,
la securite du systeme utilisant les deux fonctions serait-elle
calculable?
En admetant qu'une collision soit generable avec la premiere fonction
avec les contraintes A, et une collision avec la seconde avec les
contraintes B, est-il demontrable que l'union des ensembles A et B
est l'ensemble vide?

--
case Pratiquez-vous la zone danse? O/N
Frequentez-vous des embroches? O/N
Etes-vous souvent en interface? O/N
Etes-vous cable? O/N

case wrote:

Francois Grieu wrote:

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é)
a noter que d'après ce qui s'est dit ici, il faut la collaboration de

l'émetteur du message initialement signé. il est donc important quand on
signe un contrat, de l'avoir écrit... quand on signe un programme, de
l'avoir écrit...

par contre un attaquant pourrait faire signer un programme ou un contrat
innocent, et faire appliquer ou publier un contrat ou un programme
dangereux.

d'autre part j'avais cru lire que cette attaque permettait à partir de 2
messages aussi différent que l'on souhaite, de générer des versions
légèrementes différentes (sur seulement 128(192fixes) octets)...

pratiquement "un Escroc" pourrait ecrire un contrat B1, "bonne affaire",
et A1 "arnaque", en réservant 128/192 octets libres dans le contenu
(données cachées dans Word, espaces ou données inutiles comme le nom de
participants, ou numéro de série, dans texte ou xml) ...
ensuite avec l'algo on modifie les deux contrats en B2 et A2 pour qu'ils
partagent le même hash H(A2)=H(B2), tout en ayant la même signification
utile que A1 et B1 respectivement
enfin on fait signer B2 par "le Couillon"... et plus tard on présente A2
en justice en disant que "le Couillon" a signé !
est-ce bien ca ?... parec que ici c'est pas ce qui est dit.


d'autre part pratiquement qui sautait quelle est le nombre de round pour
générer une paire frauduleuse de contenu chiffré ? est-ce inférieur ou
proche de 2^64, ou loin au dessus?

case <case@construct.ath.cx> écrit:

Francois Grieu wrote:

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é)

128 octets, c'est pas largement suffisant pour inserer un
shellcode dans un programme?

Cette question n'a pas grand sens: si l'attaquant doit
mettre ledit "shellcode" dans un segment de 128 octets
où les fichiers *diffèrent*, il n'est plus libre de
libre de choisir ces 128 octets, et donc l'attaque ne
s'applique pas.


Observations simplificatrices (?) mais exactes:

- l'attaque ne permet PAS de modifier un fichier arbitraire
sans en changer le hash.

- l'attaque ne permet PAS générer un fichier ayant un
hash arbitraire.

- l'attaque permet de générer DEUX fichiers qui ont le
même hash (facilement pour MD5 et SHA-0, théoriquement
pour l'instant pour SHA-1).

- ces DEUX fichiers peuvent par exemple contenir CHACUN
un "shellcode" ET un autre code, tous deux arbitraires,
et un aiguillage pour que le premier fichier soit un
programme qui exécute le "shellcode", et l'autre fichier
un programme qui exécute l'autre code.


Conclusion désabusée: après je ne sais combien de messages
sur le sujet, je ne parviens pas à faire passer dans quels
cas, finalement rares, les nouvelles attaques s'appliquent.


François Grieu

Alain <none@none.org> dit

d'autre part j'avais cru lire que cette attaque permettait à partir de 2
messages aussi différent que l'on souhaite, de générer des versions
légèrementes différentes (sur seulement 128(192fixes) octets)...

J'imagine que vous voulez dire: que cette attaque permettait à partir
de 2 messages aussi différent que l'on souhaite, de générer des versions
légèrementes différentes (sur seulement 128(192fixes) octets) de chacun
des 2 messages, et qu'elles aient le même hash.

Eh bien, non, l'attaque ne permet PAS cela.

L'attaqe permet de modifier UN message original arbitraire pour produire
DEUX messages ayant le même hash, CHACUN différant de l'original sur un
(ou plusieurs) bloc(s) d'un grosse centaine d'octet, la différence entre
les deux messages modifiés portant sur quelques bits par bloc, le contenu
des blocs étant imposé par l'attaque (et non choisi par l'attaquant).

pratiquement "un Escroc" pourrait ecrire un contrat B1, "bonne affaire",
et A1 "arnaque", en réservant 128/192 octets libres dans le contenu
(données cachées dans Word, espaces ou données inutiles comme le nom de
participants, ou numéro de série, dans texte ou xml) ...
ensuite avec l'algo on modifie les deux contrats en B2 et A2 pour qu'ils
partagent le même hash H(A2)=H(B2), tout en ayant la même signification
utile que A1 et B1 respectivement
enfin on fait signer B2 par "le Couillon"... et plus tard on présente A2
en justice en disant que "le Couillon" a signé !
est-ce bien ca ?...

Non.

L'escroc doit construire un fichier contenant à la fois "bonne affaire"
et "arnaque", et affichant (et/ou imprimant) l'un ou l'autre selon la valeur
dans un bloc que l'attaque modifie. C'est facile si le fichier est du code
exécutable, et envisageable si c'est du code interprété (Postscript, PDF,
Javascript, Java, Visual Basic..). Avec du texte brut, cela n'est pas
possible. Avec un document Word, je ne connais pas de démonstration, mais
il faut supposer que c'est possible.


François Grieu