tags:

views:

834

answers:

12

Hi, does anybody know how to 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.

Hopefully there is someone out there that can help me!!

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

//Tom

+2  A: 

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 :)

mana
Well, if the checksum is 4 bits, and we're dealing with a CRC, then odds are it's a CRC-4. The polynominal is not known, but there are only 16 possibilities anyway, so it shouldn't take long to let a brute forcer try all of them.
Michael Madsen
A: 

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

No, unfortunately there isn't. A checksum algorithm can be cryptographic in nature, and to reverse engineer it by purely looking at the results is a hard problem.
Lasse V. Karlsen
Why can't you get the specification? Who expects you to do this without the specification? You're on a hiding to nothing without the specification, and would do better to ... well, try almost anything else.
Jonathan Leffler
I can´t get the specs because the manufacturer won´t give me them.
A: 

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.

A: 

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.

DrStalker
A: 

Yes 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.

+2  A: 

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.

Mecki
A: 

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.

jalf
A: 

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

+1  A: 

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

nicerobot
A: 

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.

Keegan Carruthers-Smith
A: 

I have thought of the hamming code also but haven´t been able to figure it out. Can someone with the knowledge try the hamming code on my strings? Thx

A: 

I added a comment to the first post.