The code below takes an arbitrary string, and adds some junk on the end of it to make the CRC come out to any arbitrary value. If you were going to forge many CRCs with the same polynomial, you could optimize the inner loop with a lookup table.
use String::CRC32;
my $initial_str = "foo bar";
my $desired_crc = 0x12345678;
my $magic = forge_crc(value => $desired_crc ^ 0xffffffff)
          ^ crc32($initial_str) ^ 0xffffffff;
my $forged_str = $initial_str . pack("V", $magic);
printf "%x\n", crc32($forged_str);

sub forge_crc {
  my (%opts) = @_;
  # default to the usual crc32 polynomial
  my $poly    = $opts{poly} || 0xedb88320;
  my $size    = $opts{size} || 32;
  my $highbit = 1 << ($size-1);
  my $reg     = $opts{value};
 
  $poly = ($poly << 1) ^ 1;
  for (1..$size) {
    $reg = ($reg & $highbit) ?
        ($reg << 1) ^ $poly : $reg << 1;
  }
  return $reg;
} # forge_crc

[download]

Replies are listed 'Best First'.
Re: Forge CRCs
by John M. Dlugosz (Monsignor) on Sep 13, 2001 at 09:47 UTC
    So, for a 32-bit CRC, appending 32 bits of data will have a 1-to-1 mapping of append values to all possible checksums. CRC has a lot of interesting properties.
[reply]
      Many interesting properties indeed, due to the simple mathematical structure of linear feedback shift registers. Basically, you take the bits of the input string to be the coefficients of a polynomial mod 2, and calculate the remainder modulus the CRC polynomial.

      You don't have to append to the end to get whatever CRC you want, either. By changing any 4 consecutive bytes, you can set the internal state of the CRC register however you like, as the code below shows. In certain conditions, you can do it with non-consecutive bytes, but it usually takes a little bit of a brute force search.

      Once again, you could optimize the "for (1..8)" loops with a lookup table (that's the ordinary way of calculating CRCs). It's easier to see what's happening this way, though. 

      # the usual crc32 polynomial
my $crc_poly = 0xedb88320;
my $crc_size = 32;

my $initial_str = "foo bar";
my $final_str   = "baz blat";
my $desired_crc = 0x12345678;

my $magic = forward_crc($initial_str, 0xffffffff)
    ^ reverse_crc("\0\0\0\0".$final_str,
        $desired_crc^0xffffffff);
my $forged_str = $initial_str . pack("V",$magic) .
    $final_str;

use String::CRC32;
printf "%x\n", crc32($forged_str);

# calculate an ordinary crc of $string,
# given the initial register contents
sub forward_crc {
  my ($str, $reg) = @_;
  foreach (split //, $str) {
    $reg ^= ord;
    for (1..8) {
      $reg = ($reg & 1) ?
          ($reg >> 1) ^ $crc_poly : $reg >> 1;
    }
  }
  return $reg;
} # forward_crc

# given the final register contents, calculate
# what the register state was before $str
sub reverse_crc {
  my ($str, $reg) = @_;
  my $poly = ($crc_poly << 1) ^ 1;
  my $highbit = 1 << ($crc_size - 1);
  foreach (reverse split //, $str) {
    for (1..8) {
      $reg = ($reg & $highbit) ?
          ($reg << 1) ^ $poly : $reg << 1;
    }
    $reg ^= ord;
  }
  return $reg;
} # reverse_crc

      [download]
[reply]
[d/l]

Back to Cool Uses for Perl