Substring 和 MD5 碰撞问题

Question

我需要一个四字符的哈希值。目前我正在使用md5()哈希函数的前四个字符。我要哈希的字符串长度不超过80个字符。这样会导致冲突吗？或者，假设我将少于65,536（16⁴）个不同元素进行哈希，冲突的可能性是多少？

- Neel Basu

Answer 1

好的，md5的每个字符都是一个十六进制位。这意味着它可以有16种可能的值。因此，如果您只使用前4个“十六进制位”，那么您可以有16 * 16 * 16 * 16或16^4或65536或2^16种可能性。

因此，结果的总可用“空间”仅为16位宽。根据生日攻击/问题，发生碰撞的机会如下：

• 50%的机会 -> 300条目
• 1%的机会 -> 36条目
• 0.0000001%的机会 -> 2条目。

因此，发生碰撞的机会相当高。

现在，您说您需要一个4个字符的哈希值。根据确切的要求，您可以执行以下操作：

• 16^4（65,536）个可能值的4个十六进制位
• 26^4（456,976）个可能值的4个字母位
• 36^4（1,679,616）个可能值的4个字母数字位
• 大约有93^4（74,805,201）个可能值的4个可打印ASCII位（假设ASCII 33 -> 126）
• 256^4（4,294,967,296）个可能值的4个完整字节。

现在，您选择哪个取决于实际用例。哈希需要传输到浏览器吗？您如何存储它等等。

我将给出每个示例（在PHP中，但应易于翻译/了解正在发生的情况）： 4个十六进制位：

$hash = substr(md5($data), 0, 4);

4个α位:

$hash = substr(base_convert(md5($data), 16, 26)0, 4);
$hash = str_replace(range(0, 9), range('S', 'Z'), $hash);

4个字母和数字位:

$hash = substr(base_convert(md5($data), 16, 36), 0, 4);

4可打印ASCII位：

$hash = hash('md5', $data, true); // We want the raw bytes
$out = '';
for ($i = 0; $i < 4; $i++) {
    $out .= chr((ord($hash[$i]) % 93) + 33);
}

四个完整字节:

$hash = substr(hash('md5', $data, true), 0, 4); // We want the raw bytes

- ircmaxell

---

只是一个快速的错误修复，针对你的“4 Alpha bits”解决方案，我认为第二行应该是：$hash = str_replace(range(0, 9), range('Q', 'Z'), $hash); - yosser

想一想，第二个范围是a-z + Q-Z = 36 ^ 4种可能的值。整个代码应该是：$hash = substr(base_convert(md5($data), 16, 26),0, 4); $hash = str_replace(range(0, 9), range('q', 'z'), $hash); - yosser

Answer 2

真的很高。 从这张近似碰撞概率图（公式来自wikipedia页面）中可以看出，只有几百个元素，你发生碰撞的概率就超过了50%。

当然，如果你面临攻击者提供字符串的可能性，那么你可能可以假定碰撞的概率为100%——在16位搜索空间中查找碰撞几乎可以立即在任何现代计算机上完成。甚至是任何现代手机都可以。

- bdonlan

Answer 3

前4个字符包含了16位数据，因此碰撞肯定会在65536个元素处发生，并且由于生日攻击，它会被更快地发现。您应该使用更多位的哈希。

- Nickolay Olshevsky

---

你应该做16^4而不是4*4吧？因为每个字符有16种变化，而md5仅使用十六进制字符。 - Neel Basu

他正在计算位数，而不是可能值的数量。 - bdonlan