Mkpasswd: Default patterns

From AJS.COM

The password generator tool mkpasswd's default patterns depend on what command-line switches you use. On this page, I'll assume that you used the command-line:

mkpasswd -n 10 -r --non-word -5 --min 9 --max 12

A pattern is a way of describing passwords that you want to use so that the password generator can put them together for you randomly. For example, if you said that you wanted a password that was an English word that was 8 characters long (pattern 'W8'), then it would select a random 8 letter word. Of course, that's not very secure, so patterns can specify all sorts of ways of creating useful passwords.

Contents 1 The list 2 About the patterns 2.1 Simplest 2.2 Using pseudo-words 2.3 Join words 2.4 What they all mean

The list

When using the command-line shown above, the following are the default patterns. Keep in mind that patterns with slashes in them are actually all of the patterns that can be formed by combining the sub-patterns in every permutation, so this list is a lot more complex than it might look.

'WT8-11/w', 'WDT8-11/w', 'w9-12', 'xI9-12', 'xT9-12', 'xTD12',
'xT8-11/*', 'xC(30)T8-11/*', 'xC(30)8-11/*', 'WIJ11-12', 'WC(30)J11-12',
'WTJ11-12', 'WTDJ11-12', 'WJ10-11/*', 'WTJ10-11/*', 'WTDJ10-11/*',
'WJRD9-12', 'WJRD8-11/w', '*/n2/W6-9', 'n/n2/WC(30)6-9', '*/n2/WJ6-9',
'n/n2/WJC(30)6-9', 'WT5/WT5/w/w', 'x5/x5/n/n', 'xC(20)5/x5/n/n',
'xC5/x5/n/n', 'x3-5/x3-5/n/n', 'xI3-5/x3-5/n/n', 'xC(20)3-5/x3-5/n/n',
'xC3-5/x3-5/n/n', 'W3/x6/w3', 'WJ9/w3', 'WIJ9/w3', 'WDJ9/w3', 'x4/WJ8',
'x4/WJC(30)8', 'WJC(30)9-12', 'WJT9-12', 'WJDT9-12', 'WJN9-12',
'WJDN9-12', 'xJ8-11/w1', 'xJ7-10/w1/w1', 'WJ6/WJ6', 'WIJ6/WJ6',
'WJ6/x6', 'WJ8/w1/w1/w1/w1', 'WJ4WJ4WJ4', 'WIJ4WJ4WJ4', 'WJ4/WJ4/x4',
'n/n2/n3/xC(30)T3-6', 'n/n2/n3/xC(30)3-6', 'WJ4/n1/n2/x2-5',
'WJC(30)4/n1/n2/x2-5'

About the patterns

As you can see, there are quite a lot of patterns. The goal in constructing this list was to provide as many ways of generating a password as possible so that an attacker could not easily describe what an "mkpasswd password" looked like. However, the secondary goal is to make sure that mkpasswd passwords are as easy for the user to remember as is practical with reasonably secure passwords.

Let's look at some examples:

Simplest

'WT8-11w'

Here, we have a word of 8-11 characters (my dictionary has about 50,000 of these) with transposition of some letters and a random word character after it. There are, on average, 4.5 transposable letters per word, and there are 37 word characters (a-z upper and lower, 0-9 and underscore).

That's not a very strong password choice, but it's not as weak as many. Recall that this is actually around twice as hard to break because the real pattern allows for the word character to go on the beginning or end of the dictionary word. This is specifically mkpasswd's baseline. It's the weakest password pattern it uses. If I find any other pattern to be weaker than producing 2²⁶ results, I remove it from the defaults, and typically I strive to have the patterns be much stronger.

Using pseudo-words

Pseudo-words introduce a difficulty in establishing the number of possible passwords. There are a massive number of possible pseudo-words, but some are far more likely to come up than others because they're chosen for how likely they are to be pronounceable. More accurately, there is a weight applied to the selection of word parts based on how frequently that word part appears in the input dictionary. In general, it is fairly safe to assume that there will be at least as many pseudo-words available as dictionary words, unless your input dictionary is very strange. The only difference is that, unlike the dictionary, there is no "clumping" around words of certain lengths. So, the longer a pseudo-word is, the more of them there are. With real words, longer words become increasingly rare, and it's unlikely that your dictionary has an 80-letter word. When asked to produce an 80-letter pseudo-word, mkpasswd quickly coughs up:

kerytujamysteacmavleepnoeverarhibarymaecuaebeverstiserberelawmeahifumarncouienaf

So what does this mean for security? In my dictionary, there are around 5,000 unique 3-letter words, so at a minimum, we can say that any 3-letter group could have 5,000 permutations that are roughly comparable in frequency. Thus, we could say that the pattern:

x5nx4n

has 9 pseudo-word letters, amounting to about 5000³ permutations at a minimum times 10² for the number characters. Thus about 2⁴³ possible passwords.

Now, this is a gross approximation, but it's a fairly reliable minimum which seems to be reasonable when you compare it to a random sequence of 11 letters which would be 26¹¹ or about 2⁵¹ permutations.

From this, I'll further generalize and suggest that you can assume that a pseudo-word of n letters will generate passwords that are roughly as secure as a random string of letters that is 1-2 letters sorter. So, a 9-letter pseudo word is about as secure as an 7-8 letter random sequence of letters, which is (using a standard U.S. keyboard) about the security of a 5-7 letter long sequence of all possible random characters.

Join words

Join words are words which overlap to form a larger string which is used as the password. For example, "slat" and "attack" overlap to form the password, "slattack". On my system this works out to about 2^22.5 possible results for:

WJ9

or around the same number of results as 5 random letters. This is a massive hit to the security of generated passwords, so it is typically suggested that join words only be used in places were a simple dictionary word would be used, and always supplemented with other modifiers and patterns.

In the default passwords we use sequences like x4/WJ8 which means a 4-character pseudo-word followed by an 8-character join word, resulting in approximately 2³¹ possible passwords.

What they all mean

WT8-11/w

An 8-11 letter word with random number/letter translation and a random word character at the beginning or end. e.g. tran$la7eu

WDT8-11/w

The same, but with random doubling of one of the characters of the word. e.g. tran$lla7eu

w9-12

9-12 random word characters. ud98ke5ewl

xI9-12

A 9-12 letter pseudo-word with a random character inserted. e.g. pnoevera!rh

xT9-12

The same, but with random number/letter translation. e.g. pn03vera!rh

xTD12

The same, but 12 characters and with random doubling of one of the characters. e.g. h1baryyma3cua

xT8-11/*

A random 8-11 letter pseudo-word with random number/letter translation and a random character at the start or end. e.g. %pn03verarh

The following still need descriptions:

', 'xC(30)T8-11/*', 'xC(30)8-11/*', 'WIJ11-12', 'WC(30)J11-12',
'WTJ11-12', 'WTDJ11-12', 'WJ10-11/*', 'WTJ10-11/*', 'WTDJ10-11/*',
'WJRD9-12', 'WJRD8-11/w', '*/n2/W6-9', 'n/n2/WC(30)6-9', '*/n2/WJ6-9',
'n/n2/WJC(30)6-9', 'WT5/WT5/w/w', 'x5/x5/n/n', 'xC(20)5/x5/n/n',
'xC5/x5/n/n', 'x3-5/x3-5/n/n', 'xI3-5/x3-5/n/n', 'xC(20)3-5/x3-5/n/n',
'xC3-5/x3-5/n/n', 'W3/x6/w3', 'WJ9/w3', 'WIJ9/w3', 'WDJ9/w3', 'x4/WJ8',
'x4/WJC(30)8', 'WJC(30)9-12', 'WJT9-12', 'WJDT9-12', 'WJN9-12',
'WJDN9-12', 'xJ8-11/w1', 'xJ7-10/w1/w1', 'WJ6/WJ6', 'WIJ6/WJ6',
'WJ6/x6', 'WJ8/w1/w1/w1/w1', 'WJ4WJ4WJ4', 'WIJ4WJ4WJ4', 'WJ4/WJ4/x4',
'n/n2/n3/xC(30)T3-6', 'n/n2/n3/xC(30)3-6', 'WJ4/n1/n2/x2-5',
'WJC(30)4/n1/n2/x2-5'