安全路透社
当前位置:安全路透社 > 网络转载 > 正文

如何利用查表瓶颈,对抗口令Hash破解

前言

网站被拖库后,一些弱口令的 hash 很容易被破解还原。本文讲解一种新的存储方式,使攻击者跑 hash 变得更麻烦。

传统储存

对于大多数系统,用户名和密码都是这样存储的:

user password other info
alice e37a 781a 0d06 47eb
bob 8fe4 516a de2f b73c

一个账号对应一个密码,这是很自然的想法,实现起来也很方便;而且口令在存储前经过 hash,也是比较安全的。

不过,尽管口令 不是明文 的,但它和账号的对应关系却是明确的。攻击者可针对某个有价值的用户,单独针对其 hash 进行暴力破解。

那么是否有方案,既能实现用户名、密码的认证,同时又不透露它们存储时的对应关系?

合并储存

既然不能透露对应关系,那显然需要一个单独的表来存放它们 —— 事实上这个表只需一个字段就可以,只储存 <用户名,密码> 二元组的 hash:

key = hash(user, password)

这样,唯一的 <用户名, 密码> 对应唯一的 key;而通过 key 既看不出用户名,也看不出密码!

table_key_set

key
20d2 7523 3cb5 7dbd
56ef ae28 9f39 c83f

其他和密码无关的资料,则储存在 资料表 里:

table_userinfo

user other info
alice
bob

(资料表里的用户名虽然是明文的,但它不属于认证需要的数据,因此不在本文讨论的保护范围内)

认证步骤

用户注册时,后端先通过 资料表 查询用户名是否已注册,保证用户名是唯一的。然后将 <用户名,密码> 的 hash 值(即 key)添加到 key_set 表里;其他信息则写入资料表。

登录时,服务器根据提交上来的 <用户名,密码>,使用同样的算法算出 key,并检索是否存在于 key_set 表中 —— 若存在,则认证成功;反之,则认证失败。

认证成功后,即可根据 用户名 访问 资料表 中相应的记录,进行具体的业务操作。

修改密码很简单,只需删除旧 key,添加新 key 就可以;注销用户也同理,直接删除 key 即可。

这样,认证相关的数据中,就不会出现任何有意义的信息了,甚至连用户名都没有!

FAQ

Q:将所有账号的认证信息混在一起,会相互干扰吗?比如用户 A 和用户 C 使用相同的密码,会不会有影响?

A:显然不会。因为 key 并不仅仅代表密码,同时还蕴含了用户名。只有当 用户名、密码同时符合时,才能匹配到数据库中的 key。只要有一项不符合,仍然查无此 key。

Q:key 之间会存在冲突吗?

A:尽管用户名是唯一的,但 key 还结合了密码因素,因此不能保证所有 key 绝对唯一,理论上仍有冲突的可能。

不过无需担心,只要 key 足够长就能有效避免。例如选择 32 字节,那么空间就有 256^32 ≈ 10^77。即使网站有 10 亿用户,冲突的几率仍小得忽略不计。

Q:账号 <”jack”, “123456″> 和账号 <”jack1″, “23456″> 的 key 会不会一样?

A:当然不会。二元组的 hash 值,显然不能先合并,再计算。而必须先单独计算,合并后再计算。现实中我们可以用 HMAC 函数,例如:key = hmac_sha256(user, password)

一般需要同时 hash 两个参数的场合,用 HMAC 是最方便的,并且更权威。

Q:虽然 key_set 表的数据是无意义的,但其他表仍会泄露用户名等信息,这样还有意义吗?

A:我们的目的并不是防止 用户名 等信息的泄露,而是抹掉 用户名 与 密码 之间的关联,让破解更麻烦(有多麻烦下面会讲解)。

Q:如果有人忘记了密码,那么这个用户的 key 是不是永远不知道了?

A:确实~ 不知道密码就无法算出 key。不过重置密码的功能还是可以实现的,等会我们会讨论。

优势

用了该方案之后,即使 key_set 表泄露,用户名及密码都不会暴露。攻击者还得设法获得其他表,或从网站上爬取数据,才能获得实际的用户名。

事实上就算知道某个用户名,也无法找到对应的 key —— 因为计算 key 不仅需要用户名,还要密码!光知道用户名是不够的。

当然,即使不知道某个用户对应的 key,但想破解其明文口令,仍然是可行的。假设攻击者确定有个叫 alice 的用户,则可通过如下逻辑跑字典:

for each word in dict
    key = hash('alice', word)

    # 查询该 key 是否存在
    if table_key_set.exist(key)
        print '破解成功,密码是', word

