Thursday, November 22, 2012

DIY xkcd Password Generator

One of the things I'm thankful for today is xkcd. Specifically, I want to talk about the world-famous password strip, which points out that using a few selections from a big list of things (a dictionary) is more random, and yet easier to remember, than a lot of selections from a limited list of things (the keys on your keyboard).

There are even sites which generate xkcd-style passwords for you. Many sites, in fact.

The other day I was using one of these generators to make a password for work. The only problem was that the system that I was logging on to required my password to be between 8 and 16 letters, which is difficult to do when you're dealing with a list of random dictionary words. It also checks to see if you had a string of four or more letters that matched a dictionary word.

To fix this, I needed to have a list of, say, three letter words. Where to find them? Sergey and Larry's search engine helped. For example, here's a list of allegedly legal Scrabble words. Given that, all we need is a script to generate a list of words.

That script is below. What I didn't do was include the words. For one thing I'm not sure about the copyright status of that list. For another, you might want to use your own list. For a third, it would make this post really, really long. So add your own list of words, one per line, between the two EOF lines in the script.

While I was at it, I decided to add a few improvements, towit:

  • You can specify the number of words. If you call the script xkcdpass, then
    xkcdpass 5
    will generate a password using five words from the list. The default is 4, which you can easily change.
  • Given the number of words in the list, call it N, and the number of words in the password, call it M, you can generate NM unique passwords (since strings like thethethethe are perfectly valid). That's a measure of password security, so the script tells you that.
  • You have three choices of randomness. In order of security, they are: The bash variable $RANDOM, which can be seeded to the current time, and the linux scripts /dev/urandom and /dev/random. Uncomment the one you like, depending on your level of paranoia.
  • It should work on any system that runs bash, including Macs.
  • And, of course, I tried to document where I got everything.

So here's the script. Add a comment if you see a problem, or if you just like (or hate) it.

#! /bin/bash

# Generates an xkcd-like password from a list of three-letter words

# Usage

# xkcdpass n

# where n>0 is the number of words in the string.  The default value of
#  n is 4.

# Set the default if needed

if (( $# < 1 ))

# Set up an array and populate it.
declare -a array
let index=0

# There is a list of acceptable three-letter Scrabble words at
# Add additional words, if you like, or use a different list.

while read line
	let index=$index+1

# Insert your words between the two EOFs, one per line
# There is a list of acceptable three-letter Scrabble words at
# Add additional words, if you like, or use a different list.

done <<EOF


# So how secure is this string (bigger numbers are better):

echo -n $index "words in file, giving "
unique=`echo "$index^$nwords" | bc`
echo $unique unique passwords

# Uncomment this if you use $RANDOM and want a
#  unique seed.  See
# The date +%s command gives the time from the epoch

RANDOM=$$$(date +%s)

# Select $nwords at random.  Note that you can select the
#  same word more than once.

for (( i=0 ; i<$nwords ; i++ ))

#   Uncomment the random technique you want to use:

#   Probably not all that random, but you can use the seed above
#   to make it better.
    let number=$RANDOM

#   More random, but slower (the sed gets rid of some annoying spaces)
#   -N3 prints out 3 bytes of data.  That's probably enough.  Note that
#   if you have 2^N words, for any integer N, it won't matter how
#   many bytes you use if the number of bytes is bigger than N
#    let number=`od -An -N3 -i /dev/urandom | sed "s/ *//"`

#   For the difference between random and urandom, see

#   Really random, though visibly slow
#    let number=`od -An -N3 -i /dev/random | sed "s/ *//"`

#   Do modulo arithmetic to get the number between 0 and $index-1
    let "number %= $index"

    echo -n ${array[$number]}
# Print a newline character


shawn turpin said...

I made a slight change to use my Mac's dictionary file instead of copying/pasting words:

Change: done <<EOF

To: done </usr/share/dict/words

and comment or remove the last EOF

Still works really fast and I don't have to copy/paste words.

rcjhawk said...

Yes, but it doesn't limit you to words of 3 or fewer letters. After I wrote this I found a way to query the dictionary for 3-letter words. I may add this at some later date. Note that your average dictionary will not include a lot of the words on the Scrabble list, I found over 20 in the "A" section alone.