• # Mince

    Posté par (page perso) . Évalué à -1.

    Mon système n'est plus sûr maintenant... ^^
  • # Info ou Intox ?

    Posté par . Évalué à 3.

    C'a m'a pas l'air sérieux cette news sur /. ... le mec sur la mailling list qui 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#(...)

    Perso je pense que c'est une belle intox ... et vous ?
    • [^] # Re: Info ou Intox ?

      Posté par (page perso) . Évalué à 10.

      Pour SHA-0 ce n'est pas une intox. Pour résumer :

      - 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 (page perso) . Évalué à 9.

      Je ne pense pas que ce soit de l'intox. (http://www.iacr.org/conferences/crypto2004/(...))

      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 . Évalué à 7.

      > C'a m'a pas l'air sérieux cette news sur /. ... le mec sur la mailling list qui
      > 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 (page perso) . Évalué à 10.

    Depuis quand le md5 est un algorithme de cryptage ?
    Mon petit doigt me dit que tes rumeurs sont erronées :)
    • [^] # Re: MD5, un algo de cryptage ?

      Posté par . Évalué à 8.

      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 :)
      • [^] # Hashing et collisions

        Posté par (page perso) . Évalué à 10.

        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.
      • [^] # Re: MD5, un algo de cryptage ?

        Posté par . Évalué à 9.

        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 ...
      • [^] # Re: MD5, un algo de cryptage ?

        Posté par . Évalué à 10.

        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, ...).
        • [^] # Re: MD5, un algo de cryptage ?

          Posté par . Évalué à 6.

          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)
        • [^] # Re: MD5, un algo de cryptage ?

          Posté par . Évalué à 7.

          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.
        • [^] # Re: MD5, un algo de cryptage ?

          Posté par (page perso) . Évalué à 1.

          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

          Donc ce n'est pas 100% sur
      • [^] # Re: MD5, un algo de cryptage ?

        Posté par (page perso) . Évalué à 8.

        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 :)
        • [^] # Re: MD5, un algo de cryptage ?

          Posté par . Évalué à 6.

          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 ?
          • [^] # Re: MD5, un algo de cryptage ?

            Posté par . Évalué à 10.

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

            Kha
            • [^] # Re: MD5, un algo de cryptage ?

              Posté par . Évalué à 10.

              zut, il me restait 453 jours pour finir de télécharger les sources de wget :(
            • [^] # Re: MD5, un algo de cryptage ?

              Posté par (page perso) . Évalué à 1.

              Et pourquoi n'inclut-on pas la taille du chier en bit dans la signature en plus du hash lui même ?

              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 . Évalué à 2.

                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).
              • [^] # Re: MD5, un algo de cryptage ?

                Posté par . Évalué à 3.

                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)
            • [^] # Re: MD5, un algo de cryptage ?

              Posté par . Évalué à 1.

              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.
              • [^] # Re: MD5, un algo de cryptage ?

                Posté par . Évalué à 1.

                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.

                Kha
        • [^] # Re: MD5, un algo de cryptage ?

          Posté par . Évalué à 2.

          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...
    • [^] # Re: MD5, un algo de cryptage ?

      Posté par (page perso) . Évalué à -1.

      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).
      • [^] # Re: MD5, un algo de cryptage ?

        Posté par . Évalué à 6.

        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.
        • [^] # Re: MD5, un algo de cryptage ?

          Posté par (page perso) . Évalué à 3.

          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.
          • [^] # Re: MD5, un algo de cryptage ?

            Posté par . Évalué à 4.

            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.
            • [^] # Re: MD5, un algo de cryptage ?

              Posté par (page perso) . Évalué à -1.

              ""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 reste sobre et on respire.

    Posté par . Évalué à 10.

    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.

    En bref, dormez en paix braves gens.

    Kha
    • [^] # Re: On reste sobre et on respire.

      Posté par (page perso) . Évalué à 2.

      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 ?
      • [^] # Re: On reste sobre et on respire.

        Posté par . Évalué à 8.

        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.

        Voilà a peu près totu ce que je sais.

        Kha
    • [^] # Re: On reste sobre et on respire.

      Posté par . Évalué à 3.

      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.
    • [^] # Re: On reste sobre et on respire.

      Posté par . Évalué à 4.

      > L'algorithme est de complexité 2^51.

      Ç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 (page perso) . Évalué à 3.

        > L'algorithme est de complexité 2^51.

        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 . Évalué à 2.

        > 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).
  • # Fonctions de hachage

    Posté par . Évalué à 10.

    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.

    [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 . Évalué à 3.

      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)
  • # une question pour l'inculte que je suis :

    Posté par . Évalué à 1.

    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 ?

    my2cents
    • [^] # Re: une question pour l'inculte que je suis :

      Posté par . Évalué à 3.

      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 ?

      Kha
      • [^] # Re: une question pour l'inculte que je suis :

        Posté par (page perso) . Évalué à 1.

        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.
        • [^] # Re: une question pour l'inculte que je suis :

          Posté par . Évalué à 4.

          Je ne comprend pas ton implication "Donc certains hash ne corresponderont qu'à un seul fichier"...

          Ca me semble même plutôt faux comme implication ;)
          • [^] # Re: une question pour l'inculte que je suis :

            Posté par (page perso) . Évalué à -2.

            Ben si.

            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 . Évalué à 2.

              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.
              • [^] # Re: une question pour l'inculte que je suis :

                Posté par (page perso) . Évalué à -1.

                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.
                • [^] # Re: une question pour l'inculte que je suis :

                  Posté par (page perso) . Évalué à 5.

                  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 :)
              • [^] # Re: une question pour l'inculte que je suis :

                Posté par (page perso) . Évalué à 1.

                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.
            • [^] # Re: une question pour l'inculte que je suis :

              Posté par . Évalué à 1.

              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 ;) -
              • [^] # Re: une question pour l'inculte que je suis :

                Posté par (page perso) . Évalué à 1.

                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.
                • [^] # Re: une question pour l'inculte que je suis :

                  Posté par . Évalué à 1.

                  "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 :)
                • [^] # Re: une question pour l'inculte que je suis :

                  Posté par . Évalué à 1.

                  Bon exemple, pour l'aider un peu:

                  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 . Évalué à 2.

      J'aurais plutot dit "une question de l'inculte que je suis", ou bien meme "une réponse pour l'inculte que je suis" ...

      mes 0.02¤
  • # Pour md5 je confirme :op

    Posté par (page perso) . Évalué à 3.

    http://slashdot.org/comments.pl?sid=118198&cid=9987007(...)

    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 (page perso) . Évalué à 2.

    RSA Lab annoncait dans un bulletin de 1996 les faiblesses de MD5 et les risques de collision..

    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 à ceux qui les ont postés. Nous n'en sommes pas responsables.