基于神经网络的多源密码猜测模型*

夏之阳，易 平

（上海交通大学 网络空间安全学院，上海 200240）

0 引 言

密码是目前身份认证的主流手段，且在短期内不会被取代。出于方便，用户通常不会设置复杂、不便于记忆的密码。因此，可以认为密码是存在某种规律性的[1]。由于对于密码保护的疏忽，目前已经发生了多起大规模的密码泄露事件。本文对于密码的分析，均是基于历史上国内外各个网站的泄漏密码。

目前比较成熟的密码猜测技术主要是马尔科夫模型（Markov models）[2]和概率上下文无关文法（Probabilistic Context-Free Grammars）[3]。这两种技术都是依据概率模型，存在计算量庞大、耗时长的问题。递归神经网络（Recurrent Neural Network）[4]是分析文本的常用方法。Melicher等人证实，基于神经网络的训练效率被证实要优于常用的概率模型方法[5]。然而，Melicher的研究中，针对单数据集对密码的格式、长度进行了约束，因此应用范围有限。文献[6]中提出基于对抗生成网络（Generative Adversarial Network）的模型passGAN，进一步提升了密码生成能力。然而，和Melicher的研究相同，passGAN只能提升单数据集的测试命中率，在跨数据集的测试中表现较差。

本文提出一种基于多数据集的密码生成模型GENPass（Generating General Passwords）。GENPass的目标是生成具有泛化特征的密码字典，从而提高对于未知密码集的命中率。GENPass可以同时提升单数据集和多数据集的命中率。单数据集的命中率由PL（PCFG+LSTM）保证。密码首先依据PCFG的策略进行标签替换，替换后的标签序列再进行LSTM训练，最后再将标签通过随机采样替换回密码。基于PL模型，本文提出GENPass模型来提升多数据集的命中率。GENPass运用对抗生成来消除不同数据集之间的专有特征，保留泛化特征，从而保证生成的密码具有普遍性。

本文的贡献主要有以下两个方面：

（1）提出PL（PCFG+LSTM）模型，将密码训练由以字符为单位提升到以单词为单位，从而大大提升单数据集的命中率；

（2）提出GENPass模型，将训练集的数量由一个变为多个，基于多数据集学习泛化的密码特征，从而提升对于未知数据集的测试命中率。

1 背 景

本章节首先介绍传统的密码猜测方法并分析这些方法的优缺点，随后介绍近几年深度学习在该领域的应用以及发展。

1.1 传统密码猜测方法

通常密码不会以明文的形式传输与存储[7]，对密码进行哈希运算是常用的操作。Hashcat[8]和John the Ripper（JtR）[9]是两个针对哈希码破解的常用工具。这两个工具能够借助GPU提高哈希码的计算速度，但要破解出密码必须基于一个已知的密码字典，通过暴力匹配字典中的每一个密码找出目标密码。换而言之，如果目标密码不在字典中，将无法破解出信息。因此，这两个工具提供了一些密码变异的方法来扩大字典，如增加、修改、删除几位字符等操作。然而，这些操作并不智能，实际应用效果不明显。

基于马尔科夫模型的密码猜测在2005年最早提出[10]。马尔科夫模型的核心概念是用空间换时间，通过大量的统计信息，依据前文推测下一个字符出现的概率。

基于概率上下文无关文法（Probabilistic Context-Free Grammars）的密码猜测在2009年被提出[11]，可以认为是马尔科夫模型的一种优化。用户在设置密码时通常不会使用随机的字符序列，一般都是有意义的字符串，这些字符串在生成时可以被看成一个整体。原始密码被标签替换，L代表字母，D代表数字，S代表特殊符号，每个标签后的数字表示长度。例如，“password123#”被替换成“L8 D3 S1”。经过替换后的标签串运用马尔科夫模型进行训练。在生成阶段，每次生成一个标签，然后在标签对应的字符串中随机选择一个输出。这种思想被进一步推广到针对个人信息的密码猜测[12-13]，将用户的手机号、生日等信息看做一个整体用标签来替换。然而，这种方案并没有改变马尔科夫模型的弊端，依然存在计算量大、存储量大的问题。

1.2 神经网络的发展

递归神经网络模型（RNN）[4]在自然语言处理领域中已有广泛的使用，可以根据时间序列数据进行建模，从而处理数据，如文本预测、语义分析等。

