Brute Force In Order Or Random?

Which is faster, on average to find the original plain text of a hash: brute force in-order, or with random plaintexts?

-
Assume your plaintext is in a space that can be enumerated `N, N+1, N+2, ..., M`. Your hash function ensures that finding `H(X)` for any `X` gives no new information about some other `H(Y)`. Assuming in-use plaintexts fall uniformally at random within your enumerated plaintext space, then on average neither strategy (ordered or random guessing) will be any faster. The ordered approach would save you memory in an implementation, though (you store only the last guessed plaintext, rather than a full list). Note that the real world might disobey my above theoretical assumptions. – apsillers Oct 28 '13 at 16:53

Mathematically, we assume that the user creates his password using a probability distribution that the attacker knows perfectly. The attacker then generates the passwords to try in order of plausibility. When several passwords have the exact same probability of being chosen by the user, then the order in which the attacker tries them does not matter for the average success rate.

The hypothesis of "perfect knowledge" by the attacker is the only one which allows for sustainable risk analysis. For instance, suppose that you begin in a situation where users choose their passwords at random, uniformly, in a set of N possibly passwords. Attackers then customarily explore passwords in lexicographic order. Noticing that, a user may then say to himself: "hey, I will begin my password with 'zzz' so that the attackers try that last. How cunning of me !". However, this won't last: attackers will adapt, and will begin to try passwords in reverse order. Our witty user will then choose a password which begins with "mzz" or "naa", so as to be in the middle of the range, at a "safe distance" from both kinds of attackers. This will only prompt some attackers to start exploration at the middle of the range too. And so on...

This example shows that the advantage that a user may gain over attackers based on asymmetry of information is, at best, transient in nature, and cannot be reliably quantified, because it depends on the "smartness" and evolution speed of attackers. So we prefer to assume that attackers try passwords in the "optimal" order, i.e. that they already know how we generate passwords.

Under these conditions, the best that user can hope for is uniform selection: when there are N possible passwords, and each password has probability 1/N of being selected, the attack's average cost is N/2. The interesting points being:

• With uniform selection, the attack's average cost is always _N/2_; there is no selection strategy which makes it faster or slower.
• When there are N possible passwords, for any distribution of probability of selection, the average attack cost of the best attack is always, at most, N/2. This is easily seen by considering that the attacker may try passwords in a random order, and that one will have average cost N/2 regardless of the user's strategy.

To some extent, this in fact means that random order is the attacker's strategy which minimizes the attacker's risks. Exploring the N possible passwords in a random order guarantees an average cost of N/2, regardless of how cunning the user might have been in his password selection strategy. From the point of view of the attacker, using a specific, defined order runs the risk of being outwitted by the user. Attackers are rational beings too: we assume attackers to have perfect knowledge of our password generation strategy because we could not evaluate our risks otherwise; similarly, attackers assume that users could be fully aware of the order of password space exploration and select passwords based on this knowledge, so rational attackers react by enforcing a random order.

All of the above, though, is for a known, finite space of possible passwords. This is what would apply, for instance, to old Unix passwords with the DES-based "crypt" function: the space is the set of all sequences of 8 ASCII characters.

In many practical cases, the space of passwords is more open-ended, and the attacker will have a rather low success rate: he will crack some passwords, but not all. In that case, the password exploration order does not matter much: for each password, the attacker tries a complete space of N passwords, which either works (the space contains the user's passwords), or, more often, does not. For all cases where the attack does not work, the attacker's cost will be that of N tries, no more, no less -- and this does not depend upon the order in which the attacker tries.

So the practical answer is: it does not matter.

-

It should make little difference statistically, it's the hash calculation that takes the computing power and not the plain text choice. I suppose if I had to make the choice I'd go for in order simply because it could be a slightly less intensive calculation, which over time could make a bit of a difference as it may allow the system to put just that bit more memory and CPU into hash generation.

It all comes down to how the developer has coded the mechanism to chose plain text sequentially, and randomly. I would simply try both under controlled conditions and see whether there's a significant difference in cracks per second.

As for is there a statistical reason to chose one or the other, then no.

-

In practice, the fastest will be to go in order with input ranked from most to least common for common passwords before moving in to less common things. If it is truly random, going in order vs random makes no statistical difference as your odds on each guess are exactly the same, but in practice, people aren't good at being random, so the better you can reduce the randomness in your guesses, the faster you will get a hit.

You still won't see a statistical difference choosing simple brute force (a, b, c,...aa,ab,... etc) vs choosing randomly though. You have to put some intelligence in the guesses to do better than random guessing.

-