SOPG：基於搜尋的自迴歸神經網路有序密碼生成方法

1. 引言

密碼至今仍是最普遍的使用者驗證方式，在簡便性與有效性之間取得平衡。然而，其安全性持續受到密碼猜測攻擊的挑戰，這在攻擊性安全測試與防禦強度評估中都是關鍵環節。傳統方法，從基於規則的枚舉到如馬可夫鏈和PCFG等統計模型，在多樣性與效率上存在固有的限制。深度學習的出現，特別是自迴歸神經網路，預示著典範的轉移。然而，一個關鍵的疏忽持續存在：生成方法本身。標準的取樣技術引入了隨機性，產生重複密碼和無序的輸出，嚴重阻礙了攻擊效率。本文介紹了SOPG（基於搜尋的有序密碼生成），這是一種新穎的方法，迫使自迴歸模型以近似概率降序的方式生成密碼，從而徹底改變了基於神經網路的密碼猜測效率。

2. 背景與相關工作

3. SOPG 方法

4. 技術細節與數學公式

給定一個自迴歸模型（如GPT），密碼序列 $S = (s_1, s_2, ..., s_T)$ 的概率分解為： $$P(S) = \prod_{t=1}^{T} P(s_t | s_1, ..., s_{t-1})$$ 其中 $s_t$ 是位置 $t$ 的標記，而 $P(s_t | s_1, ..., s_{t-1})$ 是模型的輸出概率分佈。

標準隨機取樣從此分佈中抽取 $s_t$，導致隨機漫步。相反地，SOPG旨在找到最大化 $P(S)$ 的序列 $S^*$，或系統性地枚舉高概率序列。這可以視為： $$S^* = \arg\max_{S \in \mathcal{V}^*} P(S)$$ 其中 $\mathcal{V}^*$ 是最大長度內所有可能序列的集合。窮舉搜尋是難以處理的。因此，SOPG採用一種啟發式搜尋演算法（例如，使用對數概率成本的 $A^*$）來有效地近似這種有序枚舉。搜尋使用負對數概率作為成本：$\text{cost}(S) = -\sum_{t=1}^{T} \log P(s_t | s_1, ..., s_{t-1})$。該演算法旨在按成本遞增的順序輸出序列。

5. 實驗結果與分析

6. 分析框架與案例示例

框架：密碼猜測效率象限
我們可以在兩個軸上分析模型：模型能力（學習複雜分佈的能力，例如 GPT > 馬可夫）和生成效率（輸出的最佳排序）。

• 象限 I（高能力，低效率）： PassGPT、VAEPass。強大的模型因隨機取樣而受限。
• 象限 II（高能力，高效率）： SOPGesGPT。本工作達成的目標狀態。
• 象限 III（低能力，低效率）： 基本的規則型攻擊。
• 象限 IV（低能力，高效率）： OMEN、FLA。它們的生成本質上是有序的（按概率），但其模型能力限制了最終性能。

7. 應用前景與未來方向

立即應用：

• 主動式密碼強度評估： 安全公司可以使用SOPG驅動的工具來稽核密碼策略，透過以指數級更快的速度生成最可能的攻擊猜測，提供真實的風險評估。
• 數位鑑識與合法恢復： 在時間至關重要的法律調查中，加速密碼恢復。

• 混合搜尋策略： 將SOPG與有限的隨機性結合，以更早地探索概率稍低但可能富有成果的「創意」猜測，平衡利用與探索。
• 硬體加速搜尋： 在GPU/TPU上實作搜尋演算法，以平行化候選者評估，減少搜尋過程本身的開銷。
• 超越密碼： 將有序生成典範應用於其他自迴歸模型任務，其中有序、唯一的輸出具有價值，例如為軟體生成測試案例，或按可行性順序創建多樣的設計變體。
• 防禦對策： 研究如何偵測和防禦此類高效、有序的攻擊，可能透過研究SOPG生成的猜測清單與隨機清單的「指紋」差異。

8. 參考文獻

1. M. Jin, J. Ye, R. Shen, H. Lu, "Search-based Ordered Password Generation of Autoregressive Neural Networks," Manuscript Submitted for Publication.
2. A. Narayanan and V. Shmatikov, "Fast dictionary attacks on passwords using time-space tradeoff," in Proceedings of the 12th ACM conference on Computer and communications security, 2005.
3. M. Weir, S. Aggarwal, B. de Medeiros, and B. Glodek, "Password cracking using probabilistic context-free grammars," in 2009 30th IEEE Symposium on Security and Privacy, 2009.
4. J. Ma, W. Yang, M. Luo, and N. Li, "A study of probabilistic password models," in 2014 IEEE Symposium on Security and Privacy, 2014.
5. B. Hitaj, P. Gasti, G. Ateniese, and F. Perez-Cruz, "PassGAN: A Deep Learning Approach for Password Guessing," in Applied Cryptography and Network Security Workshops, 2019.
6. OpenAI, "Improving Language Understanding by Generative Pre-Training," 2018. [Online]. Available: https://cdn.openai.com/research-covers/language-unsupervised/language_understanding_paper.pdf
7. M. Pasquini, D. Bernardo, and G. Ateniese, "PassGPT: Password Modeling and (Guessing) with Large Language Models," in arXiv preprint arXiv:2306.01745, 2023.

9. 原創分析與專家評論