Ke Coby Wang (Duke University), Michael K. Reiter (Duke University)

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.