子字符串 md5 碰撞

Question

我需要一个 4 字符的哈希值。目前我正在获取 md5() 哈希值的前 4 个字符。我正在对长度不超过 80 个字符的字符串进行哈希处理。这会导致碰撞吗？或者，假设我将散列少于 65,536 (16⁴) 个不同元素，碰撞的可能性是多少？

Answer 1

嗯，md5 的每个字符都是一个十六进制位。这意味着它可以具有 16 个可能值之一。因此，如果您仅使用前 4 个“十六进制位”，则意味着您可以拥有 16 * 16 * 16 * 16 或 16^4 或 65536 或 <代码>2^16 可能性。

因此，这意味着结果的总可用“空间”只有 16 位宽。现在，根据生日攻击/问题，发生碰撞的可能性如下：

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

所以发生碰撞的可能性相当大。

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

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

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

我将给出每个示例（在 PHP 中，但应该很容易翻译/看看发生了什么）：

4 十六进制位：

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

4 Alpha位：

$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 个可打印 Assci 位：

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

4 个完整字节：

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

Answer 2

确实高得惊人。 正如您从 这张近似碰撞概率图（来自 wikipedia 的公式page），只有几百个元素，发生冲突的可能性就超过 50%。

当然，请注意，如果您面临攻击者提供字符串的可能性，您可能可以假设它是 100% - 在 16 位搜索空间中扫描以查找冲突几乎可以在任何现代 PC 上立即完成。甚至任何现代手机都可以。

Answer 3

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