zxcvbn 原理详解

前言：因为工作中的一个计算密码强度的需求，了解到 zxcvbn 这个库，花了段时间看了看它的 java 实现和相关论文，编写此文作为笔记存档。注意：本文侧重其算法实现和复杂度计算，不涉及其使用方法以及与其他库的对比。本文中的公式均摘自 Dropbox 相关博客和论文。

概述

zxcvbn 是一个由 Dropbox 开发的密码强度估算库，灵感来自于密码爆破工具，其全称是 “zxcvbn: realistic password strength estimation”，旨在提供一种更准确、用户友好的密码强度评估方法。zxcvbn 的强度估计是基于一个想法：

猜测密码难度 ≈ 破解者使用最优策略所需尝试的次数（guesses）

换句话说，zxcvbn 试图模拟一个最聪明的黑客（利用所有已知技术和词库）如何最有效地破解这个密码。然后根据所需的尝试次数来估算破解时间和给出打分。

zxcvbn 将密码破解难度的计算大致分为了三步：

匹配：模式匹配，zxcvbn 会尝试对输入密码进行子串划分，它尝试以多种方式将密码拆成子串，每个子串对应一种模式(match)，即该子串符合什么特征，如若密码字典(包含常用单词、姓名)、键盘路径，具体有哪几种模式将在下文具体介绍。
评估：破解所需的尝试次数，对于每个识别出的模式子串，zxcvbn 会计算其可能的尝试次数。
搜索：使用 动态规划 算法，zxcvbn 试图找出一组首尾相接子串组合，使得总猜测数最小。

模式匹配

zxcvbn 包含的匹配模式

字典匹配：维护一个带排名的弱密码字典，如：admin、admin123、logitech
反向字典匹配：基于字典匹配，弱密码字典中的词汇倒序，如：drowssap，nimda
leet 匹配：基于字典匹配，将一些字符做相似替换，如：p@ssw0rd
键位匹配：键盘上的连续字符，如：qwerty、qazwx
重复匹配：重复的字符或者序列，如：zzz、ababab
顺序匹配：有顺序的连续字符，如：abc、123、246
日期匹配：日期字符串，如：20000102、7/8/1947
暴力破解匹配：无法使用上述方法匹配的序列，如：x$JQhMzt
正则匹配：实际代码中比论文中还多了一种正则匹配，内置常见的数据格式正则比如最近的年份

模式匹配的实现原理

