Combining two obsessions: Sudoku and safe passwords

2008-05-07T15:03:00.000-07:00

In grade school, Encyclopedia Brown was my hero. I had a brain like a sponge and could recite factoids ad nauseum. But eventually even someone with a prodigious memory can be overwhelmed by the vast numbers of passwords required for all the different accounts and services we use these days.

Yes, there's software and browser add-ons that can keep track of your passwords for you, but I distrust saving anything that sensitive in electric media. That makes it accessible to crackers, in a relatively easily accessible form.

Bruce Schneier recommends writing down your passwords, and I agree. But I still get a little uncomfortable that someone might find my list or read over my shoulder.

There's a nice little Perl module, mkpasswd.pl, that can be used to generate strong random passwords. This is good, but then you have to write them down somewhere. For a while, I had a little card with 12 rows of 3 passwords each. I printed this out, kept no electronic records, and used various patterns from the card. For variety, I would sometimes make a password out of a column of characters, but it irritated me that the initial pattern of mkpasswd.pl was broken sometimes there would be several symbols in a column, and sometimes lots of digits.

I started thinking, How could I constrain 9 rows and columns so that you had the same pattern (for example, 1 symbol and 2 digits) in each row or column? Then it occurred to me, this is nearly the same set of constraints as in a Sudoku puzzle! A solved puzzle has digits 1 through 9 uniquely in each row or column, and in each 3x3 sub-grid as well.

I put this in the back of my mind for about a year and a half, since I wasn't sure how to do it. To start with, how would I make sure that the sudoku digits corresponded to the same pattern of characters? Then suddenly, it came to me.

Here is the script, sudoku_passwd_card:


#!/bin/bash
#
#  Sudoku-constrained password card generator
#
#  Use a randomly generated solved sudoku grid plus mkpasswd.pl
#  to print a grid like this:
#
#    +-------+-------+-------++-------+-------+-------+
#    | x F B | w N 7 | 2 , o || H l a | 0 8 V | o , W |
#    | g 1 % | y m s | 9 t L || 1 u 4 | { g s | i h w |
#    | K 1 h | 0 : L | d Q u || t v } | X Z f | G 6 1 |
#    +-------+-------+-------++-------+-------+-------+
#    | c F 8 | | T 0 | u r m || } 0 z | h X l | 5 Q c |
#    | J - 8 | Y o L | x c 5 || 3 r g | X 6 u | s e > |
#    | j y p | 5 o j | L 3 ^ || w C F | 8 z ? | 2 n E |
#    +-------+-------+-------++-------+-------+-------+
#    | * t d | i 2 v | s 9 a || x F m | x v F | $ 2 7 |
#    | 0 t c | c r ^ | M x 1 || G 9 Z | x - 4 | n f g |
#    | 0 b Q | W 5 p | = X E || q ~ 1 | x h 6 | R R c |
#    +-------+-------+-------++-------+-------+-------+
#
#  Each 9-character row, column or 3x3 square contains
#  1 symbol, 2 digits, and some lower and upper case.
#
#  Reading forward, backward, up, down,
#  in rows, columns and squares, gives you at least 144 combinations.
#

umask 077
tmpdir=/tmp/sudoku_passwd.$USER.$$
MKPASSWD="mkpasswd.pl -d 2 -s 1 | sed -e 's/\([^ ]\)/\1\n/g' | grep -v '^ *$' | sed -e 's/^ *//'"

j=0
while [[ $j -lt 2 ]] ; do

j=$((j+1))
TMPDIR=${tmpdir}.$j

mkdir -p $TMPDIR/

# Use mkpasswd.pl to make a random permutation from sorted
# Symbol, 2x digit, 2x Upper, 4x lower to something else.
#
eval $MKPASSWD | \
nl | \
awk '{print $2 " " $1}' | \
sort -fd | \
awk '{print $2}' > $TMPDIR/file0

# Create a random sudoku puzzle,
# solve it,
# then print it out as a 9x9 space-separated grid:
sudoku-generator $seed | head -$((seed % 16)) | tail -1 | tr '.' '0' | \
sudoku.pl 2>&1 | \
sed -e 's/\([^ ]\)/\1 /g' | xargs -n9 echo > $TMPDIR/puzzle

i=0
while [[ $i -lt 9 ]] ; do
   i=$((i+1))

   # Make a password, sort it to standard order,
   # then permute it using file0 above to get it into same
   # sequence as template password
   eval $MKPASSWD | \
   sort -fd | \
   paste $TMPDIR/file0 - | \
   sort -n | \
   awk '{print $2}' | \
   nl | \
   awk '{print $2 " " $1}' > $TMPDIR/pair$i

   # Cut the i-th column from the puzzle, and figure out the permutation
   # needed to create that ordering
   cut -f$i -d' ' $TMPDIR/puzzle | \
   nl | \
   awk '{print $2 " " $1}' |  \
   sort -n | \
   awk '{print $2}' > $TMPDIR/perm$i

   # Now apply the puzzle-column permutation to the password column
   paste $TMPDIR/perm$i $TMPDIR/pair$i | \
   sort -n | \
   awk '{print $2}' > $TMPDIR/col$i
done

done

# Print out the two sudoku password squares side by side.
# Perl one-liner:
#   set counter, print initial line.
#   print formatted set of 18 fields,
#   increment counter,
#   print line separator if counter mod 3 is zero.
paste ${tmpdir}.{1,2}/col[1-9] |
perl -wlna -e \
'BEGIN { $i=0;
         print "+-------+-------+-------++-------+-------+-------+";
       };
 print "| @F[0..2] | @F[3..5] | @F[6..8] || @F[9..11] | @F[12..14] | @F[15..17] |"
 and ($i += 1)
 and ( $i % 3 == 0 )
 and print "+-------+-------+-------++-------+-------+-------+";'

/bin/rm -rf $tmpdir

Besides mkpasswd.pl, I use two other utilities I scarfed from the net. The first was a sudoku puzzle generator in C, and the second was a 3 line perl script that solves a sudoku puzzle using brute force.

Here's what I do:

Generate a random password and print out one character per line
Number the lines, reverse columns so the password is in front, then sort in dictionary order. Trim off the password, we're done with it.

This creates a permuted column of the digits 1 through 9, the pattern that we will use for all our generated passwords.

Generate a solved sudoku puzzle using the 9 digit sequence as our seed.

For each column of the puzzle,

Generate a random password as a column, sort to dictionary order, then permute using the template pattern to get our standard password order.
Cut a column from the puzzle, and figure out the permutation that takes an ordered list into the column ordering.
Apply that permutation to the password column

When you've created enough columns, print them out in a Sudoku type grid. I like to print this out in a credit-card-size, so I print two grids next to each other.

Every time you run this, you get a new grid. To ensure that the information isn't saved anywhere, I send the output directly to the printer:


sudoku_passwd_card | enscript

Isn't this cute? You get at least 144 passwords out of this card without much work, and even more if you want to get devious.

You're probably thinking, why do all that work? If you've found this blog, you probably don't need this yourself. You have a good system and know how to create strong passwords. But you may be blessed with some friends or customers who need a little help, and if you can make things easier for them, your system will be that much more secure.

Script Maven

Combining two obsessions: Sudoku and safe passwords