2015/09/01 by Jeremiah Blocki, Blocki, Jeremiah, Anupam Datta +1
Computer Science · #Advanced Malware Detection Techniques #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Information and Cyber Security #Spam and Phishing Detection #User Authentication and Security Systems
paper · pdf · doi:10.48550/arxiv.1509.00239
openalex publication_date 2015/09/01 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
An adversary who has obtained the cryptographic hash of a user's password can\nmount an offline attack to crack the password by comparing this hash value with\nthe cryptographic hashes of likely password guesses. This offline attacker is\nlimited only by the resources he is willing to invest to crack the password.\nKey-stretching tools can help mitigate the threat of offline attacks by making\neach password guess more expensive for the adversary to verify. However,\nkey-stretching increases authentication costs for a legitimate authentication\nserver. We introduce a novel Stackelberg game model which captures the\nessential elements of this interaction between a defender and an offline\nattacker. We then introduce Cost Asymmetric Secure Hash (CASH), a randomized\nkey-stretching mechanism that minimizes the fraction of passwords that would be\ncracked by a rational offline attacker without increasing amortized\nauthentication costs for the legitimate authentication server. CASH is\nmotivated by the observation that the legitimate authentication server will\ntypically run the authentication procedure to verify a correct password, while\nan offline adversary will typically use incorrect password guesses. By using\nrandomization we can ensure that the amortized cost of running CASH to verify a\ncorrect password guess is significantly smaller than the cost of rejecting an\nincorrect password. Using our Stackelberg game framework we can quantify the\nquality of the underlying CASH running time distribution in terms of the\nfraction of passwords that a rational offline adversary would crack. We provide\nan efficient algorithm to compute high quality CASH distributions for the\ndefender. Finally, we analyze CASH using empirical data from two large scale\npassword frequency datasets. Our analysis shows that CASH can significantly\nreduce (up to 50 %) the fraction of password cracked by a rational offline\nadversary.\n