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 -- http://mail.python.org/mailman/listinfo/python-list
