Password Hashing Algorithms

Research Areas: Cryptology and Rights Management

Principal Investigator: Jeremiah Blocki

Data breaches over the past decade have exposed billions of user passwords to the threat of offline brute-force attacks. Major incidents affecting organizations such as Yahoo!, Dropbox, LastPass, and others have demonstrated that once attackers obtain password hash values from an authentication server, they can attempt to recover user passwords by repeatedly guessing candidate passwords and comparing their hashes to the stolen values. Because these guesses are performed offline, attackers face no risk of account lockout or detection after repeated failures. Instead, the attacker is limited only by the computational cost of evaluating the password hashing algorithm.

This threat has become increasingly serious due to two trends. First, users frequently select weak or low-entropy passwords that can be guessed with relatively few attempts. Second, specialized hardware such as GPUs, FPGAs, and application-specific integrated circuits (ASICs) has dramatically reduced the cost of evaluating traditional cryptographic hash functions at scale. As a result, an attacker with modest hardware resources can test millions or billions of password guesses per second. In this environment, password hashing algorithms serve as a critical last line of defense: they are designed to deliberately increase the computational cost of verifying a password guess so that large-scale offline attacks become economically infeasible.

A secure password hashing algorithm must balance two competing goals. On the one hand, it should make it prohibitively expensive for an attacker to evaluate the function repeatedly, even when using highly optimized hardware. On the other hand, it must remain efficient enough that legitimate users can authenticate quickly on commodity devices. Ideally, the algorithm should require substantial memory resources as well as computation, since memory is more difficult and expensive to scale in specialized hardware. This observation motivated the development of memory-hard functions (MHFs)—cryptographic primitives designed so that evaluating the function requires large amounts of memory that must be maintained throughout the computation.

Recognizing the need for improved password hashing algorithms, the cryptographic community organized the Password Hashing Competition (PHC) to encourage the development and evaluation of new designs. The winning algorithm, Argon2i, and several other candidates incorporate memory-hardness as a central design principle. However, early in this line of research it became clear that understanding whether a proposed construction is truly memory-hard is a subtle and technically challenging problem. A poorly designed function may allow attackers to significantly reduce memory usage by trading additional computation or by evaluating many instances of the function in parallel while sharing memory resources. In our early work, we demonstrated that Argon2i and several other side-channel-resistant memory-hard functions were substantially less memory hard than originally intended. In particular, we showed that these constructions admit amortization attacks in which the adversary can evaluate the function on many independent inputs while reusing memory resources, resulting in amortized space–time complexity significantly lower than the quadratic cost that designers had hoped to achieve. These results highlighted the need for more rigorous analytical frameworks for evaluating the security of memory-hard functions.

Our research program seeks to provide a rigorous scientific foundation for the design and analysis of memory-hard password hashing algorithms. Early work revealed that many existing constructions were vulnerable either to side-channel attacks or to amortization attacks, in which an adversary evaluates the function on many independent password guesses while reusing memory resources across computations. Such attacks can dramatically reduce the cost of large-scale password cracking, undermining the intended security benefits of memory-hardness.

To better understand these vulnerabilities, we introduced new analytical tools based on graph pebbling games, which model the space–time tradeoffs required to evaluate the directed acyclic graphs underlying many memory-hard constructions. Using this framework, we identified a key combinatorial property called depth-robustness, which captures whether the data-dependency graph forces an adversary to maintain large amounts of memory throughout the computation. Our results demonstrated that memory-hard functions whose underlying graphs are not depth-robust can be attacked using efficient pebbling strategies that significantly reduce memory requirements.

Building on these insights, our work has helped establish depth-robust graphs as a central design principle for secure memory-hard functions. We developed new techniques for constructing such graphs and showed how they can be used to design password hashing algorithms that provably resist amortization attacks. These results include the first practical constructions of depth-robust graphs as well as improved memory-hard functions with strong theoretical guarantees. Over time, this line of work has helped place the study of memory-hard functions on a much firmer theoretical footing.

