且听疯吟 在此记录扯淡的青春
Does Facebook store plain-text passwords

越来越多的网站开始更加关注安全问题了,比如,Facebook 会在你把密码从 abc123 改为 Abc123 的时候的时候提示你

Your new password is too similar to your current password. Please try another password.

很贴心是不是?但是,他们是怎么做到的?难道 Facebook 保存了用户的明文密码么?

编辑距离

计算两个字符串的相似性,或者说「编辑距离」很容易,我们有很多现成的算法和代码。
但是,显然 Facebook 不会傻到存储明文密码,存储的肯定是 hash("abc123")
而字符串中的差别和 hash 结果并不是一一对应的。两个相近的字符串,其 hash 结果可能差别很大。

simhash

可能你听说过 simhash 算法。Google 就是使用这种算法来做网页查重的。
传统的 hash 算法如 md5,一般尽可能要求结果分布均匀,因此,原始字符串的微小变动也会导致 hash 结果出现很大差异。
而 simhash 是一种局部敏感的 hash 算法,选定位数,提取特征,然后对每一段特征值计算 hash,然后将每一段值处理到 simhash 结果,得到最后的 simhash 值。比较海明距离就可以大概知道两个文档的相似度了。
具体的算法懂得不多就不瞎说了……大概可以推测,对于长文档这种方法是有效的,但是对于短文本,如 password 来说,效果可能不会太好。

Facebook 的做法

事实上这个问题好奇的人也很多,Stack Exchange 上有一个回答 http://security.stackexchange.com/questions/53481/does-facebook-store-plain-text-passwords,下面有一个自称接触过密码验证这部分代码的人肯定了这个猜测。
我觉得这种做法看起来还是挺合理的。

Facebook 用了一种看起来很「土」的方法,操作方法类似这样:

  1. 用户注册,密码 abc123,Facebook 保存了 `hash("abc123")
  2. 用户修改密码,提交新密码 Abc123
  3. Facebook 拿到新密码,根据这个密码,生成一堆类似于 ABC123abc123 这样相近的密码,使用同样的 hash 方法,去和 1 中的 hash 比对,一旦发现有相同的,那么可以判定新密码与旧密码是相似的。

很好的反向思维,不是去计算相似性,而是通过生成一堆相似密码来「暴力」尝试。

其他想法

事实上最初想到这个问题的时候,我考虑过这样的做法:

  1. 用户修改密码操作时,提示输入原密码
  2. server 临时记录用户的原密码
  3. 用户输入新密码,server 比对新旧密码
  4. 完成修改或过期后,销毁临时记录

不过即使是临时记录依然可能存在风险,如果需要较高的安全性的话这种方法是不可取的。