Re: Arbitrarily Nested Loops

[radiantmatrix]

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;