Extra length is a good way to increase conplexity as each extra alphanumeric adds roughly one order of magnitude of complexity. Exactly one order of magnitude for digits, a little more for alphabetics where the set > 10.

Interesting. I thought about this a bit and did a little more arithmetic, and I discovered that one of my (slightly improved) randomly-generated syllables is roughly 30*15*53, or about 23 thousand. My words file in /usr/share/dict/words has about 45 thousand (according to wc), so it is less than twice as complex as one of my syllables, even though it could be a good deal longer (brahamaputra came up once; the longest syllable my algorithm can make would be six letters long). However, the word may still be as easy to remember, since it is in fact a real word.

I know it's considered bad to have a dictword for a password, so obviously one of my syllables is not enough. Two of them strung together, OTOH, with a hyphen in-between for easy legibility, comes to more like 500 million give or take; three of them sends my calculator into scientific notation (e+13). I figured up [A-Za-z0-9]{8}, and that comes to e+14, or slightly more complex. Still, it's close, and it is arguable that Shaf-Golk-Said may be easier to remember than rG8wnPe4, despite being half again as long. So, for posterity, my improved algorithm...

#!/usr/bin/perl;

use strict; use warnings;

my $dictionaryfile = '/usr/share/dict/words';
my $number_to_generate=12;
my $length = 10;
my $showalgorithm=0; # Set true to have the main loop
# tell which algorithm it calls for each password.
# Note that right now it's always using alg 3; remove
# the line $alg=3; to use all three of them.

sub rndStr{local $"=''; "@_[map{rand$#_} 1 .. shift]"; }

sub algorithm_one {
# Pretty much random, but hard to remember.  
# Security climbs steeply with length.
  return rndStr $length, 'A'..'Z', 0..9, 'a'..'z',
                         '-', '_', '.';
}

my @words;
if (open WORD, "<$dictionaryfile") {
  my $w;
  while (<WORD>) {
    chomp;
    $words[$w++]=lc;
  }
  close WORD;
} else {
  @words = ();
  warn "Unable to open dictionary file $dictionaryfile
 (error: $!); faking it.\n";
}

srand( time() ^ ($$ + ($$ << 15)) );
my @vowels = ('a', 'e', 'i', 'o', 'u'); # 5
my @dipthongs = ('ai', 'ou', 'oo', 'ee', 'oi',
         'au', 'ui', 'ea', 'ow', 'aw',
        ); # 10
my @consonants = ( 'b', 'c', 'd', 'f', 'g', 'h',
           'j', 'l', 'm', 'n', 'p', 'r',
           's', 't', 'v', 'x', 'z'
         ); # 17
my @startblends = ('bl', 'br', 'cl', 'ch', 'cr',
           'cw', 'dr', 'fl', 'fr', 'gl',
           'gr', 'ph', 'qu', 'sc', 'sh',
           'sn', 'st', 'sw', 'th', 'tr',
           'tw', 'w', 'wh',
          ); # 23
my @endblends = ('ch', 'ck', 'gh', 'k', 'ld', 'lk',
         'lm', 'ln', 'lp', 'lt', 'lv', 'lx',
         'mp', 'nd', 'ng', 'nk', 'nt', 'ph',
         'rb', 'rd', 'rf', 'rg', 'rk', 'rm',
         'rn', 'rp', 'rs', 'rt', 'rv', 'rx',
         'sh', 'sk', 'sp', 'st', 'th', 'ts',
        ); # 36
my @delimiters = (0..9, '_', '-', '.', ',', 'y', '!');
my %delimiter_pairs = (
               '<' => '>',
               '(' => ')',
               '{' => '}',
               '[' => ']',
               '-' => '-',
               '_' => '_',
               '.' => '.',
#         'y' => 'y',
        );
sub delimitpairaround {
  my (@k, $open, $close);
  @k = keys(%delimiter_pairs);
  $open = $k[rand(@k)];
  $close = $delimiter_pairs{$open};
  return $open . "@_" . $close;
}

sub syllable_start {
  my @c = (@consonants, @startblends, @consonants);
  my $s = $c[rand(@c)];
  return (rand(973)%7)>4 ? $s : ucfirst $s;
}
sub syllable_end {
  my @c = (@consonants, @endblends, @consonants);
  return $c[rand(@c)];
}
sub vowel_or_dipthong {
  my @v = (@vowels, @dipthongs, @vowels);
  return $v[rand(@v)];
}
sub syllable {
  return syllable_start() . 
      vowel_or_dipthong() . 
      syllable_end();
}

sub realword {
  my ($w, $r);
  if (@words) {
    $w = $words[rand(@words)];
    $r = rand(7378)%100;
    ($r>66) ? ucfirst $w : (($r>12) ? $w : uc $w);
  } else {
    return syllable();
  }
}

sub algorithm_two {
  my ($flip, $str, $l) = (0,'', $length-1);
  while ($flip < $l) {
    ++$flip;
    if (($flip%3)==1)    { $str .= syllable_start();      }
    elsif (($flip%3)==2) { $str .= vowel_or_dipthong();   }
    else {                 $str .= syllable_end();
    if ((rand(1000)%2)
        and ($flip<$l)) {
                       $str .= $delimiters[rand(@delimiters)]; $l--;
             }}}
  return $str;
}

sub algorithm_three {
  my $str = ""; my ($s, $prob);
  foreach $s (1..(int $length/3)) {
    $prob=(rand(873)%100);
    my $piece = ($prob>45) ? syllable() : realword();
    if (not $s % 2) {
      $str .= delimitpairaround($piece);
    } else {
      $str .= $piece;
    }
  }
  return $str;
}

my ($password, $alg);
foreach $password (1..$number_to_generate) {
  $alg=rand(1793)%3+1;
  $alg=3; # Remove to get a mix of algorithms.
  if ($showalgorithm) { printf " % 2d> ", $alg; }
  if ($alg==1) {
    print algorithm_one() . "\n";
  } elsif ($alg==2) {
    print algorithm_two() . "\n";
  } elsif ($alg==3) {
    print algorithm_three() . "\n";
  }
  else {
    print STDERR "ERROR:  Not sure what algorithm to use 
for password $password.";
  }
}
[download]

 --jonadab