不过和传统破解不同的是,现在每猜一个口令就得查表一次,成本就大幅增加了!并且现有的绝大多数破解工具,都没有提供基于查表的解决方案,因此给攻击者增加了不少复杂度!

提升成本

作为防守方,也可以人为提高查表门槛 —— 我们往 key_set 表里填充大量无用数据,故意将表撑大。而攻击者并不知道哪些是真实的,哪些是无用的,只能都将它们进行处理,这样就增加了破解所需的资源!

如果攻击者直接用现成数据库查表的话,那效率显然会非常低,密码破解速度将被限制在数据库查询速度上。对于数据库来说,每秒几万次的查询已经很快了,通常也足够用了;但对于跑 hash,这点速度就太慢了 —— 用经典 hashcat 跑字典,简单的算法每秒都是几亿 hash/s!除非攻击者自己实现一套算法,对查表进行充分优化。但是要达到每秒几亿次的查询速度,还是非常困难的!并且查表需要大量的内存占用和访问,使得很难通过 GPU 资源来加速,原因可参考 对 GPU 有抵抗效果的算法

同时,数据库体积被人为撑大后,也极大增加了拖库时的下载成本!

当然无用数据也不是完全随机生成的,而可以通过一定的规律去产生。例如:

for i = 0 ... 10000
    key = hmac(PWD, i)
    table_key_set.add(key)

这样我们只需提供 PWD 这个值,就能产生 10000 条无用记录。未来数据库太大时,可以用同类似的办法,删除一些无用记录。

此外,即使忘了无用记录的条数,通过二分法用少量的次数就可以试出!

加盐

前面为了简单描述,我们省略了和  相关的东西,现在将其补回来。

由于  需要和 用户名 关联,因此无法存储在 key_set 表中,只能存放其他表中,例如存在 资料表 里。

用户注册时,生成一个随机串作为盐,并保存。接着用 <用户名,密码,盐> 三元组的 hash 值作为 key:

key = hash(username, password, salt)

其他的步骤则保持不变。

登录时,先根据用户名查询出相应的盐,然后使用同样的方式计算 key。这样,就把盐融入到 key 里面了。

加盐还是很有必要的。因为用户名和密码大多是有规律的,如果不加盐,那么 key 也是防不住彩虹表的。

忘记密码

现在来讲解本方案的唯一缺陷 —— 密码重置。

由于用户名和密码不再有关联,因此一旦有用户忘了密码,想对其进行重置,这就非常棘手了 —— 因为不知道密码,就无法知道对应的 key!

但不用担心,解决方案还是有的。首先可通过第三方手段,证明这个帐号的拥有权,比如短信、邮箱等。

通过认证后,用户就可以设置新密码了 —— 系统生成新 key,添加到 key_set 表里,旧 key 则仍保持残留

但是,残留会有问题吗?显然有!如果旧密码以后想起来了,那还是可以登录的。这样一个帐号就可以有多个密码登录,显然不安全!因此得改进。

事实上,只要在重置密码时,将  也进行重置,就可以避免这个问题了。因为用新盐算出的新 key,和旧 key 完全不搭边了:

new_key = hash(username, password, new_salt)

同时,旧盐一旦被覆盖,也就永远消失了,没有任何人知道。不知道旧盐,当然就无法计算旧 key。所以那些残留的 key,是不会出卖曾经用过的密码的!

当然唯一的缺陷,就是残留的 key 会白白占用一条记录。不过我们本来就有意将 key_set 表撑大,因此也就不在乎这些残留数据了。如果真担心用户不断重置密码,产生大量无用的 key 将数据库撑爆的话,倒是可以限制重置密码的频率。

这里的巧妙之处在于一盐两用:最新的盐,则是防止拖库后的彩虹表攻击;曾经用过的盐,则起到 密钥的作用。并且这个密钥已从世上消失了,因此残留的 key 是不会有安全隐患的。

总结

和传统存储方案相比,该方案将敏感信息独立存储,并且不再显式透露 用户名 和 密码 的关系。

虽然从算法上看,该方案并没有提升暴力破解的难度,但从工程化角度来看,倒是增加了暴力破解的复杂度 —— 只要攻击者的查表算法优化的不够好,那么跑字典的速度就难以提升,成为密破解的瓶颈。

*本文作者:EtherDream,转载请注明来自 FreeBuf.COM

未经允许不得转载:安全路透社 » 如何利用查表瓶颈,对抗口令Hash破解

赞 (0)
分享到:更多 ()

评论 0

评论前必须登录!

登陆 注册