Re: [gull] Petit problème d =?ISO-8859-1?Q?e_maths, _pour_cr=E9er_de_liens?=

[Marc Mongenet]

Le 3 mai 2008 19:20, Sebastien Chassot <seba.linux at sinux.net> a écrit :
>
>
> Troisièmement, et là est ma question, il y a 2^128 sommes possible. Je
> veux bien que si les données ne sont pas purement aléatoire ces 2^128
> sommes n'ont pas forcément la même probabilité d'apparaître mais est-ce
> que les collisions ont vraiment autant de chance de ce produire ? 2^128
> c'est à peut près le nombre d'étoiles qu'il y a dans l'univers
> observable, non ? si il y a entre 2^30 et 2^31 ordinateurs connectés à
> Internet, que chaque ordinateur à 130'000 fichiers (2^17), le nombre de
> fichiers dans le monde n'est que de 2^48 encore bien loin des 2^128.
> C'est vraiment réaliste ce risque de collision ?

C'est irréaliste.

Avant que des cryptologues cassent MD5, un projet de calcul massivement
distribué avait été lancé pour tenter de trouver une collision par force brute.
Le projet a été interrompu car il a été plus lent que les cryptologues. :-)
http://en.wikipedia.org/wiki/MD5CRK

Bref, une collision est tellement peu probable que si l'on en rencontre une,
il vaut surement la peine de la publier dans une revue spécialisée (à moins
qu'il soit possible de l'obtenir avec la méthode de cassage, dont je ne connais
pas le fonctionnement).

Selon le tableau de l'article http://en.wikipedia.org/wiki/Birthday_attack,
si l'on a 820 milliards de fichiers, il y a une chance sur 1000000000000000
qu'il existe une collision.

> Quand je vois que :
>
>
> seba$ echo ksjdhkldasjgfgjsdafkjh |md5
> 700e81cf71d1dc5ec6a08c14ab809e03
>
> seba$ echo ksjdhkldasjgfgjsdafkjH | md5
> 95f4922d376e7f0aa7af75748d431363
>
> Ce n'est pas parce que deux fonctions de hashage ont des ressemblances
> que leurs sommes vont être proche, c'est justement la force du hashage.

Absolument. On peut même ajouter qu'une fonction de hachage qui
donnerait des hashs similaires sur des données d'entrée similaires
serait immédiatement rejetée pour les applications crytographiques.

-- 
Marc Mongenet
Creator of the Web 2 Markup Language
http://w2ml.com