[gull] Petit problème de maths, pour créer de liens

[Sebastien Chassot]

Juste une petite question. Si je résume d'un côté il faut générer une
liste de fichier à tester le plus rapidement possible et la plus
restrictive possible, et d'un autre il faut dans un deuxième temps
s'assurer que les fichiers soient identiques ou non.

Je ne connais pas la différence de temps d'exécution entre la
comparaison d'une somme md5 et une comparaison bit à bit. Je croyais que
l'utilisation d'une somme de contrôle servait à gagner du temps mais si
elle prend autant de temps voir plus et qu'il existe un risque de
collision est-ce une bonne idée ? A plus forte raison s'il faut aller
jusqu'au bout alors que bit à bit on stop s'il y a une différence. Ne
parlons même pas de coupler md5 + comparaison.

Deuxièmement md5 est une somme de contrôle, elle est utilisée comme
moyen de vérifier l'intégrité d'un fichier sans avoir besoin d'un
fichier intègre sous la main. Enfin je crois. C'est peut-être pas
l'outil adapté ?

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 ? Parce que finalement je
ne comprends pas si la peur d'avoir deux fichiers identiques est
vraisemblable ou pas ? Est-ce que d'un point de vue pragmatique il y a
vraiment lieu de pousser si loin la vérification ?


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.
A partir du moment ou un bit diffère n'importe ou dans le fichier cette
différence "se propage" tout au long du contrôle. Pour avoir deux sommes
identique il faut quand même que par hasard une deuxième différence
vienne "annuler" la première. Il est très difficile de trouver une
donnée à introduire dans un fichier pour qu'il ait la même somme de
contrôle qu'un autre. C'est le principe du hashage on l'utilise pour la
sécurité justement (avant qu'il soit cracké) parce qu'il n'y a d'autre
moyen que de de faire une recherche exhaustive pour falsifier une somme
(ou trouver un faux positif.) Le champs des possibles est suffisamment
grand pour que ce soit très difficile et/ou improbable. S'il suffisait
de générer 20'000 ou 30'000 fichiers pour avoir des sommes identiques ce
ne serait pas fiable.



On Sat, 2008-05-03 at 11:50 +0200, Félix Hauri wrote:
> On Fri, May 02, 2008 at 10:40:52PM +0200, Yves Martin wrote:
> > Dans ce cas, la taille n'est pas suffisamment discriminante à mon avis. Et une
> > somme de contrôle est trop coûteuse surtout si on veut assurer par des
> > comparaisons complètes.
> A méditer...
> 
L'un ou l'autre et pourquoi pas choisir une des deux méthode selon le
type de données à comparer. 

Tu peux aussi sortir une somme de contrôle sur qqs octets (dd if=file
skip=x count=3 | md5) c'est déjà redoutable comme discrimination. Et
puis après une comparaison complète.



PS : A moins que je ne me trompe sur le risque de collision même qqs
sommes prise au hasard dans chaque fichier me semblent suffisante pour
avoir une certitude raisonnable.