Design and Analysis of a Secure Framework for Anonymous Password-Hardened Encryption and Authentication

Password Hardening (PH) is an authentication method specifically designed to defend against offline brute-force attacks on password databases. PH employs an external server to "harden” password records by applying its own secret key, while keeping the user’s password confidential. A key feature of PH is per-user rate limiting, where the external server monitors login requests associated with unique user identifiers known as "pseudonyms” to restrict the number of login attempts and mitigate online guessing attacks. However, this raises a serious privacy concern: as the external server keeps track of all pseudonym-linked requests, it can learn the entire login history of every user. The first part of this thesis introduces Cryptnyx, a novel scheme that solves an open problem in Password Hardening by ensuring user anonymity without sacrificing rate-limiting. In contrast to previous approaches, our scheme relies solely on cryptographic primitives, thus enhancing compatibility across different systems. It not only provides encryption capabilities but also maintains all the security guarantees of earlier schemes in addition to anonymity. The second part focuses on extending Password Hardening to address the issue of metadata leakage from pseudonym-linked requests. We introduce two key concepts to model and analyze privacy threats: request indistinguishability and request unobservability. To effectively mask metadata from both the external server and network observers, we develop a low-latency Poisson mixing technique in conjunction with a novel cover request generation algorithm to emulate realistic login patterns and effectively mask genuine requests. We systematically analyze the security properties of our proposed scheme and conduct experiments to evaluate the influence of various parameters on these concepts. Finally, we provide practical guidelines for generating cover traffic in anonymous authentication systems, ensuring enhanced privacy and security for users.