这意味着平均需要花费$ 2 ^ {n-1} $来尝试查找给定消息$ x $的冲突消息$ y $，因此$ H（y）= H（x）$而$ y \ ne x $。
但是，生日攻击（例如，可以任意选择$ x $和$ y $，但是当然仍然需要$ H（x）= H（y）$）应该会更快，并且只需花费$ 2 ^ {n / 2} $来尝试查找冲突。
我看到了如何根据时间复杂度进行计算-因为我们现在正在研究所有到目前为止，所有猜测的元组（其中有$ n ^ 2 $个），碰撞的可能性现在呈平方增长，而不是线性增长。
但是我们是否不应该还需要空间来存储所有已经尝试$ x $和$ y $？如果我们不这样做，我们如何甚至可以比较到目前为止枚举的所有哈希的所有元组？似乎几乎不可能进行这样的生日袭击，因为$ 2 ^ {n / 2} $位存储空间很大，甚至都没有考虑到在恒定时间内访问所有存储空间的问题。
更新：我已经找到了http://www.cs.umd.edu/~jkatz/imc/hash-erratum.pdf，这似乎表明在恒定的空间内可以进行攻击。但是，给出的证明和解释超出了我的理解范围。
#1 楼
您引用的链接中描述的方法基于弗洛伊德（Floyd）的循环查找算法，也称为“乌龟和野兔”算法。这是一种用于检测迭代映射图中的循环的通用算法，下面我将首先对其进行介绍。具体来说，考虑由$ x_i = H（x_ {i- 1}）$用于某些地图$ H $和某些初始值$ x_0 $。如果此序列是循环的，那么我们有一些整数$ j> 0 $和$ k> 0 $，使得$ x_j = x_ {j + k} $，因此对于所有变量，$ x_i = x_ {i + nk} $整数$ i \ ge j $和$ n \ ge 0 $。
尤其适用于$ i = nk $和满足$ n \ ge j / k $的任何整数$ n $，产生$ x_i = x_ {2i} $。
因此，如果序列$（x_i）$是循环的，则存在整数$ i> 0 $使得$ x_i = x_ {2i} $。相反，这样一个整数的存在也清楚地表明该序列必须是循环的（其周期均匀地除以$ i $）。
因此得出结论，要检测序列$（ x_i）$，对于任何正整数$ i $，只要检查$ x_i = x_ {2i} $是否足够。我们可以通过跟踪序列的两个元素$ y = x_i $和$ z = x_ {2i} $（在迭代$ i = 0 $都初始化为$ x_0 $）来使用常量空间来迭代地执行此操作在每个连续的迭代中，将它们更新为$ y \得到H（y）$和$ z \得到H（H（z））$。
如果找到这样的$ i $，我们我们将知道序列$（x_i）$是循环的。现在，我们有两种可能性：初始值$ x_0 $是循环的一部分，或者不是。在后一种情况下，我们有$ x_0 \ ne x_i $，但是$$ H ^ {（i）}（x_0）= x_i = x_ {2i} = H ^ {（i）}（x_i），$$ ve因此在$ i $倍的迭代映射$ H ^ {（i）} $中发现了一个碰撞，这又意味着在基础映射$ H $中存在碰撞。
剩下要做的就是找到潜在的冲突。为此，我们将迭代倒回$ i $步骤，使$ y = x_0 $和$ z = x_i $，然后一次将它们前进一步，这一次是$ y \得到H（y）$和$ z \得到H（z）$，因此，在迭代$ j $时，我们将始终具有$ y = x_j $和$ z = x_ {i + j} $。由于我们知道$ x_0 \ ne x_i $和$ x_i = x_ {2i} $，因此得出在$ 0 $和$ i-1 $之间必须有一些$ j $，这样$ x_j \ ne x_ {i + j } $，但$ x_ {j + 1} = x_ {i + j + 1} $，因此$ H（x_j）= H（x_ {i + j}）$。当我们发现$ j $时，即当我们找到第一个$ y $和$ z $使得$ H（y）= H（z）$时，我们停止；这就是我们一直在寻找的冲突。
此算法仅需要空间即可存储固定数量的值：$ x_0 $，$ y $和$ z $。需要多少时间？好吧，如果$ j $和$ k $是满足$ x_j = x_ {j + k} $的最低正整数，则弗洛伊德的循环发现算法将采用$ i = k \ lceil j / k \ rceil
现在，如果$ H $是$ m $元素集上的随机函数，则，根据生日悖论，第一次碰撞之前的预期步数$ \ mathbb E [j + k] $为$ O（\ sqrt {m}）$。因此，上述碰撞发现算法的预期运行时间也是$ O（\ sqrt {m}）$。
评论
$ \ begingroup $
如果出现两种可能性中的第一种（初始值$ x_0 $是循环的一部分），则算法将失败。通过在检测到$ x_i = x_ {2i} $之后检查$ x_0 = x_i $，可以廉价地检测到它。如果发生这种情况，除了随机尝试另外$ x_0 $之外，我们别无选择。幸运的是，这具有较低的赔率$ O（1 / \ sqrt {m}）$。论据：如果我们在恰好$ i $次迭代后发生冲突，则所有$ 0 \ le j $ \ endgroup $
–fgrieu♦
2012年7月24日11:24
评论
关于该主题的经典文章是具有密码分析应用程序的并行碰撞搜索