1. 簡介
密碼管理器是現代數位安全的重要工具，讓使用者無需記憶負擔即可維護強度足夠且唯一的密碼。儘管其重要性不言而喻，但由於信任問題，使用者採用率仍然有限。本文探討一個關鍵的信任組成部分：隨機密碼生成演算法。我們提出使用 EasyCrypt 框架進行形式化驗證的參考實作，透過基於博弈的密碼學證明，驗證其功能正確性與安全性質。
2. 現行密碼生成演算法
本研究檢視了 15 款密碼管理器，並聚焦於三個開源實作：Google Chrome (v89.0.4364.1)、Bitwarden (v1.47.1) 和 KeePass (v2.46)。選擇這些是因為它們廣泛使用且原始碼易於取得。
2.1 密碼組成策略
密碼管理器允許使用者定義生成的密碼必須滿足的組成策略。這些策略控制密碼長度、字元類別，以及特定限制，例如每類字元的最小/最大出現次數，以及排除相似字元（例如 'l'、'I'、'O'、'0'）。
策略比較
- Chrome: 長度：1-200，集合：小寫字母、大寫字母、字母、數字、特殊字元
- Bitwarden: 長度：5-128，集合：小寫字母、大寫字母、數字、特殊字元
- KeePass: 長度：1-30000，集合：小寫字母、大寫字母、數字、特殊字元、括號、空格、減號、底線
2.2 隨機密碼生成
所調查的演算法遵循相似的模式：從不同的字元集合中生成隨機字元，直到滿足密碼長度要求，同時遵守最小和最大出現次數的限制。Chrome 的演算法具體步驟為：1) 從定義了最小出現次數的集合中生成字元，2) 從未達到最大次數的集合聯集中生成字元，3) 應用最終的排列。
3. 形式化驗證框架
我們採用 EasyCrypt（一個用於密碼協定的證明輔助工具）來形式化地規範並驗證我們的參考 RPG 實作。驗證遵循基於博弈的密碼學安全性證明方法，建立如均勻分佈和抵抗預測攻擊等性質。
核心洞見
- 形式化驗證提供關於演算法行為的數學確定性
- 基於博弈的證明能真實地模擬攻擊者的能力
- 參考實作可作為密碼管理器開發者的黃金標準
4. 技術實作細節
4.1 數學基礎
密碼生成演算法必須確保在定義的密碼空間中均勻分佈。對於一個允許使用大小為 $|C|$ 的字元集合 $C$，且要求長度為 $L$ 的策略，總密碼空間大小為 $|C|^L$。該演算法必須保證每個可能的密碼 $p \in C^L$ 具有相等的機率：
$$\Pr[\text{Generate}(L, C) = p] = \frac{1}{|C|^L}$$
當加入如最小出現次數等限制時，分佈會變成條件性的，但必須在受限空間內保持均勻。
4.2 安全性質
形式化驗證的性質包括：
- 功能正確性： 輸出滿足所有策略限制
- 均勻分佈： 密碼選擇無偏差
- 抵抗預測： 先前的輸出不會洩漏未來的輸出
- 熵值保持： 維持密碼學隨機性
5. 實驗結果
形式化驗證的實作與三個被研究的密碼管理器進行了測試。主要發現：
- 所有商業實作在邊緣案例中均顯示出輕微的統計偏差
- KeePass 展現了最靈活的策略系統，但其複雜性帶來了驗證挑戰
- Bitwarden 的實作最接近理想的均勻分佈
- Chrome 的演算法在關注點分離方面最為清晰，便於驗證
統計分佈分析
測試涉及為每種配置生成 1,000,000 個密碼，並應用 χ² 檢定來驗證均勻性。經過驗證的實作通過了所有統計檢定 (p > 0.05)，而商業實作在特定的策略配置下顯示 p 值低至 0.001，表明存在可檢測的偏差。
6. 分析框架範例
核心洞見： 本文的根本突破不僅僅是另一個密碼生成器，而是建立了一種驗證方法論，將安全性從經驗性主張轉變為數學證明。這將典範從「我們認為它是安全的」轉變為「我們可以證明它是安全的」。
邏輯流程： 本研究遵循清晰的三階段論證：1) 透過使用者研究，將信任識別為採用的瓶頸；2) 解構現有實作，找出值得驗證的共通模式；3) 建立並證明一個可作為信任錨點的參考實作。這與基礎性著作（如「驗證軟體倡議」）中的方法相呼應，將形式化方法應用於實際的安全問題。
優勢與缺陷： 優勢在於在正確的抽象層次上處理驗證問題——聚焦於生成演算法而非整個密碼管理器。然而，本文的侷限在於孤立地處理生成器。正如 NIST 的《數位身份指南》所指出的，密碼安全取決於整個生態系統：儲存、傳輸和 UI/UX。如果密碼透過旁路攻擊或不良的 UI 設計而洩漏，那麼形式化驗證的生成器也毫無用處。
可執行的洞見： 密碼管理器開發者應該：1) 採用此參考實作為起點；2) 將驗證擴展到密碼儲存和自動填入元件；3) 委託第三方使用此方法論進行稽核。此方法可擴展到其他安全關鍵的生成器（密碼學金鑰、工作階段令牌），遵循由經過驗證的密碼學函式庫（如 HACL*）建立的模式。
這 300-600 字的分析展示了形式化驗證如何解決密碼管理器中的核心信任赤字。透過提供安全性質的數學證明，這項工作超越了啟發式安全，邁向可證明的保證。此方法論的真正價值在於其可轉移性——相同的技術可以驗證其他安全元件，建立一條從密碼生成、儲存到使用的信任鏈。這與更廣泛的驗證系統趨勢相符，正如在seL4 微核心驗證等專案中所見，證明形式化方法對於現實世界的安全系統正變得實用。
7. 未來應用與方向
此處建立的形式化驗證方法論有幾個有前景的應用：
- 標準化： 可作為密碼生成器認證標準的基礎
- 瀏覽器整合： 在所有主流瀏覽器中內建經過驗證的密碼生成器
- 物聯網安全： 用於嵌入式裝置的輕量級驗證生成器
- 無密碼認證： FIDO2/WebAuthn 令牌生成器的驗證
- 教育工具： 透過實際安全範例教授形式化方法
未來研究應聚焦於：1) 將驗證擴展到密碼策略評估；2) 與硬體安全模組整合；3) 為密碼管理器開發者開發自動化驗證工具；4) 研究形式化驗證系統對可用性的影響。
8. 參考文獻
- Grilo, M., Ferreira, J. F., & Almeida, J. B. (2021). Towards Formal Verification of Password Generation Algorithms used in Password Managers. arXiv:2106.03626
- EasyCrypt: Computer-Aided Cryptographic Proofs. (2021). https://easycrypt.info/
- NIST. (2020). Digital Identity Guidelines: Authentication and Lifecycle Management. SP 800-63B
- Klein, G., et al. (2009). seL4: Formal verification of an OS kernel. SOSP '09
- Zinzindohoué, J. K., et al. (2017). HACL*: A Verified Modern Cryptographic Library. CCS '17
- Bonneau, J., et al. (2012). The quest to replace passwords: A framework for comparative evaluation of web authentication schemes. IEEE S&P
- Ur, B., et al. (2016). "I added '!' at the end to make it secure": Observing password creation in the lab. SOUPS '16