More recent research has expanded this program in several directions. First, we have developed improved techniques for constructing and analyzing memory-hard graphs, leading to stronger security guarantees and more efficient implementations. Second, we have introduced new statistical methods for analyzing real-world password distributions, which can inform the selection of parameters when deploying password hashing algorithms in practice. Finally, we have begun studying the post-quantum security of memory-hard functions, introducing new analytical tools such as the parallel reversible pebbling game to understand how quantum adversaries might attack these constructions.

Together, these results advance both the theoretical foundations and practical deployment of password hashing algorithms. By improving our understanding of how to design and analyze memory-hard functions, this research helps ensure that password hashing remains an effective defense against large-scale offline attacks, protecting users even when authentication databases are compromised.

Personnel

Students: Ben Harsha Samson Zhou Seunghoon Lee Wenjie Bai Peiyuan Liu Nathan Smearsoll Blake Holman Mohammad Hassan Ameri

Representative Publications

Blocki, J. Lee, S. and Zhou, S. Approximating Cumulative Pebbling Cost is Unique Games Hard. Innovations in Theoretical Computer Science (ITCS 2020).
Blocki, J. and Bai, W. DAHash: Distribution Aware Tuning of Password Hashing Costs. (FC 2021)
Ameri, M., Blocki, J. and Zhou, S. Computationally Data-Independent Memory Hard Functions. Innovations in Theoretical Computer Science (ITCS 2020)
Blocki, J., Cinkoske, M., Lee, S. and Jin Young, S. On Explicit Constructions of Extremely Depth Robust Graphs. 39th International Symposium on Theoretical Aspects of Computer Science
Blocki, J., Holman, B. and Seunghoon, L. The Parallel Reversible Pebbling Game: Analyzing the Post-Quantum Security of iMHFs. Theory of Cryptography Conference (TCC 2022)
Blocki, J., Holman, B., and Lee, S. The Impact of Reversibility on Parallel Pebbling. EUROCRYPT 2025
Bandwidth-Hard Functions: Reductions and Lower
Bounds. Blocki, J., Liu, P., Ren, L., and Zhou, S. Journal of Cryptology, Volume 37(16) 2024.
Bai, W., Blocki, J. and Ameri, H. Cost-Asymmetric Memory Hard Password Hashing. Information and Computation, Volume 297 (Special papers of the 13th International Conference on
Security and Cryptography for Networks (SCN 2022)), March 2024.
Provably Memory-Hard Proofs of Work With Memory-Easy Verification. Blocki, J. and Smearsoll, S. TCC 2025
Blocki, J., Harsha, B., Kang, S., Lee, S., Xing, L. and Zhou, S. Data-Independent Memory Hard Functions: New Attacks and Stronger Constructions. (CRYPTO 2019).
Bandwidth-Hard Functions: Reductions and Lower Bounds. with Ling Ren and Samson Zhou. 25th ACM Conference on Computer and Communications Security.
Practical Graphs for Optimal Side-Channel Resistant Memory-Hard Functions. with Joel Alwen and Ben Harsha 24th ACM Conference on Computer and Communications Security
A Tight Lower Bound on the TdScrypt Trapdoor Memory-Hard Function. Blocki, J. and Lee, S. IACR Communications in Cryptology 2025.
Sustained Space Complexity. with with Joel Alwen and Krzysztof Pietrzak. EUROCRYPT 2018.
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.
Towards Practical Attacks on Argon2i and Balloon Hashing. with Joel Alwen. EuroS&P 2017.
Depth-Robust Graphs and Their Cumulative Memory Complexity. with Joel Alwen and Krzysztof Pietrzak. EUROCRYPT 2017).
Harsha, B (student) and Blocki, J. Just-in-time Password Hashing. 3rd IEEE European Symposium on Security and Privacy (Euro S&P 2018).

Keywords: ASICs, Data Independent Memory Hard Functions, Depth-Robust Graphs, Graph Pebbling