Recently for a project I had to reverse-engineer the packet checksum for a poorly documented transmitted protocol
In the past I have lucked out and checksums that were simple Xor or each byte or twos complement of the sum.
Sadly not the case for this project.
First I tried various tools ( pycrc http://www.tty1.net/pycrc/ , etc. )
Given the checksum was 8bit I it was not unreasonable to attempt brute forcing.
This failed, this indicating to me that is was not permutation of a standardized CRC
Looking deeper at the data, some basic analysis indicated the checksum was a permutation of xor
When a rolling xor was applied the final value always ends in a '0' we know that the lower (least significant) nibble is a simple XOR product:
example :
03 64 78 24 80 25 13 19 00 14 = 80
07 E5 3F 16 80 25 13 19 00 B4 = D0
0B 69 54 17 80 25 13 19 00 CE = 40
23 80 25 13 F4 50 17 13 00 C5 = F0
27 80 25 13 E5 3F 16 02 51 0E = 00
42 E5 3F 16 11 0D 27 11 01 45 = E0
47 D2 6C 16 11 0D 27 11 01 84 = 40
4B E5 3F 16 11 0D 27 11 01 FC = 50
61 11 0D 27 69 54 17 13 02 61 = 00
C3 9B FF 2A 01 00 00 13 01 DE = 40
C7 69 54 17 01 00 00 11 00 9D = 60
CB 11 0D 27 02 00 00 13 00 21 = C0
Leaving only the high nibble to be defined
After reading "A paper on CRCs" ( Ross Williams : http://www.ross.net/crc/crcpaper.html )
After some reading I realized:
- Most CRCs algorithms are stateless, that is the CRC engine only acts upon the current byte (or word) without regard of surrounding data
- Many CRC algorithms are implemented as table lookup
Thus my next plan of attack was to generate a state table for the CRC engine.
Given the data and CRC were 8-bit keyspace size was not an issue.
( Crossing my fingers, hoping the implementers did not do anything crazy )
First step was to generate a multiple datasets with one byte differences.
Using data I generated tables where samples with one bit differences are Xored together and the checksum difference highlighted.
XOR 23 80 25 13 11 78 2B 11 04 : 42
=
23 80 25 13 11 78 2B 11 14 : 52
10: 00 00 00 00 00 00 00 00 10 : 10
--
23 80 25 13 11 78 2B 11 24 : 62
20: 00 00 00 00 00 00 00 00 20 : 20
--
23 80 25 13 11 78 2B 11 34 : 72
30: 00 00 00 00 00 00 00 00 30 : 30
--
23 80 25 13 11 78 2B 11 44 : 02
40: 00 00 00 00 00 00 00 00 40 : 40
--
23 80 25 13 11 78 2B 11 54 : 12
50: 00 00 00 00 00 00 00 00 50 : 50
--
23 80 25 13 11 78 2B 11 64 : 22
60: 00 00 00 00 00 00 00 00 60 : 60
--
23 80 25 13 11 78 2B 11 74 : 32
70: 00 00 00 00 00 00 00 00 70 : 70
--
23 80 25 13 11 78 2B 11 84 : C2
80: 00 00 00 00 00 00 00 00 80 : 80
--
23 80 25 13 11 78 2B 11 94 : D2
90: 00 00 00 00 00 00 00 00 90 : 90
--
23 80 25 13 11 78 2B 11 A4 : E2
A0: 00 00 00 00 00 00 00 00 A0 : A0
--
23 80 25 13 11 78 2B 11 B4 : F2
B0: 00 00 00 00 00 00 00 00 B0 : B0
--
23 80 25 13 11 78 2B 11 C4 : 82
C0: 00 00 00 00 00 00 00 00 C0 : C0
--
23 80 25 13 11 78 2B 11 D4 : 92
D0: 00 00 00 00 00 00 00 00 D0 : D0
--
23 80 25 13 11 78 2B 11 E4 : A2
E0: 00 00 00 00 00 00 00 00 E0 : E0
--
23 80 25 13 11 78 2B 11 F4 : B2
F0: 00 00 00 00 00 00 00 00 F0 : F0
From this I can tell the high nibble is not used for any permutations other than xor
and when looking how the lower nibble effects the upper nibble
.. .. .. .. .. .. .. 01 .. 31
.. .. .. .. .. .. .. 02 .. 62
.. .. .. .. .. .. .. 03 .. 53
.. .. .. .. .. .. .. 04 .. C4
.. .. .. .. .. .. .. 06 .. A6
.. .. .. .. .. .. .. 07 .. 97
.. .. .. .. .. .. .. 08 .. 88
.. .. .. .. .. .. .. 09 .. B9
.. .. .. .. .. .. .. 0A .. EA
.. .. .. .. .. .. .. 0B .. DB
.. .. .. .. .. .. .. 0C .. 4C
.. .. .. .. .. .. .. 0D .. 7D
.. .. .. .. .. .. .. 0F .. 1F
A map can be made
00 0000 0000 -> 00 0000 0000
01 0000 0001 -> 30 0011 0000
02 0000 0010 -> 60 0110 0000
03 0000 0011 -> 50 0101 0000
04 0000 0100 -> C0 1100 0000
05 0000 0101 -> F0 1111 0000
06 0000 0110 -> A0 1010 0000
07 0000 0111 -> 90 1001 0000
08 0000 1000 -> 80 1000 0000
Or in C:
r = 0 ;
for(i=0;i<dat_len;i++) {
r ^= dat[i] ;
r ^= (( r ^ ( r << 1 )) & 0x0F) << 4 ;
}
While this method will not work for all CRC methods it should help for CRC that are not based on linear-feedback shift register
----------
http://www.cosc.canterbury.ac.nz/greg.ewing/essays/CRC-Reverse-Engineering.html
http://blog.affien.com/archives/2005/07/15/reversing-crc/
http://stigge.org/martin/pub/SAR-PR-2006-05.pdf
