6

我需要一个 4 个字符的哈希。目前我正在使用md5()哈希的前 4 个字符。我正在散列一个长度为 80 个字符或更少的字符串。这会导致碰撞吗？或者，假设我将散列少于 65,536 (16 4 ) 个不同的元素，碰撞的可能性是多少？

4

3 回答 3

6

好吧，每个字符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 个 alpha 位
  • 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 个可打印的 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
于 2011-01-24T18:08:35.087 回答
1

确实高得惊人。正如您从这张近似碰撞概率图（来自维基百科页面的公式）中看到的那样，只有几百个元素，您发生碰撞的概率超过 50%。

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

于 2011-01-13T15:59:24.203 回答
0

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

于 2011-01-13T15:53:00.197 回答