0

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.

Dan Kanze
  • 135
  • 9
  • 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

2 Answers2

5

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.

lynks
  • 10,646
  • 5
  • 29
  • 54
  • 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
  • @HamZaDzCyberDeV Okay, give me a few ideas to work with. I'm trying to get a better understanding of time. – Dan Kanze May 14 '13 at 16:14
  • @DanKanze most hashing algorithms used with passwords (bcrypt, scrypt, PBKDF2) provde a configurable **working factor**, that allows you to make it harder or easier to perform each guess depending on your needs. Your goal is to make it as hard as tolerable for legitimate users (i.e. how long they can wait for a successful login to happen) so the attackers will be able to perform less guesses per second. – mgibsonbr May 14 '13 at 16:25
  • @mgibsonbr Speaking only to a local context where a user isnt throttled. – Dan Kanze May 14 '13 at 16:26
  • @DanKanze There are so many parameters that can influence the taken time, for example 32-bit or 64-bit system, using a CPU or a GPU, the algorithm, the hashing technique used and it's parameters (salt or no-salt, how long is the salt and it's uniqueness, how many iteratians) etc etc... The best is to read about hashing functions and cryptography. FYI this isn't something to explain in a few lines. – HamZa May 14 '13 at 16:29
  • 2
    @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](http://security.stackexchange.com/questions/211/how-to-securely-hash-passwords?lq=1) – mgibsonbr May 14 '13 at 16:30
  • @DanKanze the fact that I list both 1000/second and 100 BILLION/second as possible attack rates should indicate to you that *it really does* depend on the situation. Trying to attack someone's Facebook account online is **very slow**, while trying to crack a poorly protected password hash is **very fast**. – lynks May 14 '13 at 16:31
  • @mgibsonbr I dont need textbook definitions. I need resources that do sprint tests using different methods of cracking to understand tradeoffs in time. Local context assuming zero throttling. – Dan Kanze May 14 '13 at 16:35
  • @DanKanze Then what hashing algorithm are you using ? – HamZa May 14 '13 at 16:37
  • @HamZaDzCyberDeV Does the computation of the hash really throttle the performance of bruteforcing? Or are there cracking methods coupled with specific hashing algorithms that drastically improve time? – Dan Kanze May 14 '13 at 16:45
  • @DanKanze There's no way to improve time if hashes/KDFs are used correctly. For instance, a key to decrypt a file can be derived from a password using PBKDF2 with 10000 iterations. There's no [easier] way to get that key without entering the right password and performing those 10000 iterations (i.e. brute-forcing the *key* will take a lot longer, since there are many more possible keys than passwords). If you increase to 1m iterations, the number of guesses per second will drastically decrease, but the legitimate users will be annoyed to wait several seconds/minutes for the file to open. – mgibsonbr May 14 '13 at 16:50
  • @DanKanze your use of the word 'throttling' is incorrect here. The point is that in order to *test* a candidate password, the attacker has to *compute* the hash for that candidate and compare it to the hash he is trying to crack. A good defender makes this computation process **slow**. – lynks May 14 '13 at 16:55
  • @mgibsonbr Right but here we are talking about bruteforcing the plaintext on an input console with zero throttling. So wether it was hashed with MD5 or SHA1, the computation of the hash does not affect the bruteforcing correct? – Dan Kanze May 14 '13 at 16:55
  • @lynks I understand that, but we arent talking about defence mechanisms, we are talking about time tradeoffs between algorithms by removing all of the variables around attacks "like defence mechanisms". – Dan Kanze May 14 '13 at 16:57
  • @DanKanze come join us in the [DMZ](http://chat.stackexchange.com/rooms/151/the-dmz) – lynks May 14 '13 at 16:57
1

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)

Community
  • 1
mgibsonbr
  • 2,925
  • 2
  • 21
  • 35