substr md5碰撞

Question

我需要一个4个字符的哈希.目前我正在使用md5()哈希的前4个字符.我正在散列一个长度不超过80个字符的字符串.这会导致碰撞吗？或者,碰撞的几率是多少,假设我的哈希值小于65,536(16 ⁴)个不同的元素？

Answer 1

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

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

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

因此发生碰撞的可能性很高。

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

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

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

我将给出每个示例（在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

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

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