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 => 1 };
 135     my $dbh = DBI->connect("dbi:SQLite:dbname=$output", q{}, q{}, $options);
 136     $dbh->do($SQLITE_CREATE);
 137
 138     # Tune SQLite to improve the speed of bulk inserts.  Use unsafe insert
 139     # processing and increase the index cache to 500MB.
 140     $dbh->do('PRAGMA synchronous = 0');
 141     $dbh->do('PRAGMA cache_size = 500000');
 142
 143     # Start a transaction and prepare the insert statement for each word.
 144     $dbh->begin_work();
 145     my $sth = $dbh->prepare($SQLITE_INSERT);
 146
 147     # Walk through the input word list and add each word that passes the
 148     # filter to the database, both as-is and reversed.
 149     while (defined(my $word = <$in_fh>)) {
 150         chomp($word);
 151         next if !$filter->($word);
 152         my $reversed = reverse($word);
 153         $sth->execute($word, $reversed);
 154     }
 155
 156     # Commit and close the database.
 157     $dbh->commit;
 158     $dbh->disconnect;
 159     return;
 160 }
 161
 162 # Filter the given input file and write the results to a new wordlist.
 163 #
 164 # $in_fh  - Input file handle for the source wordlist
 165 # $output - Output file name to which to write the resulting wordlist
 166 # $filter - Reference to sub that returns true to keep a word, false otherwise
 167 #
 168 # Returns: undef
 169 #  Throws: Text exception on output failure
 170 sub write_wordlist {
 171     my ($in_fh, $output, $filter) = @_;
 172     open(my $out_fh, '>', $output)
 173       or die "$0: cannot create output file $output: $!\n";
 174
 175     # Walk through the input word list and write each word that passes the
 176     # filter to the output file handle.
 177     while (defined(my $word = <$in_fh>)) {
 178         chomp($word);
 179         next if !$filter->($word);
 180         print_fh($out_fh, "$word\n");
 181     }
 182
 183     # All done.
 184     close($out_fh) or die "$0: cannot write to output file $output: $!\n";
 185     return;
 186 }
 187
 188 ##############################################################################
 189 # Filtering
 190 ##############################################################################
 191
 192 # Given the parsed command-line options as a hash, construct a filter for the
 193 # word list and return it.  The filter will, given a word, return true if the
 194 # word should be included in the dictionary and false otherwise.
 195 #
 196 # $config_ref - Hash of configuration options
 197 #   ascii      - Strip non-printable or non-ASCII words
 198 #   exclude    - Reference to array of regex patterns to exclude
 199 #   min_length - Minimum word length
 200 #   max_length - Maximum word length
 201 #
 202 # Returns: Filter function to check a word.
 203 sub build_filter {
 204     my ($config_ref) = @_;
 205
 206     # Build a filter from our command-line parameters.  This is an anonymous
 207     # sub that returns true to keep a word and false otherwise.
 208     my $filter = sub {
 209         my ($word)     = @_;
 210         my $length     = length($word);
 211         my $min_length = $config_ref->{'min-length'};
 212         my $max_length = $config_ref->{'max-length'};
 213
 214         # Check length.
 215         return if (defined($min_length) && $length < $min_length);
 216         return if (defined($max_length) && $length > $max_length);
 217
 218         # Check character classes.
 219         if ($config_ref->{ascii}) {
 220             return if $word =~ m{ [^[:ascii:]] }xms;
 221             return if $word =~ m{ [[:cntrl:]] }xms;
 222         }
 223
 224         # Check regex exclusions.
 225         if ($config_ref->{exclude}) {
 226             for my $pattern (@{ $config_ref->{exclude} }) {
 227                 return if $word =~ m{ $pattern }xms;
 228             }
 229         }
 230
 231         # Word passes.  Return success.
 232         return 1;
 233     };
 234     return $filter;
 235 }
 236
 237 ##############################################################################
 238 # Main routine
 239 ##############################################################################
 240
 241 # Always flush output.
 242 STDOUT->autoflush;
 243
 244 # Clean up the script name for error reporting.
 245 my $fullpath = $0;
 246 local $0 = basename($0);
 247
 248 # Parse the argument list.
 249 my %config;
 250 my @options = (
 251     'ascii|a',      'cdb|c=s',    'max-length|L=i', 'min-length|l=i',
 252     'manual|man|m', 'output|o=s', 'sqlite|s=s',     'exclude|x=s@',
 253 );
 254 Getopt::Long::config('bundling', 'no_ignore_case');
 255 GetOptions(\%config, @options);
 256 if ($config{manual}) {
 257     print_fh(\*STDOUT, "Feeding myself to perldoc, please wait...\n");
 258     exec('perldoc', '-t', $fullpath);
 259 }
 260 if (@ARGV != 1) {
 261     die "Usage: krb5-strength-wordlist <wordlist>\n";
 262 }
 263 if ($config{cdb} && ($config{output} || $config{sqlite})) {
 264     die "$0: -c cannot be used with -o or -s\n";
 265 } elsif ($config{output} && $config{sqlite}) {
 266     die "$0: -o cannot be used with -c or -s\n";
 267 }
 268 my $input = $ARGV[0];
 269
 270 # Build the filter closure.
 271 my $filter = build_filter(\%config);
 272
 273 # Process the input file into either wordlist output or a CDB file.
 274 open(my $in_fh, '<', $input)
 275   or die "$0: cannot open input file $input: $!\n";
 276 if ($config{output}) {
 277     write_wordlist($in_fh, $config{output}, $filter);
 278 } elsif ($config{cdb}) {
 279     write_cdb($in_fh, $config{cdb}, $filter);
 280 } elsif ($config{sqlite}) {
 281     write_sqlite($in_fh, $config{sqlite}, $filter);
 282 }
 283 close($in_fh) or die "$0: cannot read all of input file $input: $!\n";
 284
 285 # All done.
 286 exit(0);
 287 __END__
 288
 289 ##############################################################################
 290 # Documentation
 291 ##############################################################################
 292
 293 =for stopwords
 294 krb5-strength-wordlist krb5-strength cdb whitespace lookups lookup
 295 sublicense MERCHANTABILITY NONINFRINGEMENT krb5-strength --ascii Allbery
 296 regexes output-wordlist heimdal-strength SQLite output-wordlist
 297 output-sqlite DBI wordlist
 298
 299 =head1 NAME
 300
 301 krb5-strength-wordlist - Create a krb5-strength database from a word list
 302
 303 =head1 SYNOPSIS
 304
 305 B<krb5-strength-wordlist> [B<-am>] [B<-c> I<output-cdb>] [B<-l> I<min-length>]
 306     [B<-L> I<max-length>] [B<-o> I<output-wordlist>] [B<-s> I<output-sqlite>]
 307     [B<-x> I<exclude> ...] I<wordlist>
 308
 309 =head1 DESCRIPTION
 310
 311 B<krb5-strength-wordlist> converts a word list (a file containing one word
 312 per line) into a database that can be used by the krb5-strength plugin or
 313 B<heimdal-strength> command for checking passwords.  Two database formats
 314 are supported, with different features.  CDB is more space-efficient and
 315 possibly faster, but supports checking passwords only against exact
 316 matches or simple transformations (removing small numbers of leading and
 317 trailing characters).  SQLite creates a much larger database, but supports
 318 rejecting any password within edit distance one of a word in the word
 319 list.
 320
 321 CDB is a format invented by Dan Bernstein for fast, constant databases.
 322 The database is fixed during creation and cannot be changed without
 323 rebuilding it, and is optimized for very fast access.  For cdb, the
 324 database generated by this program will have keys for each word in the
 325 word list and the constant C<1> as the value.
 326
 327 SQLite stores the word list in a single table containing both each word
 328 and each word reversed.  This allows the krb5-strength plugin or
 329 B<heimdal-strength> command to reject passwords within edit distance one
 330 of any word in the word list.  (Edit distance one means that the word list
 331 entry can be formed by changing a single character of the password, either
 332 by adding one character, removing one character, or changing one character
 333 to a different character.)  However, the SQLite database will be much
 334 larger and lookups may be somewhat slower.
 335
 336 B<krb5-strength-wordlist> takes one argument, the input word list file.
 337 Use the B<-c> option to specify an output CDB file, B<-s> to specify an
 338 output SQLite file, or B<-o> to just filter the word list against the
 339 criteria given on the command line and generate a new word list.
 340 The input word list file does not have to be sorted.  See the individual
 341 option descriptions for more information.
 342
 343 =head1 OPTIONS
 344
 345 =over 4
 346
 347 =item B<-a>, B<--ascii>
 348
 349 Filter all words that contain non-ASCII characters or control characters
 350 from the resulting cdb file, leaving only words that consist solely of
 351 ASCII non-control characters.
 352
 353 =item B<-c> I<output-cdb>, B<--cdb>=I<output-cdb>
 354
 355 Create a CDB database in I<output-cdb>.  A temporary file named after
 356 I<output-cdb> with C<.data> appended will be created in the same directory
 357 and used to stage the database contents.  The actual CDB file will be
 358 built using the B<cdb> command, which must be on the user's path.  If
 359 either file already exists, B<krb5-strength-wordlist> will abort with an
 360 error.
 361
 362 This option cannot be used with B<-o> or B<-s>.
 363
 364 =item B<-L> I<maximum>, B<--max-length>=I<maximum>
 365
 366 Filter all words of length greater than I<maximum> from the resulting cdb
 367 database.  The length of each line (minus the separating newline) in the
 368 input word list will be checked against I<minimum> and will be filtered
 369 out of the resulting database if it is shorter.  Useful for generating
 370 password dictionaries from word lists that contain random noise that's
 371 highly unlikely to be used as a password.
 372
 373 The default is to not filter out any words for maximum length.
 374
 375 =item B<-l> I<minimum>, B<--min-length>=I<minimum>
 376
 377 Filter all words of length less than I<minimum> from the resulting cdb
 378 database.  The length of each line (minus the separating newline) in the
 379 input word list will be checked against I<minimum> and will be filtered
 380 out of the resulting database if it is shorter.  Useful for generating
 381 password dictionaries where shorter passwords will be rejected by a
 382 generic length check and no dictionary lookup will be done for a transform
 383 of the password shorter than the specified minimum.
 384
 385 The default is not to filter out any words for minimum length.
 386
 387 =item B<-m>, B<--man>, B<--manual>
 388
 389 Print out this documentation (which is done simply by feeding the script to
 390 C<perldoc -t>).
 391
 392 =item B<-o> I<wordlist>, B<--output>=I<wordlist>
 393
 394 Rather than creating a database, apply the filter rules given by the other
 395 command-line arguments and generate a new word list in the file name given
 396 by the I<wordlist> option.  This can be used to reduce the size of a raw
 397 word list file (such as one taken from Internet sources) by removing the
 398 words that will be filtered out of the dictionary anyway, thus reducing
 399 the size of the source required to regenerate the dictionary.
 400
 401 This option cannot be used with B<-c> or B<-s>.
 402
 403 =item B<-s> I<output-sqlite>, B<--sqlite>=I<output-sqlite>
 404
 405 Create a SQLite database in I<output-sqlite>.  If this file already
 406 exists, B<krb5-strength-wordlist> will abort with an error.  The resulting
 407 SQLite database will have one table, C<passwords>, with two columns,
 408 C<password> and C<drowssap>.  The first holds a word from the word list,
 409 and the second holds the same word reversed.
 410
 411 Using this option requires the DBI and DBD::SQLite Perl modules be
 412 installed.
 413
 414 This option cannot be used with B<-c> or B<-o>.
 415
 416 =item B<-x> I<exclude>, B<--exclude>=I<exclude>
 417
 418 Filter all words matching the regular expression I<exclude> from the
 419 resulting cdb database.  This regular expression will be matched against
 420 each line of the source word list after the trailing newline is removed.
 421 This option may be given repeatedly to add multiple exclusion regexes.
 422
 423 =back
 424
 425 =head1 AUTHOR
 426
 427 Russ Allbery <eagle@eyrie.org>
 428
 429 =head1 COPYRIGHT AND LICENSE
 430
 431 Copyright 2016 Russ Allbery <eagle@eyrie.org>
 432
 433 Copyright 2013, 2014 The Board of Trustees of the Leland Stanford Junior
 434 University
 435
 436 Permission is hereby granted, free of charge, to any person obtaining a
 437 copy of this software and associated documentation files (the "Software"),
 438 to deal in the Software without restriction, including without limitation
 439 the rights to use, copy, modify, merge, publish, distribute, sublicense,
 440 and/or sell copies of the Software, and to permit persons to whom the
 441 Software is furnished to do so, subject to the following conditions:
 442
 443 The above copyright notice and this permission notice shall be included in
 444 all copies or substantial portions of the Software.
 445
 446 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 447 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 448 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
 449 THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 450 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 451 FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 452 DEALINGS IN THE SOFTWARE.
 453
 454 =head1 SEE ALSO
 455
 456 cdb(1), L<DBI>, L<DBD::SQLite>
 457
 458 The cdb file format is defined at L<http://cr.yp.to/cdb.html>.
 459
 460 The current version of this program is available from its web page at
 461 L<https://www.eyrie.org/~eagle/software/krb5-strength/> as part of the
 462 krb5-strength package.
 463
 464 =cut