对窄管道散列函数设计的关注有多有效?

信息安全 密码学 哈希 密码分析
2021-09-02 02:50:14

窄管道散列函数设计最近受到抨击,特别是在参考一些 SHA-3 候选者时。这种批评有效吗?能比这篇论文解释得更简单吗?

我很好奇,因为我想知道这是否也是可以评估旧哈希函数的标准。

1个回答

从非常严格和狭隘的角度来看,窄管道批评是一种有效的攻击,因为它表明具有 256 位输出大小和“窄管道”(运行状态不大于输出)的哈希函数提供,大多数情况下,可以使用输出为 255.34 位的散列函数实现的原像抗性。从更实际的角度来看,这对实际安全没有任何影响。Gligoroski 将这篇论文作为宽管设计的论据,特别是他自己的 SHA-3 提案,称为Blue Midnight Wish

Aumasson 是另一个 SHA-3 候选者(一种窄管设计) BLAKE的设计者之一,他说这种攻击属于“我的管道比你的大”,并不严重。然而,很能说明问题的是,在对 14 个第二轮 SHA-3 候选的所有研究结果中,Gligoroski 的窄管批评可能是最著名的攻击——这意味着据我们所知,所有 14 个函数都是,相当健壮。还可以注意到,在第 3 轮 SHA-3 比赛中,选择了 BLAKE,但没有选择 BMW。

MD4、MD5、SHA-1、SHA-256 和 SHA-512 是窄管设计,没有人会错过这一事实。

这种攻击有效的原因(对于非常低的工作值)是随机函数不太可能具有 1 -> 1 的输入到输出的映射,如果它是一个真正的随机函数。事实上,按照数学计算的方式,完美的随机映射只会产生 1 - 1/e 的可能输出空间。这可以达到 0.632 左右,并且由于不会发生不到一半的输出,因此将查找原像的难度降低了部分位(如果一半的输出不会发生,则为完整位) .

如您所见,这纯粹是理论上的,坦率地说相当愚蠢。