hash - 子字符串 md5 碰撞

Question

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

Answer 1

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

因此，这意味着结果的总可用“空间”只有 16 位宽。现在，根据 Birthday Attack/Problem ，有以下碰撞机会:

• 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 个 ascii 可打印位，大约 93^4 (74,805,201) 个可能值(假设 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