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!
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.