How long does it take to crack PBKDF2?

Question

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?

Answer 1

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.

Answer 2

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 500000 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 they 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 was 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.

---

Update: by late February 2023, bitcoin mining reportedly hashes at an aggregate rate of ≈300.000.000 TH/s (300 EH/s), where H is two SHA-256. Doing so for 10 minutes (the designed-in average time to find a so-called block) must cost less than the trading value of 6.25 bitcoin (the so-called reward by 2023) plus (comparably minor) transaction fees. This means $2^{61}$ SHA-256 are done for a marginal cost less than one USD in a bitcoin context. The bitcoin hashing infrastructure is not directly fit for PBKDF2, but this tells how insecure PBKDF2 with common parameters would be facing adversaries using dedicated ASICs.

Therefore PBKDF2 should now be considered obsolete. There are better alternatives, notably Argon2, or it's predecessor scrypt: they 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.

Such memory hardness, absent from PBKDF2, considerably increases practical resistance to brute-force password search at equal cost for legitimate user. NIST acknowledges that, but still endorses PBKDF2. I wonder how much that's because US authorities are good at breaking it.

---

† Even though SHA-1 has weaknesses, we have good assurance that the use of HMAC makes them immaterial. If PBKDF2 must be used for some reason, and there's a choice for the hash, prefer SHA-256 if there's hardware support for it on the legitimate platform, and there's none for SHA-1; or SHA-512 is there's no hardware support for either. In any case, make $c$ as high as practical.