Skip to content

Instantly share code, notes, and snippets.

@mwgamera
Created February 14, 2014 12:23
Show Gist options
  • Save mwgamera/9000138 to your computer and use it in GitHub Desktop.
Save mwgamera/9000138 to your computer and use it in GitHub Desktop.
#!/usr/bin/env perl
# CRC32 preimage with fixed prefix/suffix.
# klg, Feb 2014
use strict;
# CRC32 table
my @crc_table;
for my $n (0 .. 255) {
my $c = $n;
for my $k (0 .. 7) {
if ($c & 1) {
$c = 0xedb88320 ^ ($c >> 1);
} else {
$c = $c >> 1;
}
}
$crc_table[$n] = $c;
}
# "Inverse" table
my @crc_rtab;
$crc_rtab[$crc_table[$_] >> 24] = ($crc_table[$_] << 8) | $_ for 0 .. 255;
$_ &= 0xffffffff for @crc_rtab;
# Convert string to array of bytes
sub str2bytes($) {
local $_ = shift;
utf8::encode($_) if utf8::is_utf8($_);
return unpack 'C*'
}
# Given current state and some bytes return updated state
sub update_crc($@) {
my $c = shift;
$c = $crc_table[$_ ^ $c & 0xff] ^ ($c >> 8) for @_;
return $c;
}
# Inverse of update_crc (tempted to call it downdate)
sub deupdate_crc($@) {
my $c = shift;
$c = $_ ^ $crc_rtab[$c >> 24] ^ (($c & 0xffffff) << 8) for reverse @_;
return $c;
}
# Compute the CRC32 of given string
sub crc32($) {
0xffffffff ^ update_crc 0xffffffff, str2bytes shift;
}
# Find collision with given prefix and/or suffix
sub solve($;$$) {
my $crc = 0xffffffff ^ shift;
my $pc = update_crc 0xffffffff, str2bytes(shift // '');
my $sc = deupdate_crc $crc, str2bytes(shift // '');
pack 'V', $pc ^ deupdate_crc $sc, 0, 0, 0, 0;
}
do {
my @fuzz = map {{
str1 => join('', map { chr rand 256 } 0 .. 128 * rand),
str2 => join('', map { chr rand 256 } 0 .. 128 * rand),
int1 => (0xffffffff & rand 2**32),
}} 0 .. 100;
# CRC32 is the same as used by Zlib, PNG, Ethernet, et al.
my $zcrc32 = eval {
require Compress::Raw::Zlib;
\&Compress::Raw::Zlib::crc32;
};
for (@fuzz) {
die "Assertion failed"
unless crc32($_->{str1}) == $zcrc32->($_->{str1});
}
# deupdate_crc is inverse of update_crc
for (@fuzz) {
my @s = str2bytes $_->{str1};
die "Assertion failed"
unless deupdate_crc(update_crc($_->{int1}, @s), @s) == $_->{int1};
}
# $infix = solve($crc[, $prefix[, $suffix]])
# returns 4-byte string, s.t. crc32("$prefix$infix$suffix") == $crc
for (@fuzz) {
my $q = solve($_->{int1}, $_->{str1}, $_->{str2});
die "Assertion failed"
unless crc32("$_->{str1}$q$_->{str2}") == $_->{int1};
}
};
1;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment