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散度或卡方檢驗。一個經過形式化驗證嘅算法應該顯示出統計上與零無異嘅散度，而未經驗證嘅實現可能會揭示細微偏差。
- 圖表描述： 一個柱狀圖，比較每個密碼管理器算法生成密碼分佈嘅熵（以位為單位）與給定策略嘅理論最大熵。經過驗證嘅參考實現嘅柱應該與「理論最大值」柱完美對齊。
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步過程）能否從文檔或源代碼中清晰描述？如果唔可以，佢就未能通過透明度測試。
步驟 3 - 熵計算： 計算策略嘅理論最大熵：$log_2(|\mathcal{P}|)$ 位。對於上述策略，$|\mathcal{P}|$ 係來自一個字母表（例如，排除後有70個字符）並滿足最少限制嘅12字符字串數量。呢個就係安全基準。
步驟 4 - 統計測試設計： 設計一個實驗來生成 $N$ 個密碼並測試均勻分佈。使用卡方檢驗喺整個密碼空間或一個巧妙抽樣嘅子集上進行。
步驟 5 - 偏差檢測： 尋找特定偏差：某些字符位置係咪較少隨機？用於滿足最少次數嘅算法會唔會減少剩餘位置嘅隨機性？
呢個框架提供咗一個結構化、無需代碼嘅方法論，用於批判性審查任何RPG，與本文從模糊性轉向可驗證分析嘅目標一致。
7. 未來應用與研究方向
呢項工作開闢咗幾個有前景嘅方向：
- 標準化： 一個經過形式化驗證嘅RPG可以成為一個標準組件（好似一個庫），整合到整個行業嘅密碼管理器中，類似於libsodium提供經過驗證嘅密碼學原語。
- 瀏覽器同操作系統整合： 操作系統（例如Windows Hello、macOS鑰匙串）同瀏覽器可以採用經過驗證嘅生成器用於其內置嘅密碼建議功能，為所有用戶提高基礎安全水平。
- 硬件支援生成： 經過驗證嘅算法可以喺安全硬件元素（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. 分析師觀點：核心洞察與評論
核心洞察
本文正確地指出咗網絡安全供應鏈中一個關鍵但常被忽視嘅漏洞：密碼管理器核心嘅未經驗證隨機性。真正嘅洞察並唔係密碼生成複雜——而係一個基礎安全工具嘅信任模型已經失效。用戶被要求信任一個黑盒來保管佢哋嘅數字鑰匙。作者提議將形式化驗證（一種更常見於硬件設計同關鍵航空軟件嘅技術）應用於消費者安全原語，既雄心勃勃又必要。呢係嘗試將SRI International或INRIA研究實驗室嘅嚴謹性移植到通常馬虎嘅應用程式安全世界。
邏輯流程
論證從一個公認嘅問題（用戶對密碼管理器嘅不信任）邏輯地流向一個具體嘅技術根本原因（不透明嘅密碼生成），然後再到一個具體、高保證嘅解決途徑（形式化規格同證明）。對現有密碼管理器嘅調查唔只係學術性嘅；佢有效地展示咗實現中嘅巨大不一致性，為一個標準化、經過驗證嘅參考案例提供咗理據。轉向EasyCrypt同基於遊戲嘅證明係合適嘅，因為呢個由形式化密碼學領先機構開發嘅框架，正係為呢類問題而設計。呢個流程反映咗經過驗證嘅密碼學開創性工作（例如HMAC-DRBG生成器嘅驗證）嘅方法論。
優點與缺陷
優點： 本文最大嘅優點係佢聚焦於一個高影響力、可處理嘅問題。佢並唔嘗試驗證整個密碼管理器；而係針對密碼學核心。使用開源密碼管理器進行分析令研究紮根於現實。選擇基於遊戲嘅證明係現代密碼分析嘅行業標準。
關鍵缺陷與空白： 正如所呈現嘅，本文更多係一個引人注目嘅提議，而非已完成嘅研究。最明顯嘅遺漏係實際嘅EasyCrypt代碼同已完成嘅證明。冇咗呢啲，聲稱仍然停留喺理論層面。此外，佢低估咗策略複雜性問題。形式化規格必須處理用戶定義策略嘅每個邊緣情況（例如，衝突嘅最少/最多、自定義字符集）。呢個可能導致規格同實現一樣複雜，呢係形式化方法中已知嘅挑戰。佢亦迴避咗現實世界熵源——算法嘅好壞取決於系統嘅CSPRNG（例如/dev/urandom）。一個經過驗證嘅算法如果輸入弱隨機性，仍然係弱嘅。如果本文明確基於完美熵源假設來界定其保證，將會更強有力。
可行建議
1. 對於密碼管理器開發者： 立即開源你哋嘅密碼生成代碼並接受第三方審計。開始對你哋嘅算法進行建模，即使係非正式嘅，以識別潛在偏差。考慮整合一個經過驗證嘅庫，好似呢項研究旨在產生嘅嗰種。
2. 對於安全審計員： 將「RPG算法分析」加入你哋嘅標準密碼管理器審計清單。使用第6節概述嘅統計框架來測試客戶端輸出中嘅分佈偏差。
3. 對於標準機構（例如NIST、FIDO聯盟）： 啟動一個工作組來定義密碼生成器嘅標準API同安全要求集，為經過認證嘅實現鋪路。呢個類似於密碼算法成功嘅標準化。
4. 對於研究人員： 呢項工作係一個完美嘅起點。下一步係完成EasyCrypt實現同證明。隨後一個關鍵階段係開發一個測試工具，可以攞經過驗證嘅代碼並對Chrome、Bitwarden等嘅真實代碼進行模糊測試，以發現具體差異同漏洞，從理論走向實際影響。
總而言之，本文為我哋安全基礎設施中一個黑暗角落帶來咗必要嘅光線。雖然未完成，但其方向係正確嘅。密碼管理器行業已經成熟到超越咗「信我啦」嘅階段；係時候迎接可驗證、數學化嘅信任。呢項研究嘅成功可以為我哋如何構建所有客戶端安全軟件樹立一個新嘅先例。