Trying to work out a checksum in a 8 byte data stream..

[ataradov]

Same code with correct endianness. It does not make much difference for a table method, but it is clearly a little endian CRC.

I'm making some progress on reversing this.

[ataradov]

Just in case anyone is still interested in fully understanding this. Here is some new data.

Here is how input (47-0) bits affect output bits of the CRC (0-15). This is for a standard polynomial (0x1021).

Code: [Select]

0 :      *      * **   ***   * **      **  *   *   *   (15)
1 :     *      * **   ***   * **      **  *   *   *    (15)
2 :    *      * **   ***   * **      **  *   *   *     (15)
3 :   *      * **   ***   * **      **  *   *   *      (15)
4 :  *      * **   ***   * **      **  *   *   *       (15)
5 : *    * * ** *   *  * *** * ** **  *** **  **   *   (24)
6 :     * * ** *   *  * *** * ** **  *** **  **   *    (23)
7 :    * * ** *   *  * *** * ** **  *** **  **   *     (23)
8 :   * * ** *   *  * *** * ** **  *** **  **   *      (23)
9 :  * * ** *   *  * *** * ** **  *** **  **   *       (23)
10: * * ** *   *  * *** * ** **  *** **  **   *        (23)
11:  * ** *   *  * *** * ** **  *** **  **   *         (22)
12: * **     *      * **   ***   * **      **  *   *   (17)
13:  **     *      * **   ***   * **      **  *   *    (16)
14: **     *      * **   ***   * **      **  *   *     (16)
15: *     *      * **   ***   * **      **  *   *      (15)Numbers at the end of the line are just count. So if intersection of the input bit and output bit has an asterisk, then presence of the input bit flips (xor operation) corresponding output bit.

And here is the same map for the algorithm in question:

Code: [Select]

0 :   ** **   * *  *   * *     **   *  *   *   *   *   (16)
1 :     *      * **   ***   * **      **  *   *   *    (15)
2 : ** **   * *  *   ***   * **      **  *   *   *     (18)
3 :   *      * **   ***   * **      **  *   *   *      (15)
4 :   *   *   **   **    * *    *  **  *   *   *       (14)
5 :   ** ***    * *    * ***   ** *** **  **  **   *   (23)
6 : *     * ** *   *  * *** * ** **  *** **  **   *    (23)
7 : ** *** *  * * *  * *** * ** **  *** **  **   *     (26)
8 :   * *  *   * *     **   *  *   *   *   *           (12)
9 :   ** *      *  *  ** * *  *** *** **  **   *       (20)
10: * *  * * * *  *  **   ** **  *** **  **   *        (21)
11: ** *  *   *  * *** * ** **  *** **  **   *         (22)
12:       *   *   *   **   **    * *    *  **  *   *   (14)
13:       *        *  *   **      **      **  *   *    (11)
14:     *  **   * * **   ***   * **      **  *   *     (17)
15:     * *      * **   ***   * **      **  *   *      (15)
As you can see they are similar, but things get complicated as you move towards highest bits (those represent first byte of the data, so they get shifted in first, so they affect the result in a most complicated way).

And here is a table with formal differences:

Code: [Select]

