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]

In reply to Re: Re: Forge CRCs by no_slogan
in thread Forge CRCs by no_slogan

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.