#!/usr/bin/perl

## Jens Steube; Exploiting a SHA1 weakness in password cracking
##
## Demonstration tool to calculate the XOR zeros out
##

use strict;
use warnings;

my @subs = (3, 8, 14, 16);

## init the arrays and set them all to zero

my $db;

for (my $t = 0; $t < 80; $t++)
{
  for (my $r = 0; $r < 32; $r++)
  {
    $db->[$t]->[$r] = 0;
  }
}

## You can change the following line if you do not want to iterate W[0]

$db->[0]->[0] = 1;

for (my $t = 16; $t < 80; $t++)
{
  for my $sub (@subs)
  {
    my $tsub = $t - $sub;

    for (my $r = 0; $r < 32; $r++)
    {
      $db->[$t]->[$r + 1] += $db->[$tsub]->[$r];
    }
  }

  my @odd;

  for (my $r = 0; $r < 32; $r++)
  {
    next unless $db->[$t]->[$r] % 2;

    push @odd, $r;
  }

  my $str = join " ^ ", @odd;

  printf "%d: %s\n", $t, $str;
}