0 : 0cc4 ^ d420 = d8e4
1 : 0884 ^ 6a10 = 6294
2 : 0739 ^ 3508 = 3231
3 : 0aa5 ^ 1a84 = 1021
4 : c186 ^ 0d42 = ccc4
5 : 06a1 ^ 06a1 = 0000
6 : b871 ^ 8b40 = 3331
7 : 45a0 ^ 45a0 = 0000
8 : 4044 ^ 22d0 = 6294
9 : 0448 ^ 1168 = 1520
10: 1895 ^ 08b4 = 1021
11: 055a ^ 045a = 0100
12: 42a9 ^ 022d = 4084
13: 8906 ^ 8906 = 0000
14: 54a2 ^ 4483 = 1021
15: aa51 ^ aa51 = 0000
16: c818 ^ dd38 = 1520
17: 4c8c ^ 6e9c = 2210
18: 364e ^ 374e = 0100
19: 1ba7 ^ 1ba7 = 0000
20: 81c2 ^ 85c3 = 0401
21: caf1 ^ caf1 = 0000
22: ec68 ^ ed68 = 0100
23: 76b4 ^ 76b4 = 0000
24: 194a ^ 3b5a = 2210
25: 0c8c ^ 1dad = 1121
26: 86c6 ^ 86c6 = 0000
27: 4363 ^ 4363 = 0000
28: 8ab1 ^ a9a1 = 2310
29: dcc0 ^ dcc0 = 0000
30: 6e60 ^ 6e60 = 0000
31: 3730 ^ 3730 = 0000
32: 0ab9 ^ 1b98 = 1121
33: 0ccc ^ 0dcc = 0100
34: 06e6 ^ 06e6 = 0000
35: 0373 ^ 0373 = 0000
36: 9888 ^ 89a9 = 1121
37: ccc4 ^ ccc4 = 0000
38: 6662 ^ 6662 = 0000
39: 3331 ^ 3331 = 0000
40: 9088 ^ 9188 = 0100
41: 48c4 ^ 48c4 = 0000
42: 2462 ^ 2462 = 0000
43: 1231 ^ 1231 = 0000
44: 8008 ^ 8108 = 0100
45: 4084 ^ 4084 = 0000
46: 2042 ^ 2042 = 0000
47: 1021 ^ 1021 = 0000

So my conclusion is that there is no data pre-processing, but there are some minor changes in the CRC loop itself. So that data that comes in last affects the difference the least, but data that came in first, gets splattered all over the place.

So now the task is simplified. We just need to find a way to make that last list show 0's in all positions

[beyondhelp]

I guess this is as much help as I can offer - off to other projects

Mike

Thanks for your time and input into this Mike. Much appreciated.

[beyondhelp]

Just in case anyone is still interested in fully understanding this. Here is some new data.

I'm doing my best!! I'm going to read that again...

[beyondhelp]

Ok, I kind of get it!

I'm fearful of sound stupid, but am I right we now have enough information to generate the checksum via a lookup table and some code. So essentially in a non ideal way its cracked? As for calculating the exact code with which the checksum is calculated from we also know half of how the CRC may be being performed with a polynomial of 0x1021, but don't yet know how the CRC is being modified for the highest bits?

[ataradov]

So essentially in a non ideal way its cracked?

Yes, for any practical uses take my last code and take definitions for CS_ZERO, partial[] and calc_sum().

That's all you need. Somewhere in the beginning of your program (setup() in case of arduino) update the partials table:

Code: [Select]

  for (int i = 0; i < 6*8; i++)
    partial[i] ^= CS_ZERO;
You can precalculate this, of course.

After that you can call calc_sum() on any 6-byte array. It will return 2-byte check sum. Add those to bytes to the message and you will get 8 bytes of valid data.

Anything else is just pure fun of figuring stuff out, but you don't need to worry about that.

[hamster_nz]

Based on ataradov's tables, here is the modified CRC function:

Code: [Select]

short int magic_crc16(unsigned char *data, short unsigned length, short unsigned initial)
{
  int i;
  short unsigned crc = 0xFFFF;
  for(i = 0; i < length*8;  i++)
  {
    int mask, index,bit,wrap;
    mask = 0x80>>(i%8);
    index = i/8;
    bit = (data[index] & mask) ? 1 : 0;
    wrap = (crc & 0x8000) ? 1 : 0;
    crc <<= 1;
    if((i&7)== 4) {
      if(wrap ^ bit) crc ^= 0x1001;
    } else {
      if(wrap ^ bit) crc ^= 0x1021;
    }
  }
  return crc;
}

It works for all of the 100 test cases that are in this thread...

[JimRemington]

Cool!  Any speculation on what the original programmer might have been thinking?

I spent some time trying to imagine a simple mistake or change in the inner loop of the standard CRC that would lead to such a pattern of bit flip differences, and decided that whatever it was, was not simple. Your exposition confirms that suspicion.

[hamster_nz]

Cool!  Any speculation on what the original programmer might have been thinking?

