How could I guess a checksum algorithm?

Question

How can I figure out the CRC algorithm if a given code + CRC string is given?

I have got several strings consisting of code + matching CRCs but don't know how to calculate the CRC in question so that I could produce more code strings. Here are some samples (16bit code + 4bit CRC):

0010101000011101 + 0000
0010101000011111 + 0001
1000110011101101 + 0001
0000000000000100 + 0010
0011100011001110 + 0011
1000110011101110 + 0100
0001011110101100 + 0100
0010101000011110 + 0101
0011100011001101 + 0110
0001011110101111 + 0111
0011100011001100 + 1001
0011100011001111 + 1010
0001011110101101 + 1011
0000000000001000 + 1011
0000111100001101 + 1100
0000000000001100 + 1100
1111111111111111 + 1101
1000110011101111 + 1101
1000110011101100 + 1110
0001011110101110 + 1110
1111111100001101 + 1110
0010101000011100 + 1111

These codes come from a RF (433MHz) sender like the X10 products.

I am not sure if this is a CRC or what it is, but at least it calculated somehow out of those code strings.

Updates

RE: finding the specifications I also think would be the best solution but since this is no option I need to brute force the checksum calculation somehow.

This is the problem, I don't have the specifications and I can´t get them anywhere. I have tried several different checksum calculation methods without result, isn't there a way to compare the input strings finding out what they have in common and this way getting the algorithm

Answer 1

What makes you think it is a CRC? Usually CRCs are not used for such small pieces of data.

To me this rather looks like some kind of parity, ECC (actually FEC) or Reed-Solomon code. Might be Hamming Code - Hamming widely used in industry, in telecomunications.

Answer 2

['0010101000011101', '0000', '0'] ['0010101000011110', '0101', '5'] [1, 3]
['1000110011101101', '0001', '1'] ['1000110011101110', '0100', '4'] [1, 3]
['0000000000000100', '0010', '2'] ['0000000000001000', '1011', 'b'] [0, 3]
['0011100011001110', '0011', '3'] ['0011100011001101', '0110', '6'] [1, 3]
['0001011110101100', '0100', '4'] ['0001011110101111', '0111', '7'] [2, 3]
['0011100011001100', '1001', '9'] ['0011100011001111', '1010', 'a'] [2, 3]
['0001011110101101', '1011', 'b'] ['0001011110101110', '1110', 'e'] [1, 3]
['1000110011101111', '1101', 'd'] ['1000110011101100', '1110', 'e'] [2, 3]

results of differential "analysis", this does not look like crc, reference: http://www.cosc.canterbury.ac.nz/greg.ewing/essays/CRC-Reverse-Engineering.html

I doubt it's hamming code either, as 4 parity bits only allow 11 data bits, not 16.

Answer 3

Judging by the length of the strings versus the length of the checksum, I would say this is a simple 1-error correcting checksum. Its probably one of the simple ones using hamming distances. I can't remember off hand how it worked, and I don't have any information theory/linear algebra textbooks on me.

Answer 4

@mecki might be correct but it's hard to know. You might try Data format for X-10 wireless units and X-10 FAQ.

Answer 5

Probably it is not a CRC, but still I can´t manage to find out the error correction/redundacy algorith.

Answer 6

The entire point in a good checksum algorithm is that it doesn't have anything in common with the input text. You can change one single character in the input. and the entire checksum output will change. So the only way to go the other way is to, yes, guess. If you know what the the input and output strings are, you can try a few common checksum algorithms, and see if any of them give the right output. Other than that, no, it's not possible.

Alternatively, as others have suggested, it may not be a checksum at all, but some kind of error correction/redundancy code, and that might be easier to figure out.

Answer 7

Guessing is the very right word. If this RF device is not proprietary, try reading the specifications! This would be the easiest way to go.

Guessing all the possible CRC (or Hashing algorithms) does not look too optimistic. Just take a look here.

A third possibility is to reverse engineer the code you are using to generate the checksums.

good luck :)

Answer 8

You could try a few common CRC methods and hope to get lucky, but Mana's answer (looking for specs) would be the best choice.

Answer 9

There are too many CRC algorithm possibilities to guess effectively. You can take the easy approach, which is finding a Specification for your device. Or you can take the brute force method, which is figuring out the CRC for each possible input, and creating an algorithm that generates the same result.