写点什么

密码相似性

用户头像
red
关注
发布于: 2021 年 04 月 26 日
密码相似性

场景

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


常见非安全的做法

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


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 算法:



本文主要不是介绍如何正确选择密码 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,且需在业务前配置限流熔断措施


还有其他思路吗?

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



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


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

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


千里之堤,毁于蚁穴!


发布于: 2021 年 04 月 26 日阅读数: 21
用户头像

red

关注

还未添加个人签名 2018.08.07 加入

还未添加个人简介

评论

发布
暂无评论
密码相似性