6

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.

3
  • 1
    If you want to rely on secrets, use a real key. Either encrypt the hash, or include the key as part of the salt. That gains you far more without the downsides. Sep 8, 2013 at 10:35
  • I wouldn't derive more than the natural output size using PBKDF2. I'd rather derive one master key of exactly the natural size using PBKDF2 and then using HKDF-Expand to derive the individual keys. Sep 10, 2013 at 11:09
  • As Gordon Davisson said, the speed reduction would be small, and you could more than make up for it by increasing iteration counts. Use proven techniques instead of security by obscurity.
    – Razick
    Dec 18, 2013 at 15:07

2 Answers 2

6

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.

1
  • Great answer, really calling out the random derivation of iteration count is just a poor way to add pepper. I guess maybe a different way would be something like hashing the username and converting that to a number and mixing that on top of your base iteration count. That would only be revealable if they compromise both source code and database. Jul 29, 2016 at 6:14
3

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.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .