生日攻击

生日攻击方法没有利用Hash函数的结构和任何代数弱性质，它只依赖于消息摘要的长度，即Hash值的长度。这种攻击对Hash函数提出了一个必要的安全条件，即消息摘要必须足够长。生日攻击这个术语来自于所谓的生日问题，在一个教室中最少应有多少学生才使得至少有两个学生的生日在同一天的概率不小于1/2？这个问题的答案为23。

数学上，如果一些函数，当提供一个任意的输入时，返回k类似相等的值中的一个，然后通过重复地计算不同输入的行为，我们期望获得相同的输出大概 1.2 sqrt(k)。对上述的生日悖论，用365替代了k。生日攻击通常用于寻找哈希函数的冲突。为了防止这种攻击，针对一个签名方案的哈希函数的输出的长度能够被广泛选择因此生日攻击变得计算上不可行的。 ^[1]

生日攻击

 下面详细描述生日攻击的方法。

设h：X->Y是一个Hash函数，X和Y都是有限的，并且|X|>=2|Y|，记|X|=m，|Y|=n。显然至少有n个碰撞，问题是如何去找到这些碰撞。一个很自然的方法是随机选择k个不同的元素x1,x2,x3,.....,xk ∈X,计算yI=h(xi)，1<=i<=k，然后确定是否有一个碰撞发生。这个过程类似于把k个球随机地扔到n个箱子里边，然后检查看是否某一箱子里边至少有两个球。k个球对应于k个随机数x1,x2,x3,.....,xk，n个箱子对应于Y中的n个可能的元素。我们将计算用这种方法找到一个碰撞的概率的下界，该下界只依赖于k和n，而不依赖于m。

因为我们关心的是碰撞概率的下界，所以可以假定对所有y∈Y，有|h-1(y)|≈m/n。这个假定是合理的，这是因为如果原像集h-1(y)( y∈Y)不是近似相等的，那么找到一个碰撞的概率将增大。 因为原像集h-1(y)( y∈Y)的个数都近似相等，并且xI(1<=i<=k)是随机选择的，所以可将yI=h(xi)，1<=i<=k视作Y中的随机元素（yi(1<=i<=k)未必不同）。但计算k个随机元素y1,y2, .....yk∈Y是不同的概率是一件容易的事情。依次考虑y1,y2, .....yk。y1可任意地选择；y2 ≠y1的概率为1-1/n；y3 ≠y1 ,y2的概率为1-2/n；.....；yk ≠y1,y2, .....,yk-1的概率为1-(k-1)/n。 因此，没有碰撞的概率是（1-1/n）(1-2/n）.....(1-(k-1)/n）。如果x是一个比较小的实数，那么1-x≈e-x，这个估计可由下式推出：e-x=1-x+x2/2!-x3/3!+ .....。现在估计没有碰撞的概率（1-1/n）(1-2/n）.....(1-(k-1)/n）约为1-e-k(k-1)/2n。我们设ε是至少有一个碰撞的概率，则ε≈1-e-k(k-1)/2n，从而有k2-k≈nln(1/(1-ε)2)。去掉-k这一项，我们有k2≈nln(1/(1-ε)2)，即k≈sqrt(2nln(1/(1-ε)2))。 如果我们取ε=0.5，那么k≈1.17 sqrt(n)。这表明，仅sqrt(n)个X的随机的元素就能以50%的概率产生一个碰撞。注意ε的不同选择将导致一个不同的常数因子，但k与sqrt(n)仍成正比例。

如果X是一个教室中的所有学生的集合，Y是一个非闰年的365天的集合，h(x)表示学生x的生日，这时n=365，ε=0.5，由k≈1.17 sqrt(n)可知，k≈22.3。因此，此生日问题的答案为23。

生日攻击隐含着消息摘要的长度的一个下界。一个40比特长的消息摘要是很不安全的，因为仅仅用220（大约一百万）次随机Hash可至少以1/2的概率找到一个碰撞。为了抵抗生日攻击，通常建议消息摘要的长度至少应取为128比特，此时生日攻击需要约264次Hash。安全的Hash标准的输出长度选为160比特是出于这种考虑。

中间相遇攻击是生日攻击的一种变形，它不比较Hash值，而是比较链中的中间变量。这种攻击主要适用于攻击具有分组链结构的Hash方案。中间相遇攻击的基本原理为：将消息分成两部分，对伪造消息的第一部分从初试值开始逐步向中间阶段产生r1个变量；对伪造消息的第二部分从Hash结果开始逐步退回中间阶段产生r2个变量。在中间阶段有一个匹配的概率与生日攻击成功的概率一样。

在修正分组攻击中，为了修正Hash结果并获得期望的值，伪造消息和一个分组级联。这种攻击通常应用于最后一个组，因此也称为修正最后分组攻击。差分分析是攻击分组密码的一种方法。这种攻击也可用来攻击某些Hash算法。

针对Hash算法的一些弱点可对Hash算法进行攻击，可利用Hash算法的代数结构及其所使用的分组密码的弱点来攻击一些Hash方案。例如针对DES的一些弱点（即互补性、弱密钥、密钥碰撞等）来攻击基于DES的Hash方案。

使k个人中至少有两个人生日相同的概率大于0.5的最小k值是多少?不考虑2月29号假定每个生日出现的概率一样  
则定义:P(n,k)=Pr[k个元素中至少有一个元素重复出现，其中每个元素出现的概率均为1/n] 
所以，只是找出使得P(365,k)>=0.5的最小的k，用Q（365，k）表示没有出现的概率，若k>365,则所有值都不等是不可能的。所以假定k<=365。设k个元素均不重复的数为N，那么，第一个元素有365种取值，第二种元素有364种取值，等等，因此，不同的方式数为：N=365*364*--（365-k+1）=365！/（365-k）！ 
如果允许重复 那么每一个元素有365种取法，共365^k种取法，所以不重复的概率为无重复数除以总数：Q（365，k）=365！/（365-k）！365^k  则P(365,k)=1-365！/（365-k）！ 
对于那些没考虑过该问题的人来说，该概率大的出奇。许多人以为要使至少有一个重复的概率大于0.5，那么大约应有100人，事实上，因为P(365,23)=0.5037,所以人数为23 ，k=100时至少有一个重复的概率为0.9999997，结果显得出乎意料的原因也许如下：如果你考虑某个组里有其他人和这个人有相同生日的概率很小 
但是这里我们考虑的是任意两个人生日相同的概率 在23 个人中有23*(23-1)/2=253种不同的双人组合，因此生日的概率比较大。