I ran into a similar challenge a bit ago - the generation of rainbow tables. Yes, there are a number of programs out there that do this, but I was attempting to apply the concept to create a generic module that could use any of the Digest modules. In any case, I didn't know about Algorithm::Loops then, so I reinvented the subset I needed. Whoops. ;-)
The nifty thing about the implementation, though, is that it's restartable -- or, rather, one can start at any state in the series (pre-set the odometer, if you will) and then get results for that and all following states. This is useful if, for example, you need all combinations of a given set of chars that are between 3 and 10 chars long.
Anyhow, I'm posting here because I think my code, being so special-purpose, might be easier to follow than the wonders of Algorithm::Loops (how tye manages to repeatedly pull off such deep magic, I will never know. Go tye!). It's also not complete, production code, so feel free to rip it to shreds (though I'd prefer patches).
package RainbowTable;
=pod =================================================================
+=========
=head1 NAME
RainbowTable - A module to assist in the creation of hash-based
rainbow tables
=head1 VERSION
This document describes RainbowTable version 0.01
=head1 SYNOPSIS
Generates a range of printable character combinations (such as might
be used for passwords) and converts them to hashes via a specifiable
hash function, caching the results for easy and fast searching later.
A hash type is required, other parameters are optional.
use RainbowTable;
#generate a table of MD5 hashes for all sets 1-10 chars in length
my $rainbow = RainbowTable->new(
hash => 'MD5', maxlength => 10, minlength=>1,
);
while ($rainbow->next) {
open my $fh, '>', $rainbow->hash or die($!);
print $fh $rainbow->string;
close $fh;
}
The iterative model is used, since it can take a I<very> long time to
generate the tables, and the interruption should be restartable.
use RainbowTable;
#resume processing using the 'start_at' parameter
my $rainbow = RainbowTable->new(
hash => 'MD5', start_at => 'aaaba',
);
You can specifiy your own character set:
# process only alphanumerics (no spaces, even)
my $rainbow = RainbowTable->new(
hash => 'MD5', chars => [ ('A'..'Z'), ('a'..'z'), (0..9) ]
);
Any hash type with a related Digest::* module can be specified by
name. For example, 'MD5' will load Digest::MD5 for hashing. The
module interface must have a 'hexdigest' method in OO mode.
=cut
use strict;
use warnings;
use Params::Validate qw/validate_with :types/;
#_____________________________________________________________________
+___ new()_
sub new {
# new ( )
my $self = bless {}, shift; # creates blessed-hash object
my %args = validate_with(
params => \@_,
spec => {
hash => 1,
minlength => { type => SCALAR , default => 1 },
maxlength => { type => SCALAR , default => 10 },
start_at => { type => SCALAR , default => '' },
chars => { type => ARRAYREF, default => undef },
},
);
# some extra param checking and initialization
unless ( defined $args{chars} ) {
for ( 32 .. 126 ) { push @{ $args{chars} }, chr($_) }
for ( 128 .. 168 ) { push @{ $args{chars} }, chr($_) }
}
foreach ( keys %args ) {
$self->{$_} = $args{$_};
}
$self->{hash} = _loadHash( $args{hash} );
$self->{SET} = join( '', @{ $args{chars} } );
die("Must have sets of at least 1 char") if $self->{minlength} < 1
+;
return $self;
}
#__________________________________________________________________ _l
+oadHash()_
sub _loadHash {
# _loadHash ( $name ) - loads hashing module by name
# Returns codeRef to hash object or dies on failure.
my ($name) = @_;
my $hashobj;
eval {
eval "require Digest::$name;" or die($@);
$hashobj = "Digest::$name"->new()
or die("Unable to construct object for '$name'. $@");
die("'$name' can't 'hexdigest'") unless $hashobj->can('hexdige
+st');
};
if ($@) {
die "Unable to initialize hashing function '$name': $@";
}
return $hashobj;
}
#__________________________________________________________________ sp
+aceSize()_
sub spaceSize {
# spaceSize ( ) - size of search space, ignoring starting location
my $self = shift;
my $base = @{ $self->{chars} };
my $size =
$base**$self->{maxlength} - $base**( $self->{minlength} - 1 ) +
+1;
return $size;
}
#_____________________________________________________________________
+__ next()_
sub next {
# next ( ) - generates the next string to deal with, updates 'star
+t_at'
my $self = shift;
my $size = length $self->{start_at};
my $max = length( $self->{SET} ) - 1;
while ( length( $self->{start_at} ) < $self->{minlength} ) {
$self->{start_at} .= substr( $self->{SET}, 0, 1 );
}
#return if we started with a too-short string. This is because we
+ will
#have just initialized it.
return 1 if $size < $self->{minlength};
# increment
my $col = $size - 1;
while ( $col >= 0 ) {
#find current char in set
my $loc = index( $self->{SET}, substr( $self->{start_at}, $col
+, 1 ) );
if ( $loc == $max ) {
# roll over
substr( $self->{start_at}, $col, 1 ) = substr( $self->{SET
+}, 0, 1 );
if ( $col == 0 ) {
# leftmost column rollover adds a new place
$self->{start_at} =
substr( $self->{SET}, 0, 1 ) . $self->{start_at};
last;
}
$col--;
}
else {
substr( $self->{start_at}, $col, 1 ) =
substr( $self->{SET}, $loc + 1, 1 );
last;
}
} #/while
# $self->next if length($self->{start_at}) < $self->{minlength}
+;
return 0 if length( $self->{start_at} ) > $self->{maxlength};
return 1;
}
#_____________________________________________________________________
+__ hash()_
sub hash {
# hash ( ) - calculates and returns hashed value
my $self = shift;
$self->{hash}->reset;
$self->{hash}->add( $self->string );
my $hash = $self->{hash}->hexdigest;
return $hash;
}
#_____________________________________________________________________
+ string()_
sub string {
# string ( ) - returns current working string
my $self = shift;
my $string = $self->{start_at};
return $string;
}
1;