SOPG：基於搜尋的順序密碼生成法——適用於自迴歸神經網路

目錄

• 1. 簡介
• 2. 背景與相關研究
  • 2.1 密碼猜測技術的演進
  • 2.2 神經網路方法
  • 2.3 生成順序問題
• 3. SOPG 方法
  • 3.1 核心原理
  • 3.2 搜尋演算法
  • 3.3 與自迴歸模型的整合
• 4. 技術實作：SOPGesGPT
  • 4.1 模型架構
  • 4.2 概率估計與搜尋
• 5. 實驗結果與分析
  • 5.1 實驗設定
  • 5.2 與隨機取樣的比較
  • 5.3 與尖端技術的基準測試
  • 5.4 關鍵效能指標
• 6. 分析框架與案例範例
• 7. 未來應用與研究方向
• 8. 參考文獻
• 9. 原創分析與專家見解

1. 簡介

密碼因其簡單性和靈活性，仍是使用者身份驗證的主流方法。因此，密碼猜測是網路安全研究的關鍵組成部分，對於攻擊性安全測試（例如滲透測試、密碼恢復）和防禦強度評估都至關重要。傳統方法，從基於規則的攻擊到如馬可夫鏈和PCFG等統計模型，在可擴展性和適應性方面存在固有的限制。

深度學習的出現，特別是像GPT這樣的自迴歸神經網路，承諾透過直接從數據中學習複雜的密碼分佈來實現典範轉移。然而，一個關鍵的疏忽在於生成策略。標準的取樣方法（例如隨機取樣、top-k）以隨機順序產生密碼，導致巨大的效率低下：高重複率以及無法在攻擊早期優先產生高概率（因此更可能）的密碼。本文介紹了SOPG（基於搜尋的順序密碼生成法），這是一種新方法，迫使自迴歸模型以近似概率降序的方式生成密碼，從而顯著提高密碼猜測攻擊的效率。

2. 背景與相關研究

2.1 密碼猜測技術的演進

密碼猜測經歷了幾個不同的發展階段：

• 基於規則與字典攻擊：依賴手動規則和單詞列表。高度依賴專家知識，且容易遺漏新穎的模式。
• 統計模型（例如馬可夫鏈、PCFG）：引入了機率框架。像OMEN和FLA這樣的模型顯示了改進的性能，但在泛化能力和長尾分佈方面存在困難。
• 深度學習時代：像PassGAN（基於GAN）、VAEPass（基於VAE）和PassGPT（基於GPT）等模型利用神經網路來建模複雜的高維密碼分佈，無需手動特徵工程。

2.2 神經網路方法

自迴歸模型，例如GPT，特別適合密碼生成，因為它們逐個標記地建模序列的機率：$P(password) = \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萬個密碼。由於隨機性和重複性，高概率密碼「CompanyName2023!」可能要到500萬次猜測後才會出現，浪費時間和計算資源。

SOPG增強方法： 使用相同的模型搭配SOPG，審計員以概率降序生成密碼。「CompanyName2023!」和其他常見模式會在前10萬次猜測內出現。審計能以數量級更快的速度和更少的計算量，得出關於漏洞的結論性評估（例如「30%的使用者密碼可被100萬次猜測破解」）。

框架要點： SOPG提供了一個系統化、高效的框架，將機率模型轉化為高產出的攻擊工具，最大化每次模型推論的投資回報率。

7. 未來應用與研究方向

• 主動式密碼強度檢查器： 整合到即時密碼創建系統中，模擬基於SOPG的攻擊，並立即拒絕弱密碼。
• 增強安全培訓： 使用SOPG生成的列表，為系統管理員創建更真實的「常見密碼」黑名單。
• 對抗性機器學習： 研究SOPG的效率可以帶來更好的防禦措施，例如設計更能抵抗有序、智能猜測的密碼策略或雜湊演算法。
• 超越密碼： SOPG原理可以應用於其他自迴歸生成任務，其中按可能性排序輸出是有益的，例如為軟體模糊測試生成測試用例，或在藥物發現中探索化合物空間。
• 搜尋效率研究： 進一步優化搜尋演算法本身（例如使用更複雜的啟發式方法、平行化），以處理更大的密碼空間。

8. 參考文獻

1. M. Jin, J. Ye, R. Shen, H. Lu, "Search-based Ordered Password Generation of Autoregressive Neural Networks," Manuscript Under Review.
2. 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.
3. A. Radford, et al., "Language Models are Unsupervised Multitask Learners," OpenAI Blog, 2019. (GPT基礎論文)
4. 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.
5. M. Pasquini, et al., "PassGPT: Password Modeling and (Guessed)Strength Evaluation with Large Language Models," arXiv preprint arXiv:2306.01745, 2023.
6. 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）或胡椒（pepper）的強化系統時可能不成立。正如2012年Kelley等人關於模擬破解演算法的研究所指出的，現實世界的威脅模型是複雜的。

可行動的見解： 對於網路安全專業人士而言，本文是一個指令：立即棄用任何使用從AI模型進行單純取樣的密碼強度評估。 工具必須整合類似SOPG的有序生成，以提供真實的風險評估。對於研究人員而言，道路是清晰的：下一個前沿是混合方法。將SOPG的有序搜尋與GAN避免模式崩潰的優點或VAE的潛在空間探索相結合。此外，隨著大型語言模型（LLM）變得更加多模態，未來的「密碼猜測」可能涉及基於從社交媒體抓取的使用者個人資料生成可信的密碼短語，並由SOPG引導生成。防禦社群必須做出相應回應，超越組合規則，轉而推廣密碼管理器的使用以及廣泛採用FIDO2/WebAuthn標準（如NIST指南所建議），以使即使是最有效率的猜測攻擊也變得過時。