传统递归神经网络模型存在梯度爆炸的缺陷[14]，即在长度过长的情况下，模型的训练能力下降。一个训练文本中，如果具有关联性的两个词在文本中相隔较远，则模型无法找到其关联性。这一问题又称长时依赖问题。LSTM模型[15]是传统递归神经网络的一种变形，可以有效解决长时依赖问题。LSTM在RNN模型的基础上添加了一个“门”概念，通过“门”来控制是否遗忘或记忆之前的信息，从而解决长文本导致的梯度爆炸问题。

LSTM模型的单元（简称细胞）中，it、ft和ot分别是记忆门、遗忘门和输出门；每个细胞的输出有两个值，ct表示细胞状态，ht表示细胞输出。其中，为向量内积，σ为sigmoid函数。遗忘门的作用是通过σ来决定什么样的信息会被抛弃。记忆门的作用是决定什么样的信息会被留下。LSTM模型通过遗忘门和记忆门的设计减少梯度爆炸问题，解决传统RNN中的长时依赖问题。

对抗生成网络（Generative Adversarial Network，GAN）[16]是深度学习领域的又一个突破。GAN由一个生成器G和辨别器D组成，生成器G不断生成假数据，由辨别器D来判断数据是由G生成的假数据还是真数据。通过不断的对抗训练，使得D无法辨别G生成的数据的真假。GAN已经在图像领域取得了非常大的成就，然而并不能直接应用于文本的生成。因此，本文借鉴GAN的对抗生成思想，来实现多数据集的密码生成。

1.3 基于神经网络的密码猜测

基于神经网络的密码猜测开始于2016年Melicher等人提出运用LSTM来生成密码[5]，文中证明神经网络能够更快、更准地猜测密码。然而，Melicher等人限制了密码的格式，使得生成的密码不具有广泛性。2017年，Hitaj等人提出PassGAN[6]，运用GAN来生成密码。实验结果表明，PassGAN能够生成一些传统工具无法生成的密码。然而，这些密码并不一定匹配真实用户的习惯，在命中率的测试上，与传统方式相比并没有明显优势。在目前已有的基于神经网络的密码猜测方法中，重点均放在了提高单数据集的命中率。而实际环境中更多的是跨域攻击，因此跨数据集的数据更为重要。本文将重点放在跨数据集的数据方面，与已有的工作有明显不同。

2 系统概述

本章节将介绍文本解决的主要问题，并详细描述为了解决这些问题而设计的PL（PCFG+LSTM）和GENPass模型结构。

2.1 问题描述

研究密码猜测并不是为了破解特定密码，而是从宏观上提高训练和测试集之间的重合度。密码猜测有两种类型的测试：一种称为同站测试，其训练集和测试集是相同的；另一种称为跨站测试，其训练集和测试集是不同的。在背景介绍中已经提到，以前的研究工作都意在提高同站测试的命中率，其在跨站测试中的表现很差。然而，跨站攻击是黑客破解数据库的主要手段，这方面的技术能力需要提高。此外，历史上已经发生了多起密码泄露事件，但是每个数据集对于深度学习模型来说都不够大，不足以学习到足够的用户习惯。

工作中试图从多个数据集中生成“泛化”密码字典，以提高跨站测试中密码猜测的性能。所谓泛化，是指生成的密码具有通用性，通过学习多个数据集来获取其中共同的特征，而非各个数据集中特有的一些特征。跨站测试的目标是针对一个未知的数据集提高命中率，因此某个数据集特有的特征不利于提高跨站测试中的命中率，只有通用的特征才能提高命中率。GENPass的结构设计就是为了消除不同数据集中的特有特征，利用分类器过滤有明显偏向的密码。例如，某个密码被分类器判定为明显属于A数据集，则认为其包含A数据集的特有特征。如果分类器无法判定某个密码属于A数据集还是B数据集，则认为其包含A和B的共有特征。

2.2 PL（PCFG+LSTM）

因为密码总是有意义的几段字符的组合，PCFG将密码划分为几个不同的部分。例如，“password123”可以分为两个标签“L8”和“D3”。之前的研究表明，这会提高猜测的准确性。同时，神经网络可以检测到标签之间隐藏的关系，这是马尔科夫模型无法检测到的。因此，本文将这两种方法结合，提出了一种新模型——PL模型。

2.2.1 预处理

密码首先被编码为几个标签，每个标签由一个字符（L、D、S）和一个数字组成。其中，L代表字符，D代表数字，S代表特殊字符，数字代表序列的长度。例如，“$Password123”将表示为“S1 L8 N3”，详细规则显示在表1中。预处理密码时会生成一个表，同于统计每个字符串出现的次数。例如，统计了Myspace中的所有L8字符串，发现“password”出现了58次，“iloveyou”出现了56次，依此类推。这个表格的统计数据将会在权重选择中使用。

