1. 引言
密碼管理器（PM）係生成同儲存強隨機密碼嘅重要工具，用嚟解決密碼認證嘅漏洞。不過，用戶信任仍然係普及嘅障礙。呢篇論文提出一個用EasyCrypt證明環境嘅正式驗證參考實作，用於隨機密碼生成器（RPG），重點係功能正確性同安全特性。
2. 目錄
3. 現有密碼生成演算法
作者研究咗15個PM，重點係三個廣泛使用嘅開源PM：Google Chrome（v89.0.4364.1）、Bitwarden（v1.47.1）同KeePass（v2.46）。揀呢啲係因為佢哋受歡迎同源碼容易攞到。
3.1 密碼組成政策
PM容許用戶定義密碼組成政策，包括長度、字符類別（小寫字母、大寫字母、數字、特殊字符）、每組嘅最少/最多出現次數、排除相似字符，同自訂字符集。表1總結咗Chrome、Bitwarden同KeePass嘅政策。
3.2 隨機密碼生成
核心演算法係從定義嘅字符集中隨機生成字符，直到達到密碼長度，同時遵守最少/最多出現次數限制。Chrome嘅演算法首先從有最少出現次數嘅字符集生成字符，然後從所有字符集嘅聯集中生成，但唔超過最多次數，最後對字串進行排列。
4. 正式驗證框架
4.1 EasyCrypt概述
EasyCrypt係一個用遊戲為基礎嘅方法進行密碼安全證明嘅證明助手。佢容許指定參考實作，並對功能正確性同安全特性進行正式驗證。
4.2 安全特性
正式化包括隨機均勻性、抵抗側通道攻擊，同遵守政策限制等特性。遊戲為基礎嘅方法模擬對手能力，並證明與理想隨機生成嘅不可區分性。
5. 技術細節同數學公式
RPG嘅安全性用計算不可區分性嘅概念嚟建模。設$\mathcal{G}$為密碼生成演算法，$\mathcal{U}$為均勻隨機生成器。對手$\mathcal{A}$嘅優勢定義為：
$$\text{Adv}_{\mathcal{G}}(\mathcal{A}) = |\Pr[\mathcal{A}^{\mathcal{G}} = 1] - \Pr[\mathcal{A}^{\mathcal{U}} = 1]|$$
目標係證明對於所有概率多項式時間對手，$\text{Adv}_{\mathcal{G}}(\mathcal{A})$係可忽略嘅。EasyCrypt嘅正式證明涉及構建一系列遊戲，每個遊戲同前一個略有不同，並限制對手成功概率嘅差異。
6. 實驗結果同圖表
正式驗證係喺RPG嘅參考實作上進行。證明包含大約500行EasyCrypt代碼，涵蓋功能正確性（生成嘅密碼符合政策）同安全性（輸出同均勻隨機不可區分）。喺標準筆記型電腦上，證明時間少於10秒。以下係遊戲為基礎嘅證明結構圖：
圖1：遊戲為基礎嘅證明結構：遊戲0（真實演算法）→ 遊戲1（用隨機替換PRG）→ 遊戲2（用均勻隨機替換字符選擇）→ 遊戲3（理想）。每個過渡都由一個密碼假設或歸約證明。
7. 分析框架示例
案例研究：驗證KeePass密碼生成
考慮一個政策要求12個字符嘅密碼，至少包含2個小寫字母、2個大寫字母、2個數字同2個特殊字符。EasyCrypt嘅正式規範定義：
- 前置條件：政策參數（長度、每組最少/最多次數、排除字符）。
- 後置條件：生成嘅密碼滿足所有限制，並且喺有效密碼集上係均勻隨機嘅。
- 安全性：冇對手可以區分輸出同相同長度嘅真正隨機字串。
證明通過對密碼長度進行歸納，顯示每個字符都係從適當嘅字符集中均勻抽出，而最終嘅排列確保冇位置偏差。
8. 原始分析
核心見解：呢篇論文通過將正式驗證應用於密碼生成演算法，解決咗密碼管理器信任嘅關鍵缺口。雖然好多PM聲稱安全，但好少提供數學保證。使用EasyCrypt係向可證明安全嘅密碼生成邁出重要一步。
邏輯流程：作者首先調查現有演算法，識別常見模式同潛在缺陷。然後佢哋提出一個參考實作，並使用遊戲為基礎嘅證明正式驗證其正確性同安全性。流程係合乎邏輯嘅：問題識別 → 解決方案設計 → 正式驗證 → 影響。
優點同缺點：優點在於嚴謹嘅正式方法，提供咗超越典型測試嘅保證。不過，論文集中喺單一參考實作，而唔係驗證Chrome、Bitwarden或KeePass嘅實際代碼。呢點限制咗實際影響。此外，證明假設一個可信嘅隨機數生成器，呢個喺所有部署場景中未必成立。正如Bellare同Rogaway（1993）喺佢哋關於隨機預言機嘅開創性工作中指出，理論模型同實際實作之間嘅差距仍然係一個挑戰。
可行見解：對於PM開發者，採用正式驗證工具好似EasyCrypt可以增強信任並減少漏洞。對於研究人員，將呢項工作擴展到驗證實際PM源碼（例如通過反編譯或符號執行）會好有價值。用戶應該要求PM供應商提供透明度同正式保證。呢種方法符合安全領域正式方法嘅更廣泛趨勢，正如美國國家標準與技術研究院（NIST）喺其密碼模塊驗證指南中所倡導嘅。
9. 未來應用同展望
正式驗證框架可以擴展到其他PM功能，例如密碼儲存同自動填寫。與持續集成管道整合可以實現密碼生成代碼嘅自動驗證。未來工作亦可能探索側通道抵抗同量子安全隨機生成。隨住密碼管理器變得無處不在，正式保證對於建立用戶信任同滿足監管要求（例如GDPR、eIDAS）將會至關重要。
10. 參考文獻
- Bellare, M., & Rogaway, P. (1993). Random oracles are practical: A paradigm for designing efficient protocols. Proceedings of the 1st ACM Conference on Computer and Communications Security, 62-73.
- Barthe, G., et al. (2011). EasyCrypt: A tutorial. Foundations of Security Analysis and Design VII, 146-204.
- NIST. (2020). Cryptographic Module Validation Program (CMVP). National Institute of Standards and Technology.
- Shoup, V. (2004). Sequences of games: A tool for taming complexity in security proofs. IACR Cryptology ePrint Archive, 2004/332.
- Grilo, M., Ferreira, J. F., & Almeida, J. B. (2021). Towards Formal Verification of Password Generation Algorithms used in Password Managers. arXiv:2106.03626v2.