1. 簡介
本文介紹 PESrank，這是一種新穎的密碼強度估算器，旨在透過計算密碼在最佳可能性順序中的排序，精確模擬強大密碼破解工具的行為。它解決了對實用、具線上能力估算器的迫切需求，超越了像 LUDS（小寫、大寫、數字、符號）計數這類過於簡化的啟發式方法。
1.1. 背景
儘管已知存在漏洞，文字密碼仍是主流的身份驗證方法。使用者常選擇脆弱、可預測的密碼，使系統容易遭受猜測攻擊。精確的強度定義為攻擊者猜中它所需的嘗試次數。先前基於破解工具的估算器使用馬可夫模型、PCFG 和神經網路，但常面臨訓練時間過長或缺乏即時能力的問題。
1.2. 貢獻
PESrank 的核心創新在於將密碼排序估計重新框架於來自旁路密碼分析的機率框架內。它將密碼視為 d 維搜尋空間中的點（例如，基礎字詞、後綴、大小寫模式），並獨立學習每個維度的機率分佈。這使得無需枚舉即可進行快速、線上的排序估計，實現高效的模型個人化，並提供可解釋的回饋。
2. PESrank 方法論
PESrank 將密碼分解為可解釋的維度，將強度估計問題轉化為多維度排序估計任務。
2.1. 多維度密碼表示法
像 "P@ssw0rd2024!" 這樣的密碼，可能被表示為以下維度：基礎字詞（"password"）、L33t 替換模式、後綴（"2024"）以及特殊字元添加。每個維度都有一個從訓練資料中學習到的關聯機率質量函數。
2.2. 排序估計框架
PESrank 並非枚舉所有可能的密碼，而是透過彙總在維度定義的組合空間中，所有比特定密碼 p 可能性更高的密碼之機率，來計算該密碼的排序 R(p)。這類似於在旁路分析中估計秘密金鑰的排序。
3. 技術實作與數學模型
3.1. 機率框架
令密碼 p 表示為跨越 d 個獨立維度的向量 (x1, x2, ..., xd)。密碼 p 的機率近似為： $$P(p) \approx \prod_{i=1}^{d} P_i(x_i)$$ 其中 Pi(xi) 是維度 i 中元件 xi 的邊際機率。排序 R(p) 是所有滿足 P(q) > P(p) 的密碼 q 之機率總和。
3.2. 高效排序計算
PESrank 使用高效演算法來計算此總和而無需枚舉。對於每個維度，它維護按機率排序的元件列表。排序計算涉及遍歷這些列表並彙總部分乘積，即使在模型訓練於 9.05 億個密碼的情況下，也能達到次秒級的效能。
4. 實驗結果與評估
4.1. 效能指標
本文報告了廣泛的評估。關鍵結果包括：
- 速度： 線上查詢的回應時間「遠低於 1 秒」。
- 準確度： 排序估計的上限與下限之間差距可達 1 位元，顯示高精確度。
- 訓練時間： 比先前方法（可能需要數天）「大幅縮短」。
圖表描述（概念性）： 一個長條圖比較 PESrank 的訓練時間（數小時量級）與神經網路模型（數天量級）和 PCFG 模型（數十小時量級）。疊加的折線圖顯示，隨著模型規模（訓練集中的密碼數量）從 1000 萬增加到 10 億，PESrank 的查詢延遲保持穩定在 1 秒以下。
4.2. 與現有方法比較
PESrank 與啟發式（LUDS）、馬可夫和基於 PCFG 的估算器進行了比較。它展現出與實際破解工具（如 Hashcat）產生的破解順序更優的相關性，驗證了其「基於破解工具」的設計目標。其可解釋性功能，能提供低排序的原因（例如，「基礎字詞位於前 100 個常見清單中」），是相對於黑箱神經網路的明顯優勢。
5. 關鍵見解與分析框架
核心見解
PESrank 不僅僅是另一個漸進式改進；它是一種典範轉移。它成功將來自旁路密碼分析（一個專注於量化部分金鑰洩漏的領域）中嚴謹、量化的排序估計技術，移植到人類選擇密碼的混亂世界中。這種跨領域融合是其天才之處。雖然像 Google 2016 年神經網路這樣的模型達到了高準確度，但它們不透明且訓練緩慢。PESrank 提供了可媲美的破解建模保真度，同時具備精心設計的機率系統的透明度與速度。
邏輯流程
其邏輯優雅地體現了化約主義：1) 將密碼解構為正交、人類可解釋的維度（這一步讓人想起 Weir 等人的 PCFG，但更細緻）。2) 假設維度獨立性以使機率空間易於處理——這是一個結果驗證了其必要性的簡化。3) 應用能繞過枚舉組合爆炸的排序估計演算法。從資料（密碼外洩）到模型（各維度 PMF）再到可執行的輸出（排序與解釋）的流程，既清晰又計算高效。
優勢與缺陷
優勢： 速度（線上使用）、可解釋性 和 可調整性 這三者的結合，對於實際部署極具吸引力。能夠「在幾分之一秒內」為使用者個人化模型（例如，降低包含其姓名的密碼之排序），是企業安全的一個殺手級功能。其訓練效率也降低了使用新鮮、大規模密碼資料集的門檻。
缺陷： 維度獨立性的核心假設是其阿基里斯腱。實際上，使用者在不同維度上的選擇是相關的（例如，某些大小寫模式更可能與某些基礎字詞一起出現）。本文承認這一點，但聲稱近似仍然有效。此外，與所有基於外洩資料的模型一樣，它本質上是向後看的，可能低估了尚未在外洩資料中出現的新穎密碼建構策略的強度。
可執行的見解
對於 CISOs 和產品安全團隊：在您的使用者註冊流程中試行 PESrank 或其概念上的後繼者。其可解釋性可以將密碼政策從令人沮喪的障礙轉變為教學時刻，可能提高合規性。對於研究人員：本文開闢了新的途徑。能否透過更複雜但仍高效的機率圖形模型來放寬獨立性假設？此框架能否與「模糊」匹配整合以處理拼寫錯誤或微小變體？整合即時個人化資料（公司目錄、外洩憑證）是邁向真正自適應的企業級估算器的下一步。
6. 應用展望與未來方向
主動式密碼檢查： 整合到網站和應用程式的註冊頁面中，作為即時顧問，提供立即、可解釋的回饋。
自適應身份驗證系統： 動態風險評分，其中密碼的排序會影響是否需要額外的驗證因素（例如，低排序密碼觸發強制性雙重驗證）。
個人化安全政策： 企業系統可以為每位員工維護個人化模型，自動降低包含員工特定資訊（姓名、ID、部門）的密碼之排序。
未來研究： 將模型擴展以處理密碼短語，探索深度學習混合模型以捕捉細微的維度相關性，並為密碼強度估算器開發標準化基準，類似於 NIST 密碼指南，但用於演算法評估。
7. 參考文獻
- David, L., & Wool, A. (2020). Online Password Guessability via Multi-Dimensional Rank Estimation. arXiv preprint arXiv:1912.02551.
- Weir, M., Aggarwal, S., Medeiros, B., & Glodek, B. (2009). Password cracking using probabilistic context-free grammars. In 2009 30th IEEE Symposium on Security and Privacy.
- Melicher, W., Ur, B., Segreti, S. M., Komanduri, S., Bauer, L., Christin, N., & Cranor, L. F. (2016). Fast, lean, and accurate: Modeling password guessability using neural networks. In 25th USENIX Security Symposium.
- NIST. (2017). Digital Identity Guidelines: Authentication and Lifecycle Management. NIST Special Publication 800-63B.
- Bonneau, J. (2012). The science of guessing: analyzing an anonymized corpus of 70 million passwords. In 2012 IEEE Symposium on Security and Privacy.