  Decoy passwords, or "honeywords," planted in a credential database can alert
a site to its breach if ever submitted in a login attempt. To be effective,
some honeywords must appear at least as likely to be user-chosen passwords as
the real ones, and honeywords must be very difficult to guess without having
breached the database, to prevent false breach alarms. These goals have proved
elusive, however, for heuristic honeyword generation algorithms. In this paper
we explore an alternative strategy in which the defender treats honeyword
selection as a Bernoulli process in which each possible password (except the
user-chosen one) is selected as a honeyword independently with some fixed
probability. We show how Bernoulli honeywords can be integrated into two
existing system designs for leveraging honeywords: one based on a honeychecker
that stores the secret index of the user-chosen password in the list of account
passwords, and another that does not leverage secret state at all. We show that
Bernoulli honeywords enable analytic derivation of false breach-detection
probabilities irrespective of what information the attacker gathers about the
sites' users; that their true and false breach-detection probabilities
demonstrate compelling efficacy; and that Bernoulli honeywords can even enable
performance improvements in modern honeyword system designs.
