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

目錄

1. 簡介

密碼至今仍是最普遍的使用者身份驗證方法。因此，密碼猜測是網路安全研究的關鍵組成部分，既是攻擊性安全測試（破解）的基礎，也是防禦強度評估的依據。傳統方法，從基於規則的枚舉到如馬可夫鏈和PCFG等統計模型，在效率和多樣性上存在固有的限制。深度學習的出現，特別是自迴歸神經網路，預示著典範轉移。然而，一個關鍵瓶頸持續存在：標準的隨機取樣生成方法。這導致密碼重複，更不利的是，生成的順序是隨機的，迫使攻擊者必須篩選龐大且低效的清單。本文介紹了SOPG（基於搜尋的順序密碼生成法），這是一種新穎的方法，旨在讓自迴歸密碼猜測模型以近似概率降序的方式生成密碼，從而顯著提升攻擊效率。

2. 背景與相關工作

2.1 密碼猜測技術的演進

密碼猜測技術經歷了幾個不同的發展階段。早期方法依賴字典攻擊和手動制定的變形規則（例如 John the Ripper），這些方法具有啟發性且依賴經驗。大規模密碼外洩事件（例如 2009 年的 RockYou）的擴散，促進了數據驅動的統計方法。馬可夫模型（Weir 等人，2009）和概率上下文無關文法（PCFG）（Ma 等人，2014）提供了一個更系統化、基於概率的生成框架，儘管它們存在過度擬合的風險，且缺乏對密碼結構中複雜、長距離依賴關係進行建模的能力。

2.2 神經網路方法

深度學習模型，特別是像 PassGAN（Hitaj 等人，2017）這樣的生成對抗網路（GANs）以及基於 LSTM 或 GPT 架構的自迴歸模型，能直接從數據中學習密碼的概率分佈。它們可以生成高度多樣且逼真的密碼。然而，它們通常在每個生成步驟中，從學習到的分佈中進行隨機取樣（例如，多項式取樣）。這個基本過程與完整密碼概率的全局排序無關，從而導致了 SOPG 旨在解決的低效率問題。

3. SOPG 方法

3.1 核心概念

SOPG 將密碼生成從一個隨機取樣問題重新定義為一個引導式搜尋問題。它不再隨機挑選下一個字元，而是採用一種搜尋演算法（可能是波束搜尋或最佳優先搜尋的變體）來探索可能的密碼後續空間，優先探索那些能導向具有較高估計概率之完整密碼的路徑。目標是輸出一份密碼清單，其順序盡可能接近按 $P(密碼|模型)$ 進行真實降序排序的結果。

3.2 搜尋演算法

雖然 PDF 摘要未詳細說明具體演算法，但所描述的行為暗示了一種維護候選密碼前綴優先佇列的方法。在每一步，它透過查詢神經網路以獲得下一個字元的分佈，來擴展最有希望的前綴（累積概率最高），從而生成新的候選項。透過首先系統性地探索密碼空間的高概率區域，它確保了最早生成最可能的密碼，並從根本上避免了重複。

3.3 SOPGesGPT 模型

作者在基於 GPT 的架構上實作了他們的方法，創建了SOPGesGPT。GPT 模型（例如僅解碼器的 Transformer）在洩露的密碼資料集上進行訓練，以預測序列中的下一個字元。然後，SOPG 作為生成/推論方法應用於這個訓練好的模型之上，取代了標準的取樣方法。

4. 技術細節與數學公式

自迴歸模型將密碼 $\mathbf{x} = (x_1, x_2, ..., x_T)$ 的概率定義為條件概率的乘積： $$P(\mathbf{x}) = \prod_{t=1}^{T} P(x_t | x_1, ..., x_{t-1})$$ 其中 $x_t$ 是位置 $t$ 的字元，$T$ 是密碼長度。標準取樣選擇 $x_t \sim P(\cdot | x_1, ..., x_{t-1})$。

從概念上講，SOPG 旨在按 $P(\mathbf{x})$ 遞減的順序找到並輸出序列 $\mathbf{x}$。這可以被視為樹中的最短路徑搜尋問題，其中節點是前綴，邊的成本與 $-\log P(x_t | 前綴)$ 相關，目標是按總成本遞增（即概率遞減）的順序列舉路徑（密碼）。像統一成本搜尋（UCS）或其有界變體——具有大波束寬度和動態修剪的波束搜尋——這樣的演算法可以實現這種近似排序。關鍵在於搜尋的前沿是根據當前路徑的概率分數來確定優先順序的。

