1. 簡介

密碼因其簡單性和靈活性，至今仍是最普遍的使用者身份驗證方法。因此，密碼猜測是網路安全研究的關鍵組成部分，無論對於攻擊性安全測試（例如滲透測試、密碼恢復）還是防禦強度評估都至關重要。傳統方法，從基於規則的字典攻擊到馬可夫鏈和PCFG等統計模型，在可擴展性和適應性方面存在固有的限制。深度學習的出現，特別是自迴歸神經網路，承諾透過直接從數據中學習複雜的密碼分佈來實現範式轉移。然而，一個顯著的瓶頸依然存在：與這些模型搭配使用的標準隨機取樣生成方法效率極低，會產生重複項且缺乏任何最佳順序，這大大降低了實際密碼攻擊的速度。本文介紹了SOPG（基於搜尋的順序密碼生成法），這是一種新穎的方法，旨在從自迴歸模型中按概率近似降序生成密碼，從而徹底改變神經網路密碼猜測的效率。

2. 背景與相關工作

2.1 傳統密碼猜測方法

早期方法依賴於字典攻擊和手動編寫的變形規則（例如John the Ripper）。雖然簡單，但這些方法缺乏理論基礎，其有效性嚴重依賴專家知識。大規模密碼外洩事件（例如2009年的RockYou）的激增促進了數據驅動的機率方法。馬可夫模型（例如OMEN）和機率上下文無關文法（PCFG）代表了重大進步，系統地對密碼結構和機率進行建模。然而，它們經常面臨過度擬合的問題，並且難以生成多樣化、大規模的合理密碼集合，從而限制了其覆蓋率。

2.2 基於神經網路的方法

深度學習模型，包括像PassGAN這樣的生成對抗網路（GANs）和像VAEPass這樣的變分自編碼器（VAEs），學習密碼資料集的底層分佈。最近，自迴歸模型，特別是基於Transformer架構的模型（例如PassGPT），透過將密碼建模為序列並根據先前的標記預測下一個標記，展現了卓越的性能。這些模型能更有效地捕捉長距離依賴關係。所有這些神經網路方法的基本缺陷在於預設使用隨機取樣（例如核心取樣、top-k取樣）來生成密碼，這種方法本質上是無序且重複的。

3. SOPG 方法

3.1 核心概念與動機

SOPG的核心洞見是：為了使密碼猜測攻擊高效，生成的密碼列表應是不重複的，並且按可能性從高到低排序。隨機取樣在這兩方面都失敗了。SOPG透過將自迴歸模型視為系統性搜尋演算法的機率指南來解決這個問題，類似於集束搜尋，但最佳化用於生成完整、有序的獨特候選項集合，而非單一最佳序列。

3.2 搜尋演算法與順序生成

SOPG在潛在的密碼空間上採用基於優先佇列的搜尋策略。它從初始標記（例如序列開始標記）開始，迭代地擴展部分密碼。在每一步，它使用神經網路來預測下一個可能字元的機率。它不是隨機取樣，而是策略性地探索分支，優先處理那些能導向最高機率完整密碼的擴展。這個過程系統地以近乎最佳的順序枚舉密碼，有效地對模型的機率分佈進行引導式遍歷。

3.3 SOPGesGPT 模型架構

