Hashes to passwords with PBKDF2

Question

If an attacker wants to hack the passwords of $2^{10}$ users. And all of these users generate a password from the space of $2^{50}$ passwords** and each password is hashed with PBKDF2 with $2^{10}$ iterations**.

How many hashes would an attacker need to do to get all passwords in the worst case?

I was thinking it would be $2^{10} \cdot 2^{50} \cdot 2^{10} = 2^{70}$ since with PBKDF2 each password will be hashed with $2^{10}$ iterations in this case.

Answer 1

I would like to raise three objections to this calculation:

1. When users choose their password from the space of 2^50 passwords (the term space fits for keys, not actually for passwords, see 2.), they practically never choose it at the "outer boundary" of the space, but at the "inner boundary": some choose the password "123", the vast majority choose passwords with up to eight letters. This means that almost never the whole space has to be searched, but only a fraction of it.

2. If you crack passwords, you don't try all possibilities, but a list of passwords in the order of their frequency and you will find many of them after a few tries.

3. Even if there were still 2^40 iterations left, this sounds better than it is in practice, because 1. the passwords can be cracked in parallel and 2. it is enough for immense damage to crack only the easiest 60%.

Answer 2

How did you arrive at $2^{10} \cdot 2^{50} \cdot 2^{10}$? Presumably, it's meant to represent something like:

For each user u
    For each password p
        Compute PBKDF2(p) and compare with u.hashed_password

Which gives $2^{10} \cdot 2^{50}$ invocations of PBKDF, each of which is $2^{10}$ hash function calls. But consider this approach:

For each password p
    For each user u
        Compute PBKDF2(p) and compare with u.hashed_password

Notice that it's not necessary to calculate the PBKDF inside the loop, and instead you can do this:

For each password p
    Compute h = PBKDF2(p)
    For each user u
        compare h with u.hashed_password

This gives a total of just $2^{10} \cdot 2^{50}$ calls to the hash function. So in fact, the number of users does not impact the number of hash invocations required. Preventing this optimization is exactly the purpose of a salt. It means that there is an input to the PBKDF that depends on a property of the user, so that the hash calculation can not be hoisted out of the inner loop.