Patterns in passwords

Question

I am posting to ask about two conflicting password recommendations. I know only bits and pieces about cryptography. Let me begin by checking a basic assumption: in a cracking attempt, a string is hashed and compared to the target, so that a wrong guess provides no information other than eliminating that particular string. Is this correct?

My questions relate to this recommendation on grc (2012)

[A]fter exhausting all of the standard password cracking lists, databases and dictionaries, the attacker has no option other than to either give up and move on to someone else, or start guessing every possible password. Once an exhaustive password search begins, the most important factor is password length! The password doesn't need to have “complex length”, because “simple length” is just as unknown to the attacker and must be searched for, just the same. “Simple length”, which is easily created by padding an easily memorized password with equally easy to remember (and enter) padding creates unbreakable passwords that are also easy to use.

On the other hand, according to this, the keepass password meter

searches for patterns, like e.g. popular passwords (based on a built-in list of about 10000 most common passwords; variations by upper-/lower-case and L33t substitutions are detected), repeated sequences, numbers (consisting of multiple digits), constant difference sequences, etc.

and reduces the quality (entropy) score accordingly. This topic discusses fortuitous patterns in randomly-generated strings; the answer said that the chance of a weak password resulting is negligible. Keepassxc rates the examples given there as follows: al#k2j$9gjKDm5%l 88 (good); *g3RpasswordnG&4 53 (weak); password%G@fDnBv and Nf!hFm$xpassword 46 (weak). Strings with "simple length" are rated very low, e.g. d0G............. 19 (poor).

Have things changed so much since the grc page was written in 2012? Does the keepass meter reflect common search strategies? How widespread are things like rule-based attacks? Or are patterns bad mainly because passwords with patterns are considered more likely to have been used and thus to appear in databases?

Answer 1

TLDR: The strength of the password depends on how much resources an attacker would need to break it. Any pattern makes password weaker. Increasing the length increases the strength, provided there are independent password parts.

Formal

The higher is the entropy, the more resources are needed to brute-force the password. Any rule applied for password generation reduces the entropy. Patterns are just a small subset of rules. Thus, any patterns reduce entropy and make passwords weaker. Padding is also a type of rule and thus it reduces the entropy. You should assume that the attacker knows your password generation rules, and compute the entropy for such case. Then increase the length until you get the desired entropy.

Computational

If password generation uses some rules, or patterns, this means, that the attacker does not need to test every possible random sequence, but essentially less password candidates. For instance, 10 random English characters mean 26^10 (= 2^47) password candidates. But if the attacker knows that these 10 characters are not absolutely random, but mean a word from a 100 000 (=2^17) words dictionary, then there are only 100 000 cases to test. 2^47/2^17 = 2^30 ~= 1 000 000 000 less password candidates. In other words, 1 000 000 000 less time and 1 000 000 000 less power which means 1 000 000 000 less money needed for brute-forcing.

To padding: Choosing the padding character means 7 bits entropy (if chosen from 128 characters). The random padding length up to 50 (using length like 1000 is hard from usability point of view) means about 6 bits entropy. This gives 13 bits entropy. It is like adding just 2 more characters without padding.

The number of rules that can be easily remembered and easily applied by humans is limited. Even if the attacker considers as many as 1 000 rules, still this reduces the number of password candidates essentially.

Nevertheless, can I use patterns?

Yes. Provided the password is sufficiently long and has sufficient number of independent parts.

Example: Let say, you used some pattern and created a password that has 20 bits entropy. If you generate one more such password using the same pattern, independent on the first one, and concatenate them, then the new password will be twice longer and will have twice more entropy, 40 bits. Adding one more such password leads to 60 bits entropy, etc.

The most prominent example of this approach is diceware. There is a dictionary of 7 776 words. Picking a single word randomly gives about 13 bits entropy. A password consisting of 5 such words has 65 bits entropy, 7 words means 91 bit entropy.

You don't even need to make your password generation algorithm secret. It can be known to anyone. It you meet the conditions above (independent parts and sufficient length), you can still reach the any strength that you need.

Answer 2

Both statements basically say that easy to guess or to derive passwords are insecure no matter how long they are, i.e. known passwords (dictionary), known ways how users mutate passwords (i.e. derive new versions from the ones in the dictionary), known pattern how users create long but easy to remember passwords ...

There is one sentence I have problems with though:

“Simple length”, which is easily created by padding an easily memorized password with equally easy to remember (and enter) padding creates unbreakable passwords that are also easy to use.

The statement about the strength of the generated password is only true, if the padding is practically impossible to guess to the attacker. But this is basically only true if using a long random string only known to the user - which is contrary to the claim of "easy to remember". Using common easy to remember words or phrases as a padding can instead be easily incorporated in the heuristics for dictionary based attacks.

Answer 3

The other answers cover the technical aspects very well so I want to focus on these questions

Have things changed so much since the grc page was written in 2012? How widespread are things like rule-based attacks?

Most of the grc quote you included is correct but the very first line is flawed as it ignores rulesets used on the worlists (as @mentallurg wrote any type of rule reduces the entropy):

[A]fter exhausting all of the standard password cracking lists, databases and dictionaries, the attacker has no option other than to either give up and move on to someone else, or start guessing every possible password.

After an attacker exhausts all the wordlists, database and dictionaries, he always has the option to modify the rulesets used and restart. For example combining words instead of using them individually. All individual words in the classic 'correct horse battery staple' from https://xkcd.com/936/ are in wordlists.

While this of course increases the effort required to break it, for a low number of common words it scales less severe compared with brute forcing long, truly random passwords (which is doomed to fail within current technical limits).

The Keepassxc ratings you provide follow a similar line of thought. Parts of the password is a very common word so only the remaining few characters need to be brute-forced.

How widespread are things like rule-based attacks?

Here the answer depends on the goal of the attack. Specifically whether there is a specific target account or if any account is good enough.

The most prominent attacks currently are simple credential stuffing attacks that involve no password breaking of any kind and are thus very cheap to perform. These are all non-targeted attacks ('any account is fine') that work on the assumption that a tiny success rate in combination with a huge number of attempts still results in enough wins to be worth it.

The more a specific target exists, the more rule-based attacks come into play in the hope that some patterns exist that can be exploited.