Our Security Model

We adopt a game based definition of security. In cryptography many security properties are defined using games (e.g., semantic security).

The Game: The adversaryís goal is to break into one of the userís accounts, while the userís goal is to pick passwords strong enough to keep the adversary out of his accounts.

Play proceeds as follows:

1.     User: Using his password management scheme, the user creates n accounts A = {A1,An}with passwords P = {p1,Ö,pn}.

2.     Adversary:

a.      The adversary picks s accounts S = {j1,js} and the user must reveal the passwords pj1,Ö,pjs. This attack simulates the scenario where an adversary learns some of the userís passwords (e.g., phishing, malware, passwords stored or transmitted in the clear, unsalted passwords). The adversaryís goal is to break into one of the userís other accounts because the accounts S are already considered compromised.

b.     The adversary picks t accounts f1,ft and the user must reveal the salted cryptographic password hashes H(pf1),Ö,H(pft).

                                                             i.      The adversary is limited to M guesses per account (e.g., due to economic considerations) to crack each of these passwords.

                                                           ii.      The adversary may select f1,ft adaptively.

c.      The adversary attempts to log into each of the userís accounts in an online attack. The adversary will be locked out of each account after k guesses.

3.     Winner: The adversary wins if he can successfully log into any account for which he did not already steal the password (e.g. more formally any Ai ŌA\S). The user wins if the adversary fails to login to any of the userís non-compromised accounts.


We say that a password management scheme is (n, M, s, t, k ,d)-Secure if the adversaries probability of winning is at most d.


For example, suppose that the adversary

a)     Steals one of the users passwords (e.g. PayPaul.com),

b)     Mounts a dictionary attack against one of the userís passwords (e.g. Playstation), and

c)     Gets one-hundred guesses per account in an online attack against the userís other accounts (e.g., amazon, PNC and Slashdot).

If the userís password management scheme is (n, M, 1, 1, 100, 10-9)-Secure then odds that our adversary can break into any of his other accounts (including PlayStation) is at most one in a billion!



Note: Some people have suggested that a user should not worry about offline attacks because it is impossible to defend a password against an online attack. While I donít agree with this philosophy, (n, M, s+t, 0, k, d)-Security is a reasonable security goal for those who do. A password management scheme that satisfies (n, M, s+t, 0, k, d)-Security guarantees that the probability an adversary can successfully break into any account in an online attack is at most d.