密码相似性

场景

用户输入新密码，当与旧密码相似时，禁止修改。

常见非安全的做法

明文存储用户密码，通过编辑距离算法来计算相似性。

kitten 和 sitting 的距离是 3。将 kitten 变为 sitting 的最小处理方式如下：

kitten →sitten（将 k 改为 s）

sitten → sittin（将 e 改为 i）

sittin → sitting（最后加入 g）

明文存密码成惯例？Facebook 6 亿用户密码可被 2 万员工直接看

目前大多数的网站一般采用 MD5(password+salt) ，更安全的采用 bcrypt 算法来存储密码摘要。那么如何判断被 hash 过后的密码相似性呢？

理所当然的我们会想到，是否有一种 hash 算法，可以满足相似性判断呢？

局部敏感哈希

局部敏感哈希(Locality Sensitive Hashing，LSH)，常见的算法有：

• MinHash

• TLSH

• SimHash

看起来似乎可以，密码 hash 过后的也可以进行编辑距离算法了，是这样吗？

LSH 安全吗？

当数据泄漏后，虽然不像明文密码那样危险。

hash 过后的密码摘要既然可以进行相似性匹配了，那么攻击者理所应当也可以加以利用。

LSH 的使用场景是大量的文本相似性，而非密码学。

安全的思路

背景

在密码学中，一个优秀的 hash 算法应该满足以下特性：

• 雪崩效应，即输入发生最微小的改变（如一个字符），也会导致输出的巨大变化。

• 不可逆性，不能从摘要反推出原文。

• 确定性，相同的输入，相同的输出。

• 抗碰撞性，不能出现不同的输入得到相同的输出。

在密码相关场景，不属于密码学范畴的 hash 算法，都不要使用。

可以使用的 hash 算法：

• 精心设计的密钥扩展算法如 PBKDF2 、 bcrypt 和 scrypt 。

• OpenWall 的的 Portable PHP password hashing framework 。

• PBKDF2 在 PHP、C＃、Java 和 Ruby 的实现。

• crypt 的安全版本。

本文主要不是介绍如何正确选择密码 hash 算法的，感兴趣的可以看 infoQ 上这篇文章。

如何正确对用户密码进行加密？

业务场景

首先我们明确一下用户密码格式，目前通用的格式为:

6~18 个字符，可以使数字、字母或下划线，以字母开头，区分大小写。

一、密码简化

用户常见新密码修改一般为在旧密码后新增数字，如 wodemima 修改为 wodemima123。

因此，在数据库中新增字段，保存如下的计算结果。

根据如上伪代码，wodemima 与 wodemima123 所计算出的 s_password 是一致的。

优点

• 实现简单

• 能保障部分用户新的密码与旧密码不相似

• 只需多计算一次 hash ，对于 bcrypt 这样慢哈希函数，执行时间是可以接受的

缺点

• 不满足部分用户如从 wodemima 改为 wodemimaabc 的场景

• 对于原密码后几位都为数字的用户不友好，原密码 s00001 修改为 s88888 ，判断为相似

二、枚举编辑距离

密码可以使用数字、字母或下划线，当编辑距离为 1 的情况下，视为相似密码。

//如： 用户密码为 wodemima//插入Awodemima wAodemima woAdemima wodeAmima ...//删除odemima wdemima woemima ...//替换bodemima wbdemima wobemima ...

那么当编辑距离 = 1 时，允许字符数量为 L ，当前密码长度为 N，意味着可以删除字符 N 次，替换字符 N * L 次，插入字符 (N+1) * L 次。

当编辑距离为 2 时，意味在编辑距离为 1 为结果上，再进行一次枚举，所以当编辑距离为 d 时：

根据计算，可得出下表

//所有37个字符letters = "abcdefghijklmnopqrstuvwxyz0123456789_" //当前密码最长长度18，6～18的中位数 12

性能

测试环境：macbook pro 2015 13 寸款

MD5 执行次数 times

times: 1W, duration: 6.213565mstimes: 10W, duration: 61.934416mstimes: 100W, duration: 612.685278ms

bcrypt 配置因子 cost ，执行 一次 hash 的时间如下

cost: 10, duration: 73.496777mscost: 11, duration: 150.451933mscost: 12, duration: 301.655392mscost: 13, duration: 610.59293mscost: 14, duration: 1.196703544scost: 15, duration: 2.385871069s

优点

• 能保障全部用户新的密码与旧密码不相似

缺点

• 迭代的数量过多，对于 bcrypt 这样慢哈希函数，执行时间是完全不可以接受的

• 日常业务中，编辑距离至多只能接受为 2，且需在业务前配置限流熔断措施

还有其他思路吗？

业务上，用户重新输入一次密码。

在修改密码的场景，一般都需要用户重新输入一下原密码来进行安全认证，此时明文密码意见可以被业务获取。

既然业务上加一条这么简单逻辑就可以了，这篇文章还有什么意义呢？

用户忘记密码，无法输入原密码修改的场景，依然是安全的短板。

千里之堤，毁于蚁穴！