# Can modern password hashing functions mathematically exclude parallel computation?

A recent password hashing competition set out the following detailed technical requirement:-

that the API should include, but may not be limited to, a function with the following prototype:

int PHS(void *out, size_t outlen, const void *in, size_t inlen, const void *salt, size_t saltlen, unsigned int t_cost, unsigned int m_cost);


adding that: the t_cost and m_cost arguments are intended to parameterize time and memory usage, respectively, however this is not a strict requirement (only one parameter may be effective, m_cost might affect time, etc.).

The prototype does not require a parallelism parameter, yet the winner (Argon2) has such a parameter. Therefore parallel computation figures prominently in that algorithm.

Was it not possible to code a function that is not susceptible to speed up from parallel computation? So rather than accommodate multiple cores/threads, find an algorithm that is totally and mathematically immune instead. Do such functions not exist?

If you can compute one password hash in reasonable time $$t$$ on your computer—which is necessary for an application to be usable—then if I have $$p$$ different computers just like yours, I can compute $$p$$ hashes in the same time $$t$$, and no amount of mathemagic can stop me.

Here's a very naive password hash that completes in 1sec on your computer, which is the barrier for usability:

PWHASH1: Iterate SHA-512 on the salted password enough times that it takes 1sec on a single core in your computer.

If your computer has four cores, then you can do better—and still get the password hashed in 1sec:

PWHASH2: Iterate SHA-512 on the salted password hash and core number (0, 1, 2, 3) enough times that it takes 1sec on a single core, but do it in parallel on four cores and then hash the result with SHA-512.

Now suppose I have eight cores that run at the same speed as your computer's cores. In one minute, I can try 480 passwords using PWHASH1, but I can only try 120 passwords using PWHASH2.

Thus, the parallelism parameter of argon2 lets you dedicate more of another kind of resource than time—your computer's parallelism—to make the attacker's job harder. (Same goes for the memory parameter of argon2.)

Hashing passwords is easy to parallelize by an attacker; you'd simply perform separate tries (of different passwords) in different threads or even on different processors.

Parallelizing a password hash function or PBKDF can give you a faster response time (user time, not CPU time) while the attacker still has to perform the same amount of work as all of the work performed by the threads together.

If you don't want that then simply set the parallelization factor to 1 (thread) and you'd have a non-parallel Argon2 variant.

Was it not possible to code a function that is not susceptible to speed up from parallel computation?

Well, you cannot make an attacker refrain from testing multiple passwords as once, so in that case: no. The password hashes themselves do of course require that all the work is performed, most of it sequentially.

So rather than accommodate multiple cores/threads, find an algorithm that is totally and mathematically immune instead. Do such functions not exist?

Well, there will always be some parallelism in the primitives used, but yes, most password hashes are sequential unless you explicitly tell them to use parallelism.

Password hashes are useful for verifying passwords while securing the passwords against offline attacks on e.g. a stolen database (or entire server). You cannot protect against an adversary using parallelism on those stored values. However, it is of course possible avoid parallel attacks being performed during online verification.