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.

(n,M,s,t,k,d)-Security

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!

 

securityExample.png

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.