SOPG：基于搜索的自回归神经网络有序密码生成方法

1. 引言

密码因其简单性和灵活性，仍然是用户身份验证的主要方式。因此，密码猜测是网络安全研究的关键组成部分，对于攻击性安全测试（例如渗透测试、密码恢复）和防御强度评估都至关重要。传统方法，从基于规则的攻击到马尔可夫链和PCFG等统计模型，在可扩展性和适应性方面存在固有的局限性。

深度学习的出现，特别是像GPT这样的自回归神经网络，通过直接从数据中学习复杂的密码分布，有望带来范式转变。然而，一个关键的疏忽在于生成策略。标准的采样方法（例如随机采样、top-k）以随机顺序生成密码，导致效率极低：重复率高，并且无法在攻击早期优先生成高概率（即更可能）的密码。本文介绍了SOPG（基于搜索的有序密码生成），这是一种新颖的方法，它迫使自回归模型以近似概率降序生成密码，从而显著提高密码猜测攻击的效率。

2. 背景与相关工作

2.1 密码猜测技术的演进

密码猜测经历了不同的发展阶段：

基于规则与字典攻击：依赖人工规则和单词列表。高度依赖专家知识，容易遗漏新的模式。
统计模型（例如马尔可夫、PCFG）：引入了概率框架。像OMEN和FLA这样的模型表现出改进的性能，但在泛化和长尾分布方面存在困难。
深度学习时代：像PassGAN（基于GAN）、VAEPass（基于VAE）和PassGPT（基于GPT）这样的模型利用神经网络对复杂的高维密码分布进行建模，无需手动特征工程。

2.2 神经网络方法

自回归模型，如GPT，特别适合密码生成，因为它们按逐个标记对序列的概率进行建模：$P(密码) = \prod_{t=1}^{T} P(c_t | c_1, ..., c_{t-1})$。这允许生成可变长度的密码，并有效地捕捉上下文依赖关系。

2.3 生成顺序问题

作者发现的核心低效问题不在于模型能力，而在于生成顺序。从训练好的模型中随机采样产生的密码不考虑其可能性。对于成功的字典攻击，首先生成高概率密码至关重要。SOPG通过用定向搜索算法替代随机采样来解决这个问题。

3. SOPG方法

3.1 核心原理

SOPG将密码生成从一个随机过程转变为最佳优先搜索问题。目标是按照从最高到最低估计概率输出序列的顺序，遍历可能的密码序列空间（一棵树）。

3.2 搜索算法

该方法采用优先级队列（例如，集束搜索的变体或概率扩展算法）。在每一步，具有最高累积概率的部分序列通过添加一个标记进行扩展。部分序列 $s = (c_1, ..., c_k)$ 的概率由模型估计：$P(s) = \prod_{t=1}^{k} P(c_t | c_1, ..., c_{t-1})$。搜索持续进行，直到满足终止条件（例如，序列结束标记），输出一个完整的密码。下一个密码通过从队列中下一个最佳的部分序列恢复搜索来生成。

序列扩展的关键公式： 当扩展一个节点（部分序列）时，新候选序列 $s'$（通过将标记 $c$ 附加到 $s$ 形成）的优先级是其联合概率：$Priority(s') = P(s) \cdot P(c | s)$。搜索总是扩展当前优先级最高的节点。

3.3 与自回归模型的集成

SOPG是模型无关的。它仅使用预训练的自回归模型（例如GPT变体）作为概率估计器 $P(c_t | context)$。搜索算法协调对此估计器的调用，以系统地探索序列空间。

4. 技术实现：SOPGesGPT

4.1 模型架构

作者实现了SOPGesGPT，这是一个基于GPT架构（例如Transformer解码器块）构建的密码猜测模型，并在泄露的密码语料库上进行训练。该模型学习真实密码的字符/字节级分布。

4.2 概率估计与搜索

在生成过程中，SOPGesGPT不进行简单的采样。相反，对于给定的部分序列，它计算下一个标记在整个词汇表上的概率分布。SOPG算法使用这些概率在其优先级队列中对搜索边界进行排序和管理。

关键性能指标（概念性）

覆盖率
从测试集中破解的目标密码百分比。

有效生成率
生成的唯一有效密码的速率。

推理效率
达到给定覆盖率所需的模型调用/猜测次数。

5. 实验结果与分析

5.1 实验设置

实验在真实世界的泄露密码数据集（例如RockYou）上进行。模型在部分数据上训练，其猜测性能在保留的测试集上进行评估。

5.2 与随机采样的对比

结果： SOPG与从相同基础GPT模型进行的标准随机采样对比。

重复消除： SOPG本质上生成唯一密码；随机采样产生许多重复项。
顺序效率： 为了达到相同的覆盖率（例如10%），SOPG所需的推理次数和生成的密码总数都显著少于随机采样。这是因为SOPG的有序生成能更早地“命中”可能的密码。

图表含义： 覆盖率与猜测次数的关系图将显示SOPG曲线在早期急剧上升，而随机采样曲线则缓慢线性上升，这证明了其卓越的攻击效率。

5.3 与前沿技术的基准测试

结果： 在单站点测试中，将SOPGesGPT与OMEN、FLA、PassGAN、VAEPass和PassGPT进行比较。

覆盖率： SOPGesGPT实现了35.06%的覆盖率。
相对提升： 这表示相对于OMEN提升了254%，相对于FLA提升了298%，相对于PassGAN提升了421%，相对于VAEPass提升了380%，相对于PassGPT提升了81%。
有效生成率： SOPGesGPT在密码生成的有效率方面也处于领先地位。

