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.
- Generate a solved sudoku puzzle using the 9 digit sequence as our seed.
- 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
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.
No comments:
Post a Comment