Bernoulli Honeywords

Bernoulli Honeywords

Speakers: Ke Coby Wang

Conference: NDSS Symposium

YouTube: (no public video)

Overview

Ke Coby Wang's presentation on "Bernoulli Honeywords" at the NDSS Symposium introduces a groundbreaking methodology for the proactive detection of credential database breaches. This work directly confronts one of cybersecurity's most persistent and costly challenges: the alarmingly protracted period between a database compromise and its discovery, which typically spans between seven and fifteen months. During this extensive window, attackers are free to exploit stolen credentials, often engaging in widespread credential stuffing campaigns that leverage users' tendency to reuse passwords across multiple services. The financial and reputational ramifications for organizations are severe, with IBM estimating the average cost of breach detection and escalation at a staggering $1.24 million.

The concept of honeywords, originally proposed by Juels and Rivest, offers a promising countermeasure. These decoy passwords are strategically interspersed within a legitimate credential database alongside actual user-chosen passwords. The premise is elegant: if an attacker, having successfully breached the database, attempts to authenticate using a honeyword, the system is immediately alerted to the compromise. However, the practical efficacy of honeywords hinges on two critical requirements that have historically proven difficult to satisfy. First, flatness, meaning an attacker must be unable to reliably discern which password in a stored set is the genuine user credential. Second, and perhaps more importantly, a quantifiable and exceptionally low false-alarm rate, ensuring that an unbreached attacker cannot accidentally guess a honeyword and trigger a costly, disruptive false positive.

Traditional heuristic-based honeyword generation techniques have consistently struggled to meet these stringent requirements, often introducing new risks such as increased false alarms or the inadvertent exposure of user data by incorporating personal information into decoys. Bernoulli honeywords present a paradigm shift by treating honeyword selection as a Bernoulli process. This innovative approach allows for the analytic derivation of true and false breach-detection probabilities that are inherently independent of any intelligence an attacker might gather about a site's users. The research demonstrates that Bernoulli honeywords not only offer superior efficacy in both detection probabilities but also enhance the performance of modern honeyword system designs, marking a significant advancement in the defense against credential-based attacks.

Background

[▶ Watch: Problem of slow breach detection and honeyword challenges (0:00)]()

The landscape of credential database breach detection has long been plagued by the inherent limitations of existing methodologies. The foundational concept of honeywords, while theoretically sound, has faced significant hurdles in practical implementation. Early honeyword system designs broadly bifurcate into two categories: asymmetric and symmetric.

Asymmetric designs, exemplified by the original Juels & Rivest proposal, rely on an information asymmetry. In this model, a crucial secret datum, such as the index identifying the real user-chosen password among decoys, is stored within an assumed unbreachable honeychecker. Detection occurs if an attacker breaches the primary database but fails to compromise this secure honeychecker, allowing the system to differentiate legitimate logins from attacker attempts with honeywords. Other notable asymmetric approaches include Lethe, which employs a seed for a pseudorandom number generator to derive honeywords, and a system by Almeshekah et al. that leverages machine-dependent password hashing to obfuscate credentials. The fundamental vulnerability of asymmetric designs lies in their reliance on the integrity of the honeychecker; a compromise of this component would render the system ineffective.

In contrast, symmetric designs, such as Amnesia, operate under a more robust assumption: the attacker is permitted to learn the entire state of a breached site, including the honeychecker's data. In exchange for this increased attack surface, detection becomes probabilistic, occurring only when legitimate users attempt to log into accounts that the attacker has previously accessed. This design philosophy aims for resilience even if the entire credential system, including any monitoring components, falls into adversary hands. The work on Bernoulli honeywords demonstrates its versatility by integrating seamlessly into both asymmetric (Juels & Rivest honeychecker) and symmetric (Amnesia) frameworks.