图表含义： 比较所有模型覆盖率的条形图将显示SOPGesGPT的柱状图明显高于所有其他模型，直观地证实了其优越性能。

5.4 关键性能指标

实验最终证明，SOPG解决了神经密码猜测的核心低效问题。性能增益主要不是来自更好的基础模型（尽管GPT很强），而是来自有序生成策略，该策略确保每次猜测都尽可能有效。

6. 分析框架与案例示例

场景： 一家安全公司受命审计某企业系统的密码强度。他们拥有一个训练好的自回归密码模型。

传统方法（随机采样）： 审计员生成1000万个密码。由于随机性和重复项，高概率密码“公司名2023！”可能要到500万次猜测后才出现，浪费了时间和计算资源。

SOPG增强方法： 使用相同的模型配合SOPG，审计员按概率降序生成密码。“公司名2023！”和其他常见模式在前10万次猜测内就会出现。审计能以数量级更快的速度和更少的计算量，得出关于漏洞的结论性评估（例如，“30%的用户密码可通过100万次猜测破解”）。

框架要点： SOPG提供了一个系统、高效的框架，用于将概率模型转化为高收益的攻击工具，最大化每次模型推理的投资回报。

7. 未来应用与研究展望

主动式密码强度检查器： 集成到实时密码创建系统中，模拟基于SOPG的攻击，并即时拒绝弱密码。
增强的安全培训： 使用SOPG生成的列表为系统管理员创建更真实的“常见密码”黑名单。
对抗性机器学习： 研究SOPG的效率可以带来更好的防御措施，例如设计更能抵抗有序智能猜测的密码策略或哈希算法。
超越密码： SOPG原理可以应用于其他自回归生成任务，其中按可能性排序输出是有益的，例如为软件模糊测试生成测试用例，或在药物发现中探索化合物空间。
搜索效率研究： 进一步优化搜索算法本身（例如，使用更复杂的启发式方法、并行化）以处理更大的密码空间。

8. 参考文献

M. Jin, J. Ye, R. Shen, H. Lu, "Search-based Ordered Password Generation of Autoregressive Neural Networks," Manuscript Under Review.
J. T. G. H. M. Weir, "Using Probabilistic Context-Free Grammars for Password Guessing," in Proceedings of the 5th USENIX conference on Offensive technologies, 2009.
A. Radford, et al., "Language Models are Unsupervised Multitask Learners," OpenAI Blog, 2019. (GPT基础论文)
B. Hitaj, et al., "PassGAN: A Deep Learning Approach for Password Guessing," in Proceedings of the 16th International Conference on Applied Cryptography and Network Security, 2019.
M. Pasquini, et al., "PassGPT: Password Modeling and (Guessed)Strength Evaluation with Large Language Models," arXiv preprint arXiv:2306.01745, 2023.
P. G. Kelley, et al., "Guess Again (and Again and Again): Measuring Password Strength by Simulating Password-Cracking Algorithms," in IEEE Symposium on Security and Privacy, 2012.

9. 原创分析与专家洞见

核心洞见： 本文的卓越之处不在于发明新的神经架构，而在于识别并精准地纠正了在强大AI模型应用中一个关键但被忽视的系统性缺陷。它认识到，对于密码猜测，生成顺序不仅仅是一个实现细节——它是区分理论上强大的模型和实际高效的武器之间的决定性因素。这将研究重点从纯粹的模型能力（一场收益递减的军备竞赛，正如从PassGAN到PassGPT的进展所见）转向生成策略优化，这是一种更具算法性和根本性的改进。

逻辑脉络： 论证极具说服力且简单：1）自回归模型擅长学习密码分布。2）从该分布中随机采样对于攻击而言效率极低。3）因此，我们必须智能采样。SOPG的解决方案——将生成视为概率树上的最佳优先搜索——是将这一逻辑优雅而直接地转化为算法。它利用模型的核心能力（概率估计）来指导其自身的探索，创造了一个效率的良性循环。

优势与不足： 其优势毋庸置疑：相对于同期模型81-421%的提升，在一个成熟领域是一场压倒性的胜利，证明了该概念的极端重要性。该方法也优雅地实现了模型无关性，使其成为任何现有自回归密码模型的即插即用升级。然而，一个潜在的不足（间接承认）是每个密码的计算开销。维护和查询优先级队列比单个采样步骤成本更高。本文正确地反驳了这一点，展示了为达到相同覆盖率所需总密码数的大幅减少，使得这种权衡具有压倒性的正面意义。对于现实世界的攻击者而言，一个更深层的不足是假设可以直接访问模型的输出概率分布，这在面对使用高级哈希（如Argon2）或“胡椒”的强化系统时可能不成立。正如2012年Kelley等人关于模拟破解算法的研究所指出的，现实世界的威胁模型是复杂的。

可操作的见解： 对于网络安全专业人员而言，本文是一个指令：立即弃用任何使用AI模型进行简单采样的密码强度评估。 工具必须集成类似SOPG的有序生成，以提供现实的风险评估。对于研究人员而言，道路是清晰的：下一个前沿是混合方法。将SOPG的有序搜索与GAN的避免模式崩溃优势或VAE的潜在空间探索相结合。此外，随着大语言模型（LLM）变得多模态，未来的“密码猜测”可能涉及基于从社交媒体抓取的用户画像数据生成可信的密码短语，并由SOPG指导生成。防御界必须做出相应回应，超越组合规则，推广密码管理器的使用和FIDO2/WebAuthn标准的广泛采用（正如NIST指南所建议的），以使最高效的猜测攻击也过时。

目录