Does the haystack theory work

Question

The haystack theory is the recommendation to put repeated characters in your password in order to make it harder for brute force to reveal.

Does this have any mathematical basis? Or is it snake oil?

Answer 1

The "haystack" is just a metaphoric way to describe brute force. The idea of "repeated characters" in passwords is a poor one.

The whole password game is that the defender (i.e. the user) will draw his password from a "set of potential passwords", and the attacker will walk this set until he finds the right one. Larger sets imply more work for the attacker, but also for the defender because that's more choices to remember.

If users were robots, then "repeated characters" would be as good an idea as anything else: like love, entropy is blind, and does not mind how you achieve the set of possible passwords as long as there are sufficiently many. However, if users were robots, then they would use random 128-bit keys as "passwords" and the whole discussion would be moot. In practice, human users are human and this implies that human brains will have to do the remembering. The point here is that the "memory resources" spent on remembering a specific password feature do not equate at all with a fixed number of extra entropy bits.

If you take a password as a "normal word" and then double one letter (e.g. "passwword") then the effort needed to remember that this specific letter is doubled is quite big compared to the actual gain (for an 8-character source password, you get 3 bits of entropy out of the choice of the letter to double -- in fact a bit less because many people would elect to double the "o", because "Google", not "goggle"). That's the whole idea behind the famous comic which was discussed in this question: to get the most entropy out of human-remembered password, you must generate passwords in ways which map well to the best abilities of the human brain. Humans are very good at talking and are highly trained at reading and writing (through years of toil), so you should use words for passwords. Most "password improvement" tricks like including digits and punctuation signs or, for the case at hand, repeating letters, are at odds with the mind. They are therefore counterproductive.

In less words: instead of doubling a letter, add another word. This will be a much better use of your brain cells: it will give you more security for less effort.

Answer 2

All brute-force password attacks consist of iterating through all the elements in a password dictionary. So to protect yourself, you need to (a) make sure that the password you're using isn't in the attacker's dictionary, and (b) whatever dictionary does contain your password is too long to get through.

The most effective (and therefore common) dictionaries are just lists of common passwords, which is why using common passwords is such a bad idea. Then come list of words found in common writing, plus combinations and variations on those words (add numbers and punctuation, etc.), then every letter combination starting at the shortest and then progressing up to the longest.