1. Introduction
Password managers (PMs) are essential tools for generating and storing strong random passwords, addressing vulnerabilities in password authentication. However, user trust remains a barrier to adoption. This paper proposes a formally verified reference implementation for a Random Password Generator (RPG) using the EasyCrypt proof environment, focusing on functional correctness and security properties.
2. Table of Contents
- 1. Introduction
- 2. Table of Contents
- 3. Current Password Generation Algorithms
- 4. Formal Verification Framework
- 5. Technical Details and Mathematical Formulation
- 6. Experimental Results and Diagrams
- 7. Analysis Framework Example
- 8. Original Analysis
- 9. Future Applications and Outlook
- 10. References
3. Current Password Generation Algorithms
The authors studied 15 PMs, focusing on three widely used open-source ones: Google Chrome (v89.0.4364.1), Bitwarden (v1.47.1), and KeePass (v2.46). These were selected for their popularity and accessible source code.
3.1 Password Composition Policies
PMs allow users to define password composition policies including length, character classes (lowercase, uppercase, numbers, special characters), minimum/maximum occurrences per set, exclusion of similar characters, and custom character sets. Table 1 summarizes the policies for Chrome, Bitwarden, and KeePass.
3.2 Random Password Generation
The core algorithm generates random characters from defined sets until the password length is met, respecting minimum/maximum occurrence constraints. Chrome's algorithm first generates characters from sets with minimum occurrences, then from the union of all sets not exceeding maximums, and finally applies a permutation to the string.
4. Formal Verification Framework
4.1 EasyCrypt Overview
EasyCrypt is a proof assistant for cryptographic security proofs using a game-based approach. It allows specification of reference implementations and formal verification of functional correctness and security properties.
4.2 Security Properties
The formalization includes properties such as randomness uniformity, resistance to side-channel attacks, and adherence to policy constraints. The game-based approach models adversarial capabilities and proves indistinguishability from ideal random generation.
5. Technical Details and Mathematical Formulation
The security of the RPG is modeled using the concept of computational indistinguishability. Let $\mathcal{G}$ be the password generation algorithm and $\mathcal{U}$ be a uniform random generator. The advantage of an adversary $\mathcal{A}$ is defined as:
$$\text{Adv}_{\mathcal{G}}(\mathcal{A}) = |\Pr[\mathcal{A}^{\mathcal{G}} = 1] - \Pr[\mathcal{A}^{\mathcal{U}} = 1]|$$
The goal is to prove that $\text{Adv}_{\mathcal{G}}(\mathcal{A})$ is negligible for all probabilistic polynomial-time adversaries. The formal proof in EasyCrypt involves constructing a sequence of games, each differing slightly from the previous, and bounding the difference in adversary's success probability.
6. Experimental Results and Diagrams
The formal verification was conducted on a reference implementation of the RPG. The proof consists of approximately 500 lines of EasyCrypt code, covering functional correctness (the generated password satisfies the policy) and security (the output is indistinguishable from uniform random). The proof time was under 10 seconds on a standard laptop. A diagram of the game-based proof structure is shown below:
Figure 1: Game-based proof structure: Game 0 (real algorithm) → Game 1 (replace PRG with random) → Game 2 (replace character selection with uniform) → Game 3 (ideal). Each transition is justified by a cryptographic assumption or a reduction.
7. Analysis Framework Example
Case Study: Verifying KeePass Password Generation
Consider a policy requiring a 12-character password with at least 2 lowercase, 2 uppercase, 2 digits, and 2 special characters. The formal specification in EasyCrypt defines:
- Precondition: Policy parameters (length, min/max per set, excluded characters).
- Postcondition: Generated password satisfies all constraints and is uniformly random over the set of valid passwords.
- Security: No adversary can distinguish the output from a truly random string of the same length.
The proof proceeds by induction on the password length, showing that each character is drawn uniformly from the appropriate set, and the final permutation ensures no positional bias.
8. Original Analysis
Core Insight: This paper addresses a critical gap in password manager trust by applying formal verification to password generation algorithms. While many PMs claim security, few provide mathematical guarantees. The use of EasyCrypt is a significant step toward provably secure password generation.
Logical Flow: The authors first survey existing algorithms, identifying common patterns and potential flaws. They then propose a reference implementation and formally verify its correctness and security using game-based proofs. The flow is logical: problem identification → solution design → formal verification → implications.
Strengths & Flaws: The strength lies in the rigorous formal approach, which provides guarantees beyond typical testing. However, the paper focuses on a single reference implementation, not on verifying the actual code of Chrome, Bitwarden, or KeePass. This limits practical impact. Additionally, the proof assumes a trusted random number generator, which may not hold in all deployment scenarios. As noted by Bellare and Rogaway (1993) in their seminal work on random oracles, the gap between theoretical models and practical implementations remains a challenge.
Actionable Insights: For PM developers, adopting formal verification tools like EasyCrypt can enhance trust and reduce vulnerabilities. For researchers, extending this work to verify actual PM source code (e.g., through decompilation or symbolic execution) would be valuable. Users should demand transparency and formal guarantees from PM providers. The approach aligns with the broader trend of formal methods in security, as advocated by the National Institute of Standards and Technology (NIST) in their guidelines for cryptographic module validation.
9. Future Applications and Outlook
The formal verification framework can be extended to other PM features, such as password storage and autofill. Integration with continuous integration pipelines could enable automatic verification of password generation code. Future work may also explore side-channel resistance and quantum-safe random generation. As password managers become ubiquitous, formal guarantees will be essential for building user trust and meeting regulatory requirements (e.g., GDPR, eIDAS).
10. References
- 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.