Password Hashing Algorithms
Principal Investigator: Jeremiah Blocki
In the last few years breaches at organizations like Yahoo!, Dropbox, Lastpass, AshleyMadison and Adult FriendFinder have exposed over a billion user passwords to offline attacks. Password hashing algorithms are a critical last line of defense against an offline attacker who has stolen password hash values from an authentication server. A attacker who has stolen a user's password hash value can attempt to crack each user's password offline by comparing the hashes of likely password guesses with the stolen hash value. Because the attacker can check each guess offline it is no longer possible to lockout the adversary after several incorrect guesses. The attacker is limited only by the cost of computing the hash function. Offline attacks are increasingly commonplace and dangerous due to weak password selection and improved cracking hardware e.g., the Antminer S9, currently available on Amazon.com for around $3,000 (USD), is capable of computing 14 trillion SHA256 hashes/second. When LastPass was breached they were using PBKDF2, a slow password hashing algorithm which iteratively computes SHA256 100,000 times. Thus, a LastPass attacker could potentially check 140 million password guesses per second on the Antminer S9. By comparison, 70 million guesses suffice to crack most user passwords (e.g., see <a href="https://eprint.iacr.org/2016/153">empirical frequency data for Yahoo! passwords</a>). There is a clear need to develop secure (moderately expensive) password hashing algorithms so that it is economically infeasible for an offline adversary to check millions of password guesses.
Recognizing this clear need researchers recently organized the Password Hashing Competition (PHC) to encourage the development of better password hashing algorithms. A secure password hashing algorithm should be: 1) quickly computable (e.g., $< 1$ second) on a PC, 2) prohibitively expensive for an adversary to evaluate millions of times even using customized hardware e.g., an Application Specific Integrated Circuit (ASIC) like the Antminer S9. Memory hard functions (MHFs), functions whose computation require a large amount of memory, are a promising primitive to achieving both goals. Memory is expensive even on an ASIC, and the Area x Time (AT) complexity of computing an ideal MHF scales with $n^2$, where $n$ is the running time on a PC. Thus, an MHF allows us to rapidly increase costs. By contrast, password hash functions like PBKDF2 or BCRYPT require minimal memory to compute and the AT complexity only scales with $n$. Consequently, PBKDF2 and BCRYPT can both be evaluated on an ASIC at minimal cost. Data-Independent Memory Hard Functions (iMHFs) are an important variant of MHFs in the context of password hashing due to their resistance to side-channel attacks.
Students: Ben Harsha Samson Zhou Seunghoon Lee
Practical Graphs for Optimal Side-Channel Resistant Memory-Hard Functions. with Joel Alwen and Ben Harsha 24th ACM Conference on Computer and Communications Security
Sustained Space Complexity. with with Joel Alwen and Krzysztof Pietrzak. EUROCRYPT 2018.
Bandwidth-Hard Functions: Reductions and Lower Bounds. with Ling Ren and Samson Zhou. 25th ACM Conference on Computer and Communications Security.
On the Computational Complexity of Minimal Cumulative Cost Graph Pebbling. with Samson Zhou. Financial Crypto 2018.
- Efficiently Computing Data Independent Memory Hard Functions. with Joel Alwen. CRYPTO 2016.
- Depth-Robust Graphs and Their Cumulative Memory Complexity. with Joel Alwen and Krzysztof Pietrzak. EUROCRYPT 2017).
Towards Practical Attacks on Argon2i and Balloon Hashing. with Joel Alwen. EuroS&P 2017.
Keywords: ASICs, Data Independent Memory Hard Functions, Depth-Robust Graphs, Graph Pebbling