16 bit checksum analsysis - CRC experts?

[PamMurdoch]

Hello,

I found this amazing thread from a while back thanks to @rcgldr Find collision in CRC-16

I am almost brand new to programming, with mostly c# and python experience

Seeing that thread made me think there are some hard core CRC and checksum experts here

I have experimented with CRC RevEng (although I consistently second guess that I"m using it correctly) and SRP16 on the below:

FFFFFFFFFFFF
0100100A00000000000000000000FFFFFFFFFF72BE


000000000000
0100100A00000000000000000000FFFFFFFFFF2A3D


000000000001
0100100A00000000000000000000FFFFFFFFFF89F7


000000000002
0100100A00000000000000000000FFFFFFFFFF0864


000000000003

0100100A00000000000000000000FFFFFFFFFFABAE



Two pieces of data, unknown concatenation / insertion order


My question is as follows

If I generate huge amounts of samples, is there any other tricks to solving it? Any programs I can write?

I only need to change the lower 4 bytes of the first 6 byte piece of data. so the messages are not very random, only 4 bytes changing really

I can generate and verify as many samples as I want

[Salem]

OK, so what are you trying to do?

Find which 6 byte prefix of message M that computes the same checksum as message M by itself?

[PamMurdoch]

OK, so what are you trying to do?

Find which 6 byte prefix of message M that computes the same checksum as message M by itself?

Ideally I want to determine the polynomial and other parameters

I am hoping that if I gather enough samples, and analyze the collisions / duplicates in binary and see what multiples are happening in the 6 byte portion, I can potentially reveal the poly?

Am I understanding that other thread correctly about the multiples resulting in same CRC?

Essentially the message always contains the 6 bytes + the 19 bytes.


I only ever need to be changing the last 4 bytes of the 6 byte portion

so if I create samples 00 00 00 00 00 00 through 00 00 FF FF FF lets just say, I would surely get some collision / duplicate CRC


Can I then study those collision / duplicates and determine something in common about them?

[Salem]

> Ideally I want to determine the polynomial and other parameters
Cyclic redundancy check - Wikipedia

unlike cryptographic hash functions, CRC is an easily reversible function, which makes it unsuitable for use in digital signatures.

Maybe do some more reading, and figure out the smart way to do this rather than "try all the possible combinations".

Only certain polynomials make any sense for being useful for a CRC.


> Am I understanding that other thread correctly about the multiples resulting in same CRC?
Yes, multiple messages will result in the same CRC.

[hamster_nz]

I've done this a bit. The key thing is that flipping a given bit in the message always flips the same bits in the CRC.

So if you can generate a reference message, and the same message with only one of the bits you want to update flipped, then the difference between the two CRCs is that is made by that bit.

If you can do that for all the bits you want to update, then you don't need to know the CRC polynomial, initial value and if they are inverted.

[PamMurdoch]

I've done this a bit. The key thing is that flipping a given bit in the message always flips the same bits in the CRC.

So if you can generate a reference message, and the same message with only one of the bits you want to update flipped, then the difference between the two CRCs is that is made by that bit.

If you can do that for all the bits you want to update, then you don't need to know the CRC polynomial, initial value and if they are inverted.

Would I be able to extrapolate anything about the CRC from this? I guess I am trying to see if and how this is better than brute forcing the valid CRC for every message I might need to send

Even if I can somehow reduce my 65535 brute forcing search space, its a win. Every bit helps. I just don't see how to do that just yet.

[hamster_nz]

This site might help:

Online CRC-8 CRC-16 CRC-32 Calculator

Also, this code might help playing around with different parameters:

#include <stdio.h>


static unsigned char bitswap(unsigned char s) {
    unsigned char t = 0;
    for(int i = 0; i < 8; i++) {
       t <<= 1;
       if(s & 1) {
           t |= 1;
       }
       s >>= 1;
    }
    return t;
}


static int crc16_bit(int s, unsigned char bit, int reverse, int polynomial) {
   if(reverse) {
      if(s&1) bit ^= 1;
      s >>= 1;
      if(bit) s ^= polynomial;
   } else {
      if(s>>15) bit ^= 1;
      s <<= 1;
      s &= 0xFFFF;
      if(bit) s ^= polynomial;
   }
   return s;
}


int crc16_byte(int s, unsigned char byte, int reverse, int polynomial) {
   if(reverse)
      byte = bitswap(byte);
   s = crc16_bit(s, byte & 0x80 ? 1 : 0, reverse, polynomial);
   s = crc16_bit(s, byte & 0x40 ? 1 : 0, reverse, polynomial);
   s = crc16_bit(s, byte & 0x20 ? 1 : 0, reverse, polynomial);
   s = crc16_bit(s, byte & 0x10 ? 1 : 0, reverse, polynomial);
   s = crc16_bit(s, byte & 0x08 ? 1 : 0, reverse, polynomial);
   s = crc16_bit(s, byte & 0x04 ? 1 : 0, reverse, polynomial);
   s = crc16_bit(s, byte & 0x02 ? 1 : 0, reverse, polynomial);
   s = crc16_bit(s, byte & 0x01 ? 1 : 0, reverse, polynomial);
   return s;
}


int main(void) {
   // Settings for CRC16/X-modem
   int invert = 0;
   int reverse = 0;
   int polynomial = 0x1021;


   // Data to calculate
   unsigned char data[] = {0x41, 0x42, 0x43, 0x44};


   int crc_state = 0;


   if(invert)
      crc_state ^= 0xFFFF;


   for(int i = 0; i < sizeof(data)/sizeof(char); i++) {
      crc_state = crc16_byte(crc_state, data[i], reverse, polynomial);
   }


   if(invert)
      crc_state ^= 0xFFFF;

   // Show data and results
   printf("Data is:");
   for(int i = 0; i < sizeof(data)/sizeof(char); i++) {
      printf( " 0x%02X",data[i]);
   }
   printf("\n");
   printf("CRC is 0x%04X\n", crc_state);


   return 0;
}