tools/krb5-strength-wordlist

   1 #!/usr/bin/perl
   2 #
   3 # Turn a wordlist into a CDB or SQLite database.
   4 #
   5 # This program takes as input a word list (a file of words separated by
   6 # newlines) and turns it into either a CDB or a SQLite database that can be
   7 # used by the krb5-strength plugin or heimdal-strength program to check
   8 # passwords against a password dictionary.  It can also filter a word list in
   9 # various ways to create a new word list.
  10
  11 ##############################################################################
  12 # Declarations and configuration
  13 ##############################################################################
  14
  15 require 5.006;
  16 use strict;
  17 use warnings;
  18
  19 use File::Basename qw(basename);
  20 use Getopt::Long qw(GetOptions);
  21
  22 # The path to the cdb utility, used to create the final database.  By default,
  23 # the user's PATH is searched for cdb.
  24 my $CDB = 'cdb';
  25
  26 # The SQL used to create the SQLite database.
  27 ## no critic (ValuesAndExpressions::ProhibitImplicitNewlines)
  28 my $SQLITE_CREATE = q{
  29     CREATE TABLE passwords (
  30         password TEXT UNIQUE NOT NULL,
  31         drowssap TEXT UNIQUE NOT NULL
  32     )
  33 };
  34
  35 # The SQL used to insert passwords into the database.
  36 my $SQLITE_INSERT = q{
  37     INSERT OR IGNORE INTO passwords (password, drowssap) values (?, ?)
  38 };
  39 ## use critic
  40
  41 ##############################################################################
  42 # Utility functions
  43 ##############################################################################
  44
  45 # print with error checking and an explicit file handle.
  46 #
  47 # $fh   - Output file handle
  48 # @args - Remaining arguments to print
  49 #
  50 # Returns: undef
  51 #  Throws: Text exception on output failure
  52 sub print_fh {
  53     my ($fh, @args) = @_;
  54     print {$fh} @args or croak('print failed');
  55     return;
  56 }
  57
  58 ##############################################################################
  59 # Database output
  60 ##############################################################################
  61
  62 # Filter the given input file and write it to a CDB data file, and then use
  63 # cdb to turn that into a database.
  64 #
  65 # $in_fh  - Input file handle for the source wordlist
  66 # $output - Name of the output CDB file
  67 # $filter - Reference to sub that returns true to keep a word, false otherwise
  68 #
  69 # Returns: undef
  70 #  Throws: Text exception on output failure or pre-existing temporary file
  71 sub write_cdb {
  72     my ($in_fh, $output, $filter) = @_;
  73
  74     # Check that the output CDB file doesn't exist.
  75     if (-f $output) {
  76         die "$0: output file $output already exists\n";
  77     }
  78
  79     # Create a temporary file to write the CDB input into.
  80     my $tmp = $output . '.data';
  81     if (-f $tmp) {
  82         die "$0: temporary output file $tmp already exists\n";
  83     }
  84     open(my $tmp_fh, '>', $tmp)
  85       or die "$0: cannot create output file $tmp: $!\n";
  86
  87     # Walk through the input word list and write each word that passes the
  88     # filter to the output file handle as CDB data.
  89     while (defined(my $word = <$in_fh>)) {
  90         chomp($word);
  91         next if !$filter->($word);
  92         my $length = length($word);
  93         print_fh($tmp_fh, "+$length,1:$word->1\n");
  94     }
  95
  96     # Add a trailing newline, required by the CDB data format, and close.
  97     print_fh($tmp_fh, "\n");
  98     close($tmp_fh) or die "$0: cannot write to temporary file $tmp: $!\n";
  99
 100     # Run cdb to turn the result into a CDB database.  Ignore duplicate keys.
 101     system($CDB, '-c', '-u', $output, $tmp) == 0
 102       or die "$0: cdb -c failed\n";
 103
 104     # Remove the temporary file and return.
 105     unlink($tmp) or die "$0: cannot remove temporary file $tmp: $!\n";
 106     return;
 107 }
 108
 109 # Filter the given input file and write it to a newly-created SQLite database.
 110 # Requires the DBI and DBD::SQLite modules be installed.  The database will
 111 # contain one table, passwords, with two columns, password and drowssap, which
 112 # store the word and the word reversed for each word that passes the filter.
 113 #
 114 # $in_fh  - Input file handle for the source wordlist
 115 # $output - Name of the output SQLite database
 116 # $filter - Reference to sub that returns true to keep a word, false otherwise
 117 #
 118 # Returns: undef
 119 #  Throws: Text exception on output failure, pre-existing output file, or
 120 #          missing Perl modules
 121 sub write_sqlite {
 122     my ($in_fh, $output, $filter) = @_;
 123
 124     # Check that the output SQLite file doesn't exist.
 125     if (-f $output) {
 126         die "$0: output file $output already exists\n";
 127     }
 128
 129     # Load the required modules.
 130     require DBI;
 131     require DBD::SQLite;
 132
 133     # Open and create the database.
 134     my $options = { PrintError => 0, RaiseError => 1, AutoCommit => 0 };
 135     my $dbh = DBI->connect("dbi:SQLite:dbname=$output", q{}, q{}, $options);
 136     $dbh->do($SQLITE_CREATE);
 137
 138     # Prepare the insert statement for each word.
 139     my $sth = $dbh->prepare($SQLITE_INSERT);
 140
 141     # Walk through the input word list and add each word that passes the
 142     # filter to the database, both as-is and reversed.
 143     while (defined(my $word = <$in_fh>)) {
 144         chomp($word);
 145         next if !$filter->($word);
 146         my $reversed = reverse($word);
 147         $sth->execute($word, $reversed);
 148     }
 149
 150     # Commit and close the database.
 151     $dbh->commit;
 152     $dbh->disconnect;
 153     return;
 154 }
 155
 156 # Filter the given input file and write the results to a new wordlist.
 157 #
 158 # $in_fh  - Input file handle for the source wordlist
 159 # $output - Output file name to which to write the resulting wordlist
 160 # $filter - Reference to sub that returns true to keep a word, false otherwise
 161 #
 162 # Returns: undef
 163 #  Throws: Text exception on output failure
 164 sub write_wordlist {
 165     my ($in_fh, $output, $filter) = @_;
 166     open(my $out_fh, '>', $output)
 167       or die "$0: cannot create output file $output: $!\n";
 168
 169     # Walk through the input word list and write each word that passes the
 170     # filter to the output file handle.
 171     while (defined(my $word = <$in_fh>)) {
 172         chomp($word);
 173         next if !$filter->($word);
 174         print_fh($out_fh, "$word\n");
 175     }
 176
 177     # All done.
 178     close($out_fh) or die "$0: cannot write to output file $output: $!\n";
 179     return;
 180 }
 181
 182 ##############################################################################
 183 # Filtering
 184 ##############################################################################
 185
 186 # Given the parsed command-line options as a hash, construct a filter for the
 187 # word list and return it.  The filter will, given a word, return true if the
 188 # word should be included in the dictionary and false otherwise.
 189 #
 190 # $config_ref - Hash of configuration options
 191 #   ascii      - Strip non-printable or non-ASCII words
 192 #   exclude    - Reference to array of regex patterns to exclude
 193 #   min_length - Minimum word length
 194 #   max_length - Maximum word length
 195 #
 196 # Returns: Filter function to check a word.
 197 sub build_filter {
 198     my ($config_ref) = @_;
 199
 200     # Build a filter from our command-line parameters.  This is an anonymous
 201     # sub that returns true to keep a word and false otherwise.
 202     my $filter = sub {
 203         my ($word)     = @_;
 204         my $length     = length($word);
 205         my $min_length = $config_ref->{'min-length'};
 206         my $max_length = $config_ref->{'max-length'};
 207
 208         # Check length.
 209         return if (defined($min_length) && $length < $min_length);
 210         return if (defined($max_length) && $length > $max_length);
 211
 212         # Check character classes.
 213         if ($config_ref->{ascii}) {
 214             return if $word =~ m{ [^[:ascii:]] }xms;
 215             return if $word =~ m{ [[:cntrl:]] }xms;
 216         }
 217
 218         # Check regex exclusions.
 219         if ($config_ref->{exclude}) {
 220             for my $pattern (@{ $config_ref->{exclude} }) {
 221                 return if $word =~ m{ $pattern }xms;
 222             }
 223         }
 224
 225         # Word passes.  Return success.
 226         return 1;
 227     };
 228     return $filter;
 229 }
 230
 231 ##############################################################################
 232 # Main routine
 233 ##############################################################################
 234
 235 # Always flush output.
 236 STDOUT->autoflush;
 237
 238 # Clean up the script name for error reporting.
 239 my $fullpath = $0;
 240 local $0 = basename($0);
 241
 242 # Parse the argument list.
 243 my %config;
 244 my @options = (
 245     'ascii|a',      'cdb|c=s',    'max-length|L=i', 'min-length|l=i',
 246     'manual|man|m', 'output|o=s', 'sqlite|s=s',     'exclude|x=s@',
 247 );
 248 Getopt::Long::config('bundling', 'no_ignore_case');
 249 GetOptions(\%config, @options);
 250 if ($config{manual}) {
 251     print_fh(\*STDOUT, "Feeding myself to perldoc, please wait...\n");
 252     exec('perldoc', '-t', $fullpath);
 253 }
 254 if (@ARGV != 1) {
 255     die "Usage: krb5-strength-wordlist <wordlist>\n";
 256 }
 257 if ($config{cdb} && ($config{output} || $config{sqlite})) {
 258     die "$0: -c cannot be used with -o or -s\n";
 259 } elsif ($config{output} && $config{sqlite}) {
 260     die "$0: -o cannot be used with -c or -s\n";
 261 }
 262 my $input = $ARGV[0];
 263
 264 # Build the filter closure.
 265 my $filter = build_filter(\%config);
 266
 267 # Process the input file into either wordlist output or a CDB file.
 268 open(my $in_fh, '<', $input)
 269   or die "$0: cannot open input file $input: $!\n";
 270 if ($config{output}) {
 271     write_wordlist($in_fh, $config{output}, $filter);
 272 } elsif ($config{cdb}) {
 273     write_cdb($in_fh, $config{cdb}, $filter);
 274 } elsif ($config{sqlite}) {
 275     write_sqlite($in_fh, $config{sqlite}, $filter);
 276 }
 277 close($in_fh) or die "$0: cannot read all of input file $input: $!\n";
 278
 279 # All done.
 280 exit(0);
 281 __END__
 282
 283 ##############################################################################
 284 # Documentation
 285 ##############################################################################
 286
 287 =for stopwords
 288 krb5-strength-wordlist krb5-strength cdb whitespace lookups lookup
 289 sublicense MERCHANTABILITY NONINFRINGEMENT krb5-strength --ascii Allbery
 290 regexes output-wordlist heimdal-strength SQLite output-wordlist
 291 output-sqlite DBI wordlist
 292
 293 =head1 NAME
 294
 295 krb5-strength-wordlist - Create a krb5-strength database from a word list
 296
 297 =head1 SYNOPSIS
 298
 299 B<krb5-strength-wordlist> [B<-am>] [B<-c> I<output-cdb>] [B<-l> I<min-length>]
 300     [B<-L> I<max-length>] [B<-o> I<output-wordlist>] [B<-s> I<output-sqlite>]
 301     [B<-x> I<exclude> ...] I<wordlist>
 302
 303 =head1 DESCRIPTION
 304
 305 B<krb5-strength-wordlist> converts a word list (a file containing one word
 306 per line) into a database that can be used by the krb5-strength plugin or
 307 B<heimdal-strength> command for checking passwords.  Two database formats
 308 are supported, with different features.  CDB is more space-efficient and
 309 possibly faster, but supports checking passwords only against exact
 310 matches or simple transformations (removing small numbers of leading and
 311 trailing characters).  SQLite creates a much larger database, but supports
 312 rejecting any password within edit distance one of a word in the word
 313 list.
 314
 315 CDB is a format invented by Dan Bernstein for fast, constant databases.
 316 The database is fixed during creation and cannot be changed without
 317 rebuilding it, and is optimized for very fast access.  For cdb, the
 318 database generated by this program will have keys for each word in the
 319 word list and the constant C<1> as the value.
 320
 321 SQLite stores the word list in a single table containing both each word
 322 and each word reversed.  This allows the krb5-strength plugin or
 323 B<heimdal-strength> command to reject passwords within edit distance one
 324 of any word in the word list.  (Edit distance one means that the word list
 325 entry can be formed by changing a single character of the password, either
 326 by adding one character, removing one character, or changing one character
 327 to a different character.)  However, the SQLite database will be much
 328 larger and lookups may be somewhat slower.
 329
 330 B<krb5-strength-wordlist> takes one argument, the input word list file.
 331 Use the B<-c> option to specify an output CDB file, B<-s> to specify an
 332 output SQLite file, or B<-o> to just filter the word list against the
 333 criteria given on the command line and generate a new word list.
 334 The input word list file does not have to be sorted.  See the individual
 335 option descriptions for more information.
 336
 337 =head1 OPTIONS
 338
 339 =over 4
 340
 341 =item B<-a>, B<--ascii>
 342
 343 Filter all words that contain non-ASCII characters or control characters
 344 from the resulting cdb file, leaving only words that consist solely of
 345 ASCII non-control characters.
 346
 347 =item B<-c> I<output-cdb>, B<--cdb>=I<output-cdb>
 348
 349 Create a CDB database in I<output-cdb>.  A temporary file named after
 350 I<output-cdb> with C<.data> appended will be created in the same directory
 351 and used to stage the database contents.  The actual CDB file will be
 352 built using the B<cdb> command, which must be on the user's path.  If
 353 either file already exists, B<krb5-strength-wordlist> will abort with an
 354 error.
 355
 356 This option cannot be used with B<-o> or B<-s>.
 357
 358 =item B<-L> I<maximum>, B<--max-length>=I<maximum>
 359
 360 Filter all words of length greater than I<maximum> from the resulting cdb
 361 database.  The length of each line (minus the separating newline) in the
 362 input word list will be checked against I<minimum> and will be filtered
 363 out of the resulting database if it is shorter.  Useful for generating
 364 password dictionaries from word lists that contain random noise that's
 365 highly unlikely to be used as a password.
 366
 367 The default is to not filter out any words for maximum length.
 368
 369 =item B<-l> I<minimum>, B<--min-length>=I<minimum>
 370
 371 Filter all words of length less than I<minimum> from the resulting cdb
 372 database.  The length of each line (minus the separating newline) in the
 373 input word list will be checked against I<minimum> and will be filtered
 374 out of the resulting database if it is shorter.  Useful for generating
 375 password dictionaries where shorter passwords will be rejected by a
 376 generic length check and no dictionary lookup will be done for a transform
 377 of the password shorter than the specified minimum.
 378
 379 The default is not to filter out any words for minimum length.
 380
 381 =item B<-m>, B<--man>, B<--manual>
 382
 383 Print out this documentation (which is done simply by feeding the script to
 384 C<perldoc -t>).
 385
 386 =item B<-o> I<wordlist>, B<--output>=I<wordlist>
 387
 388 Rather than creating a database, apply the filter rules given by the other
 389 command-line arguments and generate a new word list in the file name given
 390 by the I<wordlist> option.  This can be used to reduce the size of a raw
 391 word list file (such as one taken from Internet sources) by removing the
 392 words that will be filtered out of the dictionary anyway, thus reducing
 393 the size of the source required to regenerate the dictionary.
 394
 395 This option cannot be used with B<-c> or B<-s>.
 396
 397 =item B<-s> I<output-sqlite>, B<--sqlite>=I<output-sqlite>
 398
 399 Create a SQLite database in I<output-sqlite>.  If this file already
 400 exists, B<krb5-strength-wordlist> will abort with an error.  The resulting
 401 SQLite database will have one table, C<passwords>, with two columns,
 402 C<password> and C<drowssap>.  The first holds a word from the word list,
 403 and the second holds the same word reversed.
 404
 405 Using this option requires the DBI and DBD::SQLite Perl modules be
 406 installed.
 407
 408 This option cannot be used with B<-c> or B<-o>.
 409
 410 =item B<-x> I<exclude>, B<--exclude>=I<exclude>
 411
 412 Filter all words matching the regular expression I<exclude> from the
 413 resulting cdb database.  This regular expression will be matched against
 414 each line of the source word list after the trailing newline is removed.
 415 This option may be given repeatedly to add multiple exclusion regexes.
 416
 417 =back
 418
 419 =head1 AUTHOR
 420
 421 Russ Allbery <eagle@eyrie.org>
 422
 423 =head1 COPYRIGHT AND LICENSE
 424
 425 Copyright 2013, 2014 The Board of Trustees of the Leland Stanford Junior
 426 University
 427
 428 Permission is hereby granted, free of charge, to any person obtaining a
 429 copy of this software and associated documentation files (the "Software"),
 430 to deal in the Software without restriction, including without limitation
 431 the rights to use, copy, modify, merge, publish, distribute, sublicense,
 432 and/or sell copies of the Software, and to permit persons to whom the
 433 Software is furnished to do so, subject to the following conditions:
 434
 435 The above copyright notice and this permission notice shall be included in
 436 all copies or substantial portions of the Software.
 437
 438 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 439 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 440 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
 441 THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 442 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 443 FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 444 DEALINGS IN THE SOFTWARE.
 445
 446 =head1 SEE ALSO
 447
 448 cdb(1), L<DBI>, L<DBD::SQLite>
 449
 450 The cdb file format is defined at L<http://cr.yp.to/cdb.html>.
 451
 452 The current version of this program is available from its web page at
 453 L<http://www.eyrie.org/~eagle/software/krb5-strength/> as part of the
 454 krb5-strength package.
 455
 456 =cut