At what point does adding more iterations to PBKDF2 provide no extra security?

Question

If my true passphrase is used only to generate a hash which is used as the cipher's actual key, doesn't that mean it's possible to try and brute force the cipher itself? I know it would take an impossibly long time either way, but at what point would it be faster simply to brute force the key itself, rather than going through each hash iteration? For my most secure drive, I use 20 second iterations (which results in about 2 million SHA512 iterations) instead of the default of 1. If someone wanted to crack it and had all the time in the universe (and several times over), would they do it faster if they went for the resultant hash or every possible ASCII for the original passphrase?

EDIT: I want to point out that I'm just curious about the math, not about the practicality. I already use a long passphrase, and I know that it would take impossibly long to brute force, I know about rubber hose cryptanalysis, etc. All I'm asking is, if an adversary theoretically would be capable of brute forcing the AES key directly, after how many hash iterations would it be harder to brute force the ASCII key than the AES key directly...

Answer 1

There's no exact answer, and here's why:

Brute Force

We start with a 128-bit symmetric key. Assuming the algorithm (e.g. AES) isn't yet broken, we have to look at power consumption. Assuming 100% efficient computation devices whose technology far exceeds any computer, ASIC, graphics card, or other key-cracking device you can dream up, there's a minimum energy requirement for just flipping the bits to count that high. Wikipedia has done the math for us, and it comes out to, for a 128-bit key, the minimum energy requirement demanded by physics is approximately 10¹⁸ joules, or 30 Gigawatts for one year. Obviously with "real" hardware, the requirement would be several hundred thousand times that; more than the energy production of the entire world. So that's well outside the capability of any existing terrestrial body.

But if we move to a 256-bit key, the math gets more serious. Schneier did the math on this one in Applied Cryptography, and it's been discussed here before. To avoid boring you with repeated details, I'll simply cut to the conclusion: our sun does not produce enough power to accomplish this task.

Theoretically reversible computing (which may be possible with quantum computers) could cut the effective bit length by half, making such a project merely beyond the reach of any existing power, rather than beyond the reach of physics entirely. But that's all academic.

The take-away is this: brute-forcing a reasonably-sized symmetric key cannot be done. Not by you, not by anyone.

Equivalent Rounds

So, how many rounds of PBKDF2? If the attacker has to choose between waiting 10 years for the key derivation complete versus building a Dyson sphere around the sun, the PBKDF2 route is still faster. By any practical metric, adding more time to your key derivation means adding more time to the attack, and at no point does trying to brute-force the key ever become an option (unless the PBKDF2 route also requires an extraterrestrial construction project).

So, where's the equivalence point? When does brute-forcing PBKDF2 require the whole Dyson Sphere setup? The answer is: it depends. See, the whole point to using the hash process in your attack instead of guessing the key itself is so that you try fewer password. If you know the password is either "monkey" or "123456", then you'd rather guess only twice, instead of trying to by luck hit the correct hash in a sequential scan.

So the answer depends on the size of the dictionary your attacker will use in his attack. If he knows the password exact, then he only guesses once. And therefore, the brute-force attack will take exactly as long as the correct login. However long you make that out to be. If he expects to get it in two guesses, then the his brute force will take exactly twice as long as your correct login. If he has a dictionary of 100 words to try, then exactly 100 times as long as your correct login, and if your password isn't on his dictionary, then he cannot ever succeed, ever.

Some Practical Math

So to guarantee that his brute-force attack will be impossible, you also have to guarantee that your successful login will be impossible, because you have to account for the possibility that your password is the only candidate on his list.

If on the other hand, you want to go for a reasonable average, just do some simple division. Lets say you want the brute-force attack to take 1 trillion years. And let's say our password is 14 characters alphanumeric (so 1 out of 10²⁵). Assuming his dictionary is all alphanumeric passwords, that's 10²⁵ password guesses in 10¹² years (short-scale trillion), or 10¹³ guesses per year, or about 316900 guesses per second. That's for a fully-exhaustive pass through the list. Some password will be guessed first and some will be guessed last, we probably care about the average, not the max, so lets drop our guess rate in half. About 150000 guesses per second gets us half way through the list in the same amount of time.

So as long as we tune PBKDF2 such that it takes more than 1/150,000th of a second to guess each password, and we can guarantee that the smallest dictionary our password will appear in is the list of all 14-letter possibilities, then 1 trillion years it is.

Longer Passwords

Of course, 14 character random passwords are hard to come by. With 13 characters that shrinks our password list from from 10²⁵ entries down to 10²³, requiring about a 100x slowdown in cracking speed (1500 passwords per second) to keep our 1 trillion year average (technically that 100x is actually a 62x, because that's how many alphanumeric characters there are, but I'm rounding to powers of 10). Dropping another character off your length changes your numbers by another 62x each time.

The moral of the story is that what you're hashing matters so much more than how you're hashing. For example, a 22-character alphanumeric password is a 131-bit key, which even without using PBKDF2 at all is well beyond reason for trying to crack.

