从文件内容计算的MD5哈希的前4个字节将冲突的概率是多少？ [英] What is the probability that the first 4 bytes of MD5 hash computed from file contents will collide?

问题描述

这是一个组合问题，需要一些散列算法的理论。

我们假设输入可以是任何大小为30 kB到5 MB的随机序列我想这样做了几个输入值的组合：））

MD5哈希的前4个字节（或前n个字节）计算的概率是多少对于不同的文件，字节序列将是相同的？

如果不能专门为MD5哈希计算，那么任何生成统一的哈希函数分布式m字节散列将在给定输入范围的前n个字节上计算具有冲突的散列？

解决方案

在没有关于字节值概率的更多信息的情况下，我会在2 ^ 32。 >

EDIT 。

编辑：基于注释：

MD5可以认为是统一的
，计算值是
绝对随机吗？

MD5哈希算法被设计为使得输入中的小改变导致完全不同的哈希，因此我认为MD5哈希字节以相等概率分布不会打赌它任何东西）。无论如何，您可以对您的散列应用后处理（例如，您可以使用 keyed MD5 ）增加其随机性（并使其更安全，顺便说一下，因为 plain MD5哈希已被证明是不安全的）。

This is a combinatorics question with some theory in hashing algorithms required.

Let's say the input can be any random sequence of bytes 30 kB to 5 MB of size (I guess that makes quite a few combinations of input values :))

What is the probability that the first 4 bytes (or first n bytes) of a MD5 hash computed from the byte sequence will be the same for distinct files?

In case this can not be computed specifically for MD5 hash, then what is the probability that any hash function that generates uniformly distributed m-byte hashes will compute hash with collision on first n bytes for given range of inputs?

解决方案

In absence of more information about the byte values probability, I would day it is 1 in 2^32.

EDIT. Indeed, 1 in 2^16 if you are taking the hexadecimal characters instead of the pure bytes.

EDIT based on comment:

Can MD5 be considered that uniform that a the computed values are absolutely random?

MD5 hash algorithm is designed so that a small change in the input results in a completely different hash, so I would say that MD5 hash bytes are distributed with equal probability (I would not bet anything on it anyway). Anyway you can apply a post-processing to your hash (for example you can use keyed MD5) to increase its randomness (and to make it more secure, by the way, since plain MD5 hashes have been proved to be insecure).

这篇关于从文件内容计算的MD5哈希的前4个字节将冲突的概率是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！