我正在制作一个应用程序，用于存储文档并给每个文档分配一个基于SHA1摘要的UID，其中包括时间戳等内容。摘要具有很多字符，我想允许用户使用完整摘要的前x个字符来标识文档。如果文档数量可能在10K-100K左右，那么x的合适取值是多少？
答：考虑到碰撞的概率和可读性，取x=6或7是比较好的选择。6个回答
26
根据维基百科上生日悖论问题的公式（Birthday problem），可以估算碰撞的概率为1 - e^(-n^2/(2^(b+1)))，其中n是文档数，b是位数。 用n = 100,000绘制这个公式的图表，看起来您至少需要 b > 45 。我更倾向于使用64，这样可以得到一个美观且整洁的数字。话虽如此，如果发生碰撞，您需要有应对计划（也许稍微改变时间戳或添加nonce？）。
另外，如果sha1不仅基于文档内容，还包括其他信息，为什么不将其简单地变成随机ID呢？在这种情况下，碰撞不再是一个大问题，因为您可以随时生成一个新的随机数并重试（然而，单次尝试发生碰撞的概率是相同的）。
- bdonlan
6
3
请注意在截断哈希时要小心，因为没有证明较小的哈希是安全的。请参阅Kelsey的《Kelsey_Truncation.pdf》。Kelsey提供了两个相关的启发式论据（“Related Hash Outputs”和“Near Collisions”）。Biham / Chen提供了近似碰撞的示例；Knudsen演示了截断差分攻击。最终，您可能想将数据输入到具有截断大小的HMAC中（该大小也由HMAC消化），然后使用截断的HMAC。
- jww
1
嗨JWW，关于NIST-PDF，你是如何解释它的？@bdonlan的公式
e^(-n^2/(2^(b+1)))是否是估计截断的好近似值？如果不是，那么检查SHA1截断的最小位数（_bmin_）的公式或算法是什么？ - Peter Krauss2
实际上，这个并没有一个确切的价值；SHA是一种很好的通用哈希算法的部分原因在于相似的数据不一定会产生相似的哈希值。如果您的系统没有其他更多信息，最好的方法就是搜索哈希值以用户提供的值开头的文档列表，然后向他们呈现一个文档选择列表或者直接进入文档（如果只有一个）。
- Adam Robinson
1
1Git用revs做了什么？ - dan
1
以下是几个需要考虑的关键点：
碰撞风险的理论值是多少。正如其他人所提到的那样，这是“生日悖论”的一种概括。
SHA-1哈希值与理论值相比，产生碰撞的概率有多大。理想情况下，它应该与真正随机分布的情况相同。您可以参考一些实际测试，这些测试显示出与您类似情况的相当好的结果。
您认为可接受的风险是什么。此外，如果发生碰撞，对您的应用程序会产生多大影响。对于某些人来说，10%的风险可能是可接受的。对于其他人来说，0.0001%的风险可能是无法接受的。
根据您的情况，一个好的策略可能是在内部使用更多的位，但只向用户显示其中的一部分。考虑Git所做的 - 它在内部使用SHA-1哈希值的所有160位，但通常只显示整个HEX表示中的短前缀。
考虑到这一切，对于多达100K个文档，我可能会使用64位哈希。这样，碰撞的风险将低于普通人在其一生中至少被雷击两次的风险。大多数数据库和编程语言都具有本地64位整数类型，因此这将是方便、快速和内存高效的。
然后，您需要决定如何最好地向用户显示该哈希。如果您将其显示为HEX，则整个64位哈希将有16个十六进制字符。我建议以更容易让人类视觉比较值的格式显示它。例如：72af-88c1-d2a6-5c2e。
- at54321
0
好的，这里可能是一个过于简单化的答案...
如果使用完整的sha1算法，你大约有2^160的机会发生碰撞，那么通过截取一个字符，你将增加16个碰撞的机会（所有可能的截断字符值）... 这是2^4.. 所以，如果你截取x个字符，你将得到1/2^(160-4*x)的碰撞机会.. 对吧？
- vmpstr
2
1对于单个文档而言，这是正确的，但是任意两个文档之间发生碰撞的概率会迅速增加。 - bdonlan
Biham/Chen提供了近似碰撞的例子；而Knudsen展示了截断差分攻击。这两种攻击都是针对截断哈希的问题，但都不是生日悖论的实例。 - jww
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
1 - e^(-n^2/(2^(b+1)))以匹配图中显示的内容。之前的版本不匹配，对于较小的n和较大的b会导致更多的碰撞。 - Matthias Fripp