作者在SOPGesGPT中實例化了他們的方法，這是一個基於GPT（生成式預訓練轉換器）架構構建的密碼猜測模型。該模型在真實的密碼外洩資料上進行訓練，以學習密碼標記的聯合機率分佈 $P(x_1, x_2, ..., x_T)$。GPT的自迴歸特性，即 $P(x_t | x_{

4. 技術細節與數學公式

給定一個自迴歸模型，它將密碼 $\mathbf{x} = (x_1, x_2, ..., x_T)$ 的機率定義為： $$P(\mathbf{x}) = \prod_{t=1}^{T} P(x_t | x_1, ..., x_{t-1})$$ SOPG的目標是生成一個序列 $\mathbf{x}^{(1)}, \mathbf{x}^{(2)}, ...$，使得 $P(\mathbf{x}^{(1)}) \geq P(\mathbf{x}^{(2)}) \geq ...$ 且對於 $i \neq j$ 有 $\mathbf{x}^{(i)} \neq \mathbf{x}^{(j)}$。

該演算法可以概念化為搜尋一棵樹，其中每個節點都是一個部分密碼。一個優先佇列管理節點，並根據從該節點衍生的任何完整密碼機率的上界估計值進行排序。這個估計值源自模型的條件機率。該演算法反覆提取具有最高上界的節點，將其擴展一個標記（生成子節點），計算新的上界，並將它們插回佇列中。當彈出一個葉節點（一個完整密碼）時，它將作為有序列表中的下一個密碼輸出。這確保了對機率空間的最佳優先搜尋。

5. 實驗結果與分析

覆蓋率

35.06%

SOPGesGPT在測試集上的表現

相較於PassGPT的提升

81%

更高的覆蓋率

推論效率

遠少於

所需密碼數量 vs. 隨機取樣

5.1 與隨機取樣的比較

本文首先展示了SOPG在相同底層GPT模型上相對於隨機取樣的基本優勢。為了達到相同的覆蓋率（被破解的測試密碼百分比），SOPG需要少幾個數量級的生成密碼和模型推論。這是因為SOPG生成的每個密碼都是獨特且高機率的，而隨機取樣則將計算浪費在重複項和低機率猜測上。這直接轉化為更快的攻擊時間和更低的計算成本。

5.2 與尖端技術的基準測試

在一項單一網站測試中，SOPGesGPT與主要基準進行了比較：OMEN（馬可夫）、FLA、PassGAN（GAN）、VAEPass（VAE）以及當代的PassGPT（使用隨機取樣的Transformer）。結果是決定性的。SOPGesGPT達到了35.06%的覆蓋率，超過PassGPT 81%，超過VAEPass 380%，超過PassGAN 421%，超過FLA 298%，超過OMEN 254%。這確立了新的尖端技術標準，突顯出生成方法（SOPG）與模型架構同等重要。

5.3 關鍵效能指標

有效命中率：生成的密碼中是真實密碼（與測試集中的密碼匹配）的比例。SOPGesGPT在此指標上也處於領先地位，表明它不僅生成更多，而且是品質更好的猜測。
生成效率：透過破解給定百分比密碼所需的模型呼叫/推論次數來衡量。SOPG的有序方法提供了陡峭的效率曲線，用極少的推論次數就能破解許多密碼。
圖表說明：一個假設的圖表將顯示兩條線：一條是「隨機取樣覆蓋率 vs. 生成密碼數量」，緩慢且漸近地上升，帶有長尾的重複項。另一條「SOPG覆蓋率 vs. 生成密碼數量」的線在開始時會急劇且幾乎線性上升，後期趨於平穩，展示了近乎最佳的猜測順序。

6. 分析框架與案例範例

框架：密碼猜測效率象限。 我們可以沿著兩個軸分析任何密碼猜測系統：(1) 模型品質（學習真實密碼分佈的能力），以及 (2) 生成最佳化程度（能夠按機率降序輸出猜測而不浪費）。

  • 象限 I（低模型品質，低最佳化程度）： 傳統的基於規則的攻擊。
  • 象限 II（高模型品質，低最佳化程度）： PassGPT、PassGAN – 強大的模型因隨機取樣而受限。
  • 象限 III（低模型品質，高最佳化程度）： 有序馬可夫/PCFG – 模型有限但生成效率高。
  • 象限 IV（高模型品質，高最佳化程度）： SOPGesGPT – 目標狀態，結合了高容量神經模型與SOPG最佳生成演算法。

案例範例（無程式碼）： 考慮一個模型知道密碼 "password123" 的機率為 $10^{-3}$，而 "xq7!kLp2" 的機率為 $10^{-9}$。一個隨機取樣器可能需要數百萬次猜測才能命中 "password123"。而SOPG利用其搜尋，會將 "password123" 識別並輸出為其最初的幾個猜測之一，立即貢獻於覆蓋率。這種有序的目標鎖定是其效率大幅提升的來源。

7. 應用展望與未來方向

主動式密碼強度檢查器： SOPG可以驅動下一代即時密碼強度檢測器，這些檢測器不僅僅是檢查字典，還能模擬尖端的、高效的攻擊，為使用者提供更真實的風險評估。
數位鑑識與合法恢復： 加速對扣押設備進行授權調查時的密碼恢復過程。
身份驗證系統的對抗性訓練： 使用SOPG生成的列表對身份驗證系統進行壓力測試，並針對智慧型攻擊進行強化。
未來研究方向：

  • 混合模型： 將SOPG的有序生成與其他生成式架構（例如擴散模型）結合用於密碼生成。
  • 自適應/線上SOPG： 根據目標系統的回饋（例如速率限制回應）即時修改搜尋策略。
  • 超越密碼： 將有序生成範式應用於其他安全領域，例如生成可能的釣魚網址或惡意軟體變種。
  • 防禦性對策： 研究如何偵測和緩解使用有序生成策略的攻擊。

8. 參考文獻

  1. J. Bonneau, "The Science of Guessing: Analyzing an Anonymized Corpus of 70 Million Passwords," IEEE Symposium on Security and Privacy, 2012.
  2. M. Weir, S. Aggarwal, B. de Medeiros, and B. Glodek, "Password Cracking Using Probabilistic Context-Free Grammars," IEEE Symposium on Security and Privacy, 2009.
  3. A. Radford, K. Narasimhan, T. Salimans, and I. Sutskever, "Improving Language Understanding by Generative Pre-Training," OpenAI, 2018. (GPT基礎論文)
  4. B. Hitaj, P. Gasti, G. Ateniese, and F. Perez-Cruz, "PassGAN: A Deep Learning Approach for Password Guessing," International Conference on Applied Cryptography and Network Security (ACNS), 2019.
  5. D. Pasquini, G. Ateniese, and M. Bernaschi, "Unleashing the Tiger: Inference Attacks on Split Learning," ACM SIGSAC Conference on Computer and Communications Security (CCS), 2021. (包含密碼推論的討論)。
  6. M. J. H. Almeida, I. M. de Sousa, and N. Neves, "Using Deep Learning for Password Guessing: A Systematic Review," Computers & Security, 2023.

9. 原創分析與專家評論

核心洞見

本文的突破並非一個新的神經網路架構，而是對問題的根本性重新定義。多年來，密碼猜測社群（反映了NLP領域的趨勢）一直痴迷於構建更大、更好的密度估計器（GPT部分）。SOPG正確地指出，對於破解這個下游任務而言，解碼策略至關重要。這就好比擁有一張完美的雷區地圖（模型）與知道如何一步不浪費地穿越它（SOPG）之間的區別。這將研究重點從純粹的模型容量轉移到這些模型之上的高效推論演算法——這是其他生成式AI領域更早學到的教訓（例如機器翻譯中的集束搜尋）。

邏輯流程

論點令人信服：1) 密碼攻擊效率由命中率 vs. 猜測次數曲線定義。2) 自迴歸模型提供每個標記的機率。3) 從這個分佈中隨機取樣對於創建有序猜測列表是高度次優的。4) 因此，我們需要一種搜尋演算法，將模型用作預言機，首先明確構建最可能的序列。從認識問題（3）到工程化解決方案（4）的飛躍正是其新穎性所在。與經典電腦科學搜尋演算法（A*、集束搜尋）的聯繫是清晰的，但將其適應於密碼廣闊、結構化的輸出空間並非易事。

