PGMaP：基于掩码预测的密码生成方法

《Expert Systems with Applications》：PGMaP: Password Generation Based on Mask Prediction

针对现有密码生成方法基于单向字符生成导致的遗漏问题，提出双向掩码预测的PGMaP方法。通过提取用户密码构造模板，构建基于Transformer的掩码语言模型MLM_Pass，利用双向上下文信息生成被传统方法忽略的密码变体，显著提升密码破解效率。实验验证在八组真实数据集上，融合PGMaP生成的密码使传统方法破解率提升最大达68.3%，独立生成时也优于Markov、PCFG等主流方法。

　　

陈阳王|范石|郭莎莎|张敏|沈毅|徐成熙|薛鹏飞

中国安徽合肥，国防科技大学电子工程学院，230037

摘要

近年来，许多研究专注于数据驱动的密码猜测方法，旨在减少用户使用弱密码的情况并提高密码安全性。现有的密码生成模型通过学习密码数据集的分布并拟合序列条件概率来生成候选猜测。这些方法基于一个关键假设：用户从左到右单向构建密码。然而，随着认证系统对密码策略要求的日益复杂以及人们安全意识的提高，用户开始通过修改现有或流行的密码来构建新密码。在这种情况下，用户会考虑密码的全局性和双向性信息。这打破了单向构建的关键假设，导致现有方法在生成密码时出现遗漏。受此启发，我们提出了一种基于掩码预测的密码生成方法，称为PGMaP，该方法能够捕捉到大量被遗漏的密码。首先，我们设计了一种密码构建模板提取算法，用于对用户用于构建和修改密码的模板进行聚类。然后，我们构建了一个基于Transformer的掩码语言模型来学习密码的双向特征。提取的模板被输入模型中，通过掩码预测生成密码猜测。与基于自回归模型的现有方法不同，PGMaP使用自编码模型根据双向信息生成密码。最后，通过对八个真实世界数据集进行密码猜测实验，我们证明了PGMaP能够有效生成大量被遗漏的密码，并且其密码猜测性能优于现有方法。

引言

文本密码几乎是所有网络服务中的主要认证形式，并已广泛使用了几十年。尽管已经应用了各种认证解决方案（如双因素认证Li, Tan, Meng, & Wang (2020); Wang & Wang (2016)和生物特征认证Jain, Ross, & Pankanti (2006); Zaidi, Chong, Jin, Parthiban, & Sadiq (2021)）来提高认证系统的安全性，但在可预见的未来，文本密码仍将是主要的认证方法。因为文本密码具有低成本和易于部署的优势（Bonneau, Herley, Van Oorschot, Stajano, 2012, Bonneau, Herley, Van Oorschot, Stajano, 2015; Freeman, Jain, Dürmuth, Biggio, & Giacinto (2016); Herley & Van Oorschot (2011); Oesch & Ruoti (2020)）。然而，安全性和易记性是用户在设置密码时需要考虑的两个重要方面。高度安全的密码确实是随机的，这使用户难以记住，而容易记住的密码则高度可预测且不安全。

为了帮助用户构建安全的密码并减少弱密码的使用，提出了许多密码猜测方法来评估密码在猜测攻击下的安全性。这些方法使用历史上泄露的密码数据集进行训练，并对目标密码数据集进行破解测试以评估其安全性。三种主要的密码猜测方法是基于规则的（如Hashcat Steube (2018)和John the Ripper Peslyak (2021)）、基于概率的（如PCFG Weir, Aggarwal, De Medeiros, & Glodek (2009)和Markov Narayanan & Shmatikov (2005)）以及基于深度学习的（如FLA Melicher et al. (2016), PassGAN Hitaj, Gasti, Ateniese, & Perez-Cruz (2019), 和PassGPT Rando, Perez-Cruz, & Hitaj (2023)）。基于规则的方法需要预定义的规则，无法学习密码集的分布特征。现有的基于马尔可夫和深度学习模型的密码猜测方法遵循一个关键假设：用户从左到右单向构建密码。它们训练整个密码并通过从左到右链接字符来计算密码的概率。它们通过逐步预测下一个字符的概率来顺序生成密码。

然而，单向构建密码的关键假设在实践中是有缺陷的。随着在线认证系统对密码策略要求的复杂性增加（超过两种字符类型和更长的密码长度）以及用户安全意识的提高，用户会对现有密码进行修改来构建新密码。在这种情况下，用户会选择和修改密码中的一些字符。生成密码的过程不再遵循单向条件概率分布，而应该利用密码的双向信息。这导致现有密码生成方法出现遗漏，使得难以生成所有这些用户修改后的密码。

如图1所示，实举示露数据集中的密码用实线表示，而FLA方法生成的密码用虚线表示。尽管现有方法可以生成诸如“000@webhost”、“000w3bhost”、“000webhost1”等以“000webhost”为中心的密码，但仍然存在许多遗漏。例如“0,00webhost”、“000w@ebhost”、“000vebhost”等密码没有被生成。这是基于自回归模型的密码猜测方法固有的缺陷。当模型预测下一个字符时，如果某些字符的预测概率较低，就会导致该密码前缀的路径被剪除。例如，在预测前缀“000”后的下一个字符时，“w”、“W”和“@”的概率相对较高，因此生成了前缀“000w”、“000W”和“000@”。然而，“v”和“!”的概率较低，所以前缀“000v”和“000!”被剪除，从而导致像“000vebhost”和“000!ebhost”这样的密码被遗漏。但是，这些被遗漏的密码遵循相同的密码模板“000#ebhost”。通过恢复模板中的更多“#”字符，我们可以生成这些被遗漏的密码。如果我们能够对密码的双向条件概率分布进行建模并生成这些被遗漏的密码，密码猜测性能将得到显著提高。