表1 字符替换规则

2.2.2 生成

将预处理后的密码即标签序列送入LSTM模型中进行训练，并通过LSTM模型生成标签。LSTM的结构与Melicher等人[5]使用的网络结构相同。

2.2.3 权重选择

当确定下一个标签时，将根据预处理期间生成的表格选择一个字符串进行替换。实验表明，如果每次选择最高权重输出，则会生成大量重复密码。所以，通过随机采样选择字符串。这种随机采样可以确保选择的字符串有较高的概率，但又不会出现大量重复的情况。

2.3 GENPass

由于不同的密码数据集具有不同的特征和不同的长度，因此简单的混合多个数据集反而会混淆特征，使得模型难以学习到通用的特征。实验结果也证实了这一推论。为了解决多数据集的训练问题，设计了GENPass-pro模型，总体设计如图1所示。

图1 GENPass总体结构

2.3.1 n个PL模型的独立预测

共有n个PL模型，分别学习不同的密码库，并分别训练每个模型。因此，给定输入，模型可以输出具有其自身特征的结果。

2.3.2 带权重的随机选择过程

假设概率分布p表示每个数据集的权重，∑ p=1，不同PL模型的输出概率分布应乘以该数据集的权重。图2假设两个模型的权重相同，则两个输出在合并时需要乘以0.5的权重，然后进行随机选择。选择过程采用随机采样，确保高权重的标签被高概率选择。替换同样采用随机采样，依据预处理时各个字符串的出现频率。

图2 生成-随机选择流程举例

2.3.3 分类器

分类器是由原始密码训练的CNN分类。分类器的结构采用成熟的分类模型[17]。给定密码，分类器可以给出密码来自不同数据集的概率分布。分类器处理的是生成的完整密码，而不是标签序列。只有在生成结束字符‘ ’时，一个完整的密码才会被送入分类器，并将新生成的密码与先前生成的4个密码组合在一起，作为分类器的输入。由于单个密码不足以提取特征，经过实验后认为5个密码一组作为输入是一种比较合理的方式。

2.3.4 鉴别器

辨别器的作用是判断分类器的输出，即概率分布是否接近合理分布。例如，某一个密码的特征非常偏向某一个数据集，则认为这个密码具有特定特征而非普遍特征。引入Kullback-Leibler散度[18]来描绘两个分布之间的距离，KL散度为：

训练过程中，使用梯度下降使P接近Q。分配P首先是随机生成的。每次迭代中，GENPass生成10个新密码。这些密码被送到分类器，结果记录为Qi(i=1,2,…,10)。将这些结果的平均值表示为分类器Q的输出，使用KL散度作为损失函数。通过梯度下降法来更新P，使得P快速接近Q。认为当损失小于0.001时，分布是稳定的。当训练完成后，P的值确定下来。经过实验，设定通过的标准是P与Q的KL散度是小于0.1。

图3是分类器到辨别器的整个流程举例说明。假设新生成的密码S为“abcdef1@34”。它会和之前生成并通过辨别器的4个密码组合在一起，作为分类器的输入。分类器会输出一个分布Q，假设Q为（0.4，0.6），P为（0.4，0.6），则KL散度为0，则S可以输出；若Q为（0.1，0.9），则KL散度超过0.1，S被丢弃。

图3 分类器-辨别器流程举例

3 实验及讨论

3.1 实验数据

实验数据均来自于历史上世界各网站的泄露密码，均是密码研究最常用的四个数据集。具体的实验数据见表2。

表2 实验数据

3.2 测试和评价

3.2.1 PL测试方案

为了测试PL模型，分别选取Myspace和phpBB作为训练集，生成若干长度的密码字典。测试分为两种形式：第一种是同站测试，即训练集和测试集的数据来自同一个数据集，其中70%作为训练数据，剩余的30%作为测试数据；第二种是跨站测试，即训练集和测试集的数据来自不同的数据集，测试集中随机选取10%的密码。评价标准为命中率，即生成的密码与测试集的交集占测试集的比例。为了消除合理的波动，同一模型将生成10组长度相同的密码字典，分别计算命中率后取平均值。

3.2.2 GENPass测试方案

为了测试GENPass模型，选取Myspace和phpBB作为训练集，RockYou和LinkedIn作为测试集。测试方法和评价标准与3.2.1中一致。此外，分别用PL和LSTM训练MySpace、phpBB，用来和GENPass作对比。额外的，运用PL训练Myspace和phpBB直接混合后的数据集作为对比数据。

