我如何安全地假设 SHA1 哈希的一部分的唯一性? [英] How safely can I assume unicity of a part of SHA1 hash?

问题描述

我目前正在使用 SHA1 来缩短网址:

I'm currently using a SHA1 to somewhat shorten an url:

Digest::SHA1.hexdigest("salt-" + url)

仅使用 SHA1 的前 8 个字符作为唯一标识符有多安全，就像 GitHub 显然对提交所做的那样?

How safe is it to use only the first 8 characters of the SHA1 as a unique identifier, like GitHub does for commits apparently?

推荐答案

要计算给定长度和您拥有的哈希数发生冲突的概率，请参阅 生日问题.我不知道您将拥有多少哈希值，但这里有一些示例.8 个十六进制字符是 32 位，因此对于大约 100 个散列，冲突的概率大约是 1/1,000,000，对于 10,000 个散列，它大约是 1/100，对于 100,000，它是 3/4 等等.

To calculate the probability of a collision with a given length and the number of hashes that you have, see the birthday problem. I don't know the number of hashes that you are going to have, but here are some examples. 8 hexadecimal characters is 32 bits, so for about 100 hashes the probability of a collision is about 1/1,000,000, for 10,000 hashes it's about 1/100, for 100,000 it's 3/4 etc.

请参阅维基百科上生日攻击文章中的表格，以找到满足您需求的良好哈希长度.例如，如果您希望一组超过 100,000 个散列的冲突发生的可能性小于 1/1,000,000,000，则使用 64 位或 16 个十六进制数字.

See the table in the Birthday attack article on Wikipedia to find a good hash length that would satisfy your needs. For example if you want the collision to be less likely than 1/1,000,000,000 for a set of more than 100,000 hashes then use 64 bits, or 16 hexadecimal digits.

这完全取决于您将拥有多少哈希值以及您愿意接受碰撞的概率是多少(因为总有一些概率，即使非常小).

It all depends on how many hashes are you going to have and what probability of a collision are you willing to accept (because there is always some probability, even if insanely small).

这篇关于我如何安全地假设 SHA1 哈希的一部分的唯一性?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！