1. 簡介
密碼管理器是資安專家推薦的關鍵工具，用以緩解與密碼驗證相關的弱點，例如弱密碼和密碼重複使用。它們透過處理儲存與生成，讓使用者得以使用強大且唯一的密碼。然而，使用者對這些應用程式缺乏信任，阻礙了其採用。本文指出隨機密碼生成功能是影響信任與使用率的關鍵因素。為解決此問題，作者提議為RPG演算法開發並進行形式化驗證的參考實作，旨在提供一個密碼學上健全且可證明安全的基礎，讓使用者和開發者能夠信任。
核心問題在於，雖然密碼管理器提倡安全性，但其內部機制——特別是密碼生成——通常是個不透明的黑盒子。缺乏可驗證的保證，使用者仍持懷疑態度。解決途徑涉及使用形式化方法，特別是EasyCrypt框架，以數學方式規格化演算法，並針對明確定義的敵手模型證明其正確性與安全性質。
2. 現行密碼生成演算法
本文調查了15款密碼管理器，重點分析三個開源且廣泛使用的範例：Google Chrome內建管理器、Bitwarden和KeePass。分析揭示了它們在生成隨機密碼方法上的常見模式與關鍵差異。
2.1 密碼組成原則
所有研究的密碼管理器都允許使用者定義限制生成密碼結構的原則。這些原則通常包括：
- 密碼長度：範圍從1-200（Chrome）到極端的1-30000（KeePass）。
- 字元集：標準集合包括小寫字母、大寫字母、數字和特殊字元。KeePass提供更細緻的選項，包含括號、空格、減號和底線的獨立集合。
- 每組最小/最大數量：Chrome和Bitwarden允許定義每個字元集的最小出現次數。KeePass則無此功能。
- 排除易混淆字元：三者皆允許排除視覺上相似的字元（例如 'l'、'1'、'O'、'0'），以減少使用者錯誤。
- 自訂集合與重複字元：KeePass獨特地允許定義要包含或排除的自訂字元集，並能從生成的密碼中移除重複字元。
原則選項的差異凸顯了標準化的缺乏，這使得建立一個通用、可驗證的模型變得複雜。
2.2 隨機密碼生成
通用演算法涉及從允許的集合中隨機選取字元，同時遵守原則限制（長度、最小值、最大值）。本文詳細描述了Chrome的演算法：
- 首先，為每個定義了最小出現次數的集合生成字元。
- 接著，從所有尚未達到最大允許出現次數的集合聯集中隨機選取，生成剩餘字元。
- 最後，對生成的字元字串進行隨機排列。
這個過程雖然看似直接，但必須謹慎實作，以確保真正的隨機性以及在整個原則限制的密碼空間中的無偏分佈。選擇或排列中的細微偏差可能會削弱最終密碼的強度。
3. 提議的形式化驗證實作
本文的核心貢獻是提議建立一個參考RPG實作，並附有其性質的機器檢查證明。
3.1 形式化規格
第一步是在EasyCrypt中為密碼生成演算法建立精確的數學規格。此規格定義了：
- 輸入：原則參數（長度 $L$、字元集 $S_1, S_2, ..., S_n$、最小值 $min_i$、最大值 $max_i$）。
- 輸出：長度為 $L$ 的密碼字串 $p$。
- 前置條件：原則必須一致（例如，$\sum min_i \leq L$）。
- 後置條件（功能正確性）：輸出 $p$ 必須滿足所有原則限制。形式化表示為 $\forall i, min_i \leq count(p, S_i) \leq max_i$，其中 $count$ 計算 $p$ 中來自集合 $S_i$ 的字元數量。
3.2 安全性質與證明
除了正確性，實作還必須被證明是安全的。本文採用了基於遊戲的密碼學證明方法。關鍵的安全性質是從滿足給定原則的所有密碼集合中進行均勻隨機取樣。
這被形式化為一個安全性遊戲，其中敵手試圖區分由真實演算法生成的密碼與從有效密碼空間中均勻取樣的密碼。證明顯示，沒有任何高效的敵手能以顯著優於隨機猜測（1/2）的機率贏得此遊戲。這確保了演算法不會引入可預測的模式或偏差。
證明將利用EasyCrypt的函式庫來推理機率計算和隨機取樣。
4. 實驗結果與分析
雖然提供的PDF是初步工作且未包含完整的實驗結果，但它為此鋪墊了基礎。提議的驗證將產生以下具體成果：
- 驗證報告：來自EasyCrypt的機器生成證明證書，確認演算法的程式碼符合其形式化規格與安全性定理。
- 比較分析：可將經過驗證的演算法與Chrome、Bitwarden和KeePass中的現有實作進行比較。測試將涉及在相同原則下生成大量密碼（例如100萬個），並進行統計分佈分析。
- 度量標準：一個關鍵度量標準是生成密碼的經驗分佈與原則定義空間上的理論均勻分佈之間的Kullback-Leibler（KL）散度或卡方檢定。一個經過形式化驗證的演算法應顯示出統計上與零無異的散度，而未經驗證的實作可能會揭示細微的偏差。
- 圖表描述：一個長條圖，比較每個密碼管理器演算法生成的密碼分佈的熵（以位元為單位）與給定原則的理論最大熵。經過驗證的參考實作的長條應與「理論最大值」的長條完美對齊。
5. 技術細節與數學框架
形式化驗證依賴於精確的數學建模。讓我們定義核心概念：
密碼空間：給定一個長度為 $L$、允許字元集為 $S_1, ..., S_n$ 的原則，合規密碼的總集合 $\mathcal{P}$ 是笛卡爾積 $\mathcal{C}^L$ 的一個子集，其中 $\mathcal{C} = \bigcup_{i=1}^n S_i$。$\mathcal{P}$ 的大小受到最小和最大規則的限制。
均勻分佈：安全性目標是讓演算法 $\mathcal{A}$ 實作一個與真正的均勻取樣器 $\mathcal{U}_{\mathcal{P}}$ 無法區分的函數。對於任何密碼 $p \in \mathcal{P}$，機率應為： $$\Pr[\mathcal{A}(policy) = p] = \frac{1}{|\mathcal{P}|}$$ 其中 $|\mathcal{P}|$ 是有效密碼集合的基數。
基於遊戲的證明概要： 安全性被框架為一個「真實或隨機」遊戲。
- 挑戰者拋擲一個秘密硬幣 $b \xleftarrow{\$} \{0,1\}$。
- 敵手 $\mathcal{D}$ 可以查詢挑戰者密碼原則。
- 如果 $b=0$（真實），挑戰者執行實際演算法 $\mathcal{A}$。
- 如果 $b=1$（隨機），挑戰者使用 $\mathcal{U}_{\mathcal{P}}$ 從 $\mathcal{P}$ 中均勻取樣。
- $\mathcal{D}$ 輸出一個猜測 $b'$。
6. 分析框架：非程式碼範例
由於PDF未包含實際程式碼，以下是一個用於評估RPG演算法的概念性分析框架，以檢查清單形式呈現：
案例：評估「PM-X」的密碼生成器。
步驟 1 - 原則解構：將PM-X的使用者介面選項（核取方塊、滑桿）映射到形式化原則元組：(L=12, Sets={小寫, 大寫, 數字}, min_小寫=1, min_大寫=1, min_數字=1, exclude={'l','O','0'})。
步驟 2 - 演算法透明度：演算法的步驟（如Chrome的三步流程）能否從文件或原始碼中清晰描述？若否，則未通過透明度測試。
步驟 3 - 熵計算：計算該原則的理論最大熵：$log_2(|\mathcal{P}|)$ 位元。對於上述原則，$|\mathcal{P}|$ 是來自一個字母表（例如排除後剩70個字元）且滿足最小限制的12字元字串數量。這是安全性基準。
步驟 4 - 統計檢定設計：設計一個實驗來生成 $N$ 個密碼並檢定均勻分佈。使用卡方檢定於整個密碼空間或巧妙取樣的子集。
步驟 5 - 偏差偵測：尋找特定偏差：某些字元位置是否較不隨機？滿足最小值的演算法是否降低了剩餘位置的隨機性？
此框架提供了一個結構化、無需程式碼的方法來批判性地檢視任何RPG，與本文從模糊性轉向可驗證分析的目標一致。
7. 未來應用與研究方向
這項工作開啟了幾個有前景的方向：
- 標準化：一個經過形式化驗證的RPG可以成為一個標準元件（如函式庫），整合到整個產業的密碼管理器中，類似於libsodium提供經過驗證的密碼學原語。
- 瀏覽器與作業系統整合：作業系統（例如Windows Hello、macOS Keychain）和瀏覽器可以為其內建的密碼建議功能採用經過驗證的生成器，為所有使用者提高基礎安全性。
- 硬體支援的生成：經過驗證的演算法可以在安全硬體元件（TPM、安全隔離區）中實作，以實現物理和邏輯上都安全的生成。
- 後量子考量：未來研究可以探索能產生抵抗經典和量子暴力破解攻擊的密碼生成原則，並使形式化證明適應新的威脅模型。
- 可用性-安全性權衡驗證：擴展形式化模型以證明生成密碼的可記憶性或易輸入性等性質，彌合純密碼學與人機互動之間的差距。
- 自動化原則分析：開發利用形式化模型的工具，自動分析使用者定義的原則，並報告其有效熵以及任何削弱密碼空間的非預期限制。
8. 參考文獻
- Grilo, M., Ferreira, J. F., & Almeida, J. B. (2021). Towards Formal Verification of Password Generation Algorithms used in Password Managers. arXiv preprint arXiv:2106.03626.
- Bellare, M., & Rogaway, P. (2006). The security of triple encryption and a framework for code-based game-playing proofs. In Advances in Cryptology-EUROCRYPT 2006 (pp. 409-426). Springer.
- Barthe, G., Dupressoir, F., Grégoire, B., Kunz, C., Schmidt, B., & Strub, P. Y. (2016). EasyCrypt: A computer-aided cryptography toolset. Lecture Notes in Computer Science, 9573, 3-32.
- National Institute of Standards and Technology (NIST). (2020). Digital Identity Guidelines: Authentication and Lifecycle Management (SP 800-63B).
- Shannon, C. E. (1948). A mathematical theory of communication. The Bell System Technical Journal, 27(3), 379-423. (關於熵與資訊理論的基礎工作).
- Florêncio, D., Herley, C., & Van Oorschot, P. C. (2014). An administrator's guide to internet password research. In 28th Large Installation System Administration Conference (LISA14) (pp. 44-61).
9. 分析師觀點：核心見解與評論
核心見解
本文正確地指出了網路安全供應鏈中一個關鍵但常被忽視的漏洞：密碼管理器核心未經驗證的隨機性。真正的見解不在於密碼生成很複雜——而在於一個基礎安全工具的信任模型是失效的。使用者被要求信任一個存放其數位鑰匙的黑盒子。作者提議將形式化驗證（一種更常見於硬體設計和關鍵航空軟體（如DO-178C認證系統）的技術）應用於消費級安全原語，既雄心勃勃又十分必要。這是試圖將SRI International或INRIA研究實驗室的嚴謹性，移植到通常較為草率的應用程式安全世界。
邏輯流程
論證從一個公認的問題（使用者對密碼管理器不信任）邏輯性地流向一個具體的技術根本原因（不透明的密碼生成），再到一個具體、高保證的解決途徑（形式化規格與證明）。對現有密碼管理器的調查不僅是學術性的；它有效地展示了實作上的巨大不一致性，從而為一個標準化、經過驗證的參考實作提供了論據。轉向EasyCrypt和基於遊戲的證明是恰當的，因為這個由形式化密碼學領先機構開發的框架，正是為此類問題設計的。其流程反映了驗證密碼學開創性工作（如HMAC-DRBG生成器的驗證）的方法論。
優點與缺陷
優點：本文最大的優點是聚焦於一個高影響力、可處理的問題。它並未試圖驗證整個密碼管理器；而是針對密碼學核心。使用開源密碼管理器進行分析，使研究立足於現實。選擇基於遊戲的證明是現代密碼學分析的行業標準。
關鍵缺陷與不足：本文目前呈現的內容，更像是一個引人注目的提案，而非一項已完成的研究。最明顯的遺漏是實際的EasyCrypt程式碼和已完成的證明。沒有這些，其主張仍停留在理論層面。此外，它低估了原則複雜性問題。形式化規格必須處理使用者定義原則的每一個邊緣案例（例如，衝突的最小/最大值、自訂字元集）。這可能導致規格與實作一樣複雜，這是形式化方法中已知的挑戰。它也迴避了現實世界的熵來源——演算法的好壞取決於系統的CSPRNG（例如/dev/urandom）。一個經過驗證的演算法若輸入弱隨機性，結果仍然是弱的。若能明確基於完美熵源假設來界定其保證範圍，本文會更有說服力。
可行建議
1. 對密碼管理器開發者：立即開源您的密碼生成程式碼，並接受第三方稽核。開始對您的演算法進行建模（即使是非正式的），以識別潛在偏差。考慮整合此研究旨在產生的那種經過驗證的函式庫。
2. 對安全稽核員：將「RPG演算法分析」加入您標準的密碼管理器稽核檢查清單。使用第6節概述的統計框架來測試客戶端輸出的分佈偏差。
3. 對標準制定機構（例如NIST、FIDO聯盟）：發起工作小組，為密碼生成器定義標準API和一組安全要求，為認證實作鋪路。這類似於密碼學演算法的成功標準化過程。
4. 對研究人員：這項工作是完美的起點。下一步是完成EasyCrypt實作與證明。後續關鍵階段是開發一個測試框架，能夠使用經過驗證的程式碼，對Chrome、Bitwarden等真實世界程式碼進行模糊測試，以發現具體的差異和漏洞，從理論走向實際影響。
總而言之，本文將必要的光線照進了我們安全基礎設施的一個黑暗角落。雖然不完整，但其方向是正確的。密碼管理器產業已經超越了「只管信任我們」的階段；是時候迎接可驗證的、數學化的信任了。這項研究的成功，可能為我們如何建構所有客戶端安全軟體樹立新的典範。