3.3 PL模型评价

分别用PL和LSTM训练Myspace和phpBB，并进行了同站测试，结果如图4所示。其中，PL（Myspace）表示用PL来训练Myspace数据集得到的结果，其余同理。从图4可以明显发现，PL模型的命中率要明显高于LSTM。尽管随着生成密码的数量增加，两者的准确率会最终接近相同，但PL可以生成更少的数据来获得相同的命中率。例如，用LSTM来训练Myspace，需要生成1012个密码才能达到50%的准确率，而PL模型仅需要生成107个密码。

图4 PL和LSTM同站测试比较

在跨站测试中，分别用PL和LSTM训练Myspace和phpBB，四个模型再分别生成数据，对RockYou和LinkedIn计算命中率。表3展示了生成密码量在106和107时的数据。

表3 单训练集的跨站测试

跨站测试的准确率要明显低于同站测试，因为各个数据集的特征都不相同，而仅训练一个数据集不足以猜测其他数据集。从实验结果可以看到，PL要比LSTM的准确率高16%～30%，表明用户习惯设置有意义的字符串的现象在各个数据集中通用，且PL模型在这方面能够比LSTM更优秀。

3.4 GENPass模型评价

GENPass基于多数据集生成密码。首先根据式（7）迭代计算Myspace和phpBB之间的概率分布P。迭代的过程如图5所示，横坐标为训练次数，纵坐标为KL散度。经过约450次迭代，KL散度值趋于稳定，最终得到Myspace和phpBB之间的分布为（30.004%，69.996%），表明phpBB的权重更重。同站测试中发现，phpBB的特征相对分散，而Myspace的特征比较集中，导致在生成相同数量密码的情况下，Myspace的命中率普遍高于phpBB。因此，在多数据集情形下，为了能够汲取更多phpBB的特征，应当给予其更大的关注。

图5 KL散度训练过程

图6 和图7展现了GENPass与其他模型的性能对比。其中，PL（Myspace）-RockYou表示用PL模型训练Myspace生成的密码集来测试RockYou，其余同理。可以看到，GENPass的表现几乎一直是最佳的，用PL单独训练Myspace得到的结果次之，说明Myspace具有较好的特征，与其他数据集重合度比较高。直接将Myspace和phpBB混合后训练，得到的命中率更低，说明盲目增大数据量而没有辨别的学习，结果适得其反。结果显示，使用GENPass可以比简单混合两个训练集提升超过20%的命中率。

图6 针对RockYou的跨站测试

图7 针对LinkedIn的跨站测试

最后，衡量GENPass创造有效密码的能力，结果如表4所示。以第一行为例，表示用Myspace作为训练集，运用PL模型来训练，生成107长度的密码字典，其中有460 878个不在Myspace中但却出现在RockYou中，有611 927个不在Myspace中但出现在了LinkedIn中。这说明了模型创造有效密码的能力，即生成的密码不在训练集中但出现在了跨站测试集中。从表4中可以看到，GENPass的创造能力同样是最出色的。

表4 模型创造密码的能力

4 结 语

本文介绍一种基于多数据集的密码生成模型GENPass。GENPass借用PCFG和GAN的思想，通过递归神经网络训练，提高了单数据集的命中率和多数据集的泛化性。GENPass的核心是神经网络，在此之前，大部分密码研究均是基于马尔科夫模型。随着神经网络的兴起，模型有了更好理解字符之间关系的能力，从而能够生成更贴近真实数据的密码。

本文首先提出PL（PCFG+LSTM）模型将密码的训练由字符级提升至单词级。在单数据集的测试中，PL模型取得50%的命中率仅需要生成107个密码，而单纯用LSTM需要生成1012个密码；在跨数据集的测试中，PL同样能够相比LSTM提高16%～30%。更进一步，本文将单数据集的提升拓展到多数据集，提出了GENPass模型，使用Myspace和phpBB作为训练集，RockYou和LinkedIn作为测试集。实验结果表明，使用GENPass可以比简单混合两个训练集提升超过20%的命中率。

密码是身份认证的最主要方式，短期内不会被生物识别完全取代。研究密码不是为了破解而获得私利，更重要的是能够对密码复杂度进行准确判断，从而引导用户设置更安全的密码。然而，数据量是密码研究的最重要问题。由于各家公司不会主动把用户数据公布出来，仅仅凭借目前泄漏出来的数据，不足以训练出一个非常完备的模型。为了解决数据量不足，迁移学习可以在未来进一步研究。