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.

As password distribution lays the foundation for various password research, accurately characterizing it receives considerable attention. At IEEE TIFS’17, Wang et al. proposed the CDF-Zipf distribution model with the golden-section-search (GSS) fitting method to find the optimal parameters. Their model has been adopted by over 120 password-related studies. In this paper, we address their remaining, fundamental goodness-of-fit issue of password distribution in a principled approach. First, we prove that the confidence level of the state-of-the-art Monte Carlo approach (MCA, for the goodness-of-fit test) converges asymptotically to 0. By experimenting on 228.92 million real-world passwords, we confirm Wang et al.’s conjecture on the effect of sample size that minor deviations would lead to statistical significance for large-scale datasets. We propose both absolute and relative deviation metrics, and find that 1% random deviations in both metrics suffice to reject CDF-Zipf. Second, we attempt to reduce the non-negligible gap between the empirical and fitted distributions (with the maximum deviation of cumulative distribution function (CDF) being 1.91% on average). We explore eight alternative distribution models in two coordinate systems, and find that three models are more accurate than CDF-Zipf, but none can pass MCA. Particularly, we reveal that stretched-exponential, a variant of CDF-Zipf, can on average reduce the maximum CDF deviation from 1.91% to 1.25%. Third, to replace MCA, we introduce a new goodness-of-fit measure based on log-likelihoods. We find that stretched-exponential constantly has a larger log-likelihood than its counterparts. In all, stretched-exponential fits passwords better and further supports Zipf’s law in passwords.