Trying to reverse engineer a packet checksum/CRC/hash

Question

I have an old, no longer manufactured electronic device with a serial port. I am trying to reverse engineer the data packet CRC/checksum/hash used in this device.

Anyone with keen eyes, sharp math skills out there who might be able to crack this thing ?

Here is what I know so far ...

• Every packet is always 21 bytes. 19 bytes of data plus 2 bytes at end for CRC/checksum/hash
• Hence, there are here are no length or header bytes. All 19 bytes are involved in the hash calculation.
• I have ability to generate certain amounts of data packets with the device
• My first thoughts is that the data packets have some sort of CRC-16 calculation
• So I followed reversing hints in www.cosc.canterbury.ac.nz/greg.ewing/essays/CRC-Reverse-Engineering.html

• Verified that my data packet samples observed the "superposition principle" outlined in above web link. This indicates that they have a mathematical XOR relationship.

• Started to feel good ... but then stumped after that. Have not been able to determine a CRC-16 polynomial. There is a strong possibility that these data packets hashes are not CRC-related, but rather some home brew scheme.

• Read thru “A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS” by Ross N. Williams

• See http://www.ross.net/crc/download/crc_v3.txt
• Also used application: CRC Reveng – a reverse engineering application
• See reveng.sourceforge.net
• Still no luck ...

• Unfortunately, I do not have access to any of the devices source/binary code

• Also ran tests to see if used other hashes such as Fletcher's checksum

Here are various samples of my data packets.

0x47366B2EE00000000000751CEB5F3469543B585E2D
0x47366B2ED00000000000751CEB5F3469543B582A2C
0x47366B2EC80000000000751CEB5F3469543B580B2B
0x47366B2EC40000000000751CEB5F3469543B58BB2A
0x47366B2EC20040000000751CEB5F3469543B58DFE7
0x47366B2EC10000000000751CEB5F3469543B58A328
0x47366B2EC08000000000751CEB5F3469543B584127
0x47366B2EC04000000000751CEB5F3469543B588126
0x47366B2EC02000000000751CEB5F3469543B580525
0x47366B2EC01000000000751CEB5F3469543B580124

Please note the following about these data packets ...

• CRC is found on the last 2 bytes of the data packet.
• If I look at the bits on a logic analyzer, I have expressed the bytes as MSB-first
• Hence, packet 0x47366B2EE00000000000751CEB5F3469543B585E2D is seen in binary as:
• 01000111 .............................................................00101101

• (0x47).....................................................................(0x2D)

• I do not know if my system is big or little endian, but quite certain bytes are LSB-first

• Note that for the above 10 data packet samples, each packet differs by 1 bit shifting thru 10 bit positions. Except for 5th packet, where I had to change 2 bits

• See data bytes that follows 0x47366B2E portion of the data packet.

• Only pattern I see that emerged is the last byte decrements by one (2D, 2C, ...) on each data packet. (Except the 5th packet, where I had to change 2 bits)

• This last byte is NOT some sort of sequence number, since I can generate them at any time with same value.
• But it possibly gives a hint on the mathematical hash used.

Any help is appreciated !

Answer 1

IF it follows the simple XOR relationship that (checksum(A ^ B) == checksum(A) ^ checksum(B)) then there is a simple brute force solution!

Illustration. Suppose you have a 1-byte value with a K-bit checksum - where K doesn't actually matter, so we just represent checksums as c(i).

Step 1. Experiment: observe the checksum c(-1) of the all zeros packet.

0b0000000 => c(-1) 

Step 2. Experiment: observe the checksums c(i) of all binary sequence with a single 1 in them at position i

0b00000001 => c(0) 0b00000010 => c(1) 0b00000100 => c(2) 0b00001000 => c(3) 0b00010000 => c(4) 0b00100000 => c(5) 0b01000000 => c(6) 0b10000000 => c(7) 

The values you observed the checksums for form a linear basis for GF(2), and the XOR relationship now allows you to compute any checksum.

Now you can compute checksums by adding the checksums for each bit position with a 1, e.g. suppose you want the checksum of 0XF3 which in binary is 0b11110011. Since

0b11110011 = (0) + 0x80 + 0x40 + 0x20 + 0x10 + 0x02 + 0x01 

then by XOR relationship,

checksum(0b11110011) = c(7) + c(6) + c(5) + c(4) + c(1) + c(0) + c(-1) 

i.e. for every bit you are going to output, just XOR-accumulate the known checksum for that bit.

If you do this exercise and experimentally write out all 152 checksums of the basis vectors, it's possible you will also in the process spot a simple pattern that explains how the checksums come from the basis vectors. :) If so it would be nice to post that back here! (And maybe tell us what we're reversing?)