Disons que nous avons un milliard d'images uniques, un méga-octet de chaque. On calcule le hachage SHA-256 pour le contenu de chaque fichier. La possibilité de collision dépend de:
Jusqu'où nous pouvons aller en ignorant cette possibilité, en supposant qu'il est nul?
La réponse habituelle va donc: quelle est la probabilité qu'un rogue astéroïde s'écrase sur Terre dans la seconde suivante, faisant disparaître la civilisation-comme-on-sait-il, et tuant les quelques milliards de personnes ? Il peut être argumenté que tous les malchanceux de l'événement, avec une probabilité inférieure qui n'est effectivement pas très important.
Si nous avons un "parfait" fonction de hachage avec la taille de la sortie n, et nous avons p messages de hachage (individuelle longueur du message n'est pas important), alors la probabilité de collision est sur le point p2/2n+1 (c'est une approximation qui est valable pour les "petits" p, c'est à dire sensiblement plus petit que 2n/2). Par exemple, avec l'algorithme SHA-256 (n=256) et un milliard de messages (p=109), alors la probabilité est d'environ 4.3*10-60.
Un meurtrier de masse de rocher de l'espace se produit environ une fois tous les 30 millions d'années en moyenne. Cela conduit à une probabilité d'un tel événement intervenu dans la seconde suivante à environ 10-15. C'est 45 ordres de grandeur plus probable que le SHA-256 de collision. En bref, si vous trouvez SHA-256 collisions effrayant alors vos priorités sont mauvaises.
Dans une configuration de la sécurité, où l'attaquant peut choisir les messages qui seront hachés, puis l'attaquant peut considérablement l'usage de plus d'un milliard de messages; cependant, vous trouverez que l'attaquant de la probabilité de succès sera toujours extrêmement petite. C'est toute la question de l'utilisation d'une fonction de hachage avec une 256 bits de sortie: de sorte que les risques de collision peut être négligée.
Bien sûr, tout ce qui précède suppose que SHA-256 est un "parfait" fonction de hachage, ce qui est loin d'être prouvé. Encore, SHA-256 semble assez robuste.
La possibilité d'une collision ne dépend pas de la taille des fichiers, que sur leur nombre.
Ceci est un exemple du paradoxe d'anniversaire. La page de Wikipedia donne une estimation de la probabilité d'une collision. Si vous exécutez les chiffres, vous verrez que tous les disques durs jamais produit sur la Terre ne peut pas contenir suffisamment de 1 mo de fichiers pour obtenir une probabilité de collision de la même 0,01% pour SHA-256.
Essentiellement, vous pouvez simplement ignorer cette possibilité.
Tout d'abord, il n'est pas nul, mais très proche de zéro.
La question clé est de savoir ce qui se passe si une collision se produit réellement? Si la réponse est "une centrale nucléaire va exploser", alors il est probable que vous ne devriez pas ignorer la possibilité de collision. Dans la plupart des cas, les conséquences ne sont pas si terribles et si vous pouvez ignorer la possibilité de collision.
Aussi n'oubliez pas que vous avez un logiciel (ou une petite partie de celui-ci) peut être déployé et utilisé simultanément dans une foule d'ordinateurs (quelques petites intégrés micro-ordinateurs qui sont presque partout de nos jours inclus). Dans de tels cas, vous devez multiplier l'estimation que vous avez par le plus grand nombre de copies.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
