Forum général.général Fonction de hachage (cryptographique)

Posté par  .
Étiquettes : aucune
0
11
jan.
2006
Je dois générer une signature d'un ensemble de fichiers tenant sur 8 caractères facilement saisissable (donc une empreinte entre 32 et 48 bits), pour vérifier que ces fichiers n'est pas été modifiés (intentionnellement ou pas).
Hors mis CRC32 qui tient sur huit caractères ([0-9a-z]{8}), je n'ai rien trouvé. Mais je n'ai aucune idée de la fiabilité de CRC32 vis-à-vis d'une modification volontaire.

Je cherche donc désespérément une sorte de CookBook ou un précis sur les fonctions de hachage pour en réaliser une sur mesure.

Merci

  • # suggestion bête

    Posté par  . Évalué à 2.

    A ta place, je ne réinventerai pas quoique ce soit.

    tu hashes tes fichiers avec md5sum et tu rehashe la sortie avec sum. voire tu n'utilises que sum.

    • [^] # Re: suggestion bête

      Posté par  . Évalué à 1.

      Donc en fait c'est un hachage et pas une signature.

      Sinon oui, un md5sum fait parfaitement l'affaire. La taille de sortie de md5 est de 128 bits soit 16 octets. La sortie est en hexa soit 32 lettres et chiffres. Rien ne t'empêche de tronquer le résultat pour avoir la bonne taille.

      Pour mémoire, même si un seul bit du fichier est modifié, la sortie md5sum sera complètement différente. Le tronquage ne devrait donc pas être un problème. Et réussir à obtenir une collision avec la fonction de hachage MD5 reste tout de même très difficile. Et si t'es parano il y a toujours sha1sum.

      8 caractères ça fait 2^32 codes possibles, soit plus de 4 milliards.

      • [^] # Re: suggestion bête

        Posté par  . Évalué à 2.

        Trouver une collision sur MD5 complet est certes relativement difficile (mais ca a déjà été fait), par contre, trouver des collisions sur n'importe quel fonction de hachage (MD5, SHA-1, etc.) tronquée à 32 bits est malheureusement très facile (voir commentaire plus bas sur l'attaque des anniversaire en 2^16=65536 opérations)...

        • [^] # Re: suggestion bête

          Posté par  . Évalué à 1.

          Certes mais vu qu'il souhaite que cela tienne sur 8 caractères ASCII...

  • # Fonctions de hachage

    Posté par  . Évalué à 2.

    CRC32 ne resiste pas une seconde à une modification volontaire (commes tous les CRC d'ailleurs).

    Le problème d'une empreinte de taille faible c'est que sa proprieté de résistance aux collisions (il est difficile de trouver x et y tel que h(x) = h(y)) va être très rapidement mise à mal. Exemple, pour une empreinte de 32 bits, on a une très forte probabilité de trouver des collisions à partir de 2^(32/2) = 2^16 = 65536 opérations (attaque des anniversaires). En gros tu calcul les empreintes de 65536 fichiers et tu as une probabilité importante de trouver deux empreintes identiques dans le lot.

    Alors c'est vrai pour la proprieté de résistance aux collisions mais là un attaquant aurait plutôt besoin de casser la proprieté de résistance à la seconde pré-image (étant donné x, il est difficile de trouver x' != x tel que h(x) = h(x'), donc en gros de trouver un fichier dont l'empreinte est égale à celle d'un fichier donné, et encode faut-il que ce fichier ai un sens, ce qui n'est pas gagné). Cette proprieté est plus robuste (en général) que celle de collision mais il faut quand même faire attention.

    Si tu as vraiment besoin de faire des empreintes de faible tailles (mais je recommande fortement quand même des empreintes de 128 bits ou plus), il faudrait mieux prendre un algo de hachage standard (SHA-1 de préférence à MD5) et tronquer sa sortie à la taille que tu as besoin, c'est pas génial mais c'est incomparablement mieux que CRC...

    Cependant, ne t'étonne pas que quelqu'un vienne te voir avec deux fichiers qui ont la même empreinte en quelques secondes...

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.