一个故事讲完哈希洪荒攻击

栏目: 数据库 · 发布时间: 5年前

内容简介:有一天你和你的邻居同时开了一个快递驿站,不过你的运气很好,每天都有很多快递到你这里来,生意红红火火,然而,你的邻居生意很冷清。快递一多,为了取件人方便找到快递,于是你按照快递手机号码的最后两位数字来给快递分类,例如尾号为 01 的放到柜子 1 中,尾号为 02 的放到柜子 2 。如果有人来取快递,他只需要报出他的手机号码,就可以快速找到对应的柜子,然后再根据完整的手机号码在这个柜子里找到对应的快件了。

  一个故事讲完哈希洪荒攻击

生意红火

有一天你和你的邻居同时开了一个快递驿站,不过你的运气很好,每天都有很多快递到你这里来,生意红红火火,然而,你的邻居生意很冷清。

快递一多,为了取件人方便找到快递,于是你按照快递手机号码的最后两位数字来给快递分类,例如尾号为 01 的放到柜子 1 中,尾号为 02 的放到柜子 2 。如果有人来取快递,他只需要报出他的手机号码,就可以快速找到对应的柜子,然后再根据完整的手机号码在这个柜子里找到对应的快件了。

心声恶意的邻居

日子一天天过去,你的店铺越来越火,然而,你邻居的生意冷清到哭晕在厕所里,但是你并没有去在意你的邻居,也没有分担点生意给他,于是,你的邻居心生坏意,决定搞搞你。

他知道你是采用按照快件手机号码末尾两位来分类的,于是他分批买了大量非常廉价的物品,并且把大部分快递的手机号码的末尾的两位弄成是一样的。

于是,你收到了大量的快递,并且大量的快递都被分到了同一个柜子里,导致有些柜子里堆放了大量的快件,挤满到不得不把一些放地下了,然而有些柜子里却是空荡荡的。

这也不仅导致了资源分配不均匀,每次顾客来取快件的时候,还得找好久才能找到。

于是你老爸和你说:要不加大柜子的容量吧。

你:加大容量没用,虽然能短暂不会出现挤满放地下的情况,但本质问题并没有解决。

更换策略

为了解决这个问题,于是你采取了別的策略,把手机号码当做一个数值,然后对这个数值进行取余,例如 手机号 % 99 = 柜子的编号。

每次客人来的时候,你把他的手机号码也进行取余,然后告诉他,去对应的柜子取,取余这个操作虽然麻烦了点,工作量比之前大了,但,躲开了你邻居的攻击,也算值得。

问题的本质

然而好景不长,你的邻居通过观察与测试,发现你是通过手机号码取余来映射到对应的柜子上的,于是,它又找了一堆手机号码取余后值相同的手机号码来搞定,于是,你又奔溃了。

你知道你侄子是学计算机专业的,于是你把这件事告诉了你的侄子,你的侄子一听到这个,就来了劲,于是管不住嘴吹了下面这一大堆:

告诉你,你的这种映射策略相当于我平时学的哈希算法,不管你如何改变你的算法策略,只要被别人知道了你的哈希算法,那么,都会容易遭受到别人的攻击,像你的邻居的那种攻击方式,就叫做哈希洪荒攻击。

我们都知道,在各种数据结构里,有平均时间复杂度和最差时间复杂度之分,对于哈希算法,我们插入 n 个到元素到数组里的话,平均时间复杂度是 O(n),而最差的时间复杂度是 O(n^2);查找某个元素的平均复杂度是 O(1),最差时间复杂度是 O(n),而哈希洪荒攻击就是攻击者有意给出一些特殊值,使得我们每次都遇到了最差时间复杂度。

如何防御?

刚才说了,哈希洪荒攻击的本质就是攻击者掌握了你的哈希算法,所以如何想要防御的话,就需要我们设计出优秀的哈希算法了,什么才算优秀的哈希算法?

1、映射出来的哈希码分布均匀。

2、不容易被破解。

当然,不管你如何设计,一旦攻击者掌握了你的算法细节,那么你都得凉。

那有没有比较好的防御措施呢?

其实,我们可以通过生成一些随机值来加强我们的哈希算法,例如,我们每次建立一张哈希表的时候,我们就随机生成一个新的随机值,来作为哈希算法的一部分。这样一来,即使是同样的内容,放在不同的表里也会产生完全不同的哈希码。

这样一来,攻击者就很难进行预测了,即使发生了碰撞,也是小概率的巧合,而不是攻击者在主动控制,我们也把这个随机的值称之为哈希种子(Hash Seed)。而这类使用哈希种子的哈希算法,我们称之为带密钥哈希算法(Keyed Hash Function)。

当然,上面这种方式只是防御哈希洪荒攻击的一种方式,对于哈希碰撞,在面试中问的最多的应该就是 Java 中的哈希表了,我跟大家补充讲讲 Java8 中是如何解决哈希碰撞的吧。

Java 中的哈希表如果出现了哈希冲突,就会用一个链表来存放哈希码相同的元素,但是如果出现大量哈希码相同的话,那么大量的元素都放在了同一条链表里,这样会导致哈希表的查找时间复杂度是 O(n),为了解决这个问题,当链表中的元素大于等于 8 的时候,就把用红黑树来取代链表,这样一来,可以把最差时间复杂度控制在 O(logn)。

尾声

你侄子吹了一大堆专业名词,对于只读过小学的你,想不懵逼都难,这个时候你憋不住了,抛了一句给你侄子:能不能讲点人话?你只需要告诉我,我该怎么做就行了。

你侄子:我来去给你设计一个程序吧,你到时候只需要把你的手机号码进去就可以了,它会把你自动映射出对应的柜子。

最后,邻居把店铺拆了,开了一家网吧…..

一个故事讲完哈希洪荒攻击


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Impractical Python Projects

Impractical Python Projects

Lee Vaughan / No Starch Press / 2018-11 / USD 29.95

Impractical Python Projects picks up where the complete beginner books leave off, expanding on existing concepts and introducing new tools that you’ll use every day. And to keep things interesting, ea......一起来看看 《Impractical Python Projects》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具