5. 實驗結果與分析

5.1 與隨機取樣的比較

本文展示了將 SOPG 與相同底層模型上的標準隨機取樣進行比較的令人信服的結果。主要發現：

• 零重複： SOPG 生成一份唯一的清單，而隨機取樣會產生許多重複，浪費計算資源。
• 卓越的攻擊效率： 為了達到相同的覆蓋率（測試集中被破解的密碼百分比），SOPG 需要遠少得多的模型推論次數，並生成總體小得多的清單。這直接轉化為現實場景中更快的密碼破解速度。

5.2 與尖端技術的基準測試

SOPGesGPT 與主要的密碼猜測模型進行了基準測試：OMEN（馬可夫）、FLA、PassGAN（GAN）、VAEPass（VAE）以及當代的 PassGPT。在單一網站測試中：

• 覆蓋率： SOPGesGPT 達到了35.06%，超越了 OMEN 254%、FLA 298%、PassGAN 421%、VAEPass 380% 以及 PassGPT 81%。
• 有效率： 本文還宣稱在「有效率」上領先，這可能是一個與早期生成密碼的品質或命中率相關的指標，而這正是 SOPG 的主要優勢。

這表明，對於性能而言，生成方法（SOPG）與模型架構同等重要。

6. 分析框架與案例範例

評估密碼猜測模型的框架：

1. 模型架構與訓練： 底層神經網路是什麼（GAN、VAE、自迴歸 Transformer）？它是如何訓練的？
2. 生成方法： 如何從訓練好的模型中產生密碼？（例如，隨機取樣、波束搜尋、SOPG）。這是本文的關鍵重點。
3. 排序與效率： 該方法是否以有用的順序（概率降序）產生密碼？其計算/猜測效率如何？
4. 多樣性與重複性： 它生成的是新穎密碼還是大量重複密碼？
5. 基準測試性能： 在標準資料集（例如 RockYou）上的覆蓋率、有效率以及速度。

非程式碼案例範例： 假設有兩位攻擊者，Alice 和 Bob，使用同一個訓練好的 GPT 密碼模型。Alice 使用標準隨機取樣。Bob 使用 SOPG。為了破解一個包含 1000 個密碼的測試集，Alice 的軟體可能需要生成 1000 萬個猜測，其中 30% 是重複的，才能破解 350 個。而 Bob 使用 SOPG 驅動的軟體可能僅需生成 100 萬個按最佳順序排列的唯一猜測，就能破解相同的 350 個密碼。Bob 的攻擊在資源效率上高出 10 倍，且完成速度更快。

7. 應用展望與未來方向

立即應用：

• 主動式密碼強度測試： 安全團隊可以使用 SOPG 增強後的模型，透過首先生成最可能的攻擊向量，來更有效地稽核提議的密碼策略。
• 鑑識密碼恢復： 合法的密碼恢復工具可以整合 SOPG，以在有限的時間/計算預算內提高成功率。

未來研究方向：

• 混合模型： 將 SOPG 的順序生成與其他架構的優勢相結合（例如，整合來自大型語言模型的語義知識）。
• 自適應/線上 SOPG： 根據部分攻擊結果的回饋，即時修改搜尋策略。
• 防禦對策： 研究新的密碼雜湊或儲存技術，專門針對像 SOPG 這樣有序的、概率驅動的攻擊具有韌性。
• 超越密碼： 將順序生成典範應用於其他安全領域，例如生成可能的釣魚網址或惡意軟體變種。

8. 參考文獻

1. Weir, M., Aggarwal, S., Medeiros, B., & Glodek, B. (2009). Password Cracking Using Probabilistic Context-Free Grammars. In IEEE Symposium on Security and Privacy.
2. Ma, J., Yang, W., Luo, M., & Li, N. (2014). A Study of Probabilistic Password Models. In IEEE Symposium on Security and Privacy.
3. Hitaj, B., Gasti, P., Ateniese, G., & Perez-Cruz, F. (2017). PassGAN: A Deep Learning Approach for Password Guessing. In International Conference on Applied Cryptography and Network Security.
4. Goodfellow, I., et al. (2014). Generative Adversarial Nets. Advances in Neural Information Processing Systems.
5. Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., & Sutskever, I. (2019). Language Models are Unsupervised Multitask Learners. OpenAI Blog.
6. Melicher, W., et al. (2016). Fast, Lean, and Accurate: Modeling Password Guessability Using Neural Networks. In USENIX Security Symposium.

9. 原創分析與專家評論