Caveat

Bear in mind that if the underlying crypto is ever broken, such that it can be attacked without guessing the key, then that will probably become the attack method of choice. But we know of no such attack in AES, nor do we expect one to ever exist.

Answer 2

From Colin Percival's paper on scrypt:

By using a key derivation function which requires 2^s cryptographic operations to compute, the cost of performing a brute-force attack against passwords with t bits of entropy is raised from 2^t to 2^(s+t) operations.

2,000,000 is about 2^21 iterations of SHA-512. In order for this to exceed the security offered by a 128-bit key, your password would need to have about 107 bits of entropy, or roughly equivalent to a 17-character password chosen randomly from uppercase, lowercase, digits, and twelve symbols.

Answer 3

The iterations are there to slow down the attacker. Let's suppose that the function is properly salted, so that the best an attacker can do is indeed trying out all potential passwords until a match is found. We define the password entropy to be equal to n bits if the best the attacker can do is, on average, to try 2^n-1 passwords: the attacker knows which passwords are more often chosen by users, and tries passwords in the "optimal" order, and this will work with that average success. (Note that "average" is a very important word here. All the maths fall down without that word.)

The use of "bits" comes from the fact that if the password is a sequence of k bits, such that all the possible 2^k sequences stand an equal chance of being selected by the user, then the entropy is, by the definition above, equal to k bits. See this answer for longer explanations in a famous case.

You then apply r iterations in an attempt to slow down the attacker. The computational cost for the attacker is then, on average, r·2^n-1. Thus, your goal is to get r and n sufficiently high so that this cost is prohibitive, and will not be achievable by the attacker (either the attacker deems it not worth the effort, or simply cannot). There is no security level beyond unbreakable so there is, indeed, a maximum number of iterations beyond which no actual security gain is obtained. Once the attacker is defeated, he is defeated. There is no way to defeat him more (though there could be a psychological gain in humiliating and overawing the attacker with an iteration count as high as Burj Khalifa). An important point is that the attacker's motivation depends on the value of the data which is protected by the password, so data of little value requires less protection.

Now there can be debate on the quantification of this "unbreakable" level. Traditionally, cryptographers have used "80 bits", i.e. 2⁸⁰ "simple operations", as the limit. A "simple operation" here is to be understood as an invocation of the underlying hash function (say, SHA-256) on a small message; it actually involves a few thousands 32-bit or 64-bit arithmetic operations. This level still holds quite well; the biggest published comparable effort was the cracking of a 64-bit RC5 key, with an ongoing 72-bit effort but noway nearing completion (see this page). On the other hand, this 80-bit limit was already used 20 years ago (that's this limit which implied SHA-1 with a 160-bit output, or DSA signatures with a 160-bit subgroup), and technology has improved since that time (see Moore's law for the usually quoted entry point in that debate).

Nowadays, "128 bits" is used as the "safe limit" for now and the next decades as well. In fact this includes a huge safety margin, but 128 is a power of 2, so it has a huge aesthetic appeal (if cryptographers used decimal instead of binary, they would have stopped at 100 bits).

In practice, though, you won't reach that level with your iterations. Realistically, you can expect normal human users to have passwords with entropy of 30 bits or so; more would be overly optimistic. The same users are known to have little patience (you are apparently ready to wait for 20 seconds, but most people won't be as patient). Thus, you may hope for a r counted in millions, not much more. This goes to, roughly, 2⁵⁰, i.e. a billion times easier than the traditional 80-bit limit of unbreakability. This leads to two conclusions:

1. You should use as many iterations as is tolerable for your users (including yourself), since a high iteration count implies a higher delay. You will run out of user's patience way before you reach the unbreakability limit.

2. It is always better to increase password entropy. The "correct horse" method results in passwords which are not hard to remember, but provide a substantially better entropy than usual methods (44 bits, as it was exposed).

Answer 4

" If someone wanted to crack it and had all the time in the universe (and several times over), would they do it faster if they went for the resultant hash or every possible ASCII for the original passphrase? "

That depends on the output width of the hash function. Suppose the output is a very low 32 bits and your "true passphrase" (btw what's true?) has 64 bits of entropy. Then probably the 32 bits take less time to crack, if you also know some clear text. The first one takes about 2^32 decryptions and the second one takes 2^64, though different, guesses

A long passphrase cannot be attacked by trying "every possible ASCII for the original passphrase", successfully. A dictionary based attack is used in stead. So the average recovery time calculation is different from the one trying all characters.

Why not successfully? Take for example a passphrase of 5 words, existing of just 28 lowercase characters. A dumb brute force scheme would have to test 26^28 = 10^40 combinations at maximum.

Did you consider taking a longer passphrase in stead of a substantial delay? The factor 2 million takes about 2 words extra when using a Diceware dictionary. Each words provide about 12.9 bits, see Optional stuff you don't really need to know