A persistent challenge for heuristic-based honeyword generation has been achieving flatness. Users frequently embed personal information—such as birth years, favorite sports teams, or significant dates—into their passwords. Sophisticated attackers, armed with open-source intelligence or data from other breaches, can mine this information to construct highly probable password guesses. Heuristic honeywords, which often attempt to mimic these user patterns by incorporating similar personal data, inadvertently create vulnerabilities. Attackers can leverage their knowledge of user habits to distinguish between real passwords and decoys, undermining the flatness requirement. While some researchers have advocated for this approach, the risk of increased false alarms and the potential exposure of sensitive user data make it problematic. Bernoulli honeywords circumvent this issue by implicitly selecting a fraction of all possible passwords as honeywords, rather than explicitly generating a few "tuned" decoys, thereby avoiding reliance on personal information.

The paramount importance of a quantifiable and low false-alarm rate cannot be overstated. As the Tripwire study starkly illustrated, security operators are prone to disregarding breach alarms if the perceived risk of false positives is high. This "cry wolf" effect can lead to critical alerts being ignored, allowing real breaches to go undetected. Heuristic honeyword methods, unfortunately, suffer from significant false-alarm risks; some of the best proposals still permit an attacker a 6% chance of guessing a honeyword in just 100 online login attempts. Such a high false positive rate renders these systems practically unusable. Furthermore, a truly robust honeyword system must guarantee a low false-alarm rate even if an attacker acquires user-chosen passwords through other vectors, such as phishing campaigns. Bernoulli honeywords directly address this by providing a mathematically quantifiable and tunable false breach-detection probability that remains resilient even in scenarios where attackers possess prior knowledge of legitimate user credentials.

Key Findings

[▶ Watch: Introducing Bernoulli Honeywords and core advantages (2:00)]()

The research on Bernoulli honeywords yields several significant findings that collectively represent a substantial advancement in the field of credential breach detection:

• Analytic Derivation of Probabilities: A core contribution is the ability to analytically derive both true and false breach-detection probabilities. Unlike heuristic methods that rely on empirical tuning and guesswork, Bernoulli honeywords offer a mathematically rigorous framework for understanding and predicting system behavior. This precision is crucial for practical deployment and for establishing trust in the system's reliability.
• Independence from Attacker Knowledge: Crucially, the false breach-detection probability associated with Bernoulli honeywords is demonstrated to be independent of any information an attacker might gather about a site's users. This mitigates a major vulnerability of heuristic methods, where an attacker's knowledge of user patterns or personal data could inadvertently increase the likelihood of false alarms. This independence ensures a robust and predictable false-alarm rate under diverse threat models.
• Compelling Efficacy: Extensive evaluations confirm the compelling efficacy of Bernoulli honeywords. They achieve high true-detection probabilities, indicating a strong capability to identify actual breaches, while simultaneously maintaining the critically low false-alarm rates required for operational viability. This efficacy is further enhanced when combined with defensive measures like blocklisting of weak passwords, which significantly improves detection rates by reducing the attacker's search space.
• Versatile Integration and Performance Improvements: Bernoulli honeywords are shown to integrate effectively into both established asymmetric designs (like the Juels & Rivest honeychecker) and more advanced symmetric designs (such as Amnesia). Furthermore, the research introduces a novel remote monitoring protocol for Amnesia that offers significant performance and space efficiency gains, outperforming previous proposals by an order of magnitude for common operations. This makes cross-site password reuse detection more practical and scalable.
• Superiority Over Heuristics: The mathematical foundation of Bernoulli honeywords inherently addresses the limitations of heuristic approaches concerning flatness and false-alarm rates. By treating honeyword selection as a Bernoulli process, the system avoids the pitfalls of trying to mimic user-chosen passwords, which can inadvertently create exploitable patterns or introduce personal data exposure risks.

Technical Deep Dive

[▶ Watch: Honeyword system designs and Bernoulli integration context (4:00)]()

The core innovation of Bernoulli honeywords lies in its simple yet profound probabilistic approach to honeyword generation. During the password (re)set process for a user, every possible password within the entire password space, with the sole exception of the user-chosen one, is independently selected to be a honeyword for that specific user at the site with a fixed probability, ph. This probabilistic selection differentiates it fundamentally from heuristic methods that attempt to craft a small set of "plausible" decoys.

To analyze this system, the talk introduces key variables and threat models:

• pwdr: Represents the list of allowable passwords, ranked by an attacker's likelihood of guessing them.
• U: Denotes the rank of the user-chosen password within the pwdr list.
• Sr: An indicator variable, set to 1 if U=r (i.e., pwdr is the user's password) or if pwdr is a honeyword, and 0 otherwise.

Two primary threat models are considered:

1. Raising Alarm Attacker (RAAT): This attacker has not breached the site's database but possesses knowledge of the user-chosen password (e.g., through phishing). The RAAT's objective is to input a honeyword to induce a false breach alarm. The probability HwInraat(ph, l) that at least one honeyword is input in l distinct login attempts is derived as 1 - (1 - ph)^l. A critical insight here is that this probability is independent of the distribution of U, meaning the RAAT's specific knowledge about user-chosen passwords does not influence the false alarm rate. This provides a strong guarantee against false positives.

1. Breaching Attacker (BRAT): This attacker has successfully breached the credential database, gaining access to all sr values for a given account. The BRAT's optimal strategy is to attempt the password pwdr1 with the lowest rank r1 for which sr1=1. The research derives the probability of the BRAT entering the user-chosen password (Eq. 1) and the probability of entering a honeyword (HWINbrat(ph, R)) (Eq. 2), where R is the total number of passwords considered by the BRAT. This allows defenders to quantify the true detection probability.

Integration with Juels & Rivest Honeychecker (Asymmetric Design)

The first integration discussed adapts the original Juels & Rivest honeychecker design. A significant challenge in this context is compactly representing the honeyword status for every possible password in the vast password space. Bernoulli honeywords address this by leveraging Bloom filters.

In this adapted design:

• The site stores a Bloom filter (F, B) for each user account. H is a password hashing function modeled as a random oracle.
• The Bloom filter (F, B) is configured such that H(π_user_chosen) is present in (F, B) with a probability of 1.0. Simultaneously, any other password e is included in (F, B) with the fixed probability ph. This probabilistic inclusion is achieved by setting a specific parameter B based on ph and the number of hash functions k and bits b in the Bloom filter (B = (ph)^(1/k) * b).
• The unbreachable honeychecker, which is the secure, isolated component, stores F(H(π_user_chosen)). This value essentially represents a "fingerprint" of the legitimate password within the Bloom filter.
• During a login attempt with password π_attempt:
• If H(π_attempt) is not found in (F, B), the login fails (the password is neither the real one nor a honeyword).
• If F(H(π_attempt)) matches the value stored in the unbreachable honeychecker, the login succeeds (it's the real user-chosen password).
• Otherwise (i.e., H(π_attempt) is in (F, B) but F(H(π_attempt)) does not match the honeychecker's stored value), a breach alarm is raised. This indicates that a honeyword has been used, signaling a compromise.

Evaluation of Honeychecker Integration:

For the RAAT, the false-detection probability FDP(l, n) (probability of a false alarm across n accounts with l login attempts each) is bounded by 1 - (1 - HwInraat(ph, l))^n (Eq. 7). This independence from attacker knowledge is a key strength.

For the BRAT, who has breached the site and possesses the Bloom filter (F, B) for each account, the optimal strategy is to attempt the most likely password pwdr for which H(pwdr) is present in (F, B). Detection occurs if this pwdr is a honeyword, meaning F(H(pwdr)) differs from F(H(π_user_chosen)). The research derives the true-detection probability TDPR for an R-account (Eq. 8) and TDP(A') for a set of attacked accounts A' (Eq. 9, 10).

Empirical evaluation required two main inputs:

1. FDP Bound: The study aimed for an epsilon of 10^-1 (less than one false detection every three years in expectation) for FDP(10^6, 10) and FDP(10^4, 1000).
2. Distribution of U: This was modeled using real-world password datasets: Wang et al. 40 (Chinese train-ticketing), Mazurek et al. 28 (CMU passwords with extensive attacker knowledge), and Xu et al. 43 (CKL-PCFG, Neopets dataset). These distributions were fitted to P(U = r) = a + beta*log10(r) (Table 1, Fig. 1a-b). The effect of blocklisting weak passwords was also modeled (Eq. 18).

The results were compelling: with Bloom filter dimensions k=20, b=128, and a minimum rank theta=1000 for user-chosen passwords, and epsilon=10^-1:

• For the weakest password distribution (Eq. 12), the true-detection probability (TDP) reached 0.5 when the BRAT accessed approximately 20.4% of accounts, and 1.0 when accessing 26.1%.
• Blocklisting significantly improved detection. For instance, with blocklisting using TG-I'' (Eq. 18), TDP reached 0.5 at only 13.6% of accounts accessed, and with TG-I''' (Eq. 18), it dropped to 6.4%.
• For stronger datasets (Eq. 16, 17), TDP was already near 1.0 after the BRAT accessed just one account.
• Even when driving epsilon lower (e.g., to 10^-5), stronger datasets maintained substantial detection power.

Integration with Amnesia (Symmetric Design)

The research also integrated Bernoulli honeywords into Amnesia, a symmetric honeyword design that addresses the limitation of requiring an unbreachable honeychecker. Amnesia allows for remote monitoring and local detection even if the entire site state is compromised. Local detection in Amnesia relies on attaching one-bit marks to password hashes. The last accessed password is marked, while others are marked with a certain probability (Premark). If a BRAT uses a honeyword, the legitimate user-chosen password might become unmarked, triggering an alarm upon the legitimate user's next login.

Bernoulli's adaptation of Amnesia also uses Bloom filters (F, B, M), where M specifically represents the set of marked indices.

• Login Process: If H(π_attempt) is not in (F, B), the login fails. If H(π_attempt) is in (F, M), the login succeeds. Otherwise, an alarm is triggered.
• Remarking: Upon a successful login, M is reset to include F(H(π_attempt)) with probability 1.0, and other elements in B \ F(H(π_attempt)) are marked with probability Premark.

Security Evaluation for Amnesia:

• RAAT: The FDP(l, n) is bounded as before (Eq. 7), maintaining independence from attacker knowledge.
• BRAT: The BRAT monitors L legitimate logins, capturing snapshots of (F, B, M). sr=1 if H(pwdr) remains marked across all L logins. The research derives ph(L) (Eq. 19) to account for the degradation of detection over L logins, and TDPR(L, L') (Eq. 22) and TDP(L, L', n) (Eq. 23) for the BRAT attacking L' times after L legitimate logins.

Evaluation of Amnesia integration with L=10, L'=31, theta=1000, epsilon=10^-1, k=20, b=128, Pmark=0.95, Premark=0.065 showed:

• Blocklisting again proved beneficial. Using TG-I'' (Eq. 18) reduced the fraction of accounts needed to reach TDP = 0.5 from 32% to 8.6%.
• A notable trade-off for the symmetric design's weaker assumptions: the BRAT could access approximately 34.4% more accounts in Amnesia compared to the honeychecker design before detection.
• For stronger datasets like CMU and CKL-PCFG, detection was certain after accessing only 5% and an extremely low 0.0004% of accounts, respectively.
• The TDP decayed modestly as L (legitimate logins) and L'-L (BRAT logins) increased.

Remote Monitoring Protocol for Amnesia

A significant feature of Amnesia is its support for remote monitoring, enabling a target site T to solicit help from a monitoring site M without revealing sensitive honeywords or user-chosen passwords. This is crucial for detecting password reuse across different services. Amnesia's original protocol, PCR, involved T sending encrypted password hashes to M, with M performing computations and returning ciphertexts for T to decrypt.

Bernoulli honeywords introduce a more efficient remote monitoring protocol:

• Deployment (Fig. 5): T generates a public/private key pair (pk, sk). It creates b ciphertexts cj that encode the Bloom filter indices (representing g for indices in B and g-1 for those not in B). T sends pk, F, b', cj, and a zero-knowledge proof Ψ (attesting to the well-formedness of cj) to M. M validates Ψ. M then computes do, a ciphertext of 1 if b' is accurate, otherwise a random element. M saves pk, F, cj, do.
• Monitor Response (Fig. 6): Upon an incorrect login attempt with password π at M, M calculates S = F(H(π)). M computes d1 (a ciphertext of 1 if all cj for j ∈ S are g, else g-2). M then computes c0 (a ciphertext of 1 if do and d1 are 1). Finally, M computes c1 (a ciphertext of π if c0 is 1). M sends c0, c1 to T.
• T decrypts c0 and c1. If Dec(c0) != 1 or H(Dec(c1)) is not in (F, B), T aborts (indicating M misbehavior). Otherwise, T treats Dec(c1) as a local login attempt.

Cryptographic Security Arguments: The protocol provides strong security guarantees. Against a malicious M, it does not leak information about T's honeywords (except ph). To prevent M from inducing false alarms, T can employ two distinct Bloom filters: a private one for local detection and a public one for the remote monitoring protocol. Against a malicious T, M conveys information only if the monitoring request is well-formed and H(π) is in (F, B').

Performance Evaluation (Fig. 7): The new protocol significantly outperforms Amnesia's original PCR protocol. While M's response generation is slightly more expensive (around 5ms), this can be mitigated by reducing the number of hash functions k. Overall, the Bernoulli-based protocol is an order of magnitude faster for common operations like response generation and processing, and it is far more space-efficient for storing monitoring requests.

Demo / Proof of Concept

[▶ Watch: Quantifying false alarms and Bernoulli technical approach (6:00)]()

While the talk did not describe a live, interactive demonstration in the traditional sense, the efficacy and practical viability of Bernoulli honeywords were thoroughly proven through extensive empirical evaluations and performance analyses. The detailed results from integrating Bernoulli honeywords into both the Juels & Rivest honeychecker and the Amnesia symmetric design serve as a robust proof of concept.

These evaluations involved:

• Quantifying Detection Rates: Measuring the true-detection probabilities (TDP) under various attacker models (RAAT, BRAT) and password distributions (weakest, TG-I'', TG-I''', CMU, CKL-PCFG datasets). This demonstrated that Bernoulli honeywords achieve high TDPs, often reaching 0.5 or 1.0 after an attacker accesses a remarkably small percentage of accounts (e.g., 6.4% with blocklisting, or even 0.0004% for strong datasets in Amnesia).
• Validating False-Alarm Rates: Confirming that the false-detection probability (FDP) remains exceptionally low and, crucially, independent of attacker knowledge, meeting the stringent epsilon = 10^-1 requirement (less than one false detection every three years).
• Benchmarking Performance: Evaluating the computational and space efficiency of the proposed remote monitoring protocol for Amnesia, showing an order-of-magnitude improvement over prior work.

These rigorous empirical results, based on established password datasets and threat models, effectively demonstrate that Bernoulli honeywords are not only theoretically sound but also practically implementable and highly effective in achieving their stated goals of rapid and reliable breach detection.

Defensive Implications

[▶ Watch: Integrating Bernoulli Honeywords into existing systems via Bloom filters (8:00)]()

The introduction of Bernoulli honeywords offers several critical implications for cybersecurity defenders aiming to enhance their breach detection capabilities and mitigate the impact of credential-based attacks:

• Prioritize Rapid Breach Detection: Organizations should consider implementing Bernoulli honeywords to drastically reduce the time it takes to detect credential database breaches. Moving from an average detection time of 7-15 months to near-instantaneous alarms upon honeyword activation can significantly curtail the window of opportunity for attackers and limit the scope of damage.
• Embrace Quantifiable Security: Defenders should favor security solutions, like Bernoulli honeywords, that offer analytically derived and quantifiable probabilities for both true and false breach detection. This provides a clear, data-driven understanding of system efficacy and reliability, moving away from heuristic-based approaches that carry higher, unpredictable risks of false positives.
• Leverage Blocklisting for Enhanced Efficacy: The research clearly demonstrates that combining Bernoulli honeywords with robust blocklisting of weak or commonly reused passwords dramatically improves true-detection probabilities. Defenders should integrate strong password policies and blocklisting mechanisms to maximize the effectiveness of their honeyword deployments.
• Choose Appropriate Honeyword System Design: Understand the trade-offs between asymmetric (Juels & Rivest honeychecker) and symmetric (Amnesia) honeyword system designs. If an organization can guarantee the unbreachability of a dedicated honeychecker component, an asymmetric design might offer faster detection. However, for environments where such a guarantee is difficult or for supporting remote monitoring and resilience against full system compromise, the symmetric Amnesia design with Bernoulli honeywords is a more robust choice.
• Adopt Efficient Remote Monitoring: For organizations concerned with detecting cross-site password reuse, deploying the new, efficient remote monitoring protocol for Amnesia is highly recommended. This protocol significantly reduces the performance overhead and space requirements associated with previous methods, making it a practical tool for collaborative breach detection across different services.
• Manage Online Guessing Impact: While Bernoulli honeywords minimally increase an online attacker's success probability for strong passwords, sites with extremely stringent security requirements might consider exempting accounts with exceptionally strong, unique passwords from Bernoulli honeyword protection. However, for the vast majority of users, the benefits of breach detection far outweigh this negligible risk.
• Investigate Space Optimization: For very large-scale deployments, further research into even more space-efficient implementations of Bernoulli honeywords (e.g., using H() mod w instead of full Bloom filters) could be beneficial, although Bloom filters already offer significant space savings compared to heuristic methods.

Key Takeaways

• Mathematical Foundation for Honeywords: Bernoulli honeywords introduce a novel, mathematically rigorous approach to honeyword generation, addressing the limitations of prior heuristic methods by treating selection as an independent Bernoulli process.
• Quantifiable and Attacker-Independent False Alarms: The system provides analytically derived true and false breach-detection probabilities, with the false-alarm rate being provably independent of any information an attacker might possess about user passwords, ensuring robust and predictable behavior.
• High Efficacy and Versatile Integration: Bernoulli honeywords demonstrate compelling efficacy in detecting breaches while maintaining low false-alarm rates, and they seamlessly integrate into both asymmetric (Juels & Rivest honeychecker) and symmetric (Amnesia) honeyword system designs.
• Blocklisting Boosts Detection: The effectiveness of Bernoulli honeywords is significantly enhanced when combined with blocklisting of weak or commonly used passwords, leading to substantially faster breach detection.
• Improved Remote Monitoring: A new, efficient remote monitoring protocol for Amnesia, based on Bernoulli honeywords and zero-knowledge proofs, offers an order-of-magnitude performance and space efficiency improvement over previous proposals, facilitating effective cross-site password reuse detection.
• Faster Breach Detection is Critical: By enabling rapid and reliable detection of credential database breaches, Bernoulli honeywords provide a powerful tool to counter credential stuffing attacks and mitigate the extensive financial and reputational damage associated with prolonged undetected compromises.

About the Speaker(s)

Ke Coby Wang presented the work on "Bernoulli Honeywords" at the NDSS Symposium. The transcript and metadata do not provide specific details about their title or affiliation, but they are credited as the sole speaker for this research.