  An adversary who has obtained the cryptographic hash of a user's password can
mount an offline attack to crack the password by comparing this hash value with
the cryptographic hashes of likely password guesses. This offline attacker is
limited only by the resources he is willing to invest to crack the password.
Key-stretching tools can help mitigate the threat of offline attacks by making
each password guess more expensive for the adversary to verify. However,
key-stretching increases authentication costs for a legitimate authentication
server. We introduce a novel Stackelberg game model which captures the
essential elements of this interaction between a defender and an offline
attacker. We then introduce Cost Asymmetric Secure Hash (CASH), a randomized
key-stretching mechanism that minimizes the fraction of passwords that would be
cracked by a rational offline attacker without increasing amortized
authentication costs for the legitimate authentication server. CASH is
motivated by the observation that the legitimate authentication server will
typically run the authentication procedure to verify a correct password, while
an offline adversary will typically use incorrect password guesses. By using
randomization we can ensure that the amortized cost of running CASH to verify a
correct password guess is significantly smaller than the cost of rejecting an
incorrect password. Using our Stackelberg game framework we can quantify the
quality of the underlying CASH running time distribution in terms of the
fraction of passwords that a rational offline adversary would crack. We provide
an efficient algorithm to compute high quality CASH distributions for the
defender. Finally, we analyze CASH using empirical data from two large scale
password frequency datasets. Our analysis shows that CASH can significantly
reduce (up to $50\%$) the fraction of password cracked by a rational offline
adversary.
