- milieu des années 90 - la NSA retire SHA-0 suite à une faiblesse non publiée
- 1998 - Antoine Joux publie une attaque sur SHA-0 (en 2^61, c'est-à-dire loin des possibilités de nos machines de l'époque)
- 2004 - Amélioration de l'attaque (en 2^51, c'est encore difficile à faire avec nos PC de bureaux)
De toute façon la collision est donnée dans le message, il te suffit d'essayer.
Le mec ne pretend rien, il fait suivre un message d'un autre mec -- et l'autre mec avait deja envoye son annonce la semaine passee sur une autre liste de cryptographie, donc ce n'est pas une nouveaute pour les cryptologues. Et peut-etre que cette mailing-liste est serieuse et que les gens n'ecrivent pas 100'000 reponses pour dire "ouah, ca marche" ou "de toute facon, il y a que les l053r3 qui utilisent encore SHA-0", et autres trucs du gens. Bref, tout ca explique le manque de reponses.
Pour ce qui est de savoir si c'est de l'info ou de l'intox, le mail contient les explications detailles pour pouvoir reproduire la collision, il n'y a qu'a essayer soi-meme (la bonne vieille methode scientifique...).
MD5 et SHA sont des algorithmes de hachage (calcul d'empreinte), pas de cryptage.
J'ai lu vite fait (boulot boulot), mais apparemment ils ont repéré des collisions : ils prouvent par l'exemple que le calcul de l'empreinte de 2 fichiers différents donne des résultats identiques. A partir de ce moment là, on peut dire que c'est "cassé", car on n'est plus du tout sûr de l'intégrité d'un fichier à partir d'un SHA ou d'un MD5.
Faudrait refaire le calcul de ces hash pour voir :)
Un algorithme de hashing a toujours des collisions toujours... pour dire qu'un algorithme de hashing est "cassé", ça signifie qu'il est "simple" ou du moins qu'il existe une technique pour trouver des collisions de façon certaines.
Trouver une collision ne casse pas un algo de hash, mais trouver une methode pour trouver des collisions oui.
Common hash value (can be found using for example "openssl sha file.bin"
after creating a binary file containing any of the messages)
c9f160777d4086fe8095fba58b7e20c228a4006b
This was done by using a generalization of the attack presented at Crypto'98
by Chabaud and Joux. This generalization takes advantage of the iterative
structure of SHA-0. We also used the "neutral bit" technique of Biham and
Chen (To be presented at Crypto'2004).
The computation was performed on TERA NOVA (a 256 Intel-Itanium2 system
developped by BULL SA, installed in the CEA DAM open laboratory
TERA TECH). It required approximatively 80 000 CPU hours.
The complexity of the attack was about 2^51.
Au fait, de toute façon, il me semble que ces calculs d'empreinte assurent juste que la probabilité de collision est très très faible non ? Donc bon cassé ... ils ont trouvé une collision quoi ...
Pour des calculs d'empreintes de fichiers banals ça reste amplement suffisant, vu le temps de calcul que ça prend pour les trouver, ces collisions ...
ils prouvent par l'exemple que le calcul de l'empreinte de 2 fichiers différents donne des résultats identiques. A partir de ce moment là, on peut dire que c'est "cassé", car on n'est plus du tout sûr de l'intégrité d'un fichier à partir d'un SHA ou d'un MD5.
haha :)
ça tout le monde le sait depuis l'invention du MD5.
si il n'y avait qu'une seule source possible pour un hachage donné, MD5 serait l'algorithme de compression le plus puissant du monde :D
sans rire, à une énorme quantité de données tu fais correspondre une toute petite quantité, c'est évident que cette fonction fais correspondre à plusieurs valeurs une même valeur. Il y a même des milliards de sources possibles. Le seul hic, c'est que le hachage est tellemtn "bouleversant" que 2 sources différentes donnant la même valeur sont totalement différentes. Et inversement si tu changes un bit dans la source tu change complètement la valeur du hash.
Donc si tu as un fichier valide (qui a un sens) et qui donne le bon hash, alors tu as une chance sur un milliard que ce ne soit pas le bon fichier.
En effet n'importe quelle autre source donnant le même hash n'est très probablement pas un fichier valide, car parmi toutes les chaines de bits pour une longueur donnée, une proportion extrêment faible a un sens informatique (programme exécutable, fichier d'une application, ...).
Enfin quelqu'un qui sait précisement de quoi il parle pour poster ! MERCI François !!!
Ca devient désespérant de se taper des dizaines de posts de gars qui cherchent à deviner 90% de ce qu'ils racontent, saturant la lecture des autres par une masse de conneries monumentales, juste parce qu'ils ressentent le besoin d'ouvrir leur gueule sur des sujets qui les exitent sans pour autant avoir jamais chercher à s'informer avant de ramener leur science obscure ...
(Et voila, je suis soulager d'avoir pu glisser mon coup de gueule généraliste dans un ptit coin, vous pouvez me moinsser maintenant)
Beaucoup de monde semble considérer ce post comme "pertinent", mais n'empêche que c'est faux aussi :)
Certes, une fonction associant à un ensemble de 256^n éléments, un élément pris parmi un ensemble de 2^128 éléments, n'a aucune chance d'être injective. Ce qui veut dire qu'il existe, forcément, des collisions.
Par contre, là où tu te trompes, c'est avec cette histoire de "sens informatique". Déjà, ça ne veut rien dire. Ensuite, il est assez facile de prouver que, pour la plupart des formats de fichiers donnés (voire même, pour tous ceux que je connais), il y a au moins deux fichiers valides qui ont le même hash, et même, pour un fichier donné, il y a forcément un fichier valide, mais différent, qui a le même hash.
Prenons, par exemple, un programme en C. Genre, un hello world (1):
int main() {
printf("Hello, world\n");
}
Prenons ensuite le programme suivant (2):
int main() {
char *u = "zhbvatvyvropeituuuuuuiuiu1337eoprjrnhiziopjpoerjiztopijgreopig";
printf("Goodbye, world\n");
}
Bien sûr, j'ai mis u au pif. Des combinaisons pour u, il y en a énormément, aussi. Si u est plus grand que la taille du hash, paf! on est plus injectif. Il y a forcément deux programmes (2) qui ont le même hash.
Si u est beaucoup plus grand que la taille du hash, et qu'on considère que la répartition est homogène, il y a même forcément un programme (2) qui a le même hash que le programme (1).
Ce qui fait qu'un hash est sûr, c'est non pas l'impossibilité théorique de la collision, mais l'impossibilité pratique de trouver deux messages en collision.
Dans l'exemple que je cite, en testant toutes les valeurs possibles de la chaîne de caractères u, je devrais pouvoir arriver à avoir n'importe quel hash à la fin. Mais ça veut aussi dire que, pour un hash de 128 bits, je devrai en moyenne en tester 2^127 afin d'arriver à mes fins, ce qui est censé être hors de portée, en un temps raisonnable, des moyens de calcul actuels. Si on veut "cracker" un hash, on a donc deux solutions:
* Soit avoir des moyens de calculs supérieurs aux moyens de calcul actuel
* Soit trouver une méthode pour avoir moins de 2^127 combinaisons possibles à tester
La deuxième méthode revient à trouver des faiblesses dans l'algorithme: si on trouve un moyen d'avoir des informations sur le message haché à partir du hash, alors on pourra exclude des combinaisons sans avoir à calculer leur hash. Si on arrive à trouver suffisamment de faiblesses dans l'algorithme, on peut revenir à un nombre de calculs accessible.
Merci ....
Je m'étais toujours demandé comment md5 & co fonctionnaent car si la chaîne md5 peut prendre n valeurs différentes, il y aura toujours n+x (x<0) fichiers dont on poura calculer le md5
Et il y aura toujours des fichiers avec le même md5
Toujours dans un soucis de précision, j'ajouterai qu'un algorithme de hashage tel que le sha ou le md5 est censé être irréversible. Ainsi il peut etre utilisé a des fins de "cryptage", par exemple pour stocker un mot de passe dans un fichier. Pour "decrypter", il n'y a donc théoriquement qu'une seule methode : on passe tous les mots de passes possibles et imaginables a la moulinette sha ou md5 et on verifie a chaque fois la somme du hash avec celle stocké dans le fichier sus-cité, et si ca concorde, alors c'est que le mot de passe qu'on a passé dans la moulinette est le bon.
Casser l'algo revient donc a dire dans ce cas, que justement, le mot de passe fournit a la moulinette n'est pas le bon, pourtant le hash concorde, en gros, faut imaginer quelqu'un qui s'autentifie avec votre compte, mais pas nécésairement VOTRE mot de passe, juste un autre mot de passe, le 1er trouvé qui a la meme somme de hash. Bref, c'est la foire :)
Dans le même ordre d'esprit, pourquoi le système ne fait il pas deux empreintes du mot de passe avec deux algorithmes de hashage différents (md5 et sha-1) ?
Quelle serait la probabilité pour qu'un faux mot de passe (ie. même empreinte) soit à la fois "compatible" md5 et sha-1 ?
Ce système rendrait il plus faible le système de protection actuel des accès par mot de passe ?
Quelle serait la probabilité pour qu'un faux mot de passe (ie. même empreinte) soit à la fois "compatible" md5 et sha-1 ?
Là on peut dire 0. Pour être exact il y a une chance sur 2^64 soit environ une chance sur 16 000 000 000 000 000 000. (16 milliards de millards). C'est plutôt faible non ?
Par contre réussir a génrer un "faux fichier" possédant a la fois le même MD5 et le même SHA-1 qu'un autre doit être monstrueux. Et le faux fichier doit avoir au final une taille assez importante, probablement plusieurs To.
Donc si vous voyez un fichier avec le bon SHA-1 et le bon MD5 mais qui fait plus de 4 Terra Octets de données, ne le téléchargez pas ! Si ca se trouve il a été spoofé !
Les collisions calculées dans les papiers d'Antoine Joux pour SHA-0 et Xiaoyun Wang et al. pour MD5 sont entre messages de même longueur (2048 bits pour SHA-0 et 1024 pour MD5).
Cela ne sert à rien. Mieux vaut ajouter des bits de hashage md5 et sha plutôt que d'ajouter des bit pour la taille du fichier. Ces bits supplémentaire seront plus intéressant que pour stocker la taille.
(Tu diminue la densisté des md5 et sha en augmentant le nombre de bits, et donc fiabilise beaucoup plus qu'en rajoutant la taille)
Les chances d'avoir deux fichiers qui possèdent le même hash MD5 et SHA-1 sont sans doute assez faibles. Par conséquent, si l'on trouve un fichier correspondant au deux empreintes alors il y a encore plus de chance que le fichier trouvé est le fichier qui correspond au message d'origine.
La double empreinte est peut être un afaiblissement de la sécurité au final.
Je ne suis pas assez spécialiste dans le domaine pour pouvoir répondre assez correctement, d'où mes intérrogations sur le sujet.
Les chances d'avoir deux fichiers qui possèdent le même hash MD5 et SHA-1 sont sans doute assez faibles. Par conséquent, si l'on trouve un fichier correspondant au deux empreintes alors il y a encore plus de chance que le fichier trouvé est le fichier qui correspond au message d'origine.
MD5 et SHA-1 ne sont pas facilement decryptables, Ce sont des hashs dont le but dans la transmission de données est d'assurer l'authenticité d'un fichier (eventuellement en clair). Pour chiffrer les données et faire des sigantures autant se rabattre sur des systèmes à clefs publiques beaucoup plus adaptés a ce genre de choses.
La double empreinte est peut être un afaiblissement de la sécurité au final.
En terme de sécurité, surtout si le message est déjà en clair (par exempel les RPMs de chez Mandrake) pas vraiment non.
J'ajouterais (puisqu'on est dans un soucis de précision) qu'un md5 d'un mot de passe court se cracke en quelques heures... en dessous de 7 caractères ça se compte même en minutes sur un bête PC...
Quelle est ta définition de "cryptage" ?
A priori crypter c'est "brouiller", "rendre illisible par un tiers", bref, le MD5 est bien du domaine de la crypto. Ce que n'est par contre par le MD5 c'est du "codage" (qui lui implique une manière de transmettre l'information, donc une non destruction du message d'origine).
A priori tu n'as pas cherché la définition dans un dictionnaire car "cryptage" n'existe pas. C'est une mauvaise traduction de l'anglais "to crypt" qui se dit en bon français chiffrer...
Chiffrer veut peut être dire "rendre illisible par un tiers" mais certainement pas "rendre illisible" tout court alors que le MD5 rend illisible tout court (vu qu'une infinité de binaires correspondent à un hash donné)
Bref MD5 n'est ni du cryptage, ni du chiffrement mais un algo de hachage comme dit plus haut.
Je met de coté la guerre cryptage/chiffrement. Mon terme n'est effectivement pas reconnue par l'académie française, même s'il est largement usité (je l'ai tout de même trouvé comme synonyme à chiffrement dans le premier dico où j'ai cherché). Que tu utilises "chiffrement/chiffrer" ou "cryptage/crypter" mon intervention est bien la même. En français académique il existe tout de même "cryptographie", donc la racine et le domaine existent.
Ce qui est illisible tout court n'est-il pas par nature illisible par un tiers ? est-ce que le chiffrage est par définition relisible par quelqu'un ? (c'est une vrai question).
Le dico de l'académie dit pour chiffrer : "Transcrire un texte en langage conventionnel pour en assurer le secret". Est-ce qu'on ne transcrit pas la donnée suivant une convention pour en assurer le secret ? il n'y a là aucune référence à la transformation inverse ou à la possibilité de relire le message original. J'en déduis donc que certains algos de hachage relèvent bien de la crypto et du chiffrement (et les deux dont on parle en font partie). Les hachage n'est pas exclusif de la crypto.
D'ailleurs je vois plus loin dans ce journal deux liens wikipedia, un pour les algos de hachage (de manière général) et un pour les "cryptographic hash". Je sais bien que là on parle de termes anglais, mais que tu utilises un terme barbare "cryptage" ou un terme bien propre de "chiffrement" le résultat est le même : certains algos de hash (dont md* et sha*) relèvent bien aussi de la crypto.
Ce n'est pas une gueguerre. Il y a trois mots chiffrer/déchiffrer et décrypter. Les deux premiers sont des opérations "licites" et la troisième vise, pour un tiers non autorisé, à casser un chiffrement.
Dans ta définition de chiffrer, il y a la notion d'assurer le secret d'un texte. Ceci implique la volonté d'à partir du secret retrouver le texte original donc le chiffrement n'a pas pour vocation à rendre illisible tout court (autant détruire le texte dans ce cas là). Le hachage, bien qu'étant un élément de la cryptographie, n'est en aucun cas du chiffrement vu qu'à un pseudo secret correspond une infinité de clair.
Donc le hachage, chiffrement/déchiffrement, cryptanalyse sont bien des éléments de la cryptographie mais il ne s'agit pas de la même chose. Tout cela est énormément lié aux mathématiques où chaque définition à son sens et son importance, c'est pour cela qu'il faut faire attention aux mots.
""il y a la notion d'assurer le secret d'un texte. Ceci implique la volonté d'à partir du secret retrouver le texte original donc le chiffrement n'a pas pour vocation à rendre illisible tout court (autant détruire le texte dans ce cas là)."""
Clairement non. On peut vouloir assurer le secret sans impliquer un décodage ni que ce soit aussi bien de tout détruire. Les algos dont on parle en son des bons exemples. Je ne vois pas l'implication là où tu la vois. Je ne vois pas non plus dans les définitions que j'ai pu trouver du chiffrement, que les transformations doivent être injectives (même si effectivement ça doit être l'essentiel des applications utiles).
Ceci dit c'est toi qui m'a dit que le crytage était en fait du chiffrement en bon français. Et maintenant tu me dis que c'est de la crypto mais pas du chiffrement. A priori il aurait bien fallu remplacer par "cryptographie" d'après toi, pas par chiffrement (et comme c'est la même racine on peut penser que le sens est plus proche).
On n ese laisse pas aller a la paranoia, on est encore très loin du moment ou ca va devenir dangereux.
Pour l'instant un super calculateur Bull a reussit en 80 000 heures de calculs CPU a générer deux fichiers qui on le même SHA0. L'algorithme est de complexité 2^51.
On est encore très loin du moment ou on va pouvoir remplacer un fichier existant par un autre avec un trojan en rajouter des données "poubelle" a la fin du fichier pour obtenir le même md5.
Bref remplacer le fichier ftp.rpm par un virus en gardant le même MD5 c'est pas pour tout de suite.
Il y a définitevement une faille, des gens plus ou moins bien intentionnés vont probablement s'en servir un jour, mais pas avant plusieurs années.
Vous pouvez continuer a utiliser SHA0 un petit moment, et ceux d'entre vous qui paniquent peuvent soit faire un couple SHA0( ou 1)/MD5 soit faire du MD5+Signature du binaire.
Ceux qui ont pris l'habitude de signer des hashs pour une double sécurité, devraient commencer a songer sérieusement a signer les binaires ou a signer des couples de hashs.
t'a l'air de t'y connaitre donc j'en profite pour une petite question : est-ce que cette faiblesse de SHA-0 existe aussi dans les nouveaux SHA-256 ; SHA-384 et SHA-512 ?
t'a l'air de t'y connaitre donc j'en profite pour une petite question : est-ce que cette faiblesse de SHA-0 existe aussi dans les nouveaux SHA-256 ; SHA-384 et SHA-512 ?
C'est vrai j'ai l'air ? Chouette je vais pouvoir monter d'un cran mon pipomêtre.
Non sans rire, il s'agit là d'accadémiciens de très haut niveau qui ont découvert une faille en 1998 et une deuxième en 2004 dans un protocole considéré comme obsolète par ses inventeurs depuis 1994, je suis absolument pas au niveau de commenter leur recherche ou d'extrapoler sur les effets de bords.
En ce qui concerne les autres SHA, pour l'instant rien n'a été trouvé. Mais la première faille (celle du bit neutre trouvée en 1998) voit ses chances de se produire réduire au fur et a mesure que la force augmente. En plus les algos SHA-256 et plsu ont été modifiés par rapport a SHA-1 lequel était déjà une correction de SHA-0 (Le RSA savait par preuve mathématiques qu'il y avait une faille dans SHA0, mais ils ne savaient pas ou et quoi). Ceci étant je n'ai pas entendu parler de la moindre alerte concernant les SHA > 0, mais il y a des rumeurs sur SHA1. Si elles sont fondées alors le problème pourrait bien remonté sur les autres SHA...
SHA0 était une variante de MD4, il est donc possible que les failles de SHA0 soient venus de MD4 et que celles-ci soient aussi remontés dans MD5 de façon plus ou moins abbatardie par les modifs de l'évolution MD4->MD5.
En fait, il ne faut pas se focaliser sur les 80 000 heures CPU... L'intérêt est plutôt qu'une faiblesse de l'algorithme a été mise en évidence, et qu'en général, d'autres faiblesses sont trouvées rapidement dans la foulée. La première faiblesse trouvée donne bien souvent d'autres idées à d'autres personnes.
Ça veut dire quoi ça? Ça ne correspond pas à la notion de complexité que je connais (en gros trouver un équivalent de la suite donnant le nombre d'opérations en fonction de la taille des données).
J'avoue que j'aimerais bien savoir aussi ce que ça veut dire !
Donc, si je résume, on sait qu'il y a des failles, mais il faut encore une puissance monstrueuse pour les exploiter ?
Et la probabilité de deux md5() identiques est donc quasi-nulle ?
> L'algorithme est de complexité 2^51.
Ça veut dire quoi ça?
En effet ce n'est pas une complexité au sens classique, exprimée en fonction de la taille des données à traiter (appelée "n"), genre O(n) ou O(n*log(n)).
Je crois que ça signifie qu'il faut tester jusqu'à 2^51 combinaisons différentes pour arriver à ses fins (alors qu'au total il y a beaucoup plus de combinaisons possibles).
SHA-[01] et MD5 sont des fonctions de hachage. Elles calculent une signature de longueur fixée par avance à partir d'un message quelconque. Comme toutes fonctions de hachage, il y a des collisions entre messages de même taille (plusieurs messages sur par exemple 2048 bits auront fatalement la même signature sur 160 bits).
Ce sont plus exactement des fonctions de hachage cryptographique, parce que les collisions sont difficiles à prévoir : il faut que la signature présente une apparence d'entropie, de hasard, de sorte qu'on ne puisse aisément trouver un faux message partageant une signature avec le message original.
La nouvelle sur SHA-0 [1] est que Antoine Joux a réussi à calculer une collision. Il a tout de même utilisé 80000 heures de temps CPU sur un calculateur doté de 256 Itaniums2. Cela ne signifie pas (encore) qu'il soit capable de calculer une collision pour à peu près n'importe quel message. Mais cela ouvre des portes dans cette direction.
Les collisions sur MD5 [2] ont été calculées sur des messages plus courts (et cela fait quelques années que des collisions sur MD5 ont été trouvées, il est généralement recommandé d'utiliser SHA-1), et beaucoup plus vite.
Enfin, il reste la rumeur selon laquelle les techniques employées par Antoine Joux sur SHA-0 ont été appliquées avec succès sur SHA-1 [3]. C'est plus ennuyeux, car jusqu'à présent SHA-1 était considéré comme sûr. À suivre donc.
Enfin, pour votre correspondance personnelle ou pour vos paquets de distribution linux, rassurez-vous : la probabilité qu'une collision se fasse entre deux messages qui ont un sens (en français ou en tant que paquet linux) est nulle.
rassurez-vous : la probabilité qu'une collision se fasse entre deux messages qui ont un sens (en français ou en tant que paquet linux) est nulle.
Ben... ce qui m'a surpris dans le résultat (le premier lien que tu donnes), c'est que justement les deux fichiers en collisions se ressemblent beaucoup. À vue d'oeil, je ne vois qu'un ou deux chiffres hexa de différent par paquet de 8, et il semblerait qu'ils ne différent que de 1 bit. Les 7 premiers octets sont même inchangés!
Une variation moyenne de 1 bit par octet, c'est quand même très faible. La possibilité de transformer un texte lisible n'est pas si nulle (bon, ça remplacera peut-être du bon français en spam \/!@gr4)
dans ces algorithmes ( MD5 et SHA ), est-ce que la taille du fichier est prise en compte ?
et plus précisément est-ce que la méthode que cette personne dis avoir trouver permet de trouver deux fichiers ayant la meme signature mais aussi ayant exactement la meme taille ?
car si il suffit du couple signature + taille pour securiser un peu plus, c'est bon non ?
car si il suffit du couple signature + taille pour securiser un peu plus, c'est bon non ?
Bon déjà ca n'est aps vraiment un signature, c'est un hash.
Et ensuite la taille pour la certifier, il va bien falloir a un moment ou a un autre la hasher ou la signer non ?
Oui mais juste par un argument comptable on peut montrer que plusieurs fichier de même taille donne le même hash.
Vu que par exemple, l'ensemble des fichiers de 2048 bits sont hashé vers l'ensembles des hash (un hash fait 160bits). Donc on montre que l'ensemble de départ est plus gros que l'ensemble d'arrivée, comme l'algorithme de hashing nous garantit que pour toute entrée, j'aurais un hash de 160 bits, cela signifie donc que je suis capable de hasher l'ensemble de mes fichiers de 2048 bits et comme fatalement cet ensemble est plus grand que l'ensemble d'arrivée, il y aura des collisions.
Donc comme il y a des collisions, 2 fichiers au moins de 2048 bits, ont le même hash. cqfd
Mais cela signifie aussi qu'il n'y a pas collisions pour tout les fichiers de 2048 bits, certains hash ne correspondront qu'a un et un seul fichier de 2048 bits et d'autres non.
A chaque fichier correspond un hash... à un hash correspond un ou plusieurs fichiers de taille donnée.
Dans mon exemple, certains fichiers (bcp en fait) vont entrer en collisions et avoir donc le même hash. Mais comme on c'est restreint à l'ensemble des fichiers de 2048 bits, il n'est pas dis que chaque fichier à un fichier qui collisionne avec. Un hash peut alors correspondre à un fichier unique de 2048 bits (mais par contre il peut-être le hash d'un fichier 2049).
Ce que je voulais dire, c'est que tout les fichiers de l'ensemble ne rentre pas en collisions.
Ce que tu as vraiment dit, c'est que "certains hash ne correspondront qu'a un et un seul fichier de 2048 bits", ce qui est la même chose que "tout les fichiers de l'ensemble ne rentre pas en collisions", et ce qui est faux.
Exemple trivial de hash : H(x) = 1er caractère de X
Pour ce hash, TOUS les fichiers entrent en collision.
Dis tu le fais exprès... je donne un exmple avec un hash de 160 bits non trivial comme le tiens... ce que tu dis là est évident mais déforme ce que j'explique et donc non pertinent.
Ce que tu voulais dire est juste, ce que tu as dit est faux...
Tu a dis à l'origine
1- "cela signifie aussi qu'il n'y a pas collisions pour tout les fichiers de 2048 bits" c'est à dire que le simple dénombrement prouve qu'il existe au moins un fichier ne partageant son hash avec aucun autre ; ce qui est faux, il n'y a aucune implication
2- "certains hash ne correspondront qu'a un et un seul fichier de 2048 bits et d'autres non" c'est à dire il existe au moins un hash correspondant à un fichier et un seul, ce qui est une affirmation distincte de la précédente (et sans lien logique avec elle), et pour laquelle il n'y a pas non plus d'implication
On peut juste dire qu'il est certain que certains fichiers sont en collision, et que certains hashs correspondent à plusieurs fichiers (ce qui, dans ce sens, est lié).
Quand à savoir si tous les fichiers sont en collision, ou si tous les hashs correspondent à plusieurs fichiers (ce sont évidement deux questions distinctes), on peut seulement dire qu'on n'en sait rien, et qu'il est possible que non...
Il ne déforme pas, il te donne un contre exemple de l'assertion 1 (il aurait du dire tous les fichiers d'au moins deux caracteres).
Sa question est donc pertinente... mais bon, c'est pas bien grave, et je ne sais pas pourquoi j'en fais une telle tartine :)
maintenant si tu pose que ta variable x appartient a [a-z] et bien il n'y a aucune collision car dans ce cas H(x)= x.
C'est ce qu'il dit depuis tout a l'heure, "Tout fichier possede un Hash mais tout Hash ne correspond pas a un fichier".
La seul garantie, dans notre cas, est que le Hash de tout fichier sera dans cet ensemble [0 - 2^160[, aucunement que tout les elements de l'ensemble [0 - 2^160[ soit des hash possible de fichier de 2048 b ni meme que ces elements soit des hash d'un quelquonque fichier.
ds ton ensemble de fichiers de 2048 b, il y a 2^2048 fichiers possibles ; ds l'autre, il y a 2^160 fichiers possibles ; le plus gros est dc 2^(2048-160)=2^1888 fois plus gros.
d'un cote tu suppose qu'il existe des sommes qui ne correspondent qu'a un seul fichier, de mon cote je suppose qu'il n'existe pas de somme correspondant a plus de 2^1888 fichiers de 2048 b differents. Dans mon cas, je ne trouverais aucun resultats de la fonction de hashage correspondant a un unique fichier :/
maintenant la question est de savoir qui a raison - je n'ai pas donne plus de preuve que toi ;) -
Je n'ai pas fait le calcul et je vais reformuler... une preuve serait mieux m'enfin...
Ce que je voulais dire, c'est que tout les fichiers de l'ensemble ne rentre pas nécessairement en collisions.
Maintenant, peut-être que dans mon exemple c'est faux... je me demande d'ailleurs si il est possible de prouver qu'il y a un hash de 160 bits qui correspondra a un et un seul fichier de 2048 bits.
Mais je ne voulais de toutes façons pas en venir là, mais juste répondre à la question, existe-t-il des fichiers de même taille qui ont le même hash et la réponse est oui.
"Ce que je voulais dire, c'est que tout les fichiers de l'ensemble ne rentre pas nécessairement en collisions. " -> oui, c'est vrai, mais ce n'est pas ce que tu as dit :)
Ma fonction de hash: (je n'ai pas le définition exacte d'une fonction de hashage mais celle-ci à de bonne chance d'être correcte)
-> tous les fichiers donnent comme clef 00 sauf le fichier de 2048bits contenant que des 0 qui, lui, donne 01. la clef est sur 2 bits.
Conclusion, les resultats sur tous les fichiers possible me dit:
-> il existe des clef (10 et 11) qui ne correspondent pas à un fichier
-> il existe des clef (01) qui correspondent qu'à un seul fichier
-> il existe des clef (00) qui correspondant à plusieurs fichier
Sinon pour ceux qui ont du mal, je suggère qu'ils aillent d'abbord lire la définiton d'une fonction de hashage et d'une fonction de hashage cryptographique.
# Mince
Posté par cho7 (site web personnel) . Évalué à -1.
# Info ou Intox ?
Posté par blenderman . Évalué à 3.
Perso je pense que c'est une belle intox ... et vous ?
[^] # Re: Info ou Intox ?
Posté par jcs (site web personnel) . Évalué à 10.
- milieu des années 90 - la NSA retire SHA-0 suite à une faiblesse non publiée
- 1998 - Antoine Joux publie une attaque sur SHA-0 (en 2^61, c'est-à-dire loin des possibilités de nos machines de l'époque)
- 2004 - Amélioration de l'attaque (en 2^51, c'est encore difficile à faire avec nos PC de bureaux)
De toute façon la collision est donnée dans le message, il te suffit d'essayer.
[^] # Re: Info ou Intox ?
Posté par Yoan B (site web personnel) . Évalué à 9.
SHA-0, SHA-1, MD5, etc... sont des algorithmes destructifs par ex : sqrt(4) : 2 ou -2
Il est donc naturel qu'il y ait des collisions, l'ennui survient quand il est « facile » de trouver une collision.
[^] # Re: Info ou Intox ?
Posté par Zorglub . Évalué à 7.
> prétend avoir trouvé des collisions n'a pas recu une seule réponse a son
> message ... http://www.mail-archive.com/cryptography%40metzdowd.com/index.html#(...))
Le mec ne pretend rien, il fait suivre un message d'un autre mec -- et l'autre mec avait deja envoye son annonce la semaine passee sur une autre liste de cryptographie, donc ce n'est pas une nouveaute pour les cryptologues. Et peut-etre que cette mailing-liste est serieuse et que les gens n'ecrivent pas 100'000 reponses pour dire "ouah, ca marche" ou "de toute facon, il y a que les l053r3 qui utilisent encore SHA-0", et autres trucs du gens. Bref, tout ca explique le manque de reponses.
Pour ce qui est de savoir si c'est de l'info ou de l'intox, le mail contient les explications detailles pour pouvoir reproduire la collision, il n'y a qu'a essayer soi-meme (la bonne vieille methode scientifique...).
Zorglub
# MD5, un algo de cryptage ?
Posté par tito (site web personnel) . Évalué à 10.
Mon petit doigt me dit que tes rumeurs sont erronées :)
[^] # Re: MD5, un algo de cryptage ?
Posté par sherlokk . Évalué à 8.
J'ai lu vite fait (boulot boulot), mais apparemment ils ont repéré des collisions : ils prouvent par l'exemple que le calcul de l'empreinte de 2 fichiers différents donne des résultats identiques. A partir de ce moment là, on peut dire que c'est "cassé", car on n'est plus du tout sûr de l'intégrité d'un fichier à partir d'un SHA ou d'un MD5.
Faudrait refaire le calcul de ces hash pour voir :)
[^] # Hashing et collisions
Posté par allcolor (site web personnel) . Évalué à 10.
Trouver une collision ne casse pas un algo de hash, mais trouver une methode pour trouver des collisions oui.
[^] # Re: Hashing et collisions
Posté par passant·e . Évalué à 10.
http://www.mail-archive.com/cryptography%40metzdowd.com/msg02554.ht(...)
Common hash value (can be found using for example "openssl sha file.bin"
after creating a binary file containing any of the messages)
c9f160777d4086fe8095fba58b7e20c228a4006b
This was done by using a generalization of the attack presented at Crypto'98
by Chabaud and Joux. This generalization takes advantage of the iterative
structure of SHA-0. We also used the "neutral bit" technique of Biham and
Chen (To be presented at Crypto'2004).
The computation was performed on TERA NOVA (a 256 Intel-Itanium2 system
developped by BULL SA, installed in the CEA DAM open laboratory
TERA TECH). It required approximatively 80 000 CPU hours.
The complexity of the attack was about 2^51.
- une explication technique par ici : http://eprint.iacr.org/2004/199.pdf(...) ()
- une autre explication : http://www.rtfm.com/movabletype/archives/2004_08.html#001051(...)
- le code source : http://www.rtfm.com/md5coll.tar.gz(...)
- http://www.rtfm.com/movabletype/archives/2004_08.html(...)
bonne lecture et journée :-)
Je trolle dès quand ça parle business, sécurité et sciences sociales
[^] # Re: MD5, un algo de cryptage ?
Posté par sherlokk . Évalué à 9.
Pour des calculs d'empreintes de fichiers banals ça reste amplement suffisant, vu le temps de calcul que ça prend pour les trouver, ces collisions ...
[^] # Re: MD5, un algo de cryptage ?
Posté par Nap . Évalué à 10.
haha :)
ça tout le monde le sait depuis l'invention du MD5.
si il n'y avait qu'une seule source possible pour un hachage donné, MD5 serait l'algorithme de compression le plus puissant du monde :D
sans rire, à une énorme quantité de données tu fais correspondre une toute petite quantité, c'est évident que cette fonction fais correspondre à plusieurs valeurs une même valeur. Il y a même des milliards de sources possibles. Le seul hic, c'est que le hachage est tellemtn "bouleversant" que 2 sources différentes donnant la même valeur sont totalement différentes. Et inversement si tu changes un bit dans la source tu change complètement la valeur du hash.
Donc si tu as un fichier valide (qui a un sens) et qui donne le bon hash, alors tu as une chance sur un milliard que ce ne soit pas le bon fichier.
En effet n'importe quelle autre source donnant le même hash n'est très probablement pas un fichier valide, car parmi toutes les chaines de bits pour une longueur donnée, une proportion extrêment faible a un sens informatique (programme exécutable, fichier d'une application, ...).
[^] # Re: MD5, un algo de cryptage ?
Posté par RuleZ . Évalué à 6.
Ca devient désespérant de se taper des dizaines de posts de gars qui cherchent à deviner 90% de ce qu'ils racontent, saturant la lecture des autres par une masse de conneries monumentales, juste parce qu'ils ressentent le besoin d'ouvrir leur gueule sur des sujets qui les exitent sans pour autant avoir jamais chercher à s'informer avant de ramener leur science obscure ...
(Et voila, je suis soulager d'avoir pu glisser mon coup de gueule généraliste dans un ptit coin, vous pouvez me moinsser maintenant)
[^] # Re: MD5, un algo de cryptage ?
Posté par Gruik Man . Évalué à 7.
Certes, une fonction associant à un ensemble de 256^n éléments, un élément pris parmi un ensemble de 2^128 éléments, n'a aucune chance d'être injective. Ce qui veut dire qu'il existe, forcément, des collisions.
Par contre, là où tu te trompes, c'est avec cette histoire de "sens informatique". Déjà, ça ne veut rien dire. Ensuite, il est assez facile de prouver que, pour la plupart des formats de fichiers donnés (voire même, pour tous ceux que je connais), il y a au moins deux fichiers valides qui ont le même hash, et même, pour un fichier donné, il y a forcément un fichier valide, mais différent, qui a le même hash.
Prenons, par exemple, un programme en C. Genre, un hello world (1):
int main() {printf("Hello, world\n");
}
Prenons ensuite le programme suivant (2):
int main() {char *u = "zhbvatvyvropeituuuuuuiuiu1337eoprjrnhiziopjpoerjiztopijgreopig";
printf("Goodbye, world\n");
}
Bien sûr, j'ai mis u au pif. Des combinaisons pour u, il y en a énormément, aussi. Si u est plus grand que la taille du hash, paf! on est plus injectif. Il y a forcément deux programmes (2) qui ont le même hash.
Si u est beaucoup plus grand que la taille du hash, et qu'on considère que la répartition est homogène, il y a même forcément un programme (2) qui a le même hash que le programme (1).
Ce qui fait qu'un hash est sûr, c'est non pas l'impossibilité théorique de la collision, mais l'impossibilité pratique de trouver deux messages en collision.
Dans l'exemple que je cite, en testant toutes les valeurs possibles de la chaîne de caractères u, je devrais pouvoir arriver à avoir n'importe quel hash à la fin. Mais ça veut aussi dire que, pour un hash de 128 bits, je devrai en moyenne en tester 2^127 afin d'arriver à mes fins, ce qui est censé être hors de portée, en un temps raisonnable, des moyens de calcul actuels. Si on veut "cracker" un hash, on a donc deux solutions:
* Soit avoir des moyens de calculs supérieurs aux moyens de calcul actuel
* Soit trouver une méthode pour avoir moins de 2^127 combinaisons possibles à tester
La deuxième méthode revient à trouver des faiblesses dans l'algorithme: si on trouve un moyen d'avoir des informations sur le message haché à partir du hash, alors on pourra exclude des combinaisons sans avoir à calculer leur hash. Si on arrive à trouver suffisamment de faiblesses dans l'algorithme, on peut revenir à un nombre de calculs accessible.
[^] # Re: MD5, un algo de cryptage ?
Posté par Mildred (site web personnel) . Évalué à 1.
Je m'étais toujours demandé comment md5 & co fonctionnaent car si la chaîne md5 peut prendre n valeurs différentes, il y aura toujours n+x (x<0) fichiers dont on poura calculer le md5
Et il y aura toujours des fichiers avec le même md5
Donc ce n'est pas 100% sur
[^] # Re: MD5, un algo de cryptage ?
Posté par cho7 (site web personnel) . Évalué à 8.
Casser l'algo revient donc a dire dans ce cas, que justement, le mot de passe fournit a la moulinette n'est pas le bon, pourtant le hash concorde, en gros, faut imaginer quelqu'un qui s'autentifie avec votre compte, mais pas nécésairement VOTRE mot de passe, juste un autre mot de passe, le 1er trouvé qui a la meme somme de hash. Bref, c'est la foire :)
[^] # Re: MD5, un algo de cryptage ?
Posté par _seb_ . Évalué à 6.
Quelle serait la probabilité pour qu'un faux mot de passe (ie. même empreinte) soit à la fois "compatible" md5 et sha-1 ?
Ce système rendrait il plus faible le système de protection actuel des accès par mot de passe ?
[^] # Re: MD5, un algo de cryptage ?
Posté par Jerome Herman . Évalué à 10.
Là on peut dire 0. Pour être exact il y a une chance sur 2^64 soit environ une chance sur 16 000 000 000 000 000 000. (16 milliards de millards). C'est plutôt faible non ?
Par contre réussir a génrer un "faux fichier" possédant a la fois le même MD5 et le même SHA-1 qu'un autre doit être monstrueux. Et le faux fichier doit avoir au final une taille assez importante, probablement plusieurs To.
Donc si vous voyez un fichier avec le bon SHA-1 et le bon MD5 mais qui fait plus de 4 Terra Octets de données, ne le téléchargez pas ! Si ca se trouve il a été spoofé !
Kha
[^] # Re: MD5, un algo de cryptage ?
Posté par Nap . Évalué à 10.
[^] # Re: MD5, un algo de cryptage ?
Posté par Olivier Grisel (site web personnel) . Évalué à 1.
Exemple :
signature(fichier1) = hash_sha1(fichier1) ^ hash_md5(fichier1) ^ taille(fichier1)
(^ represente l'opérateur de concaténation)
quelle serait alors la probabilité de trouver un fichier2 qui ai la même signature que fichier1 ?
[^] # Re: MD5, un algo de cryptage ?
Posté par scylla . Évalué à 2.
[^] # Re: MD5, un algo de cryptage ?
Posté par Anonyme . Évalué à 3.
(Tu diminue la densisté des md5 et sha en augmentant le nombre de bits, et donc fiabilise beaucoup plus qu'en rajoutant la taille)
[^] # Re: MD5, un algo de cryptage ?
Posté par _seb_ . Évalué à 1.
La double empreinte est peut être un afaiblissement de la sécurité au final.
Je ne suis pas assez spécialiste dans le domaine pour pouvoir répondre assez correctement, d'où mes intérrogations sur le sujet.
[^] # Re: MD5, un algo de cryptage ?
Posté par Jerome Herman . Évalué à 1.
MD5 et SHA-1 ne sont pas facilement decryptables, Ce sont des hashs dont le but dans la transmission de données est d'assurer l'authenticité d'un fichier (eventuellement en clair). Pour chiffrer les données et faire des sigantures autant se rabattre sur des systèmes à clefs publiques beaucoup plus adaptés a ce genre de choses.
La double empreinte est peut être un afaiblissement de la sécurité au final.
En terme de sécurité, surtout si le message est déjà en clair (par exempel les RPMs de chez Mandrake) pas vraiment non.
Kha
[^] # Re: MD5, un algo de cryptage ?
Posté par tene . Évalué à 2.
[^] # Re: MD5, un algo de cryptage ?
Posté par Éric (site web personnel) . Évalué à -1.
A priori crypter c'est "brouiller", "rendre illisible par un tiers", bref, le MD5 est bien du domaine de la crypto. Ce que n'est par contre par le MD5 c'est du "codage" (qui lui implique une manière de transmettre l'information, donc une non destruction du message d'origine).
[^] # Re: MD5, un algo de cryptage ?
Posté par jojo2002 . Évalué à 6.
Chiffrer veut peut être dire "rendre illisible par un tiers" mais certainement pas "rendre illisible" tout court alors que le MD5 rend illisible tout court (vu qu'une infinité de binaires correspondent à un hash donné)
Bref MD5 n'est ni du cryptage, ni du chiffrement mais un algo de hachage comme dit plus haut.
[^] # Re: MD5, un algo de cryptage ?
Posté par Éric (site web personnel) . Évalué à 3.
Ce qui est illisible tout court n'est-il pas par nature illisible par un tiers ? est-ce que le chiffrage est par définition relisible par quelqu'un ? (c'est une vrai question).
Le dico de l'académie dit pour chiffrer : "Transcrire un texte en langage conventionnel pour en assurer le secret". Est-ce qu'on ne transcrit pas la donnée suivant une convention pour en assurer le secret ? il n'y a là aucune référence à la transformation inverse ou à la possibilité de relire le message original. J'en déduis donc que certains algos de hachage relèvent bien de la crypto et du chiffrement (et les deux dont on parle en font partie). Les hachage n'est pas exclusif de la crypto.
D'ailleurs je vois plus loin dans ce journal deux liens wikipedia, un pour les algos de hachage (de manière général) et un pour les "cryptographic hash". Je sais bien que là on parle de termes anglais, mais que tu utilises un terme barbare "cryptage" ou un terme bien propre de "chiffrement" le résultat est le même : certains algos de hash (dont md* et sha*) relèvent bien aussi de la crypto.
[^] # Re: MD5, un algo de cryptage ?
Posté par jojo2002 . Évalué à 4.
Dans ta définition de chiffrer, il y a la notion d'assurer le secret d'un texte. Ceci implique la volonté d'à partir du secret retrouver le texte original donc le chiffrement n'a pas pour vocation à rendre illisible tout court (autant détruire le texte dans ce cas là). Le hachage, bien qu'étant un élément de la cryptographie, n'est en aucun cas du chiffrement vu qu'à un pseudo secret correspond une infinité de clair.
Donc le hachage, chiffrement/déchiffrement, cryptanalyse sont bien des éléments de la cryptographie mais il ne s'agit pas de la même chose. Tout cela est énormément lié aux mathématiques où chaque définition à son sens et son importance, c'est pour cela qu'il faut faire attention aux mots.
[^] # Re: MD5, un algo de cryptage ?
Posté par Éric (site web personnel) . Évalué à -1.
Clairement non. On peut vouloir assurer le secret sans impliquer un décodage ni que ce soit aussi bien de tout détruire. Les algos dont on parle en son des bons exemples. Je ne vois pas l'implication là où tu la vois. Je ne vois pas non plus dans les définitions que j'ai pu trouver du chiffrement, que les transformations doivent être injectives (même si effectivement ça doit être l'essentiel des applications utiles).
Ceci dit c'est toi qui m'a dit que le crytage était en fait du chiffrement en bon français. Et maintenant tu me dis que c'est de la crypto mais pas du chiffrement. A priori il aurait bien fallu remplacer par "cryptographie" d'après toi, pas par chiffrement (et comme c'est la même racine on peut penser que le sens est plus proche).
# On reste sobre et on respire.
Posté par Jerome Herman . Évalué à 10.
Pour l'instant un super calculateur Bull a reussit en 80 000 heures de calculs CPU a générer deux fichiers qui on le même SHA0. L'algorithme est de complexité 2^51.
On est encore très loin du moment ou on va pouvoir remplacer un fichier existant par un autre avec un trojan en rajouter des données "poubelle" a la fin du fichier pour obtenir le même md5.
Bref remplacer le fichier ftp.rpm par un virus en gardant le même MD5 c'est pas pour tout de suite.
Il y a définitevement une faille, des gens plus ou moins bien intentionnés vont probablement s'en servir un jour, mais pas avant plusieurs années.
Vous pouvez continuer a utiliser SHA0 un petit moment, et ceux d'entre vous qui paniquent peuvent soit faire un couple SHA0( ou 1)/MD5 soit faire du MD5+Signature du binaire.
Ceux qui ont pris l'habitude de signer des hashs pour une double sécurité, devraient commencer a songer sérieusement a signer les binaires ou a signer des couples de hashs.
En bref, dormez en paix braves gens.
Kha
[^] # Re: On reste sobre et on respire.
Posté par patrick_g (site web personnel) . Évalué à 2.
[^] # Re: On reste sobre et on respire.
Posté par Jerome Herman . Évalué à 8.
C'est vrai j'ai l'air ? Chouette je vais pouvoir monter d'un cran mon pipomêtre.
Non sans rire, il s'agit là d'accadémiciens de très haut niveau qui ont découvert une faille en 1998 et une deuxième en 2004 dans un protocole considéré comme obsolète par ses inventeurs depuis 1994, je suis absolument pas au niveau de commenter leur recherche ou d'extrapoler sur les effets de bords.
En ce qui concerne les autres SHA, pour l'instant rien n'a été trouvé. Mais la première faille (celle du bit neutre trouvée en 1998) voit ses chances de se produire réduire au fur et a mesure que la force augmente. En plus les algos SHA-256 et plsu ont été modifiés par rapport a SHA-1 lequel était déjà une correction de SHA-0 (Le RSA savait par preuve mathématiques qu'il y avait une faille dans SHA0, mais ils ne savaient pas ou et quoi). Ceci étant je n'ai pas entendu parler de la moindre alerte concernant les SHA > 0, mais il y a des rumeurs sur SHA1. Si elles sont fondées alors le problème pourrait bien remonté sur les autres SHA...
SHA0 était une variante de MD4, il est donc possible que les failles de SHA0 soient venus de MD4 et que celles-ci soient aussi remontés dans MD5 de façon plus ou moins abbatardie par les modifs de l'évolution MD4->MD5.
Voilà a peu près totu ce que je sais.
Kha
[^] # Re: On reste sobre et on respire.
Posté par mac . Évalué à 3.
[^] # Re: On reste sobre et on respire.
Posté par mickabouille . Évalué à 4.
Ça veut dire quoi ça? Ça ne correspond pas à la notion de complexité que je connais (en gros trouver un équivalent de la suite donnant le nombre d'opérations en fonction de la taille des données).
[^] # Re: On reste sobre et on respire.
Posté par XHTML/CSS inside (site web personnel) . Évalué à 3.
J'avoue que j'aimerais bien savoir aussi ce que ça veut dire !
Donc, si je résume, on sait qu'il y a des failles, mais il faut encore une puissance monstrueuse pour les exploiter ?
Et la probabilité de deux md5() identiques est donc quasi-nulle ?
[^] # Re: On reste sobre et on respire.
Posté par Olivier Jeannet . Évalué à 2.
Ça veut dire quoi ça?
En effet ce n'est pas une complexité au sens classique, exprimée en fonction de la taille des données à traiter (appelée "n"), genre O(n) ou O(n*log(n)).
Je crois que ça signifie qu'il faut tester jusqu'à 2^51 combinaisons différentes pour arriver à ses fins (alors qu'au total il y a beaucoup plus de combinaisons possibles).
# Fonctions de hachage
Posté par scylla . Évalué à 10.
Ce sont plus exactement des fonctions de hachage cryptographique, parce que les collisions sont difficiles à prévoir : il faut que la signature présente une apparence d'entropie, de hasard, de sorte qu'on ne puisse aisément trouver un faux message partageant une signature avec le message original.
La nouvelle sur SHA-0 [1] est que Antoine Joux a réussi à calculer une collision. Il a tout de même utilisé 80000 heures de temps CPU sur un calculateur doté de 256 Itaniums2. Cela ne signifie pas (encore) qu'il soit capable de calculer une collision pour à peu près n'importe quel message. Mais cela ouvre des portes dans cette direction.
Les collisions sur MD5 [2] ont été calculées sur des messages plus courts (et cela fait quelques années que des collisions sur MD5 ont été trouvées, il est généralement recommandé d'utiliser SHA-1), et beaucoup plus vite.
Enfin, il reste la rumeur selon laquelle les techniques employées par Antoine Joux sur SHA-0 ont été appliquées avec succès sur SHA-1 [3]. C'est plus ennuyeux, car jusqu'à présent SHA-1 était considéré comme sûr. À suivre donc.
Enfin, pour votre correspondance personnelle ou pour vos paquets de distribution linux, rassurez-vous : la probabilité qu'une collision se fasse entre deux messages qui ont un sens (en français ou en tant que paquet linux) est nulle.
[1] http://www.mail-archive.com/cryptography%40metzdowd.com/msg02554.ht(...)
[2] http://eprint.iacr.org/2004/199/(...)
[3] http://www.freedom-to-tinker.com/archives/000661.html(...)
[^] # Re: Fonctions de hachage
Posté par daggett . Évalué à 3.
Ben... ce qui m'a surpris dans le résultat (le premier lien que tu donnes), c'est que justement les deux fichiers en collisions se ressemblent beaucoup. À vue d'oeil, je ne vois qu'un ou deux chiffres hexa de différent par paquet de 8, et il semblerait qu'ils ne différent que de 1 bit. Les 7 premiers octets sont même inchangés!
Une variation moyenne de 1 bit par octet, c'est quand même très faible. La possibilité de transformer un texte lisible n'est pas si nulle (bon, ça remplacera peut-être du bon français en spam \/!@gr4)
# une question pour l'inculte que je suis :
Posté par Seneque Xavier . Évalué à 1.
et plus précisément est-ce que la méthode que cette personne dis avoir trouver permet de trouver deux fichiers ayant la meme signature mais aussi ayant exactement la meme taille ?
car si il suffit du couple signature + taille pour securiser un peu plus, c'est bon non ?
my2cents
[^] # Re: une question pour l'inculte que je suis :
Posté par Jerome Herman . Évalué à 3.
Bon déjà ca n'est aps vraiment un signature, c'est un hash.
Et ensuite la taille pour la certifier, il va bien falloir a un moment ou a un autre la hasher ou la signer non ?
Kha
[^] # Re: une question pour l'inculte que je suis :
Posté par allcolor (site web personnel) . Évalué à 1.
Vu que par exemple, l'ensemble des fichiers de 2048 bits sont hashé vers l'ensembles des hash (un hash fait 160bits). Donc on montre que l'ensemble de départ est plus gros que l'ensemble d'arrivée, comme l'algorithme de hashing nous garantit que pour toute entrée, j'aurais un hash de 160 bits, cela signifie donc que je suis capable de hasher l'ensemble de mes fichiers de 2048 bits et comme fatalement cet ensemble est plus grand que l'ensemble d'arrivée, il y aura des collisions.
Donc comme il y a des collisions, 2 fichiers au moins de 2048 bits, ont le même hash. cqfd
Mais cela signifie aussi qu'il n'y a pas collisions pour tout les fichiers de 2048 bits, certains hash ne correspondront qu'a un et un seul fichier de 2048 bits et d'autres non.
[^] # Re: une question pour l'inculte que je suis :
Posté par mac . Évalué à 4.
Ca me semble même plutôt faux comme implication ;)
[^] # Re: une question pour l'inculte que je suis :
Posté par allcolor (site web personnel) . Évalué à -2.
A chaque fichier correspond un hash... à un hash correspond un ou plusieurs fichiers de taille donnée.
Dans mon exemple, certains fichiers (bcp en fait) vont entrer en collisions et avoir donc le même hash. Mais comme on c'est restreint à l'ensemble des fichiers de 2048 bits, il n'est pas dis que chaque fichier à un fichier qui collisionne avec. Un hash peut alors correspondre à un fichier unique de 2048 bits (mais par contre il peut-être le hash d'un fichier 2049).
Ce que je voulais dire, c'est que tout les fichiers de l'ensemble ne rentre pas en collisions.
[^] # Re: une question pour l'inculte que je suis :
Posté par mac . Évalué à 2.
Exemple trivial de hash : H(x) = 1er caractère de X
Pour ce hash, TOUS les fichiers entrent en collision.
[^] # Re: une question pour l'inculte que je suis :
Posté par allcolor (site web personnel) . Évalué à -1.
[^] # Re: une question pour l'inculte que je suis :
Posté par Pat _ . Évalué à 5.
Tu a dis à l'origine
1- "cela signifie aussi qu'il n'y a pas collisions pour tout les fichiers de 2048 bits" c'est à dire que le simple dénombrement prouve qu'il existe au moins un fichier ne partageant son hash avec aucun autre ; ce qui est faux, il n'y a aucune implication
2- "certains hash ne correspondront qu'a un et un seul fichier de 2048 bits et d'autres non" c'est à dire il existe au moins un hash correspondant à un fichier et un seul, ce qui est une affirmation distincte de la précédente (et sans lien logique avec elle), et pour laquelle il n'y a pas non plus d'implication
On peut juste dire qu'il est certain que certains fichiers sont en collision, et que certains hashs correspondent à plusieurs fichiers (ce qui, dans ce sens, est lié).
Quand à savoir si tous les fichiers sont en collision, ou si tous les hashs correspondent à plusieurs fichiers (ce sont évidement deux questions distinctes), on peut seulement dire qu'on n'en sait rien, et qu'il est possible que non...
Il ne déforme pas, il te donne un contre exemple de l'assertion 1 (il aurait du dire tous les fichiers d'au moins deux caracteres).
Sa question est donc pertinente... mais bon, c'est pas bien grave, et je ne sais pas pourquoi j'en fais une telle tartine :)
[^] # Re: une question pour l'inculte que je suis :
Posté par Calim' Héros (site web personnel) . Évalué à 1.
C'est ce qu'il dit depuis tout a l'heure, "Tout fichier possede un Hash mais tout Hash ne correspond pas a un fichier".
La seul garantie, dans notre cas, est que le Hash de tout fichier sera dans cet ensemble [0 - 2^160[, aucunement que tout les elements de l'ensemble [0 - 2^160[ soit des hash possible de fichier de 2048 b ni meme que ces elements soit des hash d'un quelquonque fichier.
[^] # Re: une question pour l'inculte que je suis :
Posté par adibou . Évalué à 1.
d'un cote tu suppose qu'il existe des sommes qui ne correspondent qu'a un seul fichier, de mon cote je suppose qu'il n'existe pas de somme correspondant a plus de 2^1888 fichiers de 2048 b differents. Dans mon cas, je ne trouverais aucun resultats de la fonction de hashage correspondant a un unique fichier :/
maintenant la question est de savoir qui a raison - je n'ai pas donne plus de preuve que toi ;) -
[^] # Re: une question pour l'inculte que je suis :
Posté par allcolor (site web personnel) . Évalué à 1.
Ce que je voulais dire, c'est que tout les fichiers de l'ensemble ne rentre pas nécessairement en collisions.
Maintenant, peut-être que dans mon exemple c'est faux... je me demande d'ailleurs si il est possible de prouver qu'il y a un hash de 160 bits qui correspondra a un et un seul fichier de 2048 bits.
Mais je ne voulais de toutes façons pas en venir là, mais juste répondre à la question, existe-t-il des fichiers de même taille qui ont le même hash et la réponse est oui.
[^] # Re: une question pour l'inculte que je suis :
Posté par mac . Évalué à 1.
[^] # Re: une question pour l'inculte que je suis :
Posté par KiKouN . Évalué à 1.
Ma fonction de hash: (je n'ai pas le définition exacte d'une fonction de hashage mais celle-ci à de bonne chance d'être correcte)
-> tous les fichiers donnent comme clef 00 sauf le fichier de 2048bits contenant que des 0 qui, lui, donne 01. la clef est sur 2 bits.
Conclusion, les resultats sur tous les fichiers possible me dit:
-> il existe des clef (10 et 11) qui ne correspondent pas à un fichier
-> il existe des clef (01) qui correspondent qu'à un seul fichier
-> il existe des clef (00) qui correspondant à plusieurs fichier
[^] # Re: une question pour l'inculte que je suis :
Posté par Antoine Beck . Évalué à 2.
mes 0.02¤
# Pour md5 je confirme :op
Posté par Krunch (site web personnel) . Évalué à 3.
Sinon pour ceux qui ont du mal, je suggère qu'ils aillent d'abbord lire la définiton d'une fonction de hashage et d'une fonction de hashage cryptographique.
http://en.wikipedia.org/wiki/Hash_function(...)
http://en.wikipedia.org/wiki/Cryptographic_hash_function(...)
pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.
# Réchauffé
Posté par bghflt (site web personnel) . Évalué à 2.
ftp://ftp.rsasecurity.com/pub/pdfs/bulletn4.pdf(...)
Plus loin on trouve la recommandation pour SHA-1 et RIPEMD160
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.