生日攻击是一种
密码学攻击手段,所利用的是
概率论中生日问题的
数学原理。这种攻击手段可用于滥用两个或多个集团之间的通信。此攻击依赖于在随机攻击中的高
碰撞概率和固定置换次数(
鸽巢原理)。
举个例子,想象一位老师问一个有30名学生的班级(n = 30)每个人的生日在哪一天(为简便,此处省略
闰年)以确定是否有两个学生同一天生日(对应
碰撞 )。从直觉角度考虑,机率看起来很小。若老师选择特定日期(例如9月16日),则至少有一名学生在那天出生的几率是,约为7.9%。但是,与我们的直觉相反的是,至少一名学生和另外任意一名学生有着相同生日的几率大约为70.63%(n = 30时),从方程中可看出。
数位签章可对生日攻击十分敏感。设想一条被首次计算(f为
密码杂凑函数)所签名的信息,且随后又使用了一些密钥来签名。假设
爱丽丝与鲍伯牵涉到签名
诈骗合同。马洛里准备了一份正常合同m和一份伪造合同m'。她随后发现m所在的位置数可在不改变原意的情况下(如插入逗号、清空行、在句后增加一两个空格、替换同义词等等)被更改。通过结合这些更改,她可新建诸多m的变体且均为正常合同。
相似情况下,马洛里也为伪造合同m'新建了诸多变体。她随后应用哈希函数到所有变体直到她找到与正常合同有着相同哈希值的伪造合同位置。她随后将正常合同带给鲍勃签名。在鲍勃签名完后,马洛里将签名取下并依附到伪造签名上。此签名“证实了”鲍勃签署了伪造合同。
此例中,攻击概率与原始的生日问题稍有不同,因为马洛里将在寻找两份具有相同哈希的正常合同与伪造合同时将一无所获。马洛里的策略是生成一份伪造和一份正常的合同。生日问题公式适用于n为合同对数的情况下。但马洛里所生成的哈希数实际上为2n。
为避免这种攻击,用于签名方案的哈希函数的输出长度应够大以从计算角度防止生日攻击。换言之,位数应为防止普通
暴力破解所需位数的两倍。
除了使用更大的位数长度外,签名者(鲍勃)可以在签名前做出一些随机且无害的更改,并且在自己的手上留下一份合同副本以在法庭上展示出他的签名与正常合同上的匹配,而不匹配伪造合同。
离散对数 Pollard Rho 算法是一项使用生日攻击以计算
离散对数的算法。