9

Assuming a 6-character password uses the mixalphanumeric charset, giving each character a character set of 62 and the entire password a keyspace of 62^6 = 46.6 billion (if my calculations are correct)...

Would it be faster to brute-force the password, or generate the entire keyspace in a dictionary and use that dictionary in a dictionary attack?

Are the two approaches considered equivalent, or would there be a difference in performance? Is the latter often done? If not, why not, and if so, why isn't it more common?

Note that the example mentioned is just that, and the question I'm asking is a performance one regarding the two methods, irrespective of a particular password's keyspace and actual time taken.

Hashim Aziz
  • 969
  • 8
  • 21
  • 4
    What's the difference between brute-forcing and this kind of "dictionary" attack? – grc Mar 05 '17 at 00:53
  • 2
    That's exactly what I'm asking. – Hashim Aziz Mar 05 '17 at 01:13
  • The usually accepted premise is that dictionary attacks are always faster than brute-force attacks. This question is, in so many words, asking whether that's purely because dictionary attacks are working with smaller keyspaces, or whether there are other factors that make them more efficient. – Hashim Aziz Mar 05 '17 at 01:15
  • 5
    The former - dictionary attacks are only faster because they make assumptions about the password to significantly reduce the "keyspace". – grc Mar 05 '17 at 01:27
  • Fair enough. I see you quoted "keyspace" - is that not the proper term for what I'm looking for? I always figured it was, in the sense of the cryptographic definition. – Hashim Aziz Mar 05 '17 at 18:52

3 Answers3

10

There is no difference ... until you get into the implementations.

Efficient cracking platforms like hashcat and John the Ripper execute bruteforce directly on GPU/CPU using optimizations that make them far faster than equivalent candidate passwords could be fed into the cracking process from an external dictionary.

True bruteforce and related attacks (like mask-based and rules-based attacks) should always be faster than a pure dictionary attack.

Update: My answer applies for fast hashes. Pascal is right in his answer that if the hash is slow enough, it would be the same.

Royce Williams
  • 9,128
  • 1
  • 31
  • 55
  • 1
    This is confusing. Dictionaries are used because they contain passwords that are much, much more likely than something like "11_qZ*". A brute force attack will simply try every possible combination in lexicographic order. A dictionary attack will try the more likely passwords first, and therefore will be much, much faster in general. Rules and masks come in handy to extend a basic dictionary, e.g. to not just try "primo" but also "pr1mo", "prim0", pr1m0" and so on. Whether you feed the GPU or CPU dictionary words or something else shouldn't matter. – Out of Band Mar 05 '17 at 19:14
  • Generally, you're right, of course - but the original question is asking about a "dictionary" that is artificially "brute force" -- recreating the effect of a bruteforce attack. The asker didn't realize the value of on-chip bruteforce, so was asking about the difference. – Royce Williams Mar 05 '17 at 21:14
  • Fair enough - makes sense seen from that angle. – Out of Band Mar 05 '17 at 21:59
4

Any meaningful answer will have to take into account some specifics, for example which hash function was used to protect the passwords.

If you created a dictionary of all possible combinations of passwords, beginning with "111111" and ending with "zzzzzz" (assuming just uppercase letters, lowercase letters and digits), and you didn't sort this dictionary by password likelihood, but kept it in lexicographic order, the question would become which was faster - feeding these dictionary strings into your password guesser or having the password guesser create the combinations on the fly.

To answer that question, we must know where we store our dictionary, which is large enough that we probably can't fit it entirely into memory, so we'll need to store it on a hard drive.

It's also important to know that hard drives (the magnetic, rotating disk variant, anyway) have access times in the millisecond range. RAM is orders of magnitude faster, but still slow compared to L1 cache, which again is much slower than direct register access in a CPU. Unfortunately, general purpose CPU registers can only store maybe 128 bytes in total, and L1 cache only stores a few kb in total.

Again assuming you were working with a computer that had 8 GB of memory set aside for you to use, you could keep about 1 billion dictionary entries in RAM at the same time. That's about 2% of the whole key space.

If you loaded your dictionary from the hard drive, you'd need to load a total of 325 gigabytes of data (in junks of maybe 4 GB each - you'd always load 4 GB of passwords while trying the passwords in the other 4 GB). Even with SSDs, that would take a while.

Now if you were dealing with a hash function like md4, hashcat would easily exhaust your candidate passwords before you could load the next batch, because on a modern GPU it can literally test billions of passwords each second. In practice, you can't load candidate passwords that fast from hard disk. On the other hand, if you were trying to attack passwords encrypted with a hash function like bcrypt, loading candidate passwords from hard drive wouldn't even make a dent in the time needed to successfully attack the password, because even modern GPUs can't bcrypt fast enough to exhaust 500 million candidates before the next 500 million can be loaded from hard drive.

Let's see if creating the passwords on the fly, instead of loading them into RAM in huge chunks, would be faster:

CPUs have some interesting properties. For example, they use instruction prefetch, branch prediction and tentative execution to execute code before it's actually known whether it should be executed or not. Together with the CPU cache, this means that if you run a very small, tight piece of code, such as code to enumerate all possible combinations of a given bit length, it can basically run entirely in the CPU, never touching (slow) RAM. Small passwords (6-8 bytes) easily fit in a single CPU register, 16-byte-passwords still fit in two registers. Code to produce the next password candidate from the last one is as simple as using an "add" instruction, which is one of the fastest CPU instructions there is. So I'm fairly confident that you could generate every password combination much faster than you could load the whole list of them from an external source.

But again, the time a CPU (or GPU) would need to calculate an actual bcrypt hash to compare against a hashed password would dwarf the time required to generate the candidate passwords.

So the method of password generation simply isn't that important for well-protected passwords. It only matters when dealing with weak or very fast hash functions such as md4, md5, sha1 etc.

Conclusion

If you assume every password is equally likely, then generating all the passwords one after the other (brute forcing) on the fly makes more sense, because you won't need to keep huge dictionaries on your hard drive. You can create them faster on the fly. This is why nobody keeps unsorted password dictionaries on their hard drives for stupid brute forcing.

On the other hand, if you admit that some passwords (think "123456" and "password" are more likey than others (think "1qHGmR"), then creating a dictionary of these passwords and loading that dictionary into RAM, and maybe using some rules to create derivatives such as "sarah1997" and "sarah1998" from the base dictionary entry "sarah", is the way to go, because it will pretty much always be much faster.

That said, if you're actually dealing with 6 letter passwords and a weak hash function, it won't matter much either way, because hashcat and compatriots can exhaust a 6 character keyspace by brute force in a matter of minutes, hours or days, depending on the hash function used and the power of the available GPU rig.

Out of Band
  • 9,150
  • 1
  • 21
  • 30
  • Apologies it's taken me so long to get round to reading and accepting this, and thanks for a well-thought-out answer. – Hashim Aziz Sep 05 '22 at 18:14
2

From an implementation standpoint, it's safe to say that it'll be quicker to have an algorithm that knows it's doing brute force rather than one going through a lookup table one by one which would inherently add a lookup overhead for each attempt which wouldn't exist in the former.

Your algorithm will be faster doing brute forcing in the code with nested loops for example rather than one extra step for lookup (disk read or ram read) for each attempt.

Wadih M.
  • 1,102
  • 6
  • 20