生日攻击其实是一个概率论的问题 也就是说一个看起来很难发生的事情 事实上它发生的概率却很大。这种主观上和事实上的概率差距 让随机攻击成功的几率变的更高 这样的攻击就叫做生日攻击。
生日问题的由来生日问题也叫做生日悖论 它是这样这样描述的。
假如随机选择n个人 那么这个n个人中有两个人的生日相同的概率是多少。如果要想概率是100% 那么只需要选择367个人就够了。因为只有366个生日日期 包括2月29日 。
如果想要概率达到99.9% 那么只需要70个人就够了。50%的概率只需要23个人。
对于现在的幼儿园小朋友来说 一个班上差不多有30人 那么将会有大于50%的几率 班上有两个人的生日是一样的。
听起来是不是很神奇 跟我们第一映像中的基数是不是要少很多。
我们看一张概率图
在实际应用中 可以应用生日问题中的概率模型 从而减少碰撞攻击的复杂度 或者来评估一个hash函数中可能出现碰撞攻击的几率。
怎么计算呢
假如P(A) 是生日相同的概率 那么P(A) 1 – P(A’) 其中P(A’)是生日不同的概率。
一个人生日不同的概率是365/365,两个人生日不同的概率就是365/365 * 364/365 ,依次类推。
我们可以得到23个人生日不同的概率大概就是 0.492703。
也就是说23个人中有两个人生日相同的概率可以大于50%。
再看一张表来个更加直观的描述
生日问题的衍生生日问题的取值范围是在一年的365天之内 也就是说生日只可能有365种可能性。
我们将这个问题扩展一下到一般的情况 假设有一个函数f 它的输出范围是H 那么我们的攻击就是找到两个不同的x y 让f(x) f(y)。
这时候 我们可以称x和y发生了碰撞。
根据概率论的公式 我们想要达到50%的几率 那么需要尝试的次数是:
如果以bits位来表示可能计算出的结果的话 我们可以参考下面的概率表
生日攻击的应用生日攻击一般应用在数字签名中。一般来说为了对机密消息进行签名 因为加密的限制 如果消息很大的情况下 不可能对所有的消息进行签名 通常会对消息计算hash值 然后对这个hash值进行签名。
比如有人想做一个欺诈性的合同 那么会在原合同的基础上进行修改 不断的进行尝试 从而找到一个修改后的合同 让合同和之前合同的hash是一样的 从而导致两者的签名也是一样的。
怎么抵御这种攻击呢 根据我们生日攻击的公式 当然是将签名方案使用的哈希函数的输出长度选择得足够大 以使生日攻击在计算上变得不可行。
本文已收录于 http://www.flydean.com/birthday-attack/
最通俗的解读 最深刻的干货 最简洁的教程 众多你不知道的小技巧等你来发现
欢迎关注我的公众号:「程序那些事」,懂技术 更懂你
构建便捷可及的“大服务”体系、规范高效的“大经办”体系、智能精准的“大治理...
2021年6月9日,亚太内容分发大会暨CDN峰会在北京举行,阿里云智能边缘云技术专家...
SQL是用于数据分析和数据处理的最重要的编程语言之一,因此与数据科学相关的工作...
TOP云 (west.cn)8月3日消息,近日,专注为减脂人群提供一站式专业解决方案的“...
微服务和分布式的区别什么?有什么特点?微服务设计是为了不因为某个模块的升级和B...
一、如何标注 以外部机器人4天标注为例 1、下载源文件 进入数据看板----会话历史...
每个打工人是否都听过领导说:诶,帮我分析下数据啊;研究一下然后做个数据报告给...
还有几天就是新春佳节了,除了放假,这个时候不少用户朋友最期待的要数 TOP云 的...
本文转载自微信公众号「全栈修仙之路」,作者阿宝哥。转载本文请联系全栈修仙之...
租 云服务器 要多少钱一个月?租 云服务器 的价格,有两个影响因素。一是看在哪...