7.4 Generating Non-Totally Random Passwords

Credit: Luther Blissett

7.4.1 Problem

You need to create new passwords randomly�for example, to assign them automatically to new user accounts�and want the passwords to be somewhat feasible to remember for typical users, so they won't be written down.

7.4.2 Solution

We can use a pastiche approach for this, mimicking letter n-grams in actual English words. A grander way to look at the same approach is to call it a Markov Chain simulation of English:

import random, string

class password:
    # Any substantial file of English words will do just as well
    data = open("/usr/share/dict/words").read().lower(  )
    def renew(self, n, maxmem=3):
        self.chars = []
        for i in range(n):
            # Randomly "rotate" self.data
            randspot = random.randrange(len(self.data))
            self.data = self.data[randspot:] + self.data[:randspot]
            where = -1
            # Get the n-gram
            locate = ''.join(self.chars[-maxmem:])
            while where<0 and locate:
                # Locate the n-gram in the data
                where = self.data.find(locate)
                # Back off to a shorter n-gram if necessary
                locate = locate[1:]
            c = self.data[where+len(locate)+1]
            if not c.islower(  ): c = random.choice(string.lowercase)
            self.chars.append(c)
    def _ _str_ _(self):
        return ''.join(self.chars)

if _ _name_ _ == '_ _main_ _':
    "Usage: pastiche [passwords [length [memory]]]"
    import sys
    if len(sys.argv)>1: dopass = int(sys.argv[1])
    else: dopass = 8
    if len(sys.argv)>2: length = int(sys.argv[2])
    else: length = 10
    if len(sys.argv)>3: memory = int(sys.argv[3])
    else: memory = 3
    onepass = password(  )
    for i in range(dopass):
        onepass.renew(length, memory)
        print onepass

7.4.3 Discussion

This recipe is useful when creating new user accounts and assigning each user a different, random password, using passwords that a typical user will find feasible to remember, so that the passwords will not be written down. See Recipe 7.3 if you prefer totally-random passwords.

The recipe's idea is based on the good old pastiche concept. Each letter (always lowercase) in the password is chosen pseudo-randomly from data that is a collection of words in a natural language familiar to the users. This recipe uses /usr/share/dict/words as supplied with Linux systems (on my machine, a file of over 45,000 words), but any large document in plain text will do just as well. The trick that makes the passwords sort of memorable, and not fully random, is that each letter is chosen based on the last few letters already picked for the password as it stands so far, so that letter transitions will tend to be repetitive. There is a break when the normal choice procedure would have chosen a nonalphabetic character, in which case a random letter is chosen instead.

Here are a couple of typical sample runs of this pastiche.py password-generation script:

[situ@tioni cooker]$ python pastiche.py
yjackjaceh
ackjavagef
aldsstordb
dingtonous
stictlyoke
cvaiwandga
lidmanneck
olexnarinl
[situ@tioni cooker]$ python pastiche.py
ptiontingt
punchankin
cypresneyf
sennemedwa
iningrated
fancejacev
sroofcased
nryjackman
[situ@tioni cooker]$

As you can see, some of these are definitely wordlike, others less so, but for a typical human being, none are more problematic to remember than a sequence of even fewer totally random, uncorrelated letters. No doubt some theoretician will complain (justifiably, in a way) that these aren't as random as all that. Well, tough. My point is that they had better not be if some poor fellow is going to have to remember them! You can compensate for this by making them a bit longer. If said theoretician shows us how to compute the entropy per character of this method of password generation (versus the obvious 4.7 bits/character of passwords made up of totally random lowercase letters, for example), now that would be a useful contribution indeed. Meanwhile, I'll keep generating passwords this way, rather than in a totally random way, whenever I'm asked to do so. If nothing else, it's the closest thing to a useful application for the pastiche concept that I've found.

7.4.4 See Also

Recipe 7.3; documentation of the standard library module random in the Library Reference.