Mkpasswd

From AJS.COM

This article has been updated and re-posted as a blog posting on Aaron's Essays.

mkpasswd is a tool for the pseudo-random generation of passwords.

The source code can be acquired from http://www.ajs.com/~ajs/mkpasswd and you can generate passwords online to try it out (though running it yourself lets you tweak all of the settings).

Contents 1 Usage 2 Description 2.1 Patterns 3 Statistics 4 Options 5 Examples 6 Bugs 7 Security 8 Author

Usage

 mkpasswd [-5Pdhqrv] [-s|--salt STRING] [-w|--wordlist FILE]
       [-n|--number N] [-p|--pattern STRING] [-X|--max-password-length N]

 options:

       -h|-?|--help         Print summary help
       --man                Show manual
       -v|--verbose         Verbose output
       -d|--debug           Debugging mode
       -q|--quiet           Suppress exess output
       -j|--join-minimum N  Specify the minimum overlap for joined words (J)
       -r|--random          Choose a random pattern
       -s|--salt STRING     Use STRING as the salt for on-way encryption
       -w|--wordlist FILE   Use FILE as the source for randomly chosen words
       -n|--number N        Produce N passwords
       -p|--pattern STRING  Use STRING as the password pattern
       -C|--ciphertext      Don't produce the plain text password
       -N|--non-words       Discard results that are words (combinations)
       -P|--plaintext       Don't produce the encrypted password
       -R|--extra-random    Re-seed RNG from entropy pool constantly
       -U|--unix-crypt      Turn off MD5 (this is the default)
       -X|--max-password-length N
                            Produce passwords no more than N characters long
       -5|--md5-format      Use MD5 password encryption
       --extra-long         Allow extra-long random patterns
       --punctuation STR    Use STR as the valid punctuation
       --punctuation add:STR        Add STR to the punctuation list
       --strict             Strict mode (same as -rR5 plus harder patterns)

Some examples:

mkpasswd -n 10 -r --non-word -5 --min 9 --max 12 # uses default patterns

mkpasswd -n 10 -p '*9'

mkpasswd -n 10 -p 'x9*' --non-word

Description

This program generates a random password suggestion, by using a user-supplied pattern. Of course, the most secure UNIX-style 8-character password is a completely random 8-character string that has been pre-screened for well-known weak passwords, and I encourage anyone using mkpasswd to apply such a system. However, mkpasswd's job is to make the generation of reasonably secure passwords somewhat easier for the average operator or help-desk person who simply wants to generate that first password that a user needs to log in and change their password. Such passwords should be easy to communicate, and if they're going to be used for any period of time, they should be easy to remember. Random strings of characters don't quite meet these criteria. Enter mkpasswd.

