  We present a framework by which websites can coordinate to make it difficult
for users to set similar passwords at these websites, in an effort to break the
culture of password reuse on the web today. Though the design of such a
framework is fraught with risks to users' security and privacy, we show that
these risks can be effectively mitigated through careful scoping of the goals
for such a framework and through principled design. At the core of our
framework is a private set-membership-test protocol that enables one website to
determine, upon a user setting a password for use at it, whether that user has
already set a similar password at another participating website, but with
neither side disclosing to the other the password(s) it employs in the
protocol. Our framework then layers over this protocol a collection of
techniques to mitigate the leakage necessitated by such a test. We verify via
probabilistic model checking that these techniques are effective in maintaining
account security, and since these mechanisms are consistent with common user
experience today, our framework should be unobtrusive to users who do not reuse
similar passwords across websites (e.g., due to having adopted a password
manager). Through a working implementation of our framework and optimization of
its parameters based on insights of how passwords tend to be reused, we show
that our design can meet the scalability challenges facing such a service.
