1. 引言
密码管理器是安全专家推荐用于缓解密码认证相关漏洞的关键工具。它们有助于使用高强度、唯一的密码，减轻用户的认知负担。然而，由于对这些应用程序缺乏信任，其广泛采用受到阻碍。本文指出随机密码生成功能是影响用户信任的关键因素。作者认为，一个经过形式化验证、可证明安全的随机密码生成实现对于弥合这种信任鸿沟、促进密码管理器的采用至关重要。本文的核心贡献是提出了这样一个参考实现，并使用EasyCrypt框架提供了功能正确性和安全属性的形式化证明。
2. 当前密码生成算法
本文调查了15款密码管理器，重点分析了三个开源且广泛使用的示例：谷歌Chrome内置管理器、Bitwarden和KeePass。分析揭示了现有实现中的常见模式和关键缺陷。
2.1 密码构成策略
密码管理器允许用户定义约束生成密码的策略。这些策略规定了长度、允许的字符集（例如小写字母、大写字母、数字、特殊字符）以及每个字符集的最小/最大出现次数。本文提供了一个详细的对比表（PDF中的表1），展示了所研究的三个密码管理器的策略选项。关键观察包括：最大长度各不相同（KeePass中可达30,000）、“特殊字符”的定义不同、以及为避免视觉混淆而对“相似字符”（如‘l’、‘1’、‘O’、‘0’）的处理方式不一致。KeePass提供了最精细的控制，允许自定义包含/排除集以及重复字符移除。
2.2 随机密码生成
所调查的算法通常遵循一个两阶段过程：1) 生成随机字符以满足每个指定字符集的最小出现次数要求。2) 使用任何尚未达到其最大出现次数限制的字符集中的随机字符填充剩余的密码长度。最后，对字符序列进行随机排列。本文暗示，虽然这个逻辑是直截了当的，但其实现——特别是随机源和复杂约束的执行——很少被形式化地规定或验证，这为可能导致安全性减弱的细微错误留下了空间。
3. 形式化验证方法
作者主张使用形式化方法来消除实现错误。他们选择了EasyCrypt，这是一个用于构建和验证基于游戏的密码学证明的框架。该方法包括：
- 规约： 形式化定义随机密码生成器的功能需求（输入策略 -> 输出满足策略的密码）。
- 实现： 在EasyCrypt中编写算法代码。
- 验证： 证明该实现正确地精化了规约（功能正确性）。
- 安全性证明： 将算法建模为一个密码学游戏，以证明其属性，例如从定义空间中输出的均匀分布（安全性）。
这种方法提供了数学上的确定性，即代码的行为完全符合预期并具有所需的安全属性，前提是底层的密码学原语（随机数生成器）是安全的。
4. 提出的参考实现
本文提出了一种新的、模块化的随机密码生成器设计，旨在作为经过验证的参考。虽然提供的摘录中没有显示完整代码，但该设计在逻辑上分离了：
- 策略解析器与验证器： 确保用户定义的策略内部一致（例如，最小值不超过最大值，总最小值不超过密码长度）。
- 约束采样器： 在策略约束下执行两阶段生成的核心引擎。
- 随机排列： 对字符序列应用最终的随机打乱。
每个模块都将在EasyCrypt中拥有形式化规约和经过验证的实现。
5. 技术细节与数学表述
随机密码生成器的安全性取决于其输出的熵和均匀分布。令 $\mathcal{P}$ 为由策略定义的所有密码的集合（长度 $l$，字符集 $C_1, C_2, ..., C_n$ 带有最小/最大约束）。理想的随机密码生成器是一个从 $\mathcal{P}$ 中均匀采样的函数 $G$。
生成任何特定密码 $p \in \mathcal{P}$ 的概率应为： $$Pr[G() = p] = \frac{1}{|\mathcal{P}|}$$ 其中 $|\mathcal{P}|$ 是密码空间的大小。朴素实现中的一个常见缺陷是引入偏差，使得某些密码比其他密码更可能出现。例如，如果算法首先为强制字符集选取字符，然后填充其余部分，那么除非应用了完美的随机打乱，否则强制字符位于开头的密码会被过度表示。形式化验证证明了不存在此类偏差。
生成密码的熵 $H$（以比特为单位）为： $$H = \log_2(|\mathcal{P}|)$$ 验证确保实现不会将此熵降低到低于该策略的理论最大值。
6. 实验结果与图表说明
虽然提供的PDF摘录不包含传统的实验结果或图表，但其核心“结果”是形式化证明本身。在EasyCrypt中成功的验证即是最佳证据。可以构思一个图表来比较保证级别：
假设图表：保证级别 vs. 开发方法
- 传统测试： 对已测试案例有高置信度，但对未测试的边缘情况（策略冲突、边界值）未知。覆盖率有限。
- 代码审查： 中等置信度。高度依赖审查者的技能。可能遗漏细微的逻辑错误或侧信道问题。
- 形式化验证（如本文所提）： 最高可能的保证。为所有可能的输入和明确的安全属性提供数学上的正确性证明。该“图表”会将其显示为“保证”轴上的最高点。
本文的贡献在于将随机密码生成器从前两个类别移入第三个类别。
7. 分析框架：一个非代码案例研究
考虑一个策略：长度=8，要求至少1个大写字母、1个数字、1个特殊字符。一个有缺陷的算法可能：
- 位置1：选取随机大写字母。
- 位置2：选取随机数字。
- 位置3：选取随机特殊字符。
- 位置4-8：用所有字符集中的随机字符填充。
- 打乱所有8个字符。
缺陷： 打乱前的初始固定顺序（大写、数字、特殊字符）造成了偏差。虽然打乱操作随机化了最终位置，但该过程是从中间状态的非均匀分布开始的。一个经过形式化验证的算法将通过从约束空间 $\mathcal{P}$ 中进行一次无偏的采样过程来构建整个密码，或者将可证明地展示其多步骤过程等同于这种均匀采样。
8. 核心见解与分析视角
核心见解： 本文正确地指出了密码管理器中一个关键但常被忽视的攻击面：密码生成器本身的可信度。仅仅拥有一个坚固的保险库是不够的；如果源材料（密码）由于一个有缺陷的生成器而变得脆弱或可预测，整个系统就会失效。作者将形式化方法——一种在硬件或航空软件中更常见的技术——应用于这个消费级安全问题的举措，既雄心勃勃又十分必要。
逻辑脉络： 论证是合理的：1) 信任是密码管理器采用的障碍。2) 随机密码生成器是信任关键组件。3) 当前的随机密码生成器是临时实现的，缺乏严格的保证。4) 形式化验证提供了最高级别的保证。5) 我们使用EasyCrypt提供了一个经过验证的随机密码生成器的蓝图。该逻辑将用户中心的问题（信任）与深入的技术解决方案（形式化方法）连接起来。
优势与不足：
优势： 关注开源密码管理器是务实的。策略对比分析很有价值。提出参考实现比仅仅批评他人更有用；它设定了一个标准。使用EasyCrypt将这项工作与既定的密码学验证实践联系起来，类似于对“密码学原语的安全性”（M. Bellare, P. Rogaway）中算法的验证。
不足： 提供的摘录是一个起点。真正的考验是针对现实世界策略的完整EasyCrypt证明的复杂性。该方法假设了一个完美的随机数生成器；那里的漏洞会绕过所有形式化保证。它也没有解决最终编译二进制文件中的侧信道攻击（时序、内存）问题，这是其他形式化验证项目（如seL4微内核验证）中已指出的局限性。
可操作的见解：
1. 对于密码管理器开发者： 将此验证过的核心或类似核心集成为库。形式化验证的前期成本很高，但能减少长期的安全审查负担和责任。
2. 对于审计员与研究人员： 使用此工作作为模板来分析其他密码管理器。策略对比表是安全评估的现成检查清单。
3. 对于标准机构（例如NIST、FIDO）： 考虑将形式化验证作为认证密码生成模块的要求，类似于通用准则对高保证产品强制要求严格开发流程的方式。
4. 对于用户： 要求透明度。优先选择那些公布其随机密码生成算法、并理想情况下公布其验证证据的密码管理器。本文提供了提出此要求的词汇。
本质上，这项研究是呼吁提高一个基础安全组件的工程标准。它将目标从“希望安全”转变为“可证明正确”，这是守护我们数字身份的工具唯一可接受的基准。
9. 未来应用与研究方向
其影响超出了密码管理器的范畴：
- API与服务令牌： 云服务和微服务架构通常需要生成令牌。一个经过验证的生成器能确保这些秘密在密码学上是强壮的。
- 密码学密钥生成： 这些原则适用于为密码学密钥生成人类可读的恢复码或口令（通过类似掷骰子的方法），在这些场景中，偏差同样危险。
- 与硬件安全的集成： 未来的工作可以验证随机密码生成器软件与硬件真随机数生成器或可信执行环境之间的交互。
- 自动化策略分析： 构建工具，在生成密码之前，形式化地分析用户定义的策略是否存在弱点（例如，尽管看起来复杂，但实际搜索空间很小）。
- 标准化： 最大的未来方向是将此参考实现转变为广泛采用的标准，或许作为一个独立的库（就像用于密码学的libsodium），任何应用程序都可以用它来进行经过验证的秘密生成。
10. 参考文献
- 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. (2005). Introduction to Modern Cryptography. Chapter on Pseudorandom Functions and Permutations.
- Klein, G., et al. (2009). seL4: Formal verification of an OS kernel. Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles.
- National Institute of Standards and Technology (NIST). (2017). Digital Identity Guidelines (SP 800-63B).
- Common Criteria Recognition Agreement (CCRA). Common Criteria for Information Technology Security Evaluation.
- Chiasson, S., van Oorschot, P. C., & Biddle, R. (2006). A second look at the usability of click-based graphical passwords. Proceedings of the 3rd symposium on Usable privacy and security.
- EasyCrypt Proof Assistant. Official Documentation and Tutorials. https://easycrypt.info/