# What is the math behind iterations in PBKDF2-SHA256 for lastpass users?

I am looking for a technical estimate of how bad the situation is regarding the recent hack of lastpass. The hack was covered by several outlets: Naked Security, Ars Technica.

Lastpass has admitted that a hack took place over its servers and all the lastpass vaults were stolen on Dec 2022. So, the hacker needs the master password to decrypt the vault of a user and get all the passwords. I had a fairly good password with an entropy of about 72 bits. And set iterations at 1 million which is 10 times higher than lastpass' recommended default number of iterations (100k).

I did look into a similar post but that doesn't quite explain any math behind what I am looking for: Recommended # of iterations when using PBKDF2-SHA256?

So, here's the things I am specifically looking for:

• What exactly is "iteration" in lastpass or PBKDF2-SHA256 which lastpass uses?
• How does the iteration number impact brute forcing?
• What is the computation required to crack a lastpass vault with 1 million iterations and say 72 bits of entropy?
• Optional: How long would it take say a specific hardware device to do that computation? (Example with a currently available and widely used GPU or CPU for such tasks would be very helpful.)
• Dec 24, 2022 at 15:58

PBKDF2 is an iterated function based on a pseudorandom function (PRF) that takes a passphrase or other secret and a random salt. Essentially, there is a PRF, such as HMAC with a hash function (e.g., HMAC-SHA-256), with the output `F` and iteration count `c`:

``````F(pass, salt, c, i) = U_1 XOR U_2 XOR ... XOR U_c
``````

and `U` is defined like this:

``````U_1 = PRF(pass, salt || i)
U_2 = PRF(pass, U_1)
U_c = PRF(pass, U_(c-1))
``````

The iteration count, therefore, is the number of times the computation must be performed, and due to the way the iteration works, the computation of each round is dependent on the previous round, and the final computation is dependent on all of the rounds.

The idea of using an iterated password-based key derivation function with random salt is that it makes it harder to attack the data. Because the salt is unique for each user, it's impossible to precompute data to attack many passwords at once, and each password must be attacked individually.

If we perform, say, 1024 iterations, then we add the equivalent of 10 bits (2^10) of entropy to the password in terms of resources required to attack. For one million iterations, that's slightly less than 20 bits of entropy, so for a password with 72 bits of entropy, that means the effort to attack is approximately 92 bits worth of entropy. This is probably not practically attackable at the moment except maybe by very large government agencies.

Now, PBKDF2 is not a great password hashing function. These days, we prefer algorithms that are memory hard, which means that they perform computations which require large amounts of memory. Examples of these are Argon2 and scrypt. The reason we like these is that they raise the computational cost on GPUs and ASICs, which are extremely well suited to performing lots of parallel computations at once. A GPU, for example, may have hundreds or thousands of cores, and thus it's very possible to attack hundreds or thousands of passwords in parallel. However, the GPU will only have a few gigabytes of memory, so if we have a GPU with 16 GB of memory and we require 1 GB of memory for hashing, then the GPU can only perform 16 computations in parallel, which is substantially slower.

The main reason we might use PBKDF2 is because other password hashing functions are not approved by FIPS for U.S. (and other) government approval, but typically we prefer memory hard functions these days. I know at least some large websites which offer a FIPS-compatible product use PBKDF2 for the FIPS-compatible product and a better algorithm, like Argon2, for everyone else, which is a better choice.

For the default number of iterations, we expect to be able to crack LastPass password hashes on a GPU at the rate of 100,000 per second. Therefore, with ten times the number of iterations, we'd probably expect 10,000 per second.