受此启发，我们提出了一种基于掩码预测的密码生成方法，称为PGMaP，旨在捕捉到大量被遗漏的密码。与现有的自回归模型不同，PGMaP基于自编码模型生成密码，并利用密码的双向信息。首先，我们设计了一种密码构建模板提取算法，用于对用户用于构建和修改密码的模板进行聚类。其次，我们构建了一个基于Transformer的掩码语言模型（MLM），名为MLM_Pass，来学习密码的双向特征。提取的密码模板被输入MLM_Pass中，通过掩码预测生成密码。这一想法源于一个直觉：修改现有密码的过程类似于在特定位置插入空格，然后用字符填充这些空格。最后，我们通过两个方面的广泛实验证明了所提方法的有效性：（1）生成被遗漏的密码。我们将MLM_Pass生成的密码猜测与现有猜测模型结合起来，以补充被遗漏的密码。实验结果表明，在所有八个真实世界数据集中，所提方法显著提高了密码破解率，优于五种最先进的猜测方法。（2）大规模生成在拖网场景中。我们使用从数据集中提取的广泛密码模板，设置了一个较低的概率阈值来采样并生成大量密码。在10⁷到10⁸次猜测中，我们的方法在六个数据集上均优于现有方法。主要贡献如下。

•

一种新的密码生成方法。我们提出了PGMaP，一种基于掩码预测的密码生成方法。与现有的自回归密码生成方法不同，PGMaP使用自编码模型学习密码的双向特征，从而更全面地生成密码。

•

一种快速的密码模板提取算法。

基于用户修改密码的行为模式，我们设计了一种首先进行掩码处理然后进行聚类的密码模板提取算法。与直接密码字符串聚类相比，这种方法既快速又精确。

•

我们构建了MLM_Pass，一个基于Transformer的MLM，来学习密码的双向特征。密码模板被输入MLM_Pass中进行密码生成。

•

我们通过对八个真实世界密码数据集的广泛实验，证明了所提方法的有效性。在融合PGMaP生成的密码后，现有方法的破解率都得到了显著提高。当独立生成大量密码猜测时，PGMaP也优于现有方法。

本文的其余部分组织如下。第2节介绍了密码猜测的相关工作以及掩码语言模型（MLM）和基于采样的密码生成的背景。第3节描述了基于掩码预测的密码生成方法。第4节通过密码猜测实验评估了所提方法。第5节讨论了限制和未来的工作。最后，第6节总结了本文。

章节片段

背景和相关工作

在本节中，我们介绍了三种主要的密码猜测方法：基于规则的、基于概率的和基于深度学习的。

方法

威胁模型。密码破解攻击主要包括在线定向攻击（Wang et al. (2016b)和离线拖网攻击（Dell’Amico & Filippone (2015); Pasquini et al. (2021b); Ur et al. (2015); Wang, He, Cheng, & Wang (2016a）。在本文中，我们主要考虑离线拖网攻击的情况。攻击者试图在有限的破解预算下猜测尽可能多的密码。离线攻击通过构建模型从泄露的密码数据集中学习特征

评估

在本节中，我们进行了系统实验来评估所提出的密码生成方法的有效性。我们的方法旨在生成现有方法遗漏的密码。因此，我们训练了五种现有的密码猜测模型（Markov、PCFG、FLA、PassGAN和PassGPT），并将我们方法的生成密码猜测与这五种现有方法结合起来，以提高密码破解性能。我们在实验前后保持猜测预算的大小不变

限制

在本文中，我们提出了一种基于掩码预测的密码猜测方法，该方法基于双向信息生成密码并捕捉被遗漏的密码。尽管我们的方法能够生成被遗漏的密码并提高密码猜测性能，但仍有一些问题需要讨论。我们探索了基于文本采样的方法，以实现大规模密码生成的自编码模型。然而，所提出的方法需要一个密码模板

结论

在本文中，我们提出了一种基于掩码预测的密码生成方法，该方法基于双向信息更全面地生成密码。与现有的基于自回归模型的方法不同，这些方法仅在一个方向上递归生成密码字符，而我们的方法基于双向条件概率分布来预测字符。我们构建了一个基于Transformer的MLM，名为MLM_Pass，来学习密码的双向特征并生成猜测

作者贡献

陈阳王：概念化、方法论、软件、验证、写作——原始草稿的撰写和修订、调查、可视化。

范石：方法论、数据整理、手稿审阅。

郭莎莎：理论改进、写作——审阅和编辑。

张敏：概念化、形式分析、调查、写作——审阅和编辑。

沈毅：实验监督、手稿审阅。

薛鹏飞：数据分析、手稿修订。

徐成熙：实验改进

利益冲突声明

作者声明他们没有已知的可能会影响本文报告工作的竞争性财务利益或个人关系。