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

[JimRemington]

Maybe it starts at something other than 0

If it were a constant, reveng (post #31) would have found it. Reveng checks for both pre- and post-XOR values.

Here is an example of a rather bizarre variation on a CRC checksum that was rather laboriously decoded, and it seems to be common among several manufacturers of simple temperature sensors: https://eclecticmusingsofachaoticmind.wordpress.com/2015/01/21/home-automation-temperature-sensors/

[hamster_nz]

Getting close... only got a single bit of error in the final checksum, but can't see how this is being caused.

The issue that the error is the same for all failing tests is a big clue. But why '00 00 00 00 00 00' works yet '00 00 00 00 00 80' doesn't, and then '00 01 30 00 2a 00' passes but '00 01 30 00 13 00' doesn't, but both with the same error perplexes me.

All test vectors supplied so far (sorted and de-duplicated) and my results....

Code: [Select]

Raw    => Goes into CRC16 => Checksum
00 00 00 00 00 00 => 00 00 00 00 00 00  => b5 5f
00 00 00 00 00 01 => 00 00 00 00 00 01  => 94 4f
00 00 00 00 00 80 => 00 00 00 00 00 80  => 3d ce should be 3d cf, error 00 01
00 01 00 00 00 00 => 00 01 00 00 00 00  => e4 f5
00 01 30 00 13 00 => 00 01 30 00 13 00  => 2d 8f should be 2d 8e, error 00 01
00 01 30 00 2a 00 => 00 01 30 00 2a 01  => 01 20
00 01 30 00 41 00 => 00 01 30 00 41 00  => f0 e7
00 01 30 00 58 00 => 00 01 30 00 58 01  => 3a 4e should be 3a 4f, error 00 01
00 01 60 00 7e 00 => 00 01 60 00 7f 00  => 51 b4
00 01 60 00 80 00 => 00 01 60 00 81 00  => 9f 84 should be 9f 85, error 00 01
00 01 60 00 d7 01 => 00 01 60 00 d6 01  => 96 03
00 01 60 00 f3 01 => 00 01 60 00 f2 01  => b4 c9
00 01 70 01 22 01 => 00 01 70 01 23 00  => 14 d3
00 01 b0 00 20 00 => 00 01 b0 01 21 01  => f3 16
00 01 b0 01 20 00 => 00 01 b0 00 21 01  => c3 21
00 01 b0 02 53 00 => 00 01 b0 03 52 01  => 99 25 should be 99 24, error 00 01
00 01 b0 03 65 00 => 00 01 b0 02 64 01  => 9a bd should be 9a bc, error 00 01
00 01 b0 04 71 00 => 00 01 b0 05 70 01  => bd f7 should be bd f6, error 00 01
00 01 b0 05 75 00 => 00 01 b0 04 74 01  => 49 0c should be 49 0d, error 00 01
00 01 b0 06 65 00 => 00 01 b0 07 64 01  => 6a 56 should be 6a 57, error 00 01
00 01 b0 07 6e 00 => 00 01 b0 06 6f 00  => 81 ad
00 01 b0 08 63 00 => 00 01 b0 09 63 00  => dd c4 should be dd c5, error 00 01
00 01 b0 09 65 00 => 00 01 b0 08 65 00  => 4b 59 should be 4b 58, error 00 01
00 01 b0 0a 72 00 => 00 01 b0 0b 72 00  => ff 9a should be ff 9b, error 00 01
00 01 b0 0b 20 00 => 00 01 b0 0a 20 00  => 12 c5
00 01 b0 0c 36 00 => 00 01 b0 0d 36 00  => 57 e9
00 01 b0 0d 34 00 => 00 01 b0 0c 34 00  => 05 b8
00 01 b0 0e 20 00 => 00 01 b0 0f 20 00  => e2 2e
00 01 b0 0f 20 00 => 00 01 b0 0e 20 00  => d2 19
01 00 00 00 00 00 => 01 00 00 00 00 00  => 15 1a
01 00 20 01 01 01 => 01 00 20 01 01 01  => 7b 39 should be 7b 38, error 00 01
01 00 20 02 02 02 => 01 00 20 02 02 02  => 1b 05 should be 1b 04, error 00 01
01 00 20 03 03 03 => 01 00 20 03 03 03  => 3b 11 should be 3b 10, error 00 01
01 00 20 04 04 04 => 01 00 20 04 04 04  => db 7d should be db 7c, error 00 01
01 00 20 05 05 05 => 01 00 20 05 05 05  => fb 69 should be fb 68, error 00 01
01 00 20 06 06 06 => 01 00 20 06 06 06  => 9b 55 should be 9b 54, error 00 01
01 00 20 07 07 07 => 01 00 20 07 07 07  => bb 41 should be bb 40, error 00 01
01 00 20 08 08 08 => 01 00 20 08 09 08  => 6a bf should be 6a be, error 00 01
01 00 20 09 09 09 => 01 00 20 09 08 09  => 4a ab should be 4a aa, error 00 01
01 00 20 0a 0a 0a => 01 00 20 0a 0b 0a  => 2a 97 should be 2a 96, error 00 01
01 00 20 0b 0b 0b => 01 00 20 0b 0a 0b  => 0a 83 should be 0a 82, error 00 01
01 00 20 0c 0c 0c => 01 00 20 0c 0d 0c  => ea ef should be ea ee, error 00 01
01 00 20 0d 0d 0d => 01 00 20 0d 0c 0d  => ca fb should be ca fa, error 00 01
01 00 20 0e 0e 0e => 01 00 20 0e 0f 0e  => aa c7 should be aa c6, error 00 01
01 00 20 0f 0f 0f => 01 00 20 0f 0e 0f  => 8a d3 should be 8a d2, error 00 01
80 00 00 00 00 00 => 80 01 01 01 01 00  => 71 53


[ataradov]

Are you still adding new preprocessing rules to the same code or got something new?

I just can't see what should go though someone's head to do something like this.

The input data  size is small, so it is possible that operations involved in CRC just happened to be useful part of the real algorithm that has nothing to do with cyclic codes. In that case having the source with hacks would help, but CRC part needs to be unrolled, and some new better algorithm will emerge in combination with your preprocessing.

[ataradov]

I've got an idea for a more math-based approach, but for that you will need all checksums for all 48 single bits (80...00, 40...00, etc until 00...02, 00...01, 00...00). We have some of them already.

Basically after that any CRC will be a linear combination of the above CRCs. So for example CRC(00...05) == CRC(00...04) + CRC(00...01) - CRC(00...00).

This should work for any block code, not necessarily cyclic. There is also a way to reverse it back to a polynomial if it will turn out to be cyclic, which I doubt it will.

We really need at least blocks I've mentioned earlier. We have 00...01, 00...00, all we need is 00...05 and 00...04 to test this theory.

[JimRemington]

Basically after that any CRC will be a linear combination of the above CRCs. So for example CRC(00...05) == CRC(00...04) + CRC(00...01) - CRC(00...00).

That seems to work for this set (excerpted from one of the above posts by beyondhelp)

00 01 b0 00 20 00 f3 16
00 01 b0 01 20 00 c3 21
00 01 b0 0e 20 00 e2 2e
00 01 b0 0f 20 00 d2 19

d219=e22e^c321^f316

[ataradov]

That seems to work for this set (excerpted from one of the above posts by beyondhelp)

Good spotting on the numbers!

I guess OP will have to collect all 48 values, after that we could test this theory against all other known values.

And if that works, it can be ether used as is, or just for fun we can try to minimize it.

[beyondhelp]

Ok, I'll keep going until I have more. I'll have more time this afternoon.
I'm amazed/fascinated how tricky it appears to be, but then I guess its a case of its easy when you know how.

I'll update more as soon as I find them.

[hamster_nz]

I'm not expecting many to be valid (and some you have already mined), but if you try these and a few new ones are correct it might save you a lot of work...

Code: [Select]

80 00 00 00 00 00 71 53
40 00 00 00 00 00 10 47
20 00 00 00 00 00 bd 6b
10 00 00 00 00 00 31 45
08 00 00 00 00 00 13 8b
04 00 00 00 00 00 14 59
02 00 00 00 00 00 f5 d4
01 00 00 00 00 00 15 1a
00 80 00 00 00 00 f1 1f
00 40 00 00 00 00 fd 5a
00 20 00 00 00 00 01 56
00 10 00 00 00 00 ef 5b
00 08 00 00 00 00 0c 3e
00 04 00 00 00 00 b3 d6
00 02 00 00 00 00 36 1b
00 01 00 00 00 00 e4 f5
00 00 80 00 00 00 ad 96
00 00 40 00 00 00 39 12
00 00 20 00 00 00 fb 69
00 00 10 00 00 00 12 44
00 00 08 00 00 00 56 cf
00 00 04 00 00 00 44 95
00 00 02 00 00 00 dd b2
00 00 01 00 00 00 01 29
00 00 00 80 00 00 ff 47
00 00 00 40 00 00 39 52
00 00 00 20 00 00 73 d8
00 00 00 10 00 00 d6 1c
00 00 00 08 00 00 04 d4
00 00 00 04 00 00 75 83
00 00 00 02 00 00 d5 31
00 00 00 01 00 00 85 68
00 00 00 00 80 00 0c 54
00 00 00 00 40 00 79 52
00 00 00 00 20 00 53 58
00 00 00 00 10 00 c6 5c
00 00 00 00 08 00 3d c7
00 00 00 00 04 00 71 93
00 00 00 00 02 00 d7 39
00 00 00 00 01 00 84 6c
00 00 00 00 00 80 3d ce
00 00 00 00 00 40 71 17
00 00 00 00 00 20 d7 7b
00 00 00 00 00 10 84 4d
00 00 00 00 00 08 bd de
00 00 00 00 00 04 31 1f
00 00 00 00 00 02 f7 7f
00 00 00 00 00 01 94 4f


[ataradov]

I'm not expecting many to be valid (and some you have already mined), but if you try these and a few new ones are correct it might save you a lot of work...

Excellent idea. beyondhelp,try them first and see how many work.

I'm still not entirely convinced that my method works. I did not invent it, obviously, I just heard that something like that should work, but I'm fuzzy on the details. We need a few more test cases before you go recovering the rest of them.

[beyondhelp]

Wow thats an excellent idea.

I just got home and at some point the pc had restarted (updates??!?!!) anyway, todays work 'lost' I'll try those all now, and report back shortly.

[JimRemington]

I'm still not entirely convinced that my method works. I did not invent it, obviously, I just heard that something like that should work, but I'm fuzzy on the details. We need a few more test cases before you go recovering the rest of them.

You are certainly on the right track. Here is an excellent overview on brute force/linear algebra methods for deducing such algorithms: http://www.cosc.canterbury.ac.nz/greg.ewing/essays/CRC-Reverse-Engineering.html

Following one of the protocols suggested in the above to deduce the polynomial, if there is one, gives an important clue

Code: [Select]

00 01 30 00 01 00 3c eb
00 01 30 00 02 00 6f be  53 55
00 01 30 00 04 00 c9 14  a6 aa

In the above, the data entries differ by a single bit shift. The last column is the XOR of the two checksums, which, if this were a standard CRC, would either be the polynomial or zero.

However, the result of the XOR of two CRCs is bit shifted by one to the left in successive operations. So, one possibility is that the polynomial itself is also being shifted.

[ataradov]

Here is an excellent overview on brute force/linear algebra methods for deducing such algorithms

That looks like a good confirmation that my memory serves me well. I guess it is a safe bet to collect CRC for all positions of "1"s.

So, one possibility is that the polynomial itself is also being shifted.

It does not have to be a polynomial at all. At this point we know that it is not a CRC of any kind.

[beyondhelp]

I'm not expecting many to be valid (and some you have already mined), but if you try these and a few new ones are correct it might save you a lot of work...

You are not kidding. MANY of those were valid, about 3/5th many several of the others were out by one bit, the end result so far is this:
The gaps are the missing ones I'm working on those now, and have now a much much faster way to mine them, so shouldn't take too long.

Code: [Select]

80 00 00 00 00 00 71 53
40 00 00 00 00 00 31 57
20 00 00 00 00 00 8c 58
10 00 00 00 00 00 10 55
08 00 00 00 00 00 33 9e
04 00 00 00 00 00 14 59
02 00 00 00 00 00 c4 e7
01 00 00 00 00 00 15 1a
00 80 00 00 00 00 f1 1f
00 40 00 00 00 00 fd 5b
00 20 00 00 00 00 20 47
00 10 00 00 00 00 ef 5a
00 08 00 00 00 00 1c 1d
00 04 00 00 00 00 b3 d6
00 02 00 00 00 00 17 0b
00 01 00 00 00 00 e4 f5
00 00 80 00 00 00 ad 97
00 00 40 00 00 00 39 13
00 00 20 00 00 00 fb 69
00 00 10 00 00 00 12 44
00 00 08 00 00 00 77 de
00 00 04 00 00 00 44 95
00 00 02 00 00 00 dd b3
00 00 01 00 00 00 01 29
00 00 00 80 00 00 ff 46
00 00 00 40 00 00 39 53
00 00 00 20 00 00 73 d9
00 00 00 10 00 00 d6 1c
00 00 00 08 00 00 04 d5
00 00 00 04 00 00 75 83
00 00 00 02 00 00 d5 31
00 00 00 01 00 00 85 68
00 00 00 00 80 00 0c 55
00 00 00 00 40 00 79 53
00 00 00 00 20 00 53 59
00 00 00 00 10 00 c6 5c
00 00 00 00 08 00 3d c7
00 00 00 00 04 00 71 93
00 00 00 00 02 00 d7 39
00 00 00 00 01 00 84 6c
00 00 00 00 00 80 3d cf
00 00 00 00 00 40 71 17
00 00 00 00 00 20 d7 7b
00 00 00 00 00 10 84 4d
00 00 00 00 00 08 bd df
00 00 00 00 00 04 31 1f
00 00 00 00 00 02 f7 7f
00 00 00 00 00 01 94 4f


[ataradov]

We already had "80 00 00 00 00 00 71 53"
And this "02 00 00 00 00 80 00 00" has two bits set. "02 00 00 00 00 00" needs to be re-done.

We have plenty of bits now to do verification. I'll get to it as soon as I get home.

[beyondhelp]

Err, yes I'm just copying and pasting from my code. I'll correct those, it was an old one I'd left behind.

[JimRemington]

It does not have to be a polynomial at all. At this point we know that it is not a CRC of any kind.

I agree. I did not state that there is a polynomial.

However, I am convinced that the operations employed in the mystery calculation are quite closely related to those of the "familiar CRC", of which there are on the order of 100 well characterized variations. http://reveng.sourceforge.net/crc-catalogue/

[ataradov]

Well, I would declare it a success. First of all, none of the missing bits ever appear in the real data (I'm working with a 94 entries set combined by hamster_nz earlier). We still need to find them, of course.

And checksum calculation algorithm works perfectly on the entire set.

Source code attached.

After all values are known, we can start looking into optimizing this and reversing it back to the original formula (if one exists).

[beyondhelp]

SPEECHLESS 

WOW!!!!

[ataradov]

Find the missing bits first. We are missing like 10 bits for complete happiness

[beyondhelp]

Sorry I was running away a bit with excitement... I've been trying to do this for a long long time now.

I shall work on the last remaining ones, and update my post asap. Its 2.40am here so I'll try a couple more now but these late nights this week is catching up fast!

[beyondhelp]

Have added another one.

[ataradov]

Have added another one.

I'm counting 3 new ones compared to my table. I don't know why this happened. Anyway, 7 more left.

[beyondhelp]

All done.

I'm shattered now! have fun with those (!) and I'll see how you got on in the morning! (4am here now!)

[ataradov]

Here is an updated program in case anyone wants to play with it.

I'm going to try to turn that into an actual function, not just a table.

[hamster_nz]

Here's the guts of the code that I have so far.

* The data goes through a 'mysterious transform'

* Then it calculates a standard CRC16, with 0x1021 for the polynomial constant (the same one used for EDID ROMs, as luck would have it...)

* Finally the CRC is XORed with 0x51A5

It gets everything but the LSB for all test vectors I have so far.

Very weird!

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

Mike

Code: [Select]

short int std_crc16(unsigned char *data, short unsigned length)
{
  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(wrap ^ bit) crc ^= 0x1021;
  }
  return crc;
}
void mystery_transform(unsigned char *data, short unsigned length)
{
  int i, j;
  unsigned char a = data[0]^data[1]^data[2]^data[3]^data[4];

/* Mystery transform */
  for(i = 0; i < 5; i++) {
    if((data[i] & 0x40)) {
      for(j=i+2; j <6 && j < i+5 ; j++)
         data[j] ^= 0x01;
    }
  }

  for(i = 0; i < 5; i++) {
    unsigned char b;
    b = data[i] >> 7;
    b ^= data[i] >> 3;
    if(b & 0x1) {
      for(j=i+1; j <6 && j < i+5; j++)
         data[j] ^= 0x01;
    }
  }

/* Double mystery transform (removes some of 00 01) */
  if(a & 0x20) {
    data[2] ^= 0x01;
    data[3] ^= 0x01;
    data[5] ^= 0x04;
  }

  if(a & 0x08) {
    data[2] ^= 0x01;
    data[3] ^= 0x01;
    data[5] ^= 0x04;
  }
}

short int my_crc(unsigned char *data, short unsigned length)
{
  int i;
  short unsigned crc = 0, crc_low, crc_high;

  for(i = 0; i < length; i++)
     printf("%02x ",data[i]);
  printf("=> ");

  mystery_transform(data,length);

  /* Display the transfomed data */
  for(i = 0; i < length; i++)
     printf("%02x ",data[i]);

  crc = std_crc16(data,length);
  crc ^=  0x51A5;
  crc_low  = (crc>>0)&0xFF;
  crc_high = (crc>>8)&0xFF;

  if( crc_low == data[i] && crc_high == data[i+1])
    printf(" => %02x %02x\r\n", data[i], data[i+1]);
  else
    printf(" => %02x %02x should be %02x %02x, error %02x %02x\r\n",
           crc_low, crc_high,
           data[i], data[i+1],
           crc_low^data[i], crc_high^data[i+1]);

  return 0;
}