Dynamically Generate Password Policy via Zipf Distribution

• IEEE TIFS: Dynamically Generate Password Policy via Zipf Distribution

• 口令组合策略有助于增强密码对猜测攻击的抵抗力。本文提出了一种新的自适应口令策略生成框架HTPG，基于口令的ZipF分布，HTPG将口令按频率分成头部口令和尾部口令。 同时，本文提出了一种基于信息增益比的策略排序方法，帮助用户选择更有效的策略增强头部口令。HTPG可以提高整个数据集的安全性，使口令分布更加统一。 实验表明，通过HTPG生成的策略，与原始头部口令相比，破解的数量减少了69%。可用性调查显示80.23%的增强口令不会被记住原始口令的用户忘记。

Preliminary

口令组合策略

• NIST在2020发布指南鼓励用户在合理的范围内尽可能加长口令，然而它们仍然具有可预测的规则。

口令分布问题

• 口令分布是口令的重要特征之一，鉴于自然语言服从Zipf分布，自然可以猜测口令也服从Zipf分布。

  然而，在IEEE S&P’12, Bonneau对7000万条真是口令数据使用极大似然法估计参数，得出口令不服从Zipf愤怒的结论。2017年，Wang等人提出了一种基于统计优化的CDF-Zipf模型拟合累积分布，分布模型如下

  $$P(r) = Cr^s, \tag{1}$$

  其中$r$为口令频数排名，$C,s$为控制参数，通过黄金分割搜索确定。同时他们还提出了针对概率密度函数的PDF-Zipf模型，表达式为

  $$f(r) = \frac{C}{r^s} \tag{2}$$

  其在000webshot数据集上的表现如图1所示。

  

  图1. 分布模型与真实口令分布

口令攻击

• 如果口令在字符集上符合均匀分布，那么攻击者此时只能暴力破解。然而现实远非如此。

  根据泄露出的口令数据集，口令包含各种规则，例如常见单词、个人信息、常用序列和键盘模式等。这些规则隐含地反映了创建口令的偏好，例如弱密码通常为频繁使用的数字字符串（“1234”）、缺少特殊字符、长度较短等。

  攻击者开发了各种攻击方法。为了降低暴力方法的时间成本，提出了JTR（John the Ripper）等字典攻击方法。随后，提出了更先进的猜测模型，如马尔可夫、概率上下文无关语法（PCFG）、个人PCFG和TransPCFG，以捕获更多关于密码模式的信息，从而提高猜测模型的效率。

  到目前，基于深度学习的密码猜测模型大量出现，如LSTM、PassGAN，以自动发现密码中的未知模式，最终获得更好的猜测效率。Melicher等人发现，神经网络可以是强大而高效的密码猜测方法，他们详细评估了训练技术（如迁移学习、反向输入密码序列、辅导）、模型大小和模型压缩方法对其神经网络密码猜测有效性的影响。Hitaj等人使用GAN生成密码猜测，而无需事先了解密码模式。

HTPG

• 受Zipf分布和机器学习启发，本文提出了一种新的动态密码策略生成框架，称为头尾策略生成器（HTPG）。

图2. HTPG框架

• 图2展示了HTPG框架，图例中用户只采用第一个策略，在口令前面添加了一个字符“A”。

  具体来说，HTPG按照以下步骤工作：

  1. 读取口令数据库，计算每个口令的频率，使用Zipf拟合分布。
  2. HTPG根据口令分布对口令进行分类，分类器根据Zipf分布的最大曲率值做出决策。
  3. 特征排序器根据口令特征对分类的重要性对口令特征进行排序，每个特征的重要性通过基于头尾口令计算的信息增益比量化。
  4. 动态策略生成器动态加强头部口令，基于特征重要性排序结果和尾部密码的特征值，将口令特征值向尾部偏移，增强口令安全性。

头尾口令分类

• 首先使用线性回归计算口令的概率密度函数分布$f_r$中的参数$(C, s)$。

  在口令的频率-排名曲线中，头部曲线非常弯曲，尾部曲线可以近似为一条直线。曲率是衡量权限在给定点上方向变化快慢的一种方式，本文使用最弯点定义为曲率函数的最大点，记为$x_0$，曲率方程计算方式为

  $$\kappa(x) = \frac{\lvert y''\rvert}{(1+y'^2)^{\frac{3}{2}}}\tag{3}$$

  其中$y = f(x)$为口令集的分布方差，$\kappa(x)$表示在$y$处的曲率。

  基于曲率方程，可以得到

  $$x_0 = \argmax \kappa(x)$$

头尾口令差异

• 在开始特征排序之前，先看看头部口令和尾部口令的不同之处，本文使用之前的研究所使用的常用特征，包括：

  1. LSD Structure：LSD分别代表字母、特俗字符和数字字符串。例如口令“123456!AA”的LSD结构是D6S1L2。
  2. Length：长度常用于密码组成策略中，几乎所有策略系统都会强制执行最低长度限制，以避免爆破攻击。
  3. Capital：指口令是否包含大写字母。
  4. Date：指口令是否包含日期信息。日期是字典攻击方法的重点。
  5. Keyboard：指口令是否包含键盘序列。
  6. Specplace：特殊字符在口令中的位置。分为四种情况：无特殊字符、在头部、在尾部和在中间。
  7. Lowercase：小写字母开头还是结尾。如果第一个字符是小写，而第二个不是，或最后一个字母是小写，而倒数第二个不是，则该特征值为1.
  8. WordType：单词类型，指口令是否包含一些特殊类型的单词，如情感词等。
  9. Lastnam：是否包含常用姓氏。

  除此之外，口令策略也可以作为口令的特征，例如“3class12”代表口令至少包含三个字符类，且长度至少为$12$个字符，通过检查口令是否遵循该策略，可以得到一个口令的二进制特征向量。

特征排序

实验

数据集

• 本文使用了6个数据集，分别是

  Dataset	Language	Total	Type
  000webhost	English	$15\,271\,654$	Web Hosting
  Rockyou	English	$32\,510\,281$	Gaming
  Yahoo	English	$442\,830$	Mail
  178	Chinese	$9\,072\,966$	Gaming
  CSDN	Chinese	$4\,410\,531$	Programming
  RenRen	Chinese	$3\,229\,436$	Social forum