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

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...

-

## 4 Answers

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 1018 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 1025). Assuming his dictionary is all alphanumeric passwords, that's 1025 password guesses in 1012 years (short-scale trillion), or 1013 guesses per year, or about 316900 guesses per second.

So as long as we tune PBKDF2 such that it takes more than 1/300,000th of a second to guess each password, and our password is at least 14 letters long, then 1 trillion years it is.

## 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.

-
Besides the notes on practical impossibility and the exception of broken algos, isn't this basically a longer way of saying that to achieve a given level of security (e.g. equivalent to a 128 bit key), the number of iterations is a function of password entropy? (As in @Stephen's answer)... – AviD Oct 24 '13 at 12:04
@AviD almost -- there's one more critical bit: there's not direct conversion in the amount of time required per hash iteration versus time required per AES attempt. You can time how long it takes on your computer with your software, but this question asks about theoretical limits, not a specific Intel CPU. So even with Stephen's answer, you can't get from here to there. – tylerl Oct 24 '13 at 16:41
I think sun limited Crypto is sufficient :D +1 – Billy ONeal Oct 25 '13 at 6:34

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.

-
Brilliant, so you could actually generalize this to give a formula, based on password entropy providing how many iterations to use? – AviD Oct 24 '13 at 6:23
I suppose you could, yes. – Stephen Touset Nov 14 '13 at 22:37
Unfortunately, in practice, there's only a narrow band of passwords which you can practically strengthen to the maximum theoretical value. For instance, if we're limiting ourselves to 2,000,000 iterations or fewer (which is already well higher than the typical number of iterations recommended, which is typically in the hundreds of thousands), you could fully strengthen 17 to 21 character random alphanumeric passwords (22+ characters is already more than 128 bits of entropy). Interestingly, adding 20 symbols to the password corpus doesn't change this number at all. – Stephen Touset Nov 14 '13 at 22:48
Strengthening to be equivalent to 256 bits of entropy would require a 40–42 character alphanumeric password, or a 37–40 character password if 20 additional symbols are possible. – Stephen Touset Nov 14 '13 at 22:50

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 2n-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 2k 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·2n-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. 280 "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, 250, 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).

-

" 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

-
@tylerl kkarl88 uses passphrases, "password is at least 14 letters long" would not apply. Also "to generate a hash which is used as the cipher's actual key" means AES is out of the equation. – Dick99999 Oct 24 '13 at 21:01