It's either a bug in an unrolled loop, or an attempt to thwart reverse engineering. Most likely the former than the latter, IMO.

[ataradov]

Yep, that function yields no differences. And here is a more traditional form of CRC with this change:

Code: [Select]

uint16_t calc_crc(uint8_t *data)
{
  uint16_t crc = 0xffff;

  for (int i = 0; i < 6; i++)
  {
    crc ^= (data[i] << 8);

    for (int j = 0; j < 8; j++)
    {
      if (crc & 0x8000)
      {
        if (4 == j)
          crc = (crc << 1) ^ 0x1001;
        else
          crc = (crc << 1) ^ 0x1021;
      }
      else
        crc = (crc << 1);
    }
  }

  return crc;
}

I don't see any benefit of doing this apart from obfuscation.

beyondhelp use this function instead.

[hamster_nz]

beyondhelp use this function instead.

Given that the target is a PIC 16Fsomething, it is most probably better to rewrite the code to the platform. The have limited and segmented RAM, lots of bit test operations and bit test and skip ops can be leveraged, but minimal support for anything like a pointer... they make an AVR look feature rich!

[ataradov]

Guven that the target is a PIC 16Fsomething,

The devices runs PIC, but PC part needs to be replaced from what I understand.

But yeah, optimize as needed, of course.

[beyondhelp]

It will be replaced depending on use with a software interface that will allow it to work in more recent OS,or/and with a more simple Amtel based physical hardware interface, most probably a ATMega256, because if I'm honest that's where my (limited) experience lies.

[beyondhelp]

Yep, that function yields no differences. And here is a more traditional form of CRC with this change:

Code: [Select]

uint16_t calc_crc(uint8_t *data)
{
  uint16_t crc = 0xffff;

  for (int i = 0; i < 6; i++)
  {
    crc ^= (data[i] << 8);

    for (int j = 0; j < 8; j++)
    {
      if (crc & 0x8000)
      {
        if (4 == j)
          crc = (crc << 1) ^ 0x1001;
        else
          crc = (crc << 1) ^ 0x1021;
      }
      else
        crc = (crc << 1);
    }
  }

  return crc;
}

I don't see any benefit of doing this apart from obfuscation.

beyondhelp use this function instead.

Ok having a play now. From the code this replaces the previous code including the tables?

[ataradov]

From the code this replaces the previous code including the tables?

yes, that's the single function you need.

[beyondhelp]

With a little help from hampster_nz, and ataradov's code, ITS WORKING 

I know I'll be back with more questions, but so far for the test data I'm putting in, im getting out valid checksum data. Amazing!!

Honestly what can I say!! I'm blown away by the knowledge, skills and time put into this thread. Thanks so much!

[matkar]

I followed this thread with great interest. I'm amazed by the skills you all have. I liked the way you draw conclusions and had a small epiphany at ataradov's reply #76. You can clearly see the pattern. Unbelievable!

Can you guys give us some insight on what tools are you using when dealing with such problems?
E.g. hamster_nz was half way there in reply #51 which facilitated the search of valid entries. Did you use a "plain" CRC calculation? How did you (almost) figured which polynome and seed is used?
@ataradov:How did you figured there is not some kind of pre or post processing but the CRC algorithm obfuscation instead?
How did you came to the first solution that uses tables? How did you guys derived the second solution using equations?

I really wish there were more threads like this. Thank you!

[BravoV]

I really wish there were more threads like this. Thank you!

+1 , thanks to all who contributed. 

Imo, this thread prolly one of the best thread of the month around this forum currently. 

[ataradov]

E.g. hamster_nz was half way there in reply #51 which facilitated the search of valid entries.

It is quite obvious, since first 3 (or last 3, depending on where you count from) entries are consistent with a standard 0xffff / 0x1021 CRC-16.

@ataradov:How did you figured there is not some kind of pre or post processing but the CRC algorithm obfuscation instead?

Same reason, if you look at the progression in the change of the value, you will see that if the bit containing "1" is shifted at the beginning, then CRC is result is barely predictable. But if the "1" bit is shifted in at the end, then changes are very predictable and for the last 3 values match with the standard CRC.

