#!/usr/bin/perl # crcbfs.pl # Version 1.01 # Greg Cook, 15/Jul/2008 # Finds parameters of a Cyclic Redundancy Check algorithm by calculation # or brute force search, given three or more data points in the form of # known parameters or messages ending with a CRC code produced by that # algorithm. # Usage: perl crcbfs.pl HEX WIDTH MODE PARM STRING STRING... # HEX # 0 if PARM and STRINGs are in binary, 1 if in hexadecimal. # WIDTH # Number of bits in CRC code = highest power in G(x), # usually 16. # MODE # A number specified as follows: # \ You have: You want: Action: # a -nothing- Init, Poly, give guesses for XorOut, see (k) # XorOut (usually 0000 or FFFF), preferably # giving STRINGs all the same length, # then validate with (f) # b Init Poly, XorOut first find the Poly, see (a), then # validate with (f) or see (e) # c Init, Poly Augment same as finding XorOut from # Remainder, see (g) # d Init, Poly Remainder Use generic CRC calculator on # message+CRC with XorOut=0 # e Init, Poly XorOut use generic CRC calculator on plain # message with XorOut=message CRC # f Poly Init, XorOut MODE=2, PARM=Poly, at least two # STRINGs must be different lengths # g Poly, Remainder XorOut MODE=3, PARM=Poly, # first STRING=Remainder, # second STRING=(2xWIDTH) zero bits. # h Poly, XorOut Init MODE=3, PARM=Poly, # first STRING=XorOut, # second STRING=message+CRC # j Remainder Init, Poly MODE=1, PARM=Remainder # k XorOut Init, Poly MODE=0, PARM=XorOut # PARM # The known XorOut value, expected remainder or polynomial. See # MODE. # When MODE = 0 or 1 and all STRINGs are the same length, the value # of PARM is only considered when generating the Init value, # not when searching for the polynomial. # STRING STRING... # Two or more strings consisting of message + CRC. Binary strings # are the bits in TRANSMISSION order. Hex strings are a simple # left-to-right translation of the equivalent binary string. # When MODE = 3 the first STRING is the XorOut value. # Returns a string of the form: CRC width (decimal), polynomial (hex), # a question mark denoting that the transmission endianness is not # known, the Init value and the XorOut value (both hex). If the wrong # polynomial (or no polynomial) is found, try reversing the bits of each # byte and/or the bytes of the CRC code. # Queries on "ZMODEM": 16,1021,0000,f,f,0000,31C3 # $ perl crcbfs.pl 1 16 0 0 312672 321611 ==> 1021 # $ perl crcbfs.pl 1 16 0 0 312672 321611 330630 ==> 1021 # $ perl crcbfs.pl 1 16 0 0 31323334353637383931C3 \ # 3938373635343332319CAD ==> 1021; E03E # $ perl crcbfs.pl 1 16 0 0 31323334353637383931C3 \ # 3938373635343332319CAD \ # 3132333435343332316EA8 ==> 1021 # $ perl crcbfs.pl 1 16 0 0 321611 330630 ==> 1021 # Queries on "CRC-16/I-CODE" # 16,1021,FFFF,f,f,FFFF,D64E # $ perl crcbfs.pl 1 16 3 1021 1D0F 00000000 ==> FFFF # $ perl crcbfs.pl 1 16 3 1021 FFFF \ # 313233343536373839D64E ==> FFFF # Queries on "CRC-16/USB": 16,8005,FFFF,t,t,FFFF,B4C8 # ASCII "1" ==> 6B81, "2" ==> 6AC1, "12" ==> 0A6A # $ perl crcbfs.pl 1 16 0 0 8C81D6 4C8356 ==> 8005; 0006 # (init=D580) # $ perl crcbfs.pl 1 16 0 0 8C81D6 8C4C5650 -none found- # $ perl crcbfs.pl 1 16 0 FFFF 8C81D6 8C4C5650 ==> 8005 # $ perl crcbfs.pl 1 16 1 800D 8C81D6 8C4C5650 ==> 8005 # $ perl crcbfs.pl 1 16 2 8005 8C81D6 4C8356 -cannot derive- # $ perl crcbfs.pl 1 16 2 8005 8C81D6 8C4C5650 ==> FFFF,FFFF # $ perl crcbfs.pl 1 16 3 8005 FFFF 8C4C5650 ==> FFFF # Query on "CRC-11": 11,385,01A,f,f,000,5A3 # $ perl crcbfs.pl 1 11 0 0 6004411B 60084304 000C45D2 ==> 385,00D # $ perl crcbfs.pl 0 11 0 0 \ # 1100000000001000100000100011011 \ # 1100000000010000100001100000100 \ # 0000000000011000100010111010010 ==> 385,01A # DISCLAIMER # This software is supplied without warranty, not even the implied # warranties of merchantability or fitness for a particular purpose. In # no event shall the author or his suppliers be liable for any loss, # damage, injury or death, of any nature and howsoever caused, arising # from the use of, or failure, inability or unwillingness to use, this # software. $ZERO = "0"; $ONE = "1"; my ($base,$bits,$mode,$parm,@strings) = @ARGV; if($base) { # hexadecimal ($parm,@strings) = map {unpack('B*',pack('H*',$_))} ($parm,@strings); } my (@result) = &crcbfs($bits,$mode,$parm,@strings); print join("\n",@result),"\n"; exit(0); sub crcbfs ($$@) { my ($bits,$mode,$parm,@strings) = @_; if($mode == 2 || $mode == 3) { $parm = $ONE.substr($parm,-$bits); } if($mode == 2) { return(&initbfs($parm,@strings)); } if($mode == 3) { return(&getparams($parm,0,$strings[0],$strings[1])); } my (@workstrings) = &modulate($mode,$parm,@strings); my ($i,$j,$poly,@result); $i=1<<$bits; print STDERR "Searching for polynomials\n"; do { print STDERR "." unless ($i & 0x3FF); $poly = &inttobin($i); for($j=0; $j<@workstrings && &polydiv($workstrings[$j],$poly) == 0; ++$j) {} if($j>=@workstrings) { push @result,&getparams($poly,$mode,$parm,$strings[0]); } ++$i; } while($i<2<<$bits); print STDERR "\n"; return(@result); } sub modulate ($$@) { my ($mode,$parm,@strings) = @_; my ($long,$short,@result); foreach $a (@strings) { foreach $b (@strings) { next if $a eq $b; if(length($a) == length($b)) { $long = &norm(&strxor($a,$b)); } else { if(length($a) > length($b)) { $long=$a; $short=$b; } else { $long=$b; $short=$a; } if($mode) { # expected remainder $long.=$parm; $short.=$parm; } else { # XorOut substr($long,-length($parm)) = &strxor(substr($long,-length($parm)),$parm); substr($short,-length($parm)) = &strxor(substr($short,-length($parm)),$parm); } # justify short string $short .= $ZERO x (length($long)-length($short)); $long = &norm(&strxor($long,$short)); } push @result,$long unless grep {$_ eq $long} @result; } } return @result; } sub strxor ($$) { my ($a,$b) = @_; my ($i,$out); for($i=0;$i= length($divisor) && $dividend ne $ZERO) { substr($dividend,0,length($divisor)) = &strxor(substr($dividend,0,length($divisor)), $divisor); $dividend = &norm($dividend); } return $dividend; } sub undiv ($$) { my ($div,$poly) = @_; my ($result) = &polydiv(scalar(reverse($div)), scalar(reverse($poly))); $result = $ZERO x (length($poly)-1-length($result)) . $result; return(scalar(reverse($result))); } sub norm ($) { my ($string) = @_; return(substr($string,index($string,$ONE)) || $ZERO); } sub inttobin ($) { my ($i) = @_; my ($result); if($i < 1<<31) { return(&norm(unpack('B*',pack('N',$i)))); } else { while($i>0) { $result .= ($i & 1); $i >>= 1; } return(scalar(reverse($result))); } } sub bintoint ($) { my ($i) = @_; my ($result); while($i ne '') { $result = ($result << 1) | (substr($i,0,1,'') & 1); } return($result); } sub initbfs ($@) { my ($poly,@strings) = @_; my ($bits,$intpoly,$string,$message,$pad,$a,$b,$abm,$abt,$abh, $i,$j,$ninit,$init,$xorout,@blanks,@workstring,@result); $bits = length($poly)-1; $intpoly = &bintoint(substr($poly,1)); foreach $string (@strings) { # calculate blankmsg.((Init.blankmsg.blankCRC) % poly) ^ XorOut $message = substr($string,0,length($string)-$bits); $pad = &polydiv($message.($ZERO x $bits),$poly); $pad = $ZERO x ($bits - length($pad)).$pad; push @blanks,&strxor($string,$message.$pad); } foreach $a (@blanks) { foreach $b (@blanks) { next if $a eq $b; die "Inconsistent Init ^ XorOut" if length($a) == length($b); $abt = &strxor(substr($a,-$bits),substr($b,-$bits)); # = (Init.blankmsg1 ^ Init.blankmsg2).blankCRC % poly if(length($a) > length($b)) { $abm = length($b) - $bits; } else { $abm = length($a) - $bits; } $abt =($ZERO x $abm) . $abt; $abh = $ZERO x abs(length($a) - length($b)); $abh .= &undiv($abt,$poly); push @workstrings,$abh unless grep {$_ eq $abh} @workstrings; } } unless(@workstrings) { print STDERR "Cannot derive Init as all strings the same length\n"; return((sprintf("%d %X ? ? ?",$bits,$intpoly))); } $i=0; print STDERR "Searching for Init values\n"; do { print STDERR "." unless ($i & 0x3FF); $ninit = $init = &inttobin($i); if(length($init) < $bits) { $init = ($ZERO x ($bits-length($init))).$init; } for($j=0; $j<@workstrings && &norm(&polydiv(&strxor(substr($workstrings[$j],0,$bits),$init) .substr($workstrings[$j],$bits),$poly)) eq $ninit; ++$j) {} if($j>=@workstrings) { $xorout = &polydiv(&strxor(substr($strings[0],0,$bits),$init) .substr($strings[0],$bits),$poly); $xorout = &bintoint($xorout); push @result,sprintf("%d %X ? %X %X",$bits,$intpoly,$i,$xorout); print STDERR "\nFound parameters ",$result[$#result],"\n"; } ++$i; } while($i<1<<$bits); print STDERR "\n"; return(@result); } sub getparams ($$$$) { my ($poly,$mode,$parm,$string) = @_; my ($bits,$result); $bits = length($poly)-1; if($mode == 1) { # expected remainder $parm = $ZERO x ($bits+$bits-length($parm)).$parm; $parm=&undiv($parm,$poly); } substr($string,-length($parm)) = &strxor(substr($string,-length($parm)),$parm); $result = &undiv($string,$poly); $result = &bintoint($result); $parm = &bintoint($parm); $poly = &bintoint(substr($poly,1)); $result = sprintf("%d %X ? %X %X",$bits,$poly,$result,$parm); print STDERR "\nFound parameters $result\n"; return($result); } # End of crcbfs.pl