How much does unknown PBKDF2 iteration count improve security?

Question

We are crackers who get our hand on an encrypted file. We know the whole file is AES-256 encryption of the original plaintext file.

We also know that PBKDF2 was run 1000 times on the original plain password to make the key and IV.

In this case, we know how to bruteforce crack this:

1. Generate plaintext password
2. Run PBKFD2 1000 times
3. Try to decrypt the file
4. Repeat 1-3 until we succeed

But what if we don't know the PBKFD2 iteration count? It could be 500, 1050, 5400 or any number.

How harder does this make the crack?

To me it seems almost impossible to do a bruteforce attack. I don't know where to even begin because I don't know the iteration count. Am I correct?

The question can be rephrased: How much security is really added to a file if it is protected not only by a regular password but also by iteration count? Upon decryption, both password and iteration count would have to be specified.

Answer 1

It wouldn't add enough security to matter. It just means that the attacker has to compare with the stored hash after each iteration of the PBKFD2 function, rather than once after the (known) count. Since a comparison is much faster than an iteration (for any reasonable underlying hash function), this doesn't slow the attacker significantly.

A slightly subtler issue is that the attacker has to play priority guessing games with where to invest his cycles. If he's run his basic password dictionary through 1,000 iterations and not gotten any hits, should he go to a bigger dictionary, or extend to 2,000 iterations? In practice, he'll probably alternate search expansions until he gets a hit. Note that if his search program is written to support this (I don't know if any are, but it's certainly possible and source code is available), it can save all of the intermediate results after e.g. 1,000 iterations, so when he extends to 2,000 iterations he's only doing the computation for another 1,000 iterations.

As soon as the attacker finds one match (the weakest password in the database), he's immediately going to guess that all the other passwords have the same count, and he's back to the standard attack. (Note that if you vary the counts between accounts, you'd have to store the count along with the hash, which means when he steals the hash database he's going to have the counts too and this is all moot.)

BTW, the general term for things like this (secret elements of the hash algorithm that're the same for all users, and hence don't need to be stored along with the hashes) is "pepper". It's a useful concept (provided you have a way to store the pepper value that isn't just going to get stolen along with the hashes), but this is not a good way to inject the pepper into the hash algorithm.

Answer 2

A hidden iteration count won't add much to security, for two reasons:

• The system which normally uses PBKDF2, e.g. to decrypt the file, must know the iteration count. It may leak, e.g. by measuring the time it takes for that system to process an incoming file; so it might not be as secret as that. Moreover, that iteration count is unlikely to be considered as part of the password, rather as part of the configuration: it will be written in a configuration file, maybe defined in a specification document, or exchanged through emails... Conversely, if the iteration count is considered as part of the password by all parties, and protected as such, then at least as good (and probably better) security would be achieved by simply appending that count to the password (as a string).

• If you look at PBKDF2, you will see that computing the output for iteration count c also implies computing the output for iteration counts c-1, c-2... you get all these "for free" since this is just a big XOR between many pseudorandom values, and none of them depends on the intended number of iterations (it could have been otherwise, but PBKDF2 was defined that way). Trying out a PBKDF2 output is less expensive on average than computing the next iteration: one iteration of PBKDF2/SHA-1 for a 256-bit output entails two HMAC/SHA-1 calls, hence four SHA-1 invocations, whereas "trying out" a key means decrypting the first block with AES-256 and see if the result makes sense; trying an AES-256 key is less expensive than computing one elementary SHA-1, let alone four elementary SHA-1. It follows that "hiding" the iteration count will slow down a brute force attack by at most 25%, which is nothing astounding.