什么是哈希洪水攻击?(Algorithmic complexity attack或Hash-Flooding Attack)

【在知乎看到的,觉得那个菜鸟驿站的回答很不错,想自己也来写一篇。】

学校版

你是一名在校学生,有很多作业要做。什么语文的数学的英语的。

你有一份课程表,上面写着每门课每个章节多久教授完。由于每个章节教授完就要布置一次作业,第二天上交,于是你就把这些日期记到自己本子上,写成固定长度。例如化学习题册第二章11月19日完课,要11月20日交作业,你就写成1120,数学试卷第一章要求11月21日交,于是你就写成1121,你根据课程安排计划,写成的作业上交日期计划的这个过程叫哈希(hash),你写下的值就叫哈希值。这些值放在一起就成了哈希表(hash table)

【不过请注意,哈希表的真正算法并不是这样的,以上的例子只是通俗的理解。】

你知道作业布置计划,即每个章节讲授完立马布置作业,于是你只要知道你学的某个章节多久教授完,就知道那个章节的作业要多久交。这个方法效率很高。

然而有可能恰好一天完结两个章节,例如语文第一章和数学第一章恰好都在11月20日完课,作业都要11月21日交,那么你的笔记本上就有了两个“1121”,有两个相同的值,这就叫哈希碰撞( collision )

如何尽量让一天不要做一张以上卷子,减少哈希碰撞呢?于是一位老师建议说,作业布置慢一点,这个学期的作业下个学期交也可以,那么两份不同作业要在同一天上交的概率也更小了。这就是 扩大哈希值的取值空间 。

一天做一张卷子对你来说压力并不大,你做完卷子完全可以活蹦乱跳地出去找女朋友玩(如果你有的话)。

然而事情没那么简单。

另一位丧心病狂的负责调课的老师注意到了这点,希望大家用每分每秒的时间来学习,所以原本身体健康的体育老师突然就生病了,星期五的体育课也被改成了数学课。其他音乐老师美术老师也都不是外出考察去了就是家里有事,这些课统统被换成了主课。两个章节在同一天完成的概率就很高了,那么你现在一天要做一张以上的卷子的概率也就很高了。这就叫 哈希洪水攻击。(Algorithmic complexity attack或Hash-Flooding Attack)

这种情况下有没有办法防止你一天要做一张以上的卷子呢?

以前是每章节上完就布置作业,这样老师只要让不同的两章节在同一天上完,就能让你多做卷子。而现在你向班主任提意见,一种新的作业布置计划,说每章节上完不立即布置作业,例如11月20日数学第五章上完,11月23日才布置作业,那么即使11月20日语文第三章也上完了并布置作业,那么你也不用一天做两张卷子了。这就叫带密钥哈希算法(Keyed Hash Function)

然而那位老师还是有可能摸清规律,破解了你的算法,虽然他不能改变作业布置计划,不能改变算法,却能把语文第三章也换到11月23日。你为了一天不做那么多卷子,又想出了更难以破解的作业布置计划与之抗衡。如此往复,这就是密码学的攻防。

Leave a Reply