Honeywords are plausible-looking decoy passwords associated with each user’s real password to timely detect password leakage. The more indistinguishable the honeywords are, the more secure a honeyword scheme is. However, honeyword schemes that externally generate honeywords can only approximate, but not equate, the distribution of user-chosen passwords, so they are unlikely to achieve the ideal indistinguishability. To address this issue, internally sampled honeyword schemes that sample honeywords from other users’ passwords have been proposed. In this work, we first reveal two critical security and two critical usability flaws in existing internally sampled honeyword schemes, i.e., Honeyindex (TDSC’16) and Superword (COSE’21). We then formalize agenericframework for sound internally sampled honeyword schemes, and propose variants for both Honeyindex and Superword. To principally evaluate the security of our framework, we propose Bayesian and intersection attack theories leading to attackers’ optimal distinguishing strategies, and evaluate them under three major attacker models each with varied capabilities (e.g., using leaked datasets and users’ personal information). Evaluation results show that, when 40 sweetwords are associated with each user (as recommended at IEEE S&P’22), with only one guess per account, the basic attacker’s success rate can reach 3.82%∼4.12%, and she can identify 4.31%∼5.04% of all real passwords with 104honeyword login attempts, breaking the ideal 2.50%(=1/40) security. Two more advanced attackers can identify 18.6%∼44.8% and 20.6%∼43.6% of all real passwords in 104honeyword login attempts, respectively. When multiple password files are available, the intersection attack alone identifies 18.3%∼18.6% of real passwords. We also explore the impacts of denial-of-service attacks. In all, this work reveals theinherentinsecurity of internally sampled honeyword schemes.

Password vaults enable a user to store multiple passwords with a single master password.Honey encryption (HE) protected password vaults (called honey vaults), are promising in resisting offline master password guessing attacks.Trial-decrypted with incorrect master passwords, honey vaults are designed to yield plausible-looking decoy vaults to confuse attackers, forcing them to perform online verifications to know whether a decrypted vault is the real one.In this paper, we demonstrate how to design secure honey vault schemes in a principled approach.We first identify three major types of vulnerabilities, and propose three critical design criteria based on rigorous theories, with each aiming to address one type of vulnerability.These criteria are: (1) Employing an accurate password probability model (PPM) in the natural language encoder (NLE, a key component of a honey vault) to resist distribution-aware distinguishing attacks; (2) Employing sequence-based PPMs for unique passwords, and sufficiently concise reuse models to resist encoding attacks (USENIX SEC'19); (3) Hiding a user's real-vault-related (i.e., adaptive) PPM to resist extraction attacks (USENIX SEC'21).To meet these key criteria, we propose VaultGuard with an innovative NLE and HE-Adaptive to honey-encrypt a user's real vault and the adaptive PPM, respectively.Our NLE eliminates the first and second vulnerabilities, while HE-Adaptive addresses the third.Security evaluations on real-world data reveal that our VaultGuard can significantly enhance honey vault security, forcing attackers to perform 1.10∼3.98times online verifications.We also provide an efficient proof-of-concept VaultGuard implementation on the client side.We believe this work provides general principles and actionable guidelines for designing secure honey vault schemes.