What makes one random strong password more resistant to a brute force search than another

Question

The only way to do this is by making an educated guess on how the brute force algorithm works or probably works.

Lets say you were trying to crack a combination lock with 3 discs each with 10 notches for 0-9.

I would start with 000, 001, 002 and so on, using my very complicated cracking algorithm, the code which would get cracked on the last attempt would be 999 therefor in this instance its the strongest/safest.

We can assume a real algorithm wouldn't just increment through the numbers or work its way through the ascii table.

for example with a 3 digit numeric code you're probably far better off trying 123, 000 and 111 before 001 when trying to crack it. common pin numbers

This goes for other ascii characters

• lowercase is far more commonly used than uppercase in passwords(definitely)
• special characters are used far less that alphanumeric chars(definitely)
• special character "common substations" are more common than other special characters s$,4A@ i!.(probably).
• 0,1 and 9 are more commonly used than other numbers. (seems likely)

Using the common password method "at least 8 characters including one uppercase letter, one special character and alphanumeric characters" I've created a random* very strong 8 character password of Fs9@lw$a.

My theory is that the following random* strong passwords would be progressively harder to crack.

• Fs9@k0$a (password)
• Fs9@k0$q (changed "a" to the least common letter in english "q")
• FS9@K0$q (convert lower to uppercase leaving 1 lowercase)
• FS5@K7$q (change common numbers to other numbers)
• FS5&K7?q (changed common special Chars with other special chars)
• *%.&K7?q (replace uppercase with special char leaving 1 uppercase char.
• *%5&K7?q (replace numbers with special char leaving 1 number.

I am looking for a complete(ish) list of characteristics that a "brute force resistant" password should/n't have.

I would assume that at the top of the list would be the password length, for the example i only used 8 characters ideally you would use the maximum allowed.

Answer 1

If by random you mean select with equal probability out of some well-defined set of possible passwords, then the strength of the password is a function of the size of the set. In your example, the set is that of three-digit sequences (000, 001, ..., 999), and this set has 1,000 members, so an attacker succeeds on average after 500 guesses.

I would start with 000, 001, 002 and so on, using my very complicated cracking algorithm, the code which would get cracked on the last attempt would be 999 therefor in this instance its the strongest/safest.

We can assume a real algorithm wouldn't just increment through the numbers or work its way through the ascii table.

We don't need to assume anything. What's confusing you is that, for any given random choice, there are some orders that crack it much sooner than average. For example, if we know that the PIN is 999, the algorithm that tries all combinations in descending order is optimal.

But the attacker doesn't know ahead of time that the code is 999, so why would they pick that algorithm? If the code is 000—which is just a likely as 999—the backwards iteration algorithm is the worst one. If you try and do some compromise like 000, 999, 001, 998, ..., then if the code is 500 it'll be really bad.

This argument generalizes: if the code is chosen at random, with all codes getting equal probability, and kept secret from the attacker, then for any algorithm the attacker tries the probability that their algorithm will find the code in very few tries is equal to the probability it will find it in the complementarily pessimal number of tries. It all averages out—if the set has N codes, the attacker succeeds in N/2 tries on average.

for example with a 3 digit numeric code you're probably far better off trying 123, 000 and 111 before 001 when trying to crack it. [link to common pin numbers]

If the code was chosen uniformly at random (all codes equally likely), you're not.

Note, on the other hand, that if the codes are not chosen uniformly at random (some are more likely to be chosen than others), then yes, some guessing orders are expected to finish sooner than others. That's for example how practical password cracking works—the dictionaries and mutation rules and so on are just tricks to try likelier passwords ahead of unlikely ones.

My theory is that the following random* strong passwords would be progressively harder to crack. [...]

You keep using the word "random" but I think you need to stop and think carefully about what you mean by this. The key concept here is a discrete uniform probability distribution. If your codes are chosen that way, there's no clever order tricks to be had at all, period.

I am looking for a complete(ish) list of characteristics that a "brute force resistant" password should/n't have.

Two properties:

1. Strength: It should be chosen at random with equal probability out of a sufficiently large set.
2. User friendliness: It should be easy to remember and easy to input into the devices where the user needs to. (This can be relaxed a lot if you use a password manager that autofills password fields or allows for copy/paste.)

That's it. A simple system that arguably meets these requirements is Diceware. (There is some debate on how memorable the passphrases are, and some proposed improvements to the word list.)

Answer 2

You're correct that:

The only way to do this is by making an educated guess on how the brute force algorithm works or probably works.

Unfortunately, not all brute force algorithms are the same, and new methods for optimizing brute force attacks against user-generated passwords are being developed all the time. If you were to come up with a list of characteristics that a "brute force resistant" password should have, I could easily write a brute force algorithm which would try those passwords first, thus making them actually weaker against my algorithm than other passwords would be.

In reality what makes passwords strong against brute force attacks in general is not any specific format or set of rules, but their degree of unpredictability. One way to estimate the unpredictability of a password is to determine the entropy of the method used to generate it.

To illustrate how password entropy works, let's assume you use a very simple scheme to generate your passwords. To generate each password, you flip a coin 20 times. Each time the coin comes up heads, you add a 1 to the password; each time it comes up tails, you add a 0. This results in a password which is a random string of 20 ones and zeros. In this scenario, there are 2²⁰ possible passwords, and each possibility is equally likely to have been chosen. We can say this password generation method has log₂(2²⁰) = 20 bits of entropy. (Pretty weak, but that's beside the point for this example.)

Now let's assume the attacker knows that you use this scheme (the worst-case scenario) and wants to try to crack one of the passwords you generated. Because there are 2²⁰ possible passwords and each possibility is equally likely to have been chosen, it will take the attacker 2²⁰/2 = 2¹⁹ ~= 524,288 tries on average to crack it. The attacker might crack any given individual password on their first try or their last try, but it will always take 524,288 tries on average, regardless of what strategy the attacker uses to decide which passwords to try first.

You can use this same method to estimate the entropy of just about any password generation scheme where the passwords are chosen at random. For example, let's say you generate your passwords by choosing 6 words at random (allowing duplicates) from a 7776-word dictionary of common English words. (This is the scheme used by diceware.) With this scheme, your password has log₂(7776⁶) ~= 77.55 bits of entropy, and will take ~2^77.54/2 ~= 110 sextillion tries to crack on average. Again, with this scheme the order that the attacker tries each possible password in is irrelevant.

Thomas Pornin goes into password entropy in a lot more detail in his answer to the popular "Short complex password, or long dictionary passphrase?" question. I highly recommend you check it out.

Answer 3

I'm afraid you're approaching this very broad problem from too narrow of a viewpoint. There are many things to consider before diving into the specifics of "which characters to use".

First, what kind of threats are you worried about? Are you concerned that your Yahoo! password is going to be misused? Are you concerned that if a thief learns your Yahoo! password that he will attempt an Account Take Over of your bank account with the same password? Or is this password guarding your network, where you have invaluable business secrets that have attracted the attention of foreign spies?

For most people, the second kind of threat is both the most relevant and the most common: someone who learns a password from a breach will often try the password on various banking and shopping web sites. This is called Account Take Over (ATO), and it doesn't matter to the attacker how weak or strong your password is. He's just going to try your email address and password at each of a couple hundred sites, and if he doesn't get a match he'll move on to the next email and password he got from the breach. Brute force is almost irrelevant to the password strength in this case.

Your best defense strategy against this attack is to not reuse passwords. Again, it doesn't matter how complex they are, because the attacker already has them. As long as you aren't using the same password in multiple places, you're ahead of the game.

Also note that this strategy relies a bit on "not outrunning the bear, just outrunning the guy you're with" - if the attacker recovers 10% of the passwords from a large stolen database, he may be more interested in monetizing what he's already stolen than in working harder to crack the rest of the passwords.

But let's look at the case where the attacker wants YOUR password, and decides to apply brute force. Let's say an attacker gets the hash of your password from a breached database, or from hacking into your system, and starts trying to guess your password. What can he do?

Don't underestimate the attacker. 5 years ago someone put a bunch of graphics cards into a computer, and wrote a CUDA program to test password hashes as fast as possible. At the time, his machine was capable of testing 348,000,000,000 hashes per second; modern graphics cards are even faster today. That means if you select your password from a set of 64 possible upper and lower case characters, digits, and common symbols, an attacker with those resources can test every possible 7-character password in under 13 seconds. Think this is out of reach of your average criminal? A thief with access to a botnet of hijacked PCs on the internet can set 10,000 computers to attack your password simultaneously, and some percentage of those computers will have graphics cards to help accelerate his attack.

What all this means is that your security practices and password lengths matter far more than your specific choices of letters, digits, and symbols. Choose a 12 character password at a minimum; otherwise at least meet the site guidelines for password complexity. And never reuse passwords. A password manager application, or even a notepad in your pocket will serve you well.

Answer 4

That depends on the brute force script. If (to use your example) we start cracking from 001 through 999, then 999 is the best option, but it's also the worst option if we start from 999 backward. Therefore, if we are to assume that each value is incremented or decremented, I would suggest going for something partway between both. To do that, we need the character codes. Python has handy functions for that: ord('A') yields 65, for example, and chr(65) yields "A". So I suggest setting the first several characters to symbols with character codes close to 127, which is partway between 0 and 255, and using long passwords.

(However, I have to admit I like xkcd's opinion on this.)

Answer 5

The simple answer is length. Every character adds a magnitude of complexity. You can select random characters as you wish but if someone knows how you selected your random password, any tricks can be reversed weakening the password.

If you add another character there is suddenly 200 odd times more possible combinations