# Bruteforce Passphrase of Dictionary Words

Consider the all lowercase passphrase:

"lazy fox haggles treaty"

Assume all four words are in a dictionary of 2000.

Bruteforcing word combinations, how long does it take to crack this password at 1000/s?

How does this change if there are upper/lowercase?

How does this change if there is a dictionary of 10000 words?

## Edit:

Attacker is not throttled, local context.

-
Please provide more information. What are you trying crack? Are you trying to recover single-round MD5 hashes? Are you trying to crack `.rar` or `.zip` archives? The speed hugely depends on what you're trying crack. – Adi May 14 '13 at 16:18
@Adnan I guess I'm trying to figure out the range of contexts and how they are different for each senario. Pointing to litterature is helpful as well. – Dan Kanze May 14 '13 at 16:20
I hardly think you'll find a book/paper listing every possible encryption/hashing algorithm and their implementations (could be in the hundreds of thousands). – Adi May 14 '13 at 16:23
@Adnan Sure mabye not every single one. Broad categories, unique approaches. Surely one pattern doesnt vastly outpreform another under a nearly identical context with slight variation. Im just trying to understand a scope of time. – Dan Kanze May 14 '13 at 16:25

4 samples from a dictionary of 2000, gives a passphrase-space cardinality of 20004.

Time to crack at 1000 attempts per second;

20004 / 1000 = 1.6E10 seconds = 507 years.

With possible uppercase first-characters you have a cardinality of 4,0004 (twice as many words per slot). Which is quite a bit larger, and would take 8,117 years at 1000 attempts per second.

A dictionary of 10,000 words would yield 0.3 million years crack time at 1000 per second.

Whether this is a realistic threat model depends entirely on your situation. If you are talking about cracking the passphrase offline after it has been hashed with a single iteration of MD5, a determined attacker can reach over 100 billion attempts per second, which gives you just 27 hours rather then 0.3 million years in the last example.

-
This is brute forcing combinations of words correct? i.e. "lazy + turtle" , "lazy + snail" ... ? Would you consider 1000 guesses per second realistic or is type of attack preformed much faster? – Dan Kanze May 14 '13 at 15:30
This is attempting all possible combinations of 4 words. And 1000 guesses per second is realistic for an online attack, such as a web-service. In an offline attack, it varies, but can be as much as 100 billion attempts per second in the worst cases (such as single iteration md5). – lynks May 14 '13 at 15:31
On a 2.5 ghz processor (average consumer PC) how many guesses per second is reasonably possible? i.e. is 100 billion attempts for an average PC reasonable...? – Dan Kanze May 14 '13 at 15:58
@DanKanze That totally depends on the used algorithm. – HamZa May 14 '13 at 16:02
@DanKanze The difficulty of performing the hash function itself is what throttles the guess attempts. In other words, even with the CPU/GPU running at full power, it's not possible to peform more than X guesses per second. To learn more about the subject, I'd suggest starting with this question – mgibsonbr May 14 '13 at 16:30

If the words are randomly selected, then Iynks' answer applies, but it could be a lot worse if the passphrase forms a [gramatically valid] sentence. Given a starting word (from the 2000 word set), not every other word (including itself) could follow it and still produce a valid sentence, so the choices are much more narrow. If you let users choose their own passwords, that would probably happen. And attackers are also likely to try those combinations first.

As for time to crack, to answer that we need to know more about your threat model. I see from your edit that you're trying to protect something installed offline, but are you worried that only "common" users will be interested in cracking those passwords, or are you expecting a more determined and skillful attacker? A commong PC trying to crack passwords with the CPU (or even the GPU) will perform far worse than what an attacker can achieve with a cluster of them or maybe some dedicated hardware.

As explained better in this question, your best defense should be a good hashing algorithm with a configurable work factor. PBKDF2, bcrypt or scrypt should be fine (refer to that question for a more in-depth explanation of pros and cons of each one). As for time to crack, it will all depend on the work factor - you can choose one where only a single attempt can be made per second (or less), or one where millions or billions are possible. It just boils down to what delay is tolerable by your legitimate users each time they attempt to enter the password. (for hard numbers, the only way to be sure is benchmarking on a particular machine)

-