生日攻击

生日攻击

原图链接

中文名: 生日攻击 别 名: 平方根攻击

生日攻击是一种密码学攻击手段，所利用的是概率论中生日问题的数学原理。这种攻击手段可用于滥用两个或多个集团之间的通信。此攻击依赖于在随机攻击中的高碰撞概率和固定置换次数（鸽巢原理）。

目录

简介

生日攻击是一种密码学攻击手段，所利用的是概率论中生日问题的数学原理。这种攻击手段可用于滥用两个或多个集团之间的通信。此攻击依赖于在随机攻击中的高碰撞概率和固定置换次数（鸽巢原理）。使用生日攻击，攻击者可在中找到散列函数碰撞，为原像抗性安全性。然而，量子计算机可在

内进行生日攻击（虽然饱受争论）。

理解问题

主条目：生日问题

举个例子，想象一位老师问一个有30名学生的班级（n = 30）每个人的生日在哪一天（为简便，此处省略闰年）以确定是否有两个学生同一天生日（对应碰撞 ）。从直觉角度考虑，机率看起来很小。若老师选择特定日期（例如9月16日），则至少有一名学生在那天出生的几率是中可看出。

数字签名敏感度

数位签章可对生日攻击十分敏感。设想一条被首次计算。假设爱丽丝与鲍伯牵涉到签名诈骗合同。马洛里准备了一份正常合同m和一份伪造合同m'。她随后发现m所在的位置数可在不改变原意的情况下（如插入逗号、清空行、在句后增加一两个空格、替换同义词等等）被更改。通过结合这些更改，她可新建诸多m的变体且均为正常合同。

相似情况下，马洛里也为伪造合同m'新建了诸多变体。她随后应用哈希函数到所有变体直到她找到与正常合同有着相同哈希值

的伪造合同位置。她随后将正常合同带给鲍勃签名。在鲍勃签名完后，马洛里将签名取下并依附到伪造签名上。此签名“证实了”鲍勃签署了伪造合同。

此例中，攻击概率与原始的生日问题稍有不同，因为马洛里将在寻找两份具有相同哈希的正常合同与伪造合同时将一无所获。马洛里的策略是生成一份伪造和一份正常的合同。生日问题公式适用于n为合同对数的情况下。但马洛里所生成的哈希数实际上为2n。

为避免这种攻击，用于签名方案的哈希函数的输出长度应够大以从计算角度防止生日攻击。换言之，位数应为防止普通暴力破解所需位数的两倍。

除了使用更大的位数长度外，签名者（鲍勃）可以在签名前做出一些随机且无害的更改，并且在自己的手上留下一份合同副本以在法庭上展示出他的签名与正常合同上的匹配，而不匹配伪造合同。

离散对数 Pollard Rho 算法是一项使用生日攻击以计算离散对数的算法。

生日攻击其实是一个概率论的问题，也就是说一个看起来很难发生的事情，事实上它发生的概率却很大。这种主观上和事实上的概率差距，让随机攻击成功的几率变的更高，这样的攻击就叫做生日攻击。

生日问题的由来

生日问题也叫做生日悖论，它是这样这样描述的。

假如随机选择n个人，那么这个n个人中有两个人的生日相同的概率是多少。如果要想概率是100%，那么只需要选择367个人就够了。因为只有366个生日日期（包括2月29日）。

如果想要概率达到99.9% ，那么只需要70个人就够了。50%的概率只需要23个人。

对于现在的幼儿园小朋友来说，一个班上差不多有30人，那么将会有大于50%的几率，班上有两个人的生日是一样的。

听起来是不是很神奇？跟我们第一映像中的基数是不是要少很多。

生日问题的衍生

生日问题的取值范围是在一年的365天之内，也就是说生日只可能有365种可能性。

我们将这个问题扩展一下到一般的情况，假设有一个函数f，它的输出范围是H，那么我们的攻击就是找到两个不同的x，y，让f(x)=f(y)。

这时候，我们可以称x和y发生了碰撞。

生日攻击的应用

生日攻击一般应用在数字签名中。一般来说为了对机密消息进行签名，因为加密的限制，如果消息很大的情况下，不可能对所有的消息进行签名，通常会对消息计算hash值，然后对这个hash值进行签名。

比如有人想做一个欺诈性的合同，那么会在原合同的基础上进行修改，不断的进行尝试，从而找到一个修改后的合同，让合同和之前合同的hash是一样的，从而导致两者的签名也是一样的。

怎么抵御这种攻击呢？根据我们生日攻击的公式，当然是将签名方案使用的哈希函数的输出长度选择得足够大，以使生日攻击在计算上变得不可行。

另请参阅

碰撞攻击

中途相遇攻击