网站被拖库后，一些弱口令的 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 即可。

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

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

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

---

A：key 之间会存在冲突吗？

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

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

---

A：账号 <"jack", "123456"> 和账号 <"jack1", "23456"> 的 key 会不会一样？

Q：当然不会。二元组的 hash 值，显然不能先合并，再计算。而必须先单独计算，合并后再计算。现实中我们可以用 HMAC 函数，例如：

key = hmac_sha256(user, password)

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

---

A：虽然 key_set 表的数据是无意义的，但其他表仍会泄露用户名等信息，这样还有意义吗？

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

---

A：如果有人忘记了密码，那么这个用户的 key 是不是永远不知道了？

Q：确实~ 不知道密码就无法算出 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 表里填充大量无用数据，故意将表撑大。而攻击者并不知道哪些是真实的，哪些是无用的，只能都将它们进行索引等处理，这样就增加了破解所需的资源！

如果攻击者直接用现成数据库查表的话，那效率显然会非常低，密码破解速度将被限制在数据库查询速度上。对于数据库来说，几万的 query/s 已经很快了，通常也足够用了；但对于跑字典，几万的 hash/s 就太慢了。例如经典的破解工具 hashcat，简单的算法能达到上亿的 hash/s，如果 GPU 够好，甚至还可以再提高几个量级！

这个速度，对于查表来说是很难达到的 —— 即使攻击者自己实现一套更优化的算法。因为查表需要大量的内存占用和访问，使得很难利用硬件加速。（可参考 对硬件有抵抗效果的 Hash 算法）

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

对于无用的填充数据，我们也不是完全随机生成的，而是通过一定的规律去产生。例如基于一个口令进行推导：

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 是不会有安全隐患的。

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

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