我认为找到$ h（a）= h（b）$和另一个$ O（| T | ^）将是$ O（| T | ^ {1/2}）$ {1/2}）$来找到第三个，但是在考虑时，这是错误的。如何计算呢？
#1 楼
挥舞着手的论据是这样的：当您累积$ n $哈希输出时，您实际上是在生成$ n ^ 3/6 $三胞胎，每个三胞胎都有概率$ t ^ {-2} $是三向碰撞（其中$ t = | T | $，即输出空间的大小）。因此，您应该期望在$ n ^ 3/6 = t ^ 2 $，即$ n = 6·t ^ {2/3} $时出现第一个三向碰撞。对于具有128位输出的完美哈希函数，这意味着您将需要大约$ 2 ^ {88} $哈希函数调用。现在这只是一个近似值，因为它不能给出确切的结果，因为三胞胎并不完全相互独立；但它产生适当的数量级。
更重要的是，这假设一个完美的哈希函数。对于具体的哈希函数，即使是“安全”的哈希函数，也可以更快地获得多冲突。如Joux在2004年所展示的，内部状态为$ s $位的“迭代哈希函数”（例如MD5或SHA-256），您只需要产生$ k $个“简单”冲突（单个费用为$ 2 ^ { s / 2} $）来推导$ 2 ^ k $多碰撞。当$ s $等于输出大小时（如@Codes所说，这称为“窄管设计”），这比上面的成本低得多；即使MD5没有损坏，它仍将允许进行四次碰撞，费用为$ 2 ^ {65} $，进行八次碰撞，费用为$ 2 ^ {66} $，依此类推...通常的安全性“对$ 2 ^ {s / 2} $的碰撞抵抗能力”与“超过$ 2 ^ {s / 2} $的抵抗力”不相容。
评论
$ \ begingroup $
我为我的幼稚而道歉，但是请您解释一下为什么有$ n ^ 3/6 $三胞胎吗？
$ \ endgroup $
– Moshe
2014年1月28日在21:26
$ \ begingroup $
大小为$ n $的三个选择表示$ n ^ 3 $，但顺序无关紧要（三元组$（a，b，c）$，$（a，c，b）$，$（b，a， c）$ ...是相同的），因此您必须除以$ 3！$，恰好等于$ 6 $。
$ \ endgroup $
–托马斯·波宁（Thomas Pornin）
2014年1月28日在22:11
$ \ begingroup $
您遇到了一次费用为$ l \ cdot 2 ^ {64} $的$ 2 ^ l $方式碰撞。因此，您将获得成本为$ 2 ^ {66} = 4 \ cdot 2 ^ {64} $的16向碰撞，而不仅仅是八向碰撞。
$ \ endgroup $
– CodesInChaos
2014年3月3日13:50
$ \ begingroup $
当$ n $大时，$ n ^ 3/6 $和$ n（n-1）（n-2）/ 6 $几乎是同一回事。在讨论近似值时（例如此处的情况），这种缩短是有效的。
$ \ endgroup $
–托马斯·波宁（Thomas Pornin）
2014年11月23日下午16:52
评论
对于窄管（甚至本地的宽管）构造，您将得到四向哈希冲突，而仅需花费两次普通碰撞的代价。