这是一个组合问题，需要一些散列算法的理论。
假设输入可以是 30 kB 到 5 MB 大小的任意随机字节序列（我猜这会产生相当多的输入值组合 :)）
从字节序列计算的 MD5 哈希的前 4 个字节（或前 n 个字节）对于不同的文件相同的概率是多少？
如果这不能专门针对 MD5 哈希计算，那么任何生成均匀分布的 m 字节哈希的哈希函数在给定输入范围的前 n 个字节上计算冲突哈希的概率是多少？
问问题
7476 次
6 回答
9
在没有关于字节值概率的更多信息的情况下，我认为它是 2^32 中的 1。
编辑。实际上，如果您使用十六进制字符而不是纯字节，则为 2^16 中的 1。
根据评论编辑：
MD5 是否可以认为计算值是绝对随机的？
MD5 哈希算法的设计是为了输入的微小变化会导致完全不同的哈希，所以我会说 MD5 哈希字节以相等的概率分布（无论如何我不会打赌）。无论如何，您可以对哈希应用后处理（例如，您可以使用键控 MD5）以增加其随机性（顺便说一下，使其更安全，因为普通 MD5 哈希已被证明是不安全的）。
于 2009-11-13T08:21:38.700 回答
4
对于理想的散列函数，输出是均匀分布的，因此两个碰撞的机会是 2^32 分之一。然而，生日悖论告诉我们，如果我们正在比较所有散列对，我们应该期望在平均有 2^16 个散列时看到冲突 - 所以不要仅仅依赖 4 个字节“我的价值远低于 40 亿”。
正如我们所知，MD5 并不是一个理想的散列函数，但这里的弱点有些偶然：发现 4 个字节的冲突完全属于合理的暴力攻击范围，因此无需诉诸加密弱点。如果您只关心随机选取的数据，您将不会看到与随机性的显着统计偏差。
于 2009-11-13T08:48:02.367 回答
3
如果您对具有相同 4 字节哈希的两个特定输入的几率感兴趣，那么它只是 1/2^32。如果您对一组 X 总输入中具有相同几率的两个输入的几率感兴趣，那么在您开始接近集合中的 2^16 = 65536 个不同输入之前，这将保持相当低的几率，达到接近 50% (这种现象被称为生日悖论）。
一般来说，散列函数在密码学上有用的标准之一是所有位的一致性。
于 2009-11-13T09:36:37.723 回答
3
由于生日悖论，在 n 位散列中发生冲突的几率约为 2^(n/2) 分之一 - 因此在这种情况下约为 2^16 分之一。如果出于某种原因您指的是使用 32 位十六进制编码，当然那只是前 16 个实际位，那么冲突的几率大约是 2 ^ 8 中的 1。
给定一个特定的固定文件，随机选择的任何其他文件与该文件具有相同哈希的几率约为 2^n。就密码散列而言，它们之间的区别是第一个是冲突，另一个是原像。
在这种散列大小下，MD5 的弱点几乎无关紧要，因为对 MD5 的最著名攻击大约需要 2^32 次计算，而即使是理想安全的 32 位散列，也可能在大约 2^16 次计算中产生冲突（因为仅选择随机输入，您就有 2^16 中的 1 个发生碰撞的机会，因此在大约 2^16 次随机猜测之后，您可能会发现一对碰撞的输入）。
于 2009-11-13T12:19:59.487 回答
0
MD5 哈希通常是十六进制，因此每个字节有 16 个可能的值。因此对于四个字节，有 16*16*16*16 = 65536 种可能的组合，使得哈希冲突的概率为 1:65536。
于 2009-11-13T08:22:17.030 回答
-1
md5 是十六进制的，所以每个字符可以是 16 个等位基因中的任何一个。所以这会让16^n
对于 4 个字符，产生 65536 种不同的可能组合。
于 2009-11-13T08:22:56.083 回答