Est-il sûr d'ignorer la possibilité de collisions SHA dans la pratique?

Disons que nous avons un milliard d'images uniques, un mégaoctet chacune. Nous calculons le hachage SHA-256 pour le contenu de chaque fichier. La possibilité de collision dépend de:

• le nombre de fichiers
• la taille du fichier unique

Jusqu'où pouvons-nous aller en ignorant cette possibilité, en supposant qu'elle est nulle?

La réponse habituelle est la suivante: quelle est la probabilité qu'un astéroïde voyou s'écrase sur Terre dans la seconde qui suit, anéantissant la civilisation telle que nous la connaissons et tuant quelques milliards de personnes? On peut affirmer que tout événement malchanceux avec une probabilité inférieure à celle-ci n'est pas réellement très important.

Si nous avons une fonction de hachage « parfaite » avec la taille de sortie n , et nous avons p messages de hachage (longueur individuelle du message n'a pas d' importance), alors la probabilité de collision est d' environ p ² /2 ^{n + 1} (ce qui est une approximation qui est valable pour "petit" p , c'est-à-dire sensiblement inférieur à 2 ^{n / 2} ). Par exemple, avec SHA-256 ( n = 256 ) et un milliard de messages ( p = 10 ⁹ ), la probabilité est d'environ 4,3 * 10 ^-60 .

Une roche spatiale meurtrière se produit environ une fois tous les 30 millions d'années en moyenne. Cela conduit à une probabilité d'un tel événement se produisant dans la prochaine seconde à environ 10 ^-15 . C'est 45 ordres de grandeur plus probables que la collision SHA-256. En bref, si vous trouvez les collisions SHA-256 effrayantes, vos priorités sont fausses.

Dans une configuration de sécurité, où un attaquant peut choisir les messages qui seront hachés, l'attaquant peut utiliser sensiblement plus d'un milliard de messages; cependant, vous constaterez que la probabilité de succès de l'attaquant sera toujours très faible. C'est tout l'intérêt d'utiliser une fonction de hachage avec une sortie 256 bits: pour que les risques de collision puissent être négligés.

Bien sûr, tout ce qui précède suppose que SHA-256 est une fonction de hachage "parfaite", ce qui est loin d'être prouvé. Pourtant, SHA-256 semble assez robuste.

La possibilité d'une collision ne dépend pas de la taille des fichiers, seulement de leur nombre.

Ceci est un exemple du paradoxe d'anniversaire . La page Wikipédia donne une estimation de la probabilité d'une collision. Si vous exécutez les chiffres, vous verrez que tous les disques durs jamais produits sur Terre ne peuvent pas contenir suffisamment de fichiers de 1 Mo pour obtenir une probabilité de collision de 0,01%, même pour SHA-256.

Fondamentalement, vous pouvez simplement ignorer la possibilité.

Tout d'abord, ce n'est pas zéro, 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", vous ne devriez probablement pas ignorer la possibilité de collision. Dans la plupart des cas, les conséquences ne sont pas si graves et vous pouvez donc ignorer la possibilité de collision.

N'oubliez pas non plus que votre logiciel (ou une infime partie de celui-ci) peut être déployé et utilisé simultanément dans une multitude d'ordinateurs (de minuscules micro-ordinateurs intégrés qui sont presque partout de nos jours inclus). Dans ce cas, vous devez multiplier l'estimation que vous avez par le plus grand nombre possible de copies.