# How is it possible to parallelize a hashing function to crack an iteratively hashed password?

Suppose I have an algorithm that relies on multiple iterations of a hash function like SHA1 to slow down an attacker trying to bruteforce a hash.

digest[0] = hash(password + salt)
for i in 1..r:
digest[i] = hash(digest[i-1] + password)


The final digest[r] is then used as the hash. How does this compare to a more standard implementation like PBKDF2 or bcrypt?

This website states:

simply iteratively hashing the hash of the password isn't enough as it can be parallelized in hardware and executed as fast as a normal hash.

Is there any truth to this statement? Since every iteration of the hash function is dependent on the previous, how could this be possible?

-
Yes, I've seen this closely related question: crypto.stackexchange.com/questions/959/… – NXE Oct 9 '12 at 4:14
PBKDF2 works similar to your construction, just with an XOR of the individual digests, password always at first position, and a mechanism to produce longer output than the hash function size. The security should be similar for same counts and same password. – Paŭlo Ebermann Oct 9 '12 at 19:40

The bit about parallelization is not for hashing one password. But the attacker, by definition, has a lot of passwords to try, and these can be computed in parallel, provided that the function maps well to whatever parallel architecture the attacker would like to use. In the case of the multi-SHA-1 method you describe, it maps very well on GPU. Note that the same can be said about PBKDF2, which is why I tend to recommend bcrypt, which is more resilient to GPU.

Although I do not immediately see any obvious problem with your SHA-1* function, it has the generic issue of being homemade and of not having been investigated thoroughly by dozens of cryptographers during several years. Therefore I would not trust it.

-
An important point to make is that a GPU is essentially a large parallel arithmetic unit. Think of it as a 256-core (or more) CPU with little/no ability to do branching (if/then/else), but a particularly strong ability to perform scalar calculations. Most hash functions can be expressed almost entirely as a series of scalar calculations, which means that it's possible to use a GPU to perform lots of them at once. – Polynomial Oct 10 '12 at 7:41

The quoted statement is correct except for the "executed as fast as a normal hash" fragment, when:

• we compare speed of attack of the proposed construct to that for the non-iterated normal hash with the same hardware; that attack can use parallelism, although the computation of the result for one password cannot;
• and digest[] is wide enough (like with significantly more than twice as many bits as in r, or entropy in salt if that's smaller), which is the case in practice with all standard hashes (If that was not the case, there would be the possibility of shortcuts allowing faster computation, or/and amortization of computations to get the result for different salts and the same password).

Still, the construction is not state-of-the-art: the increase of the cost of a parallel implementation of password search is only a multiplication by a factor (at best) r. Compare to scrypt (resp. bcrypt), where a parameterizable amount of RAM memory (resp. a fixed amount) is used continuously while hashing, forcing the adversary to invest not only in fast hardware for the hashes, but also, for each search running in parallel, in that amount of RAM memory and the associated energy; this greatly raise the cost of the attack, when the necessary memory often comes at nearly no cost for legitimate users. In particular, that makes parallelization using standard GPUs very inefficient, when these architectures are a near perfect match for the given algorithm, since all the data manipulated by an instance fits in registers.

Further, in the case of scrypt, if parallelization is available to legitimate users, that can be leveraged to increase in the number of hashes per password processed, again with penalty for the attacker, but seldom any for legitimate users.

-
He uses a salt on the first iteration. – CodesInChaos Oct 9 '12 at 6:29
@CodesInChaos; oups, fixed it, thank! – fgrieu Oct 9 '12 at 8:53

PBKDF2 salts each hashing stage with a new value and the uses a mix of all stages. It also does several thousands rounds of this hashing. This makes it impossible to build rainbow tables for, while in your case custom rainbow tables can be built if the salt value is known.

-
I can't see any practical difference between PBKDF2 and his scheme. It doesn't make sense to build a rainbow table for the OPs scheme, just like it doesn't make sense for PBKDF2. In both cases the salting makes rainbow tables useless. – CodesInChaos Oct 9 '12 at 8:08

If anyone's interested, I asked Bruce Schneier the same question, and here's his response:

Seems okay at first glance.

Maybe add a counter to the iterative hash: Xi = H(Xi-1 + S + i)

I also asked the author of the article to back up his statement that "simply iteratively hashing the hash of the password isn't enough as it can be parallelized in hardware and executed as fast as a normal hash", and here's his response:

If the key stretching algorithm is something like

sha1(sha1(....sha1(sha1($password .$salt))..))

Say it's sha1 applied 5000 times.

Then, you can construct a piece of hardware that looks like this:

 input
|
[SHA1-1]
|
[SHA1-2]
|
[SHA1-3]
|
.
.
.
|
[SHA1-5000]
|
\ /
output


...which is just 5000 SHA1 circuits in series. Whenever one of them finishes, it passes its output on to the next. So, like an assembly line, it will take 5000 units of time for a single input to go through the entire system, but the total throughput is one input per unit of time.

Of course, no matter what algorithm you use, the cracker could make 5000 chips that compute that algorithm and get the speedup, but I believe it's in some way more expensive (either in chip size, chip complexity, or in time) to do that with an algorithm like PBKDF2, which includes the iteration number and password in every hash computation.

-
His response is fundamentally wrong because each iteration of the SHA1 hash doesn't give you an output. It takes 5000 units of time to produce the first output, then another 5000 units of time to produce the second output, and so on.. – Thomas Dec 5 '12 at 8:49
@Thomas How so? Can't I just feed one hash per unit of time? – NXE Dec 5 '12 at 23:43
You feed one input in your pipeline per unit of time, sure. But that input needs to go down 5000 iterations before becoming a valid PBKDF2 (or whatever iterated scheme you use) output. You can't overlap computations like that. It's somewhat hard to explain in words, so I recommend you try to code it and see how it doesn't work. – Thomas Dec 5 '12 at 23:50
Sure, but by the time the first hash reaches its 5000th iteration, the second hash is in its 4999th, the third hash in its 4998th, etc. In the 5001st iteration, the second hash is in its 5000th iteration and I have its correct output, in addition to the first hash's. Right? – NXE Dec 5 '12 at 23:55
Sure! But here's the one crucial point you're missing: for this argument to hold, all 5000 "assembly line units" in the chain have to work in parallel. So, really, it's no better than just working on different hashes in parallel, and it certainly doesn't help you compute any one input/output pair in less than 5000 units of time. His scheme is misleading. – Thomas Dec 6 '12 at 0:03