This algorithm produces 2*20*6*20*6*10*20*6*20*6*20 or around 82 billion permutations so it is quite feasible to brute force it though quite time consuming.
If all passwords don't have to be exactly the same
length (just within a range), it's possible to modify
your algorithm slightly, keeping the same principle,
by allowing a vowel to be a dipthong and/or allowing
a consonant to be a blend, at random. This will
throw off the odd-even pattern, while still leaving
something more likely to be pronounceable than an
entirely random string.
srand( time() ^ ($$ + ($$ << 15)) );
my @v = ( 'a', 'e', 'i', 'o', 'u', 'y');
#, 'ai', 'ou', 'oo', 'ee', 'oi');
my @c = ( 'b', 'c', 'd', 'f', 'g', 'h', 'j',
'k', 'l', 'm', 'n', 'p', 'q', 'r',
's', 't', 'v', 'w', 'x', 'z');
$nc = @c; # Number of consonants excluding blends.
# (Some of the blends are not good endings.)
@c = (@c, 'bl', 'br', 'tr', 'st', 'dr',
'th', 'ch', 'sh');
my @d = (0..9, '_', '-', '.');
my $length = 10; # This is a minimum.
my ($flip, $str) = (0,'');
for ( 1 .. ($length - 1) ) {
$flip++;
if ($flip%2) {
if ($flip==$length-1) {
$str .= $c[rand($nc)];
} else {
$str .= $c[rand(@c)];
}
} else {
$str .= $v[rand(@v)];
}
}
my $re;
my $digitpos = rand(5)+3; foreach (1..$digitpos) {
$re .= ".";
}
$str =~ s/($re)/$1 . $d[rand(@d)]/e;
$str = ucfirst $str;
print "$str\n";
Results...
- Vedos5titem
- Rif7yfadrom
- Cajy1dugec
- Kunory7trir
- Zih4ychusyv
- Meb9rishystil
- Brucuce4chyv
- Nob0achuchew
- Buq6ehiqor
- Lybru-bexuk
So the question is, how secure are these passwords
with that modification? Well, if the person doing the
brute-forcing knows exactly how you generate them, or
has seen a good number of them, they're not much better,
because there's not enough variation. Adding in a bunch
of different blends and dipthongs would probably help a
bit. What would help more would be using several different
algorithms and alternating between them at random -- so
that one time you might get one like the above, and another
time you might get "ad-hoc(Variable)17" or
"e.g.{Sputnik}82" and yet another time you
might get "f0rtu1t10us_gr33nh0us3" or
"m4rg1n_bl4sph3my". (Update: those patterns
are not as hard to brute-force as the one above, but
they were intended only as quick examples.)
Any one of those patterns could
be brute-forced, but trying to code a general case that
takes in all of them could be just about as bad as doing
each one of them in turn; with a dozen different such
patterns, that could get prohibitive. If you want to
be sure that they have to do them in turn (rather than
coding a general case of some kind), throw in one
pattern that generates fairly lengthy stuff
like "running-implicit-tomorrow-wet-Howard"
and "chortle-wax-Susan-dromedary-green".
That makes for a very nice pessimal case when the
algorithm trying to break it also has to deal with
the possibilities inherent in the other patterns.
Oh, and make sure your wordlist is large and
undisclosed. (The wordlist can be disclosed if it
is seriously large, e.g., if you scan in the OED.)
Of course, if they can get what they want by
compromising only any one password, then you have to
make sure each and every one of the patterns has a
certain minimum of resistance to brute-forcing. Your
exact threshhold will depend on your circumstances.
--jonadab | [reply] [Watch: Dir/Any] [d/l] [select] |
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.";
}
}
--jonadab | [reply] [Watch: Dir/Any] [d/l] [select] |