tricky crc algorithm

Question

Hi,

I am trying to find the crc that works with the following results. The byte string consists of 4 bytes (ie. CE1E) and the crc is an single byte (ie. 03)

byte crc
CE1E 03
CE20 45
CE22 6F
0000 C0
0001 D4
FFFF 95

Can anyone help?

Answer 1

Assuming they are two byte (16 bit) values, I've tried a few on some online CRC generators without getting your results. So it looks like it's not a commonly used CRC algorithm.

Do you have any clues about the likely algorithm? Or is this a homework assignment and you're supposed to reverse-engineer the CRC algorithm/parameters?

Summary: more information needed.

Answer 2

First, 4 hex digits aren't 4 bytes. Since all your examples show 4 hex digits -- 2 bytes -- I'll assume you mean 2 bytes.

There are only 65,536 distinct hash values, here's what you do.

Execute the hash function for all 65,536 values from 0000 to FFFF. Tabulate the results. That table is the function. It maps input value to output value.

While lame, it's always correct, it's not terribly big (65K bytes), and it's really fast after you've done the calculation.

You can't reverse engineer hash functions very easily. The good ones are sophisticated state machines that use all of the input bits in some "fair" way so that the output values are dramatically different for input values that differ by only a few bits.

If you compare 0000 with 0001, 0002, 0004, 0008, 0010, 0020, 0040, 0080, 0100, 0200, 0400, 0800, 1000, 2000, 4000 and 8000, you might be able to figure out what each bit contributes to the hash. But I doubt it.

Answer 3

http://www.geocities.com/SiliconValley/Pines/8659/crc.htm#r2

It looks to my inexperienced eyes that you will have to implement a general crc algorithm and try it out with several polys (try the "popular" ones mentioned in that article first).

edit: after further reading, it seems that you have to take into account reverse polys too.

Answer 4

A CRC is simply division, just like you learn long-hand division in grade school except that add and subtract are replaced with XOR. So what you need to do is solve the following equations in GF(2):

CE1E % p = 03
CE20 % p = 45
CE22 % p = 6F
0000 % p = C0
0001 % p = D4
FFFF % p = 95

There is no polynomial p for which 0000%p = c0. (0 modulo p is 0 for all values of p.) So maybe it's (x+input) % p = crc. In your case, x must be c0. If that's true, then (x+0001)%p must be c1. Looks like it isn't a CRC at all. If you're determined and you believe that the answer is linear, make a matrix of zeroes and ones that is invertible and solve the set of equations that arises from your matrix times input = output. You'll need more inputs, though.