0

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.

  • 1
    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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.