字典匹配、反向字典匹配、leet 匹配 ：首先将整个密码字符串小写，然后再获取该小写密码的所有子串，遍历子串看其是否在密码排名字典中；反向字典匹配在此基础上将子串反转判断其是否在排名字典中；leet 匹配则会根据替换规则，得到一个子串的所有 leet 替换值，再判断替换后的子串是否在排名字典中，如@ba1one，l33t 表会将@映射到a，将1映射到i或者l(即按照 leet 规则将字符串中的符号和数字替换为对应的字母)，因此它会通过替换 [@->a, 1->i] 和 [@->a, 1->l]分两次尝试去排名字典中匹配，第二次会匹配中单词abalone(单词：鲍鱼)； zxcvbn 的密码字典包括：英语词汇表、常用人名、常用密码、常用姓氏、美国电影和电视剧名
顺序匹配：通过计算相邻字符的 unicode 码的差值来找到顺序，一个”递增“或”递减“的子串其相邻字符的 unicode 码的差值是相同的；
重复匹配：通过使用贪婪正则"(.+)\1+"和懒惰正则"(.+?)\1+"来识别密码字符串中的重复块。对于字符串 “aabaab” 贪婪模式的结果(aab)较懒惰模式的结果(aa)会胜出，因为贪婪模式覆盖的长度为 6(“aabaab”)而贪婪模式覆盖的长度为 2(“aa”)；对于 “aaaaa” 懒惰模式覆盖长度为 5(“aaaaa”)，而贪婪模式覆盖长度为 4(“aaaa”)，故懒惰模式胜出。在得到整个密码的所有重复单元后，会再对每个重复单元再执行完整的匹配过程(即对子串再执行一遍搜索的模式匹配)，以此识别重复的单词或日期；
键位匹配：遍历密码字符串，对比多种键盘键位的邻接图，找到密码中键位相邻的模式子串，并记录每个模式子串的长度、转折次数、shift 键(如!@#$%QAZ)的数量以及键盘种类。如密码“zxcvfR$321”将会被记录为以下数据：键盘种类-qwerty、转折次数-3、shift键数量-2(R和$)、长度-10；
日期匹配：对于不带分隔符( / \ _ . - 空格)的日期格式，遍历整个密码字符串，匹配长度为 4~8 的数字子串如'1191'、'11111991'，然后针对不同长度使用不同的分割策略分割为三部分组合、过滤出日期，再从这些日期中挑出离现在最近的日期作为最优解；对于带分隔符的日期格式，遍历整个密码字符串，匹配长度为 6~10 的数字子串如'1/1/91'、'11/11/1991'，使用正则匹配分割为三部分，然后重复上述的逻辑；
正则匹配：实际代码实现中只内置了一种常用正则即最近年份用于匹配 19** 或者 20** 这种年份，如 1999、2019；

评估尝试次数

每种模式的猜测次数计算

对于模式匹配阶段的结果，在评估阶段会计算其中每一个模式子串的猜测次数，对每种模式的子串的猜测计算方法根据模式匹配特点决定：

字典和反向字典匹配：假设攻击者按照弱密码流行度顺序猜测
- 对于字典匹配，模式子串的猜测次数即为弱密码字典排名值；
- 对于反向字典匹配，由于需要尝试字典值的正反两种情况，因此还要在流行度排名值的基础上乘二；
- 对于仅首字母、仅尾字母和全部字母为大写的三种情况，也需要在流行度排名值得基础上乘二；
- 对于其他的大小写情况(如：对于密码paSswOrd，需要在猜出password的基础上，再猜出哪些位置的字母是大写)使用下面的公式计算：
$$ \frac{1}{2}\sum_{i=1}^{\min(U,L)}\binom{U+L}{i} $$
公式解读：
- $U$：大写字母数量
- $L$：小写字母数量
- $\min(U,L)$：取两值中的较小值，当大写字母数量大于小写字母数量时，改为猜测小写字母
- $\binom{U+L}{i}$：组合公式 $C^{i}_{U+L}$ ，即从 $U+L$ 个中选出 $i$ 个有多少种选法
- $\frac{1}{2}\sum_{i=1}^{\min(U,L)}\binom{U+L}{i}$：攻击者不知道其中有多少个大写字母，假设攻击者从 1 个大写字母尝试到 $min(U,L)$，当尝试到大写字母数量为 $i$ 时，此轮共需要尝试 $C^i_{U+L}$ 次，记为 $\binom{U+L}{i}$，$i$ 需要从 1 尝试到 $min(U,L)$，总数为 $\binom{U+L}{i}+\binom{U+L}{i}+…+\binom{U+L}{min(U,L)}$ 记为 $\sum_{i=1}^{\min(U,L)}\binom{U+L}{i}$，最后添加一个 $\frac{1}{2}$ 来取平均猜测次数。
Leet 匹配：在字典匹配的基础上，与上述大小写替换的计算方式一致，只不过是将大写字符替换改为了 leet 字符替换。
键位匹配：对于键位匹配，假设攻击者总是从较短的键位匹配长度(最短为 2)和较少的方向(最少为 1)开始计算。以 qwertyhnm 为例，它从 q 开始，长度为 9，包含 3 个方向：最开始向右(qwerty)，然后向右下(yhn)，然后向右(nm)。
$$ \frac{1}{2}\sum_{i=2}^{L}\sum_{j=1}^{\min(T,i-1)}\binom{i-1}{j-1}SD^j $$
公式解读：
- $L$：密码的长度
- $T$：密码在键盘上方向段数
- $D$：键盘上每个键平均的相邻键数
- $S$：键盘上键的个数
- $i$：假设键位匹配模式子串的长度为 $i$，从 2 开始（1 长度没有“转向”的意义）
- $j$：假设长度为 $i$ 的键位匹配模式子串包含 $j$ 个方向段，即对应 $j-1$ 次转向，不能超过 $i-1$ 或最大方向段数 $T$
- $SD^j$：键盘上任意一个字符都有可能作为起始字符，每一个方向段都有 $D$ 种方向选择，共 $j$ 段。(这里应该也是估算，因为第二个方向段的方向肯定与第一个方向段方向不同，那能选的方向应该是 $D-1$，对应 $S \cdot D \cdot D^{j-1}$，不过这里的数量级应该是一样的且 $D$ 本身不是精确值，所以直接简化为 $SD^j$ 也无妨)
- $\binom{i-1}{j-1}$：在 $i$ 个键上包含 $j$ 个方向段，可以这样理解：$j$ 个方向段对应 $j-1$ 次转向，转向应该发生在“内部键”上，而 $i$ 个键位对应 $i-2$ 个内部键(即去除首尾键)，那位该问题转化为在 $i-2$ 个内部键中挑选出 $j-1$ 个作为转向键，对应的组合公式即为 $\binom{i-2}{j-1}$。⁉️ 离谱的来的，怎么跟论文里的公式对不上 😅
- $\frac{1}{2}\sum_{i=2}^{L}\sum_{j=1}^{\min(T,i-1)}\binom{i-1}{j-1}SD^j$：假设攻击者总是从较短的序列长度(最短为 2)和较少的方向段数(最少为 1)开始猜测，针对 $i$ 从 $2$ 到 $L$ 的每种序列长度的情况，方向段数从 1 最多尝试到 $min(T,i-1)$ 次；每种长度的模式子串的首字符有 $S$ 种选择，每个方向段有 $D$ 种方向选择，共有 $j$ 个方向段，故针对每种空间模式的模式子串都有 $SD^j$ 种可能；$\frac{1}{2}$ 用于计算平均情况；
⚠️ 注意 ⚠️：上述个人理解与论文中的公式对不上 😅，不必惊慌数量级应该是一样的那就先凑合用论文中的公式吧，当然我的理解可能也是错的欢迎指正。

其实下面参考链接里的论文中存在多处公式与代码实现不符且存在错误……经过查看 Dropbox 官方的代码库实现和相关的 java 库实现后发现，实际并没有使用论文中提到的 $\frac{1}{2}$ 来计算平均尝试情况，除了键位匹配，字典匹配的实现中也没有使用 $\frac{1}{2}$ 来计算平均值。代码实现中实际使用的公式如下：
$$ \sum_{i=2}^{L}\sum_{j=1}^{\min(T,i-1)}\binom{i-1}{j-1}\cdot S \cdot D^j \cdot \text{shift\_factor} $$
公式解读：
- $\text{shift\_factor}$：大写因子，即按住 shift 键输入的值，比如大写的字母或是数字键对应的符号如 !@# 等。
  - 当整个模式子串全部为"小写"时因子值为 1；
  - 当整个模式子串全部大写时，因为值为 2，因为假定攻击者先尝试全部小写再尝试全部大写，所以尝试了两次；
  - 其余情况使用公式 $\sum_{i=1}^{\min(\text{shifted},\text{unshifted})}\binom{\text{shifted}+\text{unshifted}}{i}$ 计算，$shifted$ 是按住 shift 键输入的个数，$unshifted$ 是不需要按住 shift 键输入的个数，这个公式就不展开介绍了，原理与上面的字典匹配中的大小写模式计算一致。
重复匹配：整个重复的模式子串由 n 个重复的基础字串组成，如 nownownow 由基础子串 now 重复 3 次组成；重复匹配首先会递归的检测基础子串 now 的匹配模式，并计算其猜测次数 $g$；子串 now 的模式为字典模式，在字典表中排名第 42 位，子串重复了 3 次，整个重复模式子串的猜测次数为：$g\times n$，即 nownownow 的猜测次数为 $42\times 3$。

如何理解这里的乘法呢：密码 123abcabcabc 中存在一段重复的子串 abcabcabc，只看基础单元 abc 攻击者需要尝试 $g$ 次才能猜对，在猜对基础单元后对于整个重复子串 abcabcabc 需要尝试将基础单元重复 3 次才能完整匹配中这段完整的重复子串：尝试重复 abc、尝试 abcabc、尝试 abcabcabc，即从重复 1 次一直到重复 $n$ 次，所以要猜对这段完整的重复子串需要猜测 $g\times n$
顺序匹配：顺序匹配的猜测次数计算方法为：$S\cdot N\cdot \lvert d\lvert$，$S$ 为起始字符的可选个数，$N$ 为长度，$d$ 为相邻前后字符的 Unicode 编码差值（如 9753 的前后字符差值为 -2）。当模式子串首字符为 ['a','A','z','Z','0','1','9'] 中的任何一个时，$S$ 将被赋值为 4，如果首字符不在上述列表中，但是首字符为其他数字，则 $S$ 将被赋值为 10，其他情况 $S$ 将被赋值为 26，当字符序列为倒序时，还要在 $S\cdot N\cdot \lvert d\lvert$ 的基础上乘以二(因为猜完正序还要再猜一次倒叙)，即 $2\cdot S\cdot N\cdot\lvert d\lvert$
日期匹配：日期匹配的猜测次数计算方法为：$365\cdot \lvert now.year-date.year \lvert$，可以看出这里的计算为估算
暴力破解匹配：暴力破解的猜测次数计算方法为：$C^N$，$C$ 为常数被赋值为 10，即假设暴力破解时每个位置上的字符需要尝试 10 次，$N$ 为密码长度
正则匹配：该模式在最终的代码实现中有但是论文中并未提及，猜测次数计算公式为：
- 对于最近年份的正则：$\lvert now.year-date.year \lvert$，即年份差值的绝对值
- 对于其他正则：$C^N$，$C$ 为常数，每一种正则表达式都有一个对应的常数，代表破解一位需要尝试的次数，$N$ 为密码长度。可以看出此类匹配模式其实与暴力破解匹配模式类似

整个密码的猜测次数计算

整个猜测过程可由以下启发式搜索表示：

$$ \argmin\limits_{S\subseteq\mathcal{S}}(D^{\lvert S\lvert-1}+\lvert S\lvert!\prod\limits_{m\in S}m.guesses) $$

公式含义：

$\mathcal{S}$：密码字符串的所有模式子串的集合，如：[levono(字典模式), eno(字典反转模式), no(单词模式), no(单词反转模式), 1111(重复模式), 1111(日期模式)]
$S$：首尾相接能组成密码的非重叠模式子串序列，如：[levono(字典模式), 1111(重复模式)]，可以看出 $S$ 是 $\mathcal{S}$ 的子集，即 $S\subseteq\mathcal{S}$
$\lvert S\lvert$：首尾相接组成密码的模式子串序列 $S$ 的长度，即密码由几段模式子串组成，如上述子串序列的长度为 2
$m$：$S$ 中的某个模式子串，可表示为：$m\in S$ ；$m.guesses$ 为该模式子串的所需猜测次数
$\lvert S\lvert!\prod\limits_{m\in S}m.guesses$：假设攻击者知道密码由 $\lvert S\lvert$ 个模式子串组成，即假设攻击者知道密码中模式子串的数量，但是不知道这几个模式子串的排列顺序。
- 比如一个密码由：字典模式子串 A、单词模式子串 B、日期模式子串 D 组成，那么这个密码可能为 ABC、ACB、BAC、BCA、CAB、CBA，共有 6 种。由排列公式 $P_{n}^{m}=\frac{n!}{(n-m)!}$ 可知从 $\lvert S\lvert$ 个元素中选 $\lvert S\lvert$ 个元素进行排列，共有 $P_{\lvert S\lvert}^{\lvert S\lvert}=\frac{\lvert S\lvert!}{(\lvert S\lvert-\lvert S\lvert)!}=\frac{\lvert S\lvert!}{0!}=\frac{\lvert S\lvert!}{1}={\lvert S\lvert!}$ 种可能；
- 每个组成密码的模式子串 $m$ 的猜测次数为 $m.guesses$，那么不考虑模式子串顺序时整个密码的猜测次数为：组成密码的所有模式子串的猜测次数的累乘，即 $\prod\limits_{m\in S}m.guesses$ ；
- 由上可知，当考虑模式子串之间的顺序时，整个密码的猜测次数为 $\lvert S\lvert!$ 乘以 $\prod\limits_{m\in S}m.guesses$ ，即 $\lvert S\lvert!\prod\limits_{m\in S}m.guesses$
$D$：一个常数，为经验值，即平均每个模式子串大概需要的猜测次数。根据 Dropbox 的经验，D 为 1000~10000 时公式表现较优
$D^{\lvert S\lvert-1}$：为 $\sum_{l=1}^{\lvert S\lvert-1}D^l$的近似值。假设攻击者不知道密码由多少个模式子串组成，每个模式子串的猜测次数假定为 $D$ ，那么 $l$ 个模式子串的猜测次数即为 $D^l$ 。假设攻击者总是从较少的模式子串数量开始猜测，在猜到正确的模式子串个数 $\lvert S\lvert$ 前，总的猜测次数即为 $\sum_{l=1}^{|S|-1} D^l = \frac{D(D^{|S|-1} - 1)}{D - 1} \approx D^{|S|-1}$，即可近似简化为 $D^{\lvert S\lvert-1}$。
$D^{\lvert S\lvert-1}+\lvert S\lvert!\prod\limits_{m\in S}m.guesses$：现在从整体上来看，前半部分表示：在猜到正确的模式子串个数 $\lvert S\lvert$ 前的累计猜测次数；后半部分表示：在猜到正确的模式子串个数 $\lvert S\lvert$ 后，不知道这几个模式子串排列顺序的情况下需要的猜测次数；两部分相加即为总的猜测次数；
$\argmin\limits_{S\subseteq\mathcal{S}}(D^{\lvert S\lvert-1}+\lvert S\lvert!\prod\limits_{m\in S}m.guesses)$：可能存在多种首尾相接能组成密码的模式子串的组合 $S$，猜测次数最少的 $S$ 即为最优的组合，此时的猜测次数即为最小猜测次数

从整个公式中可以看出，$D^{\lvert S\lvert-1}$ 和 $\lvert S\lvert!$ 以不同的方式惩罚过于复杂的模式子串组合。当两个不同长度的模式子串组合具有相近的 $\prod\limits_{m\in S}m.guesses$ 猜测次数时，$\lvert S\lvert!$ 会倾向于较短的模式子串组合。$D^{\lvert S\lvert-1}$ 倾向于反对较长的模式字串组合，即使其具有较小的 $\lvert S\lvert!\prod\limits_{m\in S}m.guesses$ 值。

搜索最佳模式组合

给定一个密码字符串的所有模式子串(模式子串之间可能存在重叠)集合 $\mathcal{S}$，最后一步是从 $\mathcal{S}$ 中搜索出不存在重叠的模式子串的序列，使得整个序列能够刚好覆盖住整个密码，并使得猜测次数最小。下面将描述搜索使用的动态规划算法，可以很好的完成搜索任务。

💡 整体思想是搜索能够覆盖从index=0到index=K的密码子串且猜测次数最小的模式子串序列。K从0迭代到password.length-1，进而逐渐的从局部最优迭代至整体最优。

下面使用伪代码阐述该算法：

简单介绍一下几个初始值：

解释
1. $n$ 为密码字符串的长度，$k$为索引值，$k\in{0,1,2,…,password.length-1}$
2. $\mathcal B_{opt}$ 为反向指针列表，用于记录密码上每个字符的相关数据。$\mathcal B_{opt}[k][l]$ 是能覆盖密码子串 password[0~k] 且长度为 $l$ 的模式子串序列中的最后一个模式子串(该子串以 password[k] 结尾；该模式子串序列为尾字符是 password[k] 长度是 $l$ 的模式子串序列中猜测次数最少的子串序列，即 end=password[k] && length=l 的局部最优解)
3. $\prod_{opt}[k][l]$ 为上述最佳模式子串序列中所有模式子串猜测次数的累乘。
4. $l_{opt}$ 是最佳模式子串序列的长度
5. $g_{opt}$ 上述模式子串序列的猜测次数

搜索函数：

解释
1. K 值从 0 迭代到 n-1，即从头到尾遍历密码上的每一个字符
  1. 以 K 索引对应字符为结尾的密码前缀子串的最佳猜测次数，初始值赋值为无限大
  2. 遍历密码所有模式子串 $\mathcal S$ 中以 $k$ 结尾的模式子串 $m$
    1. 如果该模式子串 $m$ 的起始位置 $m.i$ 大于 0，即该模式子串不是从密码的起始位置开始，其前面还有其他模式子串
      1. 遍历 $\mathcal B_{opt}$ 中以 $m.i-1$ 结尾的所有最佳解模式子串序列的长度值(层级数) $l$
      2. 在 $\mathcal B_{opt}$ 中记录下以 $k$ 结尾，长度为 $l+1$ 的最佳模式子串序列的信息
    2. 如果该模式子串 $m$ 的起始位置 $m.i$ 为 0
      1. 在 $\mathcal B_{opt}$ 中记录下以 $k$ 结尾，长度为 1 的最佳模式子串序列的信息
  3. 在 $\mathcal B_{opt}$ 中记录下以 $k$ 结尾，暴力破解匹配的模式子串序列的信息
2. 返回完整的 $\mathcal B_{opt}$ 中以 $n-1$ 结尾的最佳模式子串序列的猜测次数值

补充暴力破解匹配的函数：

解释
1. 构建一个从 0 到 $k$ 的暴力破解模式子串 $m$
2. 在 $\mathcal B_{opt}$ 中记录下以 $k$ 结尾，长度为 1 的最佳模式子串序列的信息
3. 遍历 $\mathcal B_{opt}$ 中所有以 $k-1$ 结尾的模式子串序列，其长度为 $l$，结尾的模式子串为 $m$
  1. 如果该模式子串 $m$ 的匹配方式为暴力破解
    1. 构建一个从 $m.i$ 到 $k$ 的模式子串，赋值给新的 $m$
    2. 以 $m$ 更新在 $\mathcal B_{opt}$ 中以 $k$ 结尾，长度为 $l$ 的最佳模式子串序列的信息
  2. 如果该模式子串 $m$ 的匹配方式不是暴力破解
    1. 构建一个只有 $k$ 的模式子串，赋值给新的 $m$
    2. 以 $m$ 更新在 $\mathcal B_{opt}$ 中以 $k$ 结尾，长度为 $l+1$ 的最佳模式子串序列的信息

更新 $\mathcal B_{opt}$ 表的函数：更新 $\mathcal B_{opt}$ 中以模式子串 $m$ 结尾长度为 $l$ 的最佳模式子串序列

解释
1. 将模式子串 $m$ 的猜测次数赋值给 $\prod$
2. 如果模式子串序列的长度 $l$ 大于 1，即模式子串序列以 $m$ 结尾但是 $m$ 前面还有其他模式子串
  1. $\prod$ 等于该模式字串序列中所有模式子串的猜测次数的累乘值
3. 如果模式子串序列的长度 $l$ 等于 1，即该序列中只有 $m$ 一个模式子串
  1. 则模式子串序列的猜测值 $\prod$ 等于其中唯一的模式子串 $m$ 的猜测次数 $m.guesses$
4. 使用上面讲解的启发式计算整个模式子串序列的猜测次数 $g$
5. 如果 $g$ 小于$g_{opt}=\mathcal B_{opt}[k][l]$
  1. $g_{opt}$ 赋值为 $g$
  2. $l_{opt}$ 赋值为 $l$
  3. $\prod_{opt}[k][l]$ 赋值为 $\prod$
  4. $\mathcal B_{opt}[k][l]$ 赋值为 $m$

从完整的 $\mathcal B_{opt}$ 表中选出覆盖整个密码且猜测次数最小的模式子串序列：

解释

由前一个步骤知最佳模式子串序列的长度为 $l_{opt}$，于是从 $\mathcal B_{opt}[k][l_{opt}]$ 不断向前倒推便能得到完整的最佳的模式子串序列（动态规划——从局部最优中搜索出整体最优）

根据最终评估出的密码猜测次数，会将密码分为四个等级：

1
2
3
4
5
6
7
8


public static int guessesToScore(double guesses) {
    int DELTA = 5;
    if (guesses < 1e3 + DELTA) return 0;
    else if (guesses < 1e6 + DELTA) return 1;
    else if (guesses < 1e8 + DELTA) return 2;
    else if (guesses < 1e10 + DELTA) return 3;
    else return 4;
}

概述