優勢與缺陷

優勢： 實證結果令人震驚，幾乎無可置疑地證明了SOPG在標準離線、單一網站評估中的優越性。效率論點在理論上是合理的，並在實踐中得到驗證。這是一種通用方法，適用於任何自迴歸模型，不僅僅是他們的GPT實作。
缺陷與疑問： 評估雖然令人印象深刻，但仍處於實驗室環境。真實世界的攻擊面臨自適應防禦（速率限制、鎖定、誘餌密碼），而本文並未測試SOPG在這些情境下的韌性。搜尋演算法本身每生成一個密碼的計算開銷可能高於單次隨機取樣，儘管整體效率增益是淨正值。此外，還有房間裡的大象——倫理問題：雖然作者將其定位為防禦用途，但這個工具顯著降低了高效攻擊的門檻。該領域必須應對此類進步的雙重用途性質，就像圍繞CycleGAN或大型語言模型等生成式AI模型的討論一樣。

可行建議

對於安全從業者：本文是一個警鐘。密碼策略必須超越僅僅封鎖簡單字典單字。防禦者需要開始對其系統進行針對SOPG類有序攻擊的壓力測試，這現在已成為新的基準。像Have I Been Pwned或zxcvbn這樣的工具需要整合這些先進的生成技術，以進行更真實的強度估計。
對於研究人員：接力棒已經傳遞。下一個前沿不再是模型本身，而是自適應的和查詢高效的生成。我們能否建立能從部分攻擊回饋中學習的模型？我們能否開發出能偵測並干擾有序生成的防禦模型？此外，正如NIST等機構在其數位身份指南中指出的那樣，長遠解決方案在於超越密碼。這項研究同時突顯了密碼破解的巔峰，也強調了其固有的局限性，推動我們邁向無密碼身份驗證。SOPG既是密碼猜測的一步精妙的終局之棋，也是促使其退役的有力論據。