# How long does it take to crack PBKDF2?

How much time will it take to crack PBKDF2 while using a 9 character password? I'm not specifying any specific system or platform. If a brute force attack is made using the best ever super computer around how much time will it take to crack it?

-
Have you done any prior research regarding this topic? –  hunter Jul 17 '14 at 10:07
not much. But right now I am to find out the answers. –  Giliweed Jul 17 '14 at 10:10
The posting has too many questions to produce a useful answer. The Wikipedia article covers at least some of the questions. –  Dmitry Yanushkevich Jul 17 '14 at 10:10
Should I edit and ask only one? –  Giliweed Jul 17 '14 at 10:11
You could split this at least into 3 parts. Also, please check this page for guidelines on how to ask. –  Dmitry Yanushkevich Jul 17 '14 at 10:13

Firstly, How much time will it take to crack PBKDF2 while using a 9 character password? and how do I calculate the cost? I'm not specifying any specific system or platform. If a brute force attack is made using the best ever super computer around how much time will it take to crack it?

Unless the underlying PRF is broken, brute force and dictionary attacks are the only way to find the password. The time it takes depends on how the password is chosen, what iteration count is used with PBKDF2, and what computer(s) used. There is no generic answer except the formula:

• time to brute force = number of passwords to try * time to try one

Using the original default of 1000 iterations, a typical PC can try at least a few thousand passwords a second. A random 9 character lowercase password needs $26^9 \approx 2.7\cdot 10^{12}$ tries on average, which would take a PC a decade or two, at least. The largest supercomputers are about a million times as fast, which means it's a matter of minutes instead.

Secondly, Is PBKDF2 the best ever key generator up to now? If not then what is the most secure key generator or key derivation function?

It's the most widely studied. Others, like bcrypt and scrypt, are meant to be more difficult to crack using GPUs and ASICs, but haven't been studied as much.

There is also a password hashing competition currently running. It's winner may eventually be a good choice.

-
Is there any upper limit to output bytes generated from PBKDF2? –  Giliweed Jul 17 '14 at 10:24
How many passwords (9 charactes) does the largest supercomputer on earth generate with in 1s? –  Giliweed Jul 17 '14 at 10:27
@Giliweed, maximum output is $2^{32} - 1$ times the hash length. However, it is probably not a good idea to use more than one block of PBKDF2 output because it takes longer. Instead PBKDF2 -> HKDF works better. –  otus Jul 17 '14 at 10:30
@Giliweed, that time could be better spend on multiplying the number of iterations. You can find it explained, e.g. here. (Couldn't find a better match, but there should be. If not, feel free to ask another question.) –  otus Jul 17 '14 at 10:45
You have to make assumptions to get anything exact. Brute force is embarassingly parallel so you can simply divide the time it takes by the processing power, i.e. doubling # of CPUs halves the time. –  otus Jul 17 '14 at 10:49

PBKDF2 (as defined by RFC 2898) is a function of the form

$$DK = \text{PBKDF2}(\text{PRF}, Password, Salt, c, dkLen)$$

In most practical use cases, the $\text{PRF}$ is $\text{HMAC}$ instantiated with a Merkle-Damgård hash function such as $\text{SHA-1}$. The time to compute $\text{PBKDF2}$ is roughly linear with the iteration parameter $c$, all other things being equal. The output $DK$ has $dkLen$ bytes, and can be thought as a random-like function of $Salt$ dependent on $Password$, or vice versa.

When used to manage passwords, $c$ and $dkLen$ are typically assumed public; $c$ from 1000 to 100000 is common (much more tends to be taxing for normal use). $dkLen$ could be 16 (or other value making it practically impossible that a particular $DK$ is reached by chance). $Salt$ typically depends on the username, and should also include a server-unique value, preferably secret (at least in part). Normally, neither this secret, nor $DK$ values, should be accessible to an attacker. However PBKDF2 is here to act as a second line of defense should this information leak, and therefore the standard assumption when considering an attack using PBKDF2 to protect passwords is that all $(DK,Salt)$ pairs have leaked (as well as $c$ and $dkLen$); again, that itself should be avoided inasmuch as possible (which is not much more than it is possible to prevent an adversary from accessing an unencrypted backup of the system; notice that if an adversary somewhat can pwn the system, that's at least equivalent, and may give more direct ways to get at the passwords).

With these assumptions (and constant $c$), the best known attacks basically try various $DK,Salt,Password$ combinations, computing $\text{PBKDF2}(\text{PRF}, Password, Salt, c, dkLen)$ until that matches $DK$: this will reveal an acceptable password for the username extracted from $Salt$ on the system attacked, which will also be the original password with overwhelming certainty for common $dkLen$ (perhaps allowing to attack that user on other systems where he or she uses the same password, or a similar one). For large $c$, the attack duration is dominated by the evaluation of $\text{PRF}$ at least $c$ times for each $DK,Salt,Password$ tried.

If the passwords are random and equally likely among $N$ (e.g. consist of $n$ symbols each chosen randomly among $m$, leading to $N=m^n$), having many $DK,Salt,Password$ does not help, and an attack is expected to find the password of a given user with odds $p$ after no less (and about) $N\cdot c\cdot p$ evaluation of $\text{PRF}$; that's an expected $N\cdot c/2$ $\text{PRF}$ evaluations. For example, with the iteration count $c$ set to 100000, $m=26$, $n=9$, and $\text{PRF}$ HMAC-SHA1, an attack is expected to require about $2^{60}$ evaluations of the round function of SHA-1. That's about the number of hashes performed every 5 second for the purpose of bitcoin mining by mid 2014 according to that source, or what could be done by a 2000-core general purpose computer in a year of operation. So with the iteration count set to 100000, the expected duration for an attack ranges from little for a resourceful adversary doing the job with ASICs or FPGAs, to somewhat too much for the average guy with a bunch of PCs.

If the passwords are chosen by users, the best attack tries the password from most likely to least likely, for each $DK,Salt,Password$ available. For 8 letters perhaps 1% of users will pick password as the password, and even for 9 letters, with a few hundred users, finding a valid $(username,Password)$ will be trivial for any adversary worth consideration after $DK,Salt,Password$ leaked.

There are better alternatives to PDKDF2; notably scrypt, which requires a parameterizable amount of RAM to perform the calculation, making ASICs and FPGAs much less practical; and can be distributed on multiple cores, allowing a corresponding increase in the iteration count (thus security) in some setups. As pointed in another answer, that's an active research area.

-
If $DK$ is e.g. used as a key for a symmetric encryption scheme and the attacker has access to some cipher text and partial information about the plain text, testing if a $(DK, Salt, Password)$ guess is correct usually doesn't require prior knowledge of $DK$. –  Henrick Hellström Jul 17 '14 at 13:09
@Henrick Hellström: very true. That's a possible usage of PBKDF2, not the one I had in mind with my "used to manage passwords". –  fgrieu Jul 17 '14 at 13:31