Reverse engineering CRC?

[Steven D'Aprano]

On Mon, 08 Mar 2010 16:09:12 +1300, Gregory Ewing wrote:

> Given some known data/crc pairs, how feasible is it to figure out the
> polynomial being used to generate the crc?

Can you just ask the application developer what CRC is being used? Or 
look at the source code? Disassemble the binary?


> In the case I'm looking at, it appears that the crc size may be at least
> 24 bits, so just trying all possible polynomials probably isn't doable.

"At least"? Can't you tell by looking at them?

A good place to start is here:

http://en.wikipedia.org/wiki/Cyclic_redundancy_check
http://en.wikipedia.org/wiki/List_of_checksum_algorithms

You can at least eliminate known CRCs. There doesn't appear to be any 24-
bit CRCs in common use, and very few other 24-bit checksums either, so 
you're probably looking at a custom CRC.

 
> An article I found hints at the possibility of using GCDs to make the
> search more efficient, but doesn't go into any details. Anyone know of
> any literature about this?

If you're reduced to trying to determine the polynomial from a sample of 
checksums, that's a curve fitting problem. There are various ways to fit 
polynomials through a set of known points, but as far as I know none of 
them are designed for reverse-engineering CRCs.

You may be able to find something about curve-fitting using discrete 
maths (i.e. where all values are limited to integers) or with constraints.

You should probably take this to somewhere like sci.crypt. Here's a 
thread from a few years back which might give you some hints:

http://www.derkeiler.com/Newsgroups/sci.crypt/2008-07/msg00035.html

Or here:

http://stackoverflow.com/questions/401231/determining-crc-algorithm-from-
data-crc-embedded-application


-- 
Steven