26

我听说在创建哈希时,如果使用小文件或大量数据,则生成的哈希更有可能发生冲突。如果这是真的,是否应该使用最低“安全”数据量来确保不会发生这种情况?

我想这个问题也可以表述为:

可以安全可靠地散列的最小数据量是多少?

4

5 回答 5

96

哈希函数接受任意(或至少非常高)长度的输入,并产生固定长度的输出。可能的输入多于可能的输出,因此必然存在冲突。安全哈希函数的全部意义在于它是“抗冲突的”,这意味着虽然在数学上必须存在冲突,但实际计算一个非常非常困难。因此,对于 SHA-256 和 SHA-512 没有已知的冲突,并且最知名的计算方法(通过故意这样做)非常昂贵,以至于它们不会很快应用(整个美国联邦预算为世纪只会购买任务的一小部分)。

因此,如果不能有意地实际完成,您可以期望不会因为(坏)运气而发生碰撞。

此外,如果您将自己限制为非常短的输入,则有可能根本没有碰撞。例如,如果您考虑 12 字节输入:有 2 96 个可能的 12 字节序列。这是巨大的(超过今天的技术可以列举的)。然而,SHA-256 会将每个输入映射到一个 256 位的值,即在更宽的空间(大小为 2 256)中的值。我们无法正式证明它,但很可能所有这 2 96 个哈希值彼此不同。请注意,这没有实际后果:因为没有碰撞而没有发现碰撞与因为极不可能撞到碰撞而没有发现碰撞之间没有可测量的区别。

只是为了说明 SHA-256 发生碰撞的风险有多低:考虑一下被从当地动物园或私人所有者那里逃脱的大猩猩伤害的风险。不太可能?是的,但它仍然可能发生:似乎一只大猩猩在 2004 年从达拉斯动物园逃走,造成四人受伤;2010年,另一只大猩猩从同一个动物园逃脱。假设整个地球上每 6 年只有一只狂暴的大猩猩(不仅在达拉斯地区),而您恰好是 65 亿人口中走在他道路上的不幸小伙子,那么您将面临严重的风险- 大猩猩对身体的伤害估计约为每天2 43.7分之一。现在,拿一PC 并让他们努力寻找 SHA-256 的冲突。每天发生碰撞的几率接近 2 75分之一 -比愤怒的猿猴小十亿多。结论是,如果您担心 SHA-256 碰撞但没有始终随身携带上膛的霰弹枪,那么您的优先级就错了。另外,不要惹得克萨斯州。

于 2011-01-13T14:38:48.663 回答
2

没有最小输入大小。SHA-256 算法实际上是一种随机映射,碰撞概率不依赖于输入长度。即使是 1 位输入也是“安全的”。

请注意,对于 SHA-256,输入被填充到 512 位(64 字节)的倍数(对于 SHA-512 是 1024 的倍数)。采用 12 字节输入(Thomas 在他的示例中使用),当使用 SHA-256 时,有 2^96 个可能的长度为 64 字节的序列。

例如,一个 12 字节的输入Hello There!(0x48656c6c6f20546865726521) 将用一位填充,然后是 351 个零位,然后是输入长度的 64 位表示形式,即 0x00000000000000060 以形成 512 位的填充消息。此 512 位消息用作计算散列的输入。

更多细节可以在 RFC:4634“美国安全散列算法(SHA 和 HMAC-SHA)”中找到,http ://www.ietf.org/rfc/rfc4634.txt

于 2011-10-02T04:46:09.463 回答
2

不,消息长度不会影响发生冲突的可能性。

如果是这样的话,算法就坏了。

您可以自己尝试通过针对所有一字节输入运行 SHA,然后针对所有两字节输入等等,看看是否会发生冲突。可能不会,因为没有人发现 SHA-256 或 SHA-512 的冲突(或者至少他们对 Wikipedia 保密

于 2011-01-13T04:40:30.493 回答
0

Τhe hash 是 256 位长,任何超过 256 位的东西都会发生冲突。

你不能在没有碰撞的情况下将某些东西压缩成更小的东西,这违背了数学。

是的,因为算法和 2 的 256 次方有很多不同的哈希值,但它们不是无冲突的,这是不可能的。

于 2016-11-16T22:44:25.843 回答
-4

很大程度上取决于您的应用程序:如果您只是简单地散列“YES”和“NO”字符串以通过网络发送以指示您是否应该给我 100,000 美元的贷款,那将是一个很大的失败——答案的域可以'不是那么大,所以有人可以很容易地检查在线上观察到的哈希值与“小输入”哈希输出的数据库。

如果您要包括日期、时间、我的姓名、我的税号、请求的数量、被散列的数据量可能不会太多,但是这些数据在预先计算的散列表中的可能性非常小。

但我知道没有任何研究可以指出你超出我的直觉。对不起。

于 2011-01-13T04:41:58.503 回答