Created
February 14, 2014 12:23
-
-
Save mwgamera/9000138 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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