To run mkpasswd, you should get the Crypt::Random package, which can be found on any CPAN site (see http://www.perl.com), but it works just fine on Linux and other modern Unix-like systems that don't have Crypt::Random by using /dev/random.

Patterns

Now you need to decide what you want your passwords to look like. In general, it is best to not have one set format of passwords (even a really good password formula will likely reduce the number of passwords that a cracker has to guess by tens of millions). Instead, you the person executing mkpasswd should have a pre-determined list of 5-10 password formats to let mkpasswd choose from. It has some built-in patterns for those who don't want to come up with their own, but using them obviously limits the security advantages of the tool.

You specify patterns with the -p or --pattern option.

Before we go too far, let's just look at a basic pattern:

WT9

The pattern format is <pattern><modifier(s)><length> where pattern is a character from the set listed below; modifier is a specific set of parameters taken by the pattern; and length is either a number, or two numbers with a dash between them. The length is applied to the pattern, limiting how many characters can be in the result. If a length range is given, then the result will be in the range of lengths given, inclusive.

Multiple patterns can be joined together in two ways. You can just concatenate them, and then they will be used in the order given (e.g. WT5WT4). You can also join them with a / character. If you do this, then mkpasswd will actually choose between all permutations of the patterns that you give, so the pattern:

 w/*/p

Is going to choose between the following:

 w*p
 wp*
 *wp
 *pw
 pw*
 p*w

and then it will use the selected pattern to generate a password.

This is what the pattern format means:

W

Word from the system's wordlist /usr/dict/words (or equiv, see -w to specify your own wordlist)

Modifiers:

   T or N: Translate a, e, i, o and s to 4, 3, 1, 0 and 5 respectively.
           N does this to all occurrences, T flips a coin for each one.
   S:      Used with T or N. May randomly convert an s to $ instead of 5
   C:      Mix up case of letters (50% chance upper/lower)
   D:      Double a random character
   J:      Join two words (e.g. "basend" from "base" "end")
   R:      Reverse the resulting word always
   V:      Reverse the resulting word 50% of the time

Example of usage:

WST8-10

might produce:

pas$0ver
3n7ero7omy
7inderb0x

The J parameter is special. It actually causes two words to be looked up that have an overlap such as "skite" which combines "ski" and "kite". You can control how much overlap is sought using the -j flag which specifies the minimum allowed overlap in joins. Joined words are both more and less secure than regular words. They're less prone to simple dictionary attacks, however, an intruder who knows that you use this feature has less work to do in figuring out what the result is than if you, for example, tacked a random letter on the end of a random word (in some cases, depending on the lengths involved).

p

24 punctuation characters that are believed to be safe for most operating systems and other systems that store passwords. (!$%&*+=:;?.,(){}[]\/<>"')

Some systems cannot store some characters such as @ in passwords because of input restrictions. If you wish to override this restriction, use the --punctuation option.

a

Alpha character (a-z, A-Z)

w

Word character (same as a, but includes 0-9 and _)

n

Number (0-9)

Any of the above characters or space.

c

A specific list of characters. The modifier must be a bracket-delimited list of available characters that will be chosen from randomly like so:

c[abcd]2

Which will result in 2 characters from the set ``a, ``b, ``c and ``d.

x

Generates a random word that is pronounceable because it is statistically similar to the words in the dictionary, but not actually one of them (at least not selected from the list. It could happen to be one of them if you don't use the --non-words option).

This is done through a heuristic that selects letter groups based on their frequency in the given word list. The length must be 2 or more. The resulting word is likely to be pronounceable, and thus memorizable by someone who speaks the same language as the wordlist.

It is debatable how secure a password based on such statistical trickery is, but it is safe to assume that it is at least slightly more secure than just picking a word from the list, and usually very much more secure, approaching a limit of the same security found by simply selecting random letters, but not getting within an order of magnitude due to the fact that the generated pseudo-words will have a very similar letter frequency to the words in the wordlist.

NOTE: The same attributes can be specified for x as for W (e.g. C, D, etc.)

J has a special meaning when combined with x. The result will be a set of short join-words (see W's J attribute) between 3 and 5 characters long, with a trailing normal x range if needed for padding. For example, xJ10 might produce:

gap/apt + bra/rap + "la" = "gaptbrapla"

Each of these characters may be followed by a count, which is either a number (e.g. 3) or a range (e.g. 3-5). The only special-case is W, where the ``count specifies how long the word should be.

Statistics

I used to have a big section on statistics, but it kept getting invalidated every time I updated my dictionary.

Suffice to say that *n where n is some number is the most secure pattern for length n. Second most secure is wn unless you count convoluted uses of the c pattern. After that, you start to get into some debatable territory where word list and pattern selection are variables in a rather complex equation.

I like patterns that abuse multiple character sub-sets while not firmly requiring anything. So, I'm a big fan of things like:

 WTC5/WJT4/*

and

 xJT9/*

These don't have a great range in terms of permutations, but unless an attacker specifically focuses their attention on these and only these patterns (yes, that means you should pick your own patterns rather that just using those or the built-in -r defaults), they fall into much larger domains of passwords that are difficult to brute-force.

That said, everything can be brute-forced, so don't get too cocky about your passwords being strong. Use password expiration if you can, and educate your users about their options if you're a sysadmin.

S/Key and other one-time options are also a win.

Options

Other options to mkpasswd:

-d

Turn on debugging output. Intended for development purposes only.

-n

Give a number of passwords that you wish to generate. This is for creating a lot of passwords for, say, the initial creation of an entire incoming year of freshmen at a college. This is a serious opportunity for crackers, because all of your passwords will be generated with one pattern, so either use this option very sparingly, or make sure that the users have to change their passwords as soon as they log in.

-p

Give the pattern here.

-r

Generate a random pattern: not implemented. Right now this option causes mkpasswd to use one default pattern, and thus is not secure!

-s

Give the salt to use. If you don't know what a salt is, you likely don't care, and mkpasswd will make one up randomly. But, if you need to preserve the same salt as an existing password, this is how.

-w

Give the full path to the word list to be used. This list should consist of single words, on to a line.

-C
--ciphertext 

Only produce the encrypted version of the password to standard output. This option is the default when providing a password to standard input.

-P
--plaintext 

Only produce the plain text version of the password to standard output. This option is useful when generating a password that will be entered into a password prompt of another program, rather than directly typed into a password database or config file.

-5

On systems which support the MD5 crypt(3) extension, use that for the encrypted password. This allows for long passwords by default, and raises the default max-password length.

Also with this option, the ``salt used for the one-way encryption is 8 instead of 2 characters.

On systems that do not support this extension, this option will probably result in a ``salt of $1 being used and any extra characters after the first 8 being discarded.

There is also a -U option to shut this off, but that's the default.

--extra-long

Normally, when using MD5-passwords, resulting passwords are limited to 12 characters. However, the use of this parameter forces extra-long passwords to be considered valid. Use with caution, as some password generation techniques can take a long (possibly infinite) time once you get past 15-20 characters. It is best to combine this option with -X and/or -p and not -r unless you're very sure of what you expect to get as a result.

--extra-random

Normally, a random number is chose by using the best random number generation techniques available, once at the start of the program. Subsequent random numbers (e.g. for choosing letters or words) are chosen via a pseudo-random sequence built into the Perl libraries. You can force the program to take extra time by re-seeding the random number generation with a much more random number before every choice by using this option.

--non-words

Normally a randomly chosen result that happens to be a word (or a concatenation of two or more words) is considered valid, but with this option all such results are rejected.

This option also removes some of the default random patterns that can generate word-like results.

--passwd-program

Given a program name or full path, use that program for the --user option. You must specify the username with the --user option for this option to have any effect.

The default is simply passwd. NOTE: THIS IS NOT CURRENTLY WORKING!

--punctuation

You can provide a set of punctuation marks to use. To just add to the default set, use add: followed by the character(s), like so:

--punctuation add:@

--user

Use the passwd program (or the program specified by the --passwd-program option) to change a user's password. This option requires two things: the username as an argument and for the Expect Perl library to be installed and functional.

NOTE: THIS IS NOT CURRENTLY WORKING! I have had problems with expect, and no ETA on resolving them yet.

--strict

Turn on strict mode. Makes much stronger default passwords, but also passwords that are harder to remember and thus potentially less secure against social engineering.

If you provide your own pattern via the -p option, then --strict just turns on a number of extra security parameters like --extra-random, -j 2, -5 and --non-words.

Examples

Examples of command-line usage (adding -d to any of these lets you watch them do their thing):

This can take a long time, but produces a fairly decent password:

 mkpasswd -p 'WJ9/*' --strict

The WJ9 says that we want two words which overlap to form a 9-letter non-word. The asterisk requests any one random character. The slash means that the two parts of the password can be swapped around randomly, so you might get the random character first, or you might get the two words first. This use of slash is pretty important in generating complex patterns. If you take the slash out of that pattern, you radically reduce the number of possible passwords that it can generate.

Here's a nice simple command-line that produces a password that can be hard to remember, but is VERY secure:

 mkpasswd --strict

And here's the default random patterns used to generate 10 passwords:

 mkpasswd -r -n 10

The same as the above, but just print the passwords, not the encrypted form:

 mkpasswd -r -n 10 -P

And again the same, but for longer (MD5-encrypted) passwords:

 mkpasswd -r -n 10 -5

If you have to choose one of these for general-purpose, medium-security work, I'd go with the last one.

In some environments, you might have special rules about having at least one of a list of types of characters. Please note that this is a very bad idea because it means that possible passwords are limited by the characters that must be in them. However, you can write a pattern to do this easily. For example, if the rule is that you must have one upper and one lower-case letter, one number, and one punctuation character, then this pattern will give you a decent password within the constraints:

 mkpasswd -p 'c[a-z]/c[A-Z]/n/p/WJ4-6' -5 -n 10 --non-word

Bugs

Mostly statistical in nature. More work needs to be done to allow more randomness in word selection especially.

Security

So, you think mkpasswd weakens security? Try your hand at breaking some of the generated passwords:

$1$88rrdNN9$2PJvultPtuRQo1dk/CNaQ/
$1$Tis3TFY/$l5juM3qkkTB1nKAKs3tnt1
$1$L.6XlQOg$lcoZlB4hU3zZwFmQSRaDs/
$1$oFwBVhqR$nekMjhBlpru.73GTsIM6v/
$1$rXN6WqLX$Rbpi3CjdzzCZ9/n6L8.7./
$1$XMFZXW90$nz2dQzPP4dZFVHPfLrJmr1
$1$EgWwXINc$l/222MjqFbMcaiM6YDon51
$1$oLwmuzm2$s3z.FO/FxAvw/VURAxB.20
$1$Uv4vNdeE$Oi4lzDnvLjYaPt8nEi2Te/
$1$bgBTHktx$PzhAw.l2V9RLN4X0AXT7I0

These passwords were generated with:

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

On a typical Linux system. If you think you have broken any two, send them my way. If you have, I'll list your name here.

Author

mkpasswd was written by Aaron Sherman (c) 1999 and distributed under the terms of the GNU General Public License version 2 (see http://www.gnu.org).