# Reverse engineering a checksum or CRC

I am trying to reverse engineer a checksum or CRC wherein an 8 bit number* gets converted to a 5 bit number for error checking. I have an incomplete list of data values and checksums, and need to figure out the algorithm so I can fill in the missing data. I've plotted it out in hex and binary and can't spot a pattern. I'm hoping someone recognizes the algorithm/technique that was used. Here is my incomplete list (values are in decimal):

``````Data Val == Checksum

4 = 15;
5 = 2;
6 = 1;
7 = 12;
8 = 17;
9 = 28;
10 = 31;
11 = 18;
12 = 30;
13 = 19;
14 = 16;
15 = 29;
16 = 18;
17 = 31;
18 = 28;
19 = 17;
20 = 29;
21 = 16;
22 = 19;
23 = 30;
24 = 3;
25 = 14;
26 = 13;
27 = 0;
28 = 12;
29 = 1;
30 = 2;
31 = 15;
32 = 19;
33 = 30;
34 = 29;
35 = 16;
36 = 28;
37 = 17;
38 = 18;
39 = 31;
40 = 2;
41 = 15;
42 = 12;
43 = 1;
44 = 13;
45 = 0;
46 = 3;
47 = 14;
48 = 1;
49 = 12;
51 = 2;
53 = 14;
53 = 3;
54 = 0;
55 = 13;
56 = 16;
57 = 29;
58 = 30;
59 = 19;
60 = 31;
61 = 18;
62 = 17;
63 = 28;
64 = 20;
65 = 25;
66 = 26;
67 = 23;
68 = 27;
69 = 22;
73 = 8;
74 = 11;
76 = 10;
79 = 9;
80 = 6;
81 = 11;
82 = 8;
``````

*It might be 16 bits. There are another 8 bits that come afterwards that in my sample data are not used and all zeros. In which case it might be:

``````1024 = 15;
1280 = 2;
1536 = 1;
1792 = 12;
2048 = 17;
2304 = 28;
etc.
``````

If it is 16 bit as I suspect, I need the algorithm to handle those bits as well. FYI: This is part of a proprietary infrared format used by the old Microsoft Media Center Infrared Keyboard from XP, similar to but not quite like the RC5 protocol. The documentation I have found is sparse, incomplete, and contains errors.

• Have you tried the common CRC algorithms and coefficients documented on wikipedia and seen if any of those yield the expected values? – whatsisname Apr 11 '18 at 3:10

## 1 Answer

SOLVED! But not by me. And it is not any sort of standard algorithm.

I have been working on this project off and on for about 3 years. I've done tons of google searches with every keyword combination I could think of. But since the last time I worked on this and last time I googled, someone else "The Robman" on the JP1 Forums cracked it. Each of the 5 bits of the checksum is xored from various bits of the 16 bit value, but not in any logical or consistent way.

• Checksum Bit 4 = xor of value bits 15,14,13,12,11
• Checksum Bit 3 = xor of value bits 10,9,8,7,6,5,4
• Checksum Bit 2 = xor of value bits 15,14,11,10,9,8,2,1
• Checksum Bit 1 = xor of value bits 13,12,10,9,7,5,3,2,0
• Checksum Bit 0 = xor of value bits 15,13,11,10,8,7,4,3,0

The Robman did not explain how he ended up figuring that out but I've tested it and got a 100% match. I'd be curious to find out his technique.

• Possibly just brute force; possibly he plotted it in binary and spotted a pattern. – immibis Apr 11 '18 at 3:55
• The technique is quite simple: find two values that differ only in bit 1, see how their checksums differ. Then find two values that differ in bit 2, ... It's called differential cryptanalysis. – Rainer P. Apr 11 '18 at 21:05
• I got an answer back from The Robman. He wrote a script with a bunch of nested loops trying various combinations of bits until he found the right one. – DrWizard Apr 12 '18 at 13:58