本页目录

论文精读：zxcvbn: Low-Budget Password Strength Estimation (Security 2016)

1.Introduction

本文主要提出一个易于实现的密码强度检测器。研究者来自Dropbox。

2.Background and Related Work

LUDS

一种常见的密码强度估计方案：利用小写字母(Lowercase)、大写字母(Uppercase)、数字(Digit)和特殊字符(Symbol)的出现次数来评估密码强度，简写为LUDS，这种策略可以追溯到NIST（美国国家标准与技术研究院）的标准。作者认为这种估计方案从根本上就是无效的——Passw0rd因为有数字0，反而会比QJqUbPpA这样明显随机的密码拥有更高的分数；密码中常见的模式，如日期、键盘规律（比如qwerty）无法在分数中有体现。

NIST的标准（通常叫NIST熵）伪代码见下图：

前两条都是LUDS规则：根据密码长度和特殊字符加分；尽管第三条（是可选的）考虑了字典攻击，前面的例子Passw0rd（假设它没通过字典测试）依然会得到和QJqUbPpA（假设它通过了）一样的分数，这是令人困惑的。

密码猜测相关

本文使用的“黄金准则”（原文是gold standard，含义类似于Ground Truth，在后面的实验用于验证强度估计的准确性）是利用Ur等人提出的Password Guessability Service（论文在这里，后面简称PGS）得到的面对四种现代密码猜测攻击中，需要进行的最少限度的尝试。

本文将区分在线猜测（攻击者通过公共界面进行猜测）和离线猜测（拿到哈希值之后攻击者可以在自己的硬件上爆破）。

3.Evaluation Framework

对于一个旨在替代LUDS的方案，这一节讨论了各方面的评价标准。作者参考了两种LUDS方法：NIST熵和3class8（一种易于采用的要求，即密码包含至少3种类型的8个或更多字符）。

新的方案不应该比LUDS方案更难被采用。

新的方案只应该警告那些真正存在风险的用户。

新的方案应该直接以“猜测这个密码所需的尝试次数”作为标准。（因为这是安全社区对密码强度定义的共识）

在小数量级上要保证准确性。

在线攻击同样是一个重要威胁，能够在约几百次内猜测出的密码对于在线攻击显然是脆弱的，但NIST熵会严重高估这种密码的安全性。作者将 $1 0^{6}$ 作为在线攻击的阈值（认为需要猜测 $1 0^{6}$ 以上次的密码对于在线攻击相对安全），并希望新的方案能够在阈值之前保持较高的准确性。

新的方案应该可以选择不同的数据集大小，应该给予使用者自主权衡大小和准确性的权利。

4.Algorithm

形式化的表达：

arg min_{S} D^{∣ S ∣ - 1} + ∣ S ∣! \prod_{m \in S} m . gu esses

$m$ 表示一个模式，它可能是一个满足格式的日期、一段键盘上相邻的字符串等等：

对于一个给定的密码字符串，可以匹配到多种模式，并且这些模式会有重叠，例如密码lenovo1111可能提取到lenovo(token)、eno(reversed 'one')、1111(repeat)、1111(date of 2011/1/1)等模式。

如果一部分模式能够不重不漏地组成原始的密码字符串，这个模式序列就计作 $S$ 。 $∣ S ∣$ 代表模式的数量。

连乘项代表对于所有模式，最坏情况下猜测的总数； $∣ S ∣!$ 考虑了不同模式之间的组合顺序； $D^{∣ S ∣ - 1}$ 代表攻击者事先不知道模式的长度 $∣ S ∣$ 时，从 $l = 1$ 尝试到 $l = ∣ S ∣ - 1$ ； $D$ 是一个常数，反映对于单个模式需要猜测的次数，因此猜测总次数 $\sum_{l = 1}^{∣ S ∣ - 1} \approx D^{∣ S ∣ - 1}$ 。