Collision de Hash-quelles sont les chances?
j'ai du code sur mon site php powered qui crée un hash aléatoire (en utilisant sha1() ) et je l'utilise pour faire correspondre les enregistrements dans la base de données.
Quelles sont les chances d'une collision? Si je génère le hachage, Vérifiez d'abord s'il est dans la base de données (je préfère éviter une requête supplémentaire) ou l'insérer automatiquement, en fonction de la probabilité qu'il probablement ne se heurtera pas à un autre.
11 réponses
si vous supposez que SHA-1 fait du bon travail, vous pouvez conclure qu'il y a 1 chance sur 2^160 que deux messages donnés aient le même hachage (puisque SHA-1 produit un hachage de 160 bits).
2^160 est un nombre ridiculement grand. C'est à peu près 10^48. Même si vous avez un million d'entrées dans votre base de données, c'est encore une chance 1 sur 10^42 qu'une nouvelle entrée partagera le même hachage.
SHA-1 s'est avéré être assez bon, donc je ne pense pas que vous avez besoin de vous soucier de collisions.
comme note secondaire, utilisez la fonction raw_output de PHP lorsque vous utilisez SHA-1 car cela conduira à une chaîne plus courte et donc rendra vos opérations de base de données un peu plus rapides.
EDIT: pour répondre au paradoxe de l'anniversaire, une base de données avec 10^18 (Un million de millions d'entrées) a une chance d'environ 1 en 0.00000000003 d'une collision. Really ne mérite pas de s'inquiéter.
utilisez une symmetric encryption scheme et une private server key pour chiffrer L'ID (et d'autres valeurs) lorsque vous les envoyez au client et les déchiffrer à nouveau à la réception. Veillez à ce que votre fonction cryptographique assure à la fois la confidentialité et les contrôles d'intégrité.
cela vous permet d'utiliser valeurs sensibles lorsque vous parlez à la DB sans aucune collision , grande sécurité lorsque vous parlez à la le client et réduit votre probabilité d'atterrir sur thedailyWTF d'environ 2^160.
Voir aussi Marteler Un Clou: Vieille Chaussure ou une Bouteille en Verre? !
pourquoi ne pas faire quelque chose qui garanties il n'y aura pas de collisions, ainsi que permet de s'assurer que personne ne peut modifier un paramètre GET pour afficher quelque chose qu'ils ne devraient pas: à l'aide d'un sel, mélanger l'id et son hachage.
$salt = "salty";
$key = sha1($salt . $id) . "-" . $id;
// 0c9ab85f8f9670a5ef2ac76beae296f47427a60a-5
même si vous tombez accidentellement sur deux numéros qui ont exactement le même hachage sha1 (avec votre sel), alors la clé $sera toujours différente et vous éviterez toutes les collisions.
si vous utilisez un IDs croissant numériquement comme entrée, alors les chances sont pratiquement nulles que SHA-1 se heurte.
si L'ID est la seule entrée, alors SHA-1 semble être un peu exagéré - produisant un hash de 160 bits à partir d'un entier de 32 bits. Je préférerais utiliser l'exponentiation modulaire, par exemple choisir un grand (32 bits) premier p, calculer le générateur modulaire g de ce groupe, puis utiliser g^id. Cela sera garanti sans collision, et ne donner 32 - bit "hashes".
SHA-1 produit de 160 peu long à digérer. Par conséquent, vous êtes en sécurité tant que vous avez moins de 2^(160/2) entrées. Division par 2 est due à paradoxe de l'anniversaire .
, à Partir des principes:
SHA-1 produit un digest de 160 bits. En supposant qu'il utilise le bit-espace entier uniformément (ce qui est probablement ce qu'il a été conçu pour faire), c'est seulement une chance 2^-160 sur chaque insertion que vous obtiendriez une collision.
ainsi, pour chaque insertion, il devrait être sûr de supposer qu'il n'y a pas de collision, et de traiter de l'erreur s'il y a.
ce qui ne veut pas dire que vous pouvez ignorer le risque de collision entièrement.
le paradoxe de L'anniversaire suggère que la probabilité qu'il y ait au moins une collision dans votre base de données est plus élevée que vous ne le pensez, en raison des collisions possibles O(N^2).
si vous devez obscurcir certaines données dans votre url pour cacher des données, vous faites quelque chose de mal.
posez la question ce que cela vous coûtera s'il y a une collision. Si c'est un site gratuit d'amende. Si vous dirigez une entreprise lucrative et qu'un rachat vous coûtera un contrat d'un million de dollars, alors j'y repenserais.
je pense que vous vous trompez.
Je pense que vous devez garder l'ID unique, mais vous voulez vous assurer que les utilisateurs ne peuvent pas changer l'ID manuellement.
une façon de faire ceci est pour mettre l'ID et le hachage de l'ID (avec quelques données supplémentaires) dans le lien.
par exemple: (mon PHP est rouillé donc l'algorithme général serait:)
id = 5;
hash = hash("My Private String " + id)
link = "http://mySite.com/resource?id=" + id + "&hash=" + hash
ensuite, lorsque vous recevez une requête, validez simplement que vous pouvez régénérer le hachage à partir de L'ID. Cela ne vous laisse ouvert à une attaque pour travailler sur "ma chaîne privée", mais ce sera tout à fait difficile sur le plan informatique et vous pourriez toujours ajouter quelque chose d'autre unique qui n'est pas directement disponible pour l'utilisateur (comme l'ID de session).
il y a une règle très simple pour savoir si un algorithme de hachage aurait des collisions ou non. Si la plage de sortie d'un algorithme est un nombre fini, on est obligé d'avoir une collision, tôt ou tard.
même si SHA1 a une très large gamme de 2^160 possibilités de hachage, son nombre encore fini. Toutefois, les entrées qui peuvent être transmis sur cette fonction sont littéralement infinies. Étant donné un ensemble de données d'entrée assez grand, les collisions sont lié à arriver.
les autres commentaires vous ont couvert sur les probabilités, mais si vous regardez de façon pragmatique, vous pouvez obtenir une réponse définitive pour vous-même.
vous avez dit vous-même que vous alliez Hasher vos identifiants séquentiels. Il serait facile de coder un cas d'essai. Itérer ~100 000 000 d'identifiants et de vérifier les collisions. Ce ne serait pas long à faire. D'autre part, vous risquez de manquer de mémoire quart du chemin à travers.