How did you came to the first solution that uses tables?

Just knowledge of this property for block codes. I don't know where it came from, probably some university course.

How did you guys derived the second solution using equations?

Trying things and looking at the results.

[hamster_nz]

I followed this thread with great interest. I'm amazed by the skills you all have. I liked the way you draw conclusions and had a small epiphany at ataradov's reply #76. You can clearly see the pattern. Unbelievable!

Can you guys give us some insight on what tools are you using when dealing with such problems?

I've been doing a few projects that are loosely aligned to CRCs lately. They turn up quite a bit in hardware. LFSRs, CRCs, BCH codes are all somewhat related. CRC16 is used in the physical layer of SD cards for verifying block data transfers, and it is also used in SDI video where the checksum of each raster is sent following the active video data. So I had a C implementation handy, for verifying against my VHDL code. (I mistakenly said a monitor's EDID ROM. but I just checked and that is a simple checksum....).

E.g. hamster_nz was half way there in reply #51 which facilitated the search of valid entries. Did you use a "plain" CRC calculation? How did you (almost) figured which polynome and seed is used?

beyondhelp did an awesome job of collecting the data, and included quite a few pairs of messages that differed by one bit, especially the status message with the counters that increment by one.

The checksums for the pairs differed by a consistent amount when bits when the same bits changed, regardless of the rest of the message. On top of that when the neighboring bits changed the difference was the same pattern rotated one bit. That is expected for a CRC, where it is a rotate and then XOR by a constant amount. So I just ran some patterns through the CRC16 code, and rather than just getting unrelated numbers (which would be expected if the polynomial was different) the errors looked somehow related.

With a bit of fiddling I could get most of the changes to sort of agree, and with a bit of hacking I managed to get it close enough that I would take a guesses at what each bit's effect on the checksum would be. My 'mystery transform' was propagating the then-unknown change made to the polynomial through the input data. My bad 

How did you guys derived the second solution using equations?

I had decided to move on to other things, but when I saw ataradov's tables it nagged at me . I just printed it out, turned it on it's side and highlighted the differences.

Code: [Select]

FEDCBA9876543210
 44 other lines
x......O....x...
.x......x....x..
..x......x....x.
...x......x....x

Then undid the rotation step:

Code: [Select]

FEDCBA9876543210
 44 other lines
...x...........x  0x1001
...x......x....x  0x1021
...x......x....x  0x1021
...x......x....x  0x1021

So I plugged 0x1001 as the polynomial constant used on the third-to-last bit, and everything worked out back to the 11th to last bit. I plugged 0x1001 in for the 12th-to-last bit, and that worked too.

Then I just tried the two most common initial values (all zeros or all ones), half expecting to do an exhaustive search, and 0xFFFF just worked.

I really wish there were more threads like this. Thank you!

A big thanks should go to beyondhelp giving us such a fun problem. Much more fun than doing Sudoku in the wife's Women's Day

I pinged him a message this afternoon and helped him with his Arduino/C testing code, but I still forgot to ask him/her what the end device actually does!

[android]

I still forgot to ask him/her what the end device actually does!

...just some kind of missile launch control system, I think 

[beyondhelp]

Quite agree, this thread has been EPIC!! So glad that others have found it as fascinating as I have Gotta love the EE community

I still forgot to ask him/her what the end device actually does!

...just some kind of missile launch control system, I think 

Incredibly close!!!! Not going to name it, but it is for the use of pyrotechnics for entertainment purposes!! It was either get this working or ultimately ditch and replace with something else!

[abyrvalg]

Lots of fun here! For completeness I would like to extract the original algo and post it here for comparison. beyondhelp, would you mind sending me an original executable that talks to this hardware? IDA is my girlfriend

[rs20]

I just finished reading The Da Vinci Code; parts of this thread have a similar vibe... 

[beyondhelp]

Lots of fun here! For completeness I would like to extract the original algo and post it here for comparison. beyondhelp, would you mind sending me an original executable that talks to this hardware? IDA is my girlfriend

I'll see what I can do Only runs on XP however. Even in a VM it crashes...