# Guessing CRC checksum algorithm

I am trying to reverse engineer a 16 bit checksum algorithm of one relatively old (10 years) LAN game that is no longer supported nor has source code available. As it seems, data packets don't have standard structure when it comes to placing checksum bytes:

``````Example 1:

1f456e01
``````

Where first byte `1f` seems to repeat itself in each packet and I assume it doesn't take part in generating checksum.

Next two bytes `456e` represent a checksum that presumably is a variation of `CRC-CCITT` with non-standard polynomial.

Lastly, `01` byte represents data.

Here are few more examples of packets with various data values:

``````1f466e02
1f496e05
1f4b6e07
1f4c6e08
``````

I wish I could post more diverse values but these are only ones I've been able to capture so far.

I tried fiddling with reveng to reverse engineer the polynomial with following command:

``````reveng -w 16 -s 01456e 02466e 05496e
``````

Here the checksum bytes are relocated at the end, as reveng expects them in this format. But this gave no results.

I have tried comparing these checksums to most if not all common crc algorithms using online calculators but none of them give even close outputs to those above.

Honestly, I don't know where else to look.

Any hints/help or anything at all is much appreciated.

EDIT:

I managed to capture some more samples, however they are slightly different in terms of structure:

Example 1:

``````0e ed76 00 312e362e37544553540000000000000000000000000000000000000000 00
``````

Here the first byte `0E` represents a sort of index, that I still think doesn't take part in generating checksum. Then comes two byte checksum `ED76` followed by `00` sort of separator (newline?) byte that I also think doesn't take part in computing checksum. Afterwards follows data sequence: `312e362e37544553540000000000000000000000000000000000000000` which finally is proceeded by `00` terminating character that I also think has nothing to do with checksum.

I can manipulate with the data part of this sequence of bytes so here are some more examples:

``````Example 2:

HEX:    0E109D00414141414141414141414141414141414141414141414141414141414100
ASCII:  ....AAAAAAAAAAAAAAAAAAAAAAAAAAAAA.

Example 3:

HEX:    0E8DC300424242424242424242424242424242424242424242424242424242424200
ASCII:  ....BBBBBBBBBBBBBBBBBBBBBBBBBBBBB.

Example 4:

HEX:    0E403500313131313131313131313131313131313131313131313131313131313100
ASCII:  .@5.11111111111111111111111111111.

Example 5:

HEX:    0E34CF00353535353535353535353535353535353535353535353535353535353500
ASCII:  .4..55555555555555555555555555555.

Example 6:

HEX:    0E3E0C00313233343536373839304142434445464748494A4B4C4D4E4F5051525300
ASCII:  .>..1234567890ABCDEFGHIJKLMNOPQRS.
``````

EDIT 2: More samples added, checksum bytes reversed to show the actual 16 bit int (little endian)

``````Data         Checksum

0x01         0x6E45
0x02         0x6E46
0x03         0x6E47

0x0001       0x3284

0x0002       0x3285
0x0003       0x3286
0x0104       0x32A8
0x0005       0x3288
0x0903       0x33AF
0x0106       0x32AA

0x3600       0x0AAE

0xF300       0x230B
0xF400       0x232C
0xF500       0x234D
0xF600       0x236E
0xF700       0x238F
0xF800       0x23B0

0xFE00       0x2476
0xA800       0x1960

0xE200       0x20DA
0xE500       0x213D
0xEE00       0x2266

0x7300       0x128B
0x7600       0x12EE
0xF700       0x238F

0xB400       0x1AEC
0xB800       0x1B70
0xBC00       0x1BF4

0x015E00     0xF68B
0x013D00     0xF24A
0x011C00     0xEE09
``````

EDIT 3: More samples that might make it easier to see the pattern:

``````Checksum     Data (ASCII)

3540         11111111111111111111111111111
3561         11111111111111111111111111112
3582         11111111111111111111111111113

3981         11111111111111111111111111121
39A2         11111111111111111111111111122

c1a1         11111111111111111111111111211
4DC1         11111111111111111111111112111

5de1         11111111111111111111111121111
7201         11111111111111111111111211111
``````

EDIT 4:

There was a typo in one of EDIT 3 samples - correct checksum for `11111111111111111111111112111` is `4DC1` instead of `C10E`. Edited original sample. Apologies to everyone who lost their time because of this.

EDIT 5:

It turns out, the index byte does play a role in calculating checksum, here is one particular example proving it:

``````INDEX   CHECKSUM    PAYLOAD

0x2B    0x704E      0x7E
0x3E    0x72C1      0x7E

Same payload has different checksum for different indexes. (checksum bytes reversed to show the actual 16 bit int)
``````

Some more samples:

``````INDEX   CHECKSUM    PAYLOAD

0x3E    0x72C0      0x7D
0x1F    0x6E45      0x01
0x2B    0x704F      0x7F
``````

Epilogue

Please see the accepted answer for the exact algorithm. Special thanks to Edward, nrz and Guntram Blohm; solving this would take a lifetime without your help guys!

• can't you locate the routine, for example via memory read/write breeakpoint ? – Ange May 27 '14 at 10:35
• Unfortunately a quick scan with PEID shows that the main executable is packed with ASProtect 1.2x - 1.3x. I could try unpacking it and then following your suggestion, but I thought somebody might've recognized the pattern in crc algorithm – astralmaster May 27 '14 at 10:52
• Are you sure your example when you change the 4th digit from the right, where the checksum is c10e, is correct? I have an idea, but that would need this checksum to be 4dc1. Maybe you were off by one byte/two hex digits when you copy/pasted that checksum? – Guntram Blohm May 29 '14 at 21:48
• looking at the packet it looks like a packet counter to make sure you don't inject packets not a checksum. – SSpoke May 29 '14 at 22:45
• @astralmaster: in your Edit 2 data, is the first byte of each packet always 0x1f as with the originals? That is, when you write "0xBC00 0x1BF4" I'm interpreting that as coming from a packet that was originally `1f f4 1b bc 00`. Is that correct? – Edward May 30 '14 at 16:30

Got it. Here's how to calculate, using your first string as a simple example:

``````1f456e01
``````

First, we rearrange the packet, omitting the checksum.

``````1f 01
``````

Then prepend the values A3 02:

``````a3 02 1f 01
``````

Then calculate the checksum by starting with a sum of 0, multiplying the sum by 33 (decimal) each time and adding the value of the next byte.

Here it is in C with a few of your sample strings for illustrations. Note that this assumes a little-endian machine (e.g. x86).

``````#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

const unsigned char s1[]= "\x0e\x01\x72\x00\x31\x31\x31\x31\x31\x31\x31\x31\x31\x31\x31\x31\x31\x31\x31\x31\x31\x31\x31\x31\x31\x31\x31\x32\x31\x31\x31\x31\x31\x00";
const unsigned char s2[]="\x2b\x4f\x70\x7f";
const unsigned char s3[]="\x1f\x46\x6e\x02";

uint16_t verify(const unsigned char *pkt, size_t sz)
{
uint16_t sum = 0xa3 * 33 + 2;
int i;
for (i=0; i < sz; ++i) {
if ((i != 1) && (i != 2))
sum = sum*33 + pkt[i];
}
return sum;
}

int main()
{
printf("calculated %4.4x, actual %4.4x\n",
verify(s1, sizeof(s1)-1), *(uint16_t *)(&s1));
printf("calculated %4.4x, actual %4.4x\n",
verify(s2, sizeof(s2)-1), *(uint16_t *)(&s2));
printf("calculated %4.4x, actual %4.4x\n",
verify(s3, sizeof(s3)-1), *(uint16_t *)(&s3));
return 0;
}
``````

Here's the output from that program:

``````calculated 7201, actual 7201
calculated 704f, actual 704f
calculated 6e46, actual 6e46
``````

# Update:

I thought it might be useful to describe how I came about this answer so that it may help others in the future. First, as other answers note, your packets that were identical except for a single bit were invaluable in determining the general checksum algorithm (multiplying by 33 and adding the next byte).

What remained was to determine the starting position which could have included the first byte (the one you're calling the index byte) and/or the length. When I compared two packets which were identical except for the index byte, and assuming a linear relationship also for these bytes, it was easy to determine that the index byte was "next to" the data bytes for calculation purposes.

When I did that, all of the complete packets among your samples differed from my calculated value (long packets all by the constant `0xe905` and short packets by `0x6a45`). Since the checksum is only 2 bytes, I guessed that there might be a 2-byte initialization value and simply wrote a small program to try all combinations. I chose one combination (A3 02) but in fact, there are exactly eight combinations that work -- all you need is something that ultimately evaluates to `0x1505` (5381 decimal).

• Good job! Beat me by 25 minutes. – Guntram Blohm May 30 '14 at 21:01
• I've been staring at it for a while. Puzzles are fun! – Edward May 30 '14 at 21:03
• Bullseye! Nice catch on that index byte mate! Indeed, puzzles are fun! The only thing that puzzles me now is that I can't upvote your answer more than once))) – astralmaster May 30 '14 at 21:15
• @astralmaster: The other answers are valuable, too, I think, in that they nicely explain the process by which one goes about such sleuthing. I'll add a bit to my answer to explain how I came about this, in the hope that it might help the next person to reverse engineer unknown packets. – Edward May 30 '14 at 21:23
• I'd like to add that this algorithm is called DJB2. – Xcelled Aug 14 '14 at 1:50

I'd assume the first byte is a message type ID, the 2nd and 3rd bytes are checksum, and the rest is payload. As the game is probably an i386 game, the payload ought to be little-endian. Now, if we compare your first 4 examples, with bytes 2 and 3 written as a 16-bit-int, we have:

``````1f 6e45 01
1f 6e46 02
1f 6e49 05
1f 6e4b 07
1f 6e4c 08
``````

in these cases the checksum is always 0x6E44 plus the payload byte. This looks like a simple checksum algorithm to me, not a crc algorithm.

(Maybe your game's name could be abbreviated as E N or N E, which could explain why the programmer used 0x6E44 as seed for his checksum?)

In your example 2 and 3, the checksum difference is C38D-9D10=267C (9853 decimal) which is a lot more than is explained by a few byte-wise +1 additions, so the bytes probably get multiplied by something depending on their position. Which would mean the checksum is

``````0x6E44+sum(byte[i]*weight[i])
``````

where i runs from 0 to the number of bytes.

I'd start out with your version packet set to 11111, then 21111, then 31111, 41111, then 12111, 13111, 14111, then 11211, 11311, 11411, .... to see if

1. increasing a byte at a certain position always results in the same difference in checksum
2. those bytes have different weight, and find a pattern which byte position increases the checksum by how much, to get the `weight` values in above equation.

## Edit

I have a program that almost works. As always, take it as an example of something quickly thrown together, not of good programming style. The last byte has a multiplier of 1; the multiplier for every other byte (n) is 33 (0x21) times the multiplier of (n+1).

``````void chksum(char *s) {
int i, b, l, sum, fact;

if ((l=strlen(s))%2!=0) {
printf("not an even number of digits\n");
exit(2);
}
l/=2;

if (l==1)                       { sum=0x6e44; }
else if (l==2 && s<='2')         { sum=0x3283; }
else if (l==2 && s>='3')         { sum=0x03B8; }
else if (l==31)                     { sum=0xd753; }
else            {
printf("unknown seed for %d bytes\n", l);
exit(3);
}

fact=1;
for (i=l-1; i>=0; i--) {
sscanf(s+2*i, "%02x", &b);
sum+=b*fact; sum &=0xffff;
fact*=0x21;    fact&=0xffff;
}
printf("checksum is %04x\n", sum);
}

void allsums() {
int i;
char *samples[]={
"01", "02", "03",
"0001", "0002", "0003", "0104", "0005", "0903", "0106",
"3600", "ad00", "f300", "f400", "f500", "f600", "F700", "f800",
"fe00", "a800", "e200", "e500",

"00313131313131313131313131313131313131313131313131313131313100",
"00313131313131313131313131313131313131313131313131313131313200",
"00313131313131313131313131313131313131313131313131313131313300",
"00313131313131313131313131313131313131313131313131313131323100",
"00313131313131313131313131313131313131313131313131313131323200",
"00313131313131313131313131313131313131313131313131313132313100",
"00313131313131313131313131313131313131313131313131313231313100",
"00313131313131313131313131313131313131313131313131323131313100",
"00313131313131313131313131313131313131313131313132313131313100",

"00414141414141414141414141414141414141414141414141414141414100",
"00424242424242424242424242424242424242424242424242424242424200",
"00353535353535353535353535353535353535353535353532353535353500",
"00313233343536373839304142434445464748494A4B4C4D4E4F5051525300",
};

for (i=0; i<sizeof(samples)/sizeof(char *); i++) {
printf("%s: ", samples[i]);
chksum(samples[i]);
}
}

int main(int argc, char **argv) {

if (argc==2) {
chksum(argv);
} else if (argc==1) {
allsums();
} else {
exit(1);
}
}
``````

It returns your checksums for most test strings; one of your checksums has probably been copy/pasted wrong (see my comment on your post), the last 2 don't seem to match, and what's really ugly is the initial checksum value depending on the length of the string. I'd assume it depends on the type byte (byte one in the packet, before the checksum) as well, so it would probably help if you could add that to your examples.

## Edit 2

What @Edward said. Initialize the checksum to 0, and prepend A3 02 and the type byte to the string, then use the above algorithm.

• Interesting! Thank you, Im trying these now – astralmaster May 27 '14 at 16:20
• Yes indeed, the index byte does take part in calculating checksum. Check my last edit in the original post – astralmaster May 30 '14 at 19:48

The checksum is very simple, as can be seen from the minimal difference in checksum between `11111111111111111111111111111` and `11111111111111111111111111112`, the difference is 0x21 (33 in decimal).

Then, difference between `11111111111111111111111111121` and `11111111111111111111111111111` is 0x441, that is 0x21^2.

The checksum (I'll call it `y`) is clearly a linear function of the terms (bytes) of the payload (29 bytes, I'll call them `x1` ... `x29`), each byte having its' own coefficient (multiplier, beta, you name it, I'll call them `b1` ... `b29`) and then there is a constant term (I'll call it `c`), in the following form:

```y = b1*x1 + b2*x2 + b3*x3 + ... + b27*x27 + b28*x28 + b29*x29 + c
```

We know already that `b29` is 0x21, from the difference of checksums between payloads `11111111111111111111111111111` and `11111111111111111111111111112`. We also know that `b28` is 0x441, from the difference of checksums between payloads `11111111111111111111111111121` and `11111111111111111111111111111`. Let's assume that coefficients multiply by 0x21 when going through them in reverse order, that is, starting from `b29` (0x21), then `b28` (0x441), ... At some point there will be overflow for 16-bit integers, but that does not matter, we only need the lowest 16 bits.

Now we have an idea of all coefficients `b1` ... `b29`. We only need to find out the constant `c`. Well, it's very easy, it's the difference between the correct checksum and the checksum computed with `c` = 0. For `11111111111111111111111111111` the checksum with `c == 0` is 0x5ded, so well subtract from 0x3540 (the correct checksum) the computed checksum 0x5ded to get the correct constant `c`. The value of `c` is therefore `0x3540 - 0x5ded = -0x28ad`.

To try this solution (these betas `b1` ... `b29` and this constant `c`) to all given samples I wrote a simple Common Lisp program, here's the code:

```(defparameter *ascii-checksum-data* (list (list "11111111111111111111111111111" #x3540)   ; OK.
(list "11111111111111111111111111112" #x3561)   ; OK.
(list "11111111111111111111111111113" #x3582)   ; OK.
(list "11111111111111111111111111121" #x3981)   ; OK.
(list "11111111111111111111111111122" #x39a2)   ; OK.
(list "11111111111111111111111111211" #xc1a1)   ; OK.
(list "11111111111111111111111112111" #xc10e)   ; does not match, produces 4dc1.
(list "11111111111111111111111121111" #x5de1)   ; OK!
(list "11111111111111111111111211111" #x7201)   ; OK.
(list "1234567890ABCDEFGHIJKLMNOPQRS" #x0c3e)   ; OK.
(list "55555555555555555555555555555" #xcf34)   ; OK.
(list "AAAAAAAAAAAAAAAAAAAAAAAAAAAAA" #x9d10)   ; OK.
(list "BBBBBBBBBBBBBBBBBBBBBBBBBBBBB" #xc38d))) ; ok.

(defun ascii-to-numeric (my-string)
"This function converts an ASCII string into a list of ASCII values."
(map 'list #'(lambda (x)
(char-code (coerce x 'character)))
my-string))

(defun compute-checksum (bytes-list)
"This function computes the checksum for a given list of bytes."
(let
((multiplier #x21)
(checksum 0))
(loop for i from (1- (length bytes-list)) downto 0
do (progn
(incf checksum (* multiplier (nth i bytes-list)))
(setf multiplier (* #x21 multiplier))))
(logand (+ checksum (- #x3540 #x5ded)) #xffff)))

(defun compute-all-checksums (checksum-data)
"This function computes and prints all checksums for a given list of lists of checksum data."
(format t "~29a ~8x ~5x ~a~%" "payload" "computed" "given" "matches")
(loop for checksum-list in checksum-data
do (let*
(given-checksum (second checksum-list))
(matches (if (eql computed-checksum given-checksum) "Y" "N")))
(format t "~a ~8x ~5x ~a~%" payload computed-checksum given-checksum matches))))

(defun do-all ()
(compute-all-checksums *ascii-checksum-data*))
```

Compiles at least with SBCL. Then running `(do-all)` in SBCL REPL produces the following:

```payload                       computed given matches
11111111111111111111111111111     3540  3540 Y
11111111111111111111111111112     3561  3561 Y
11111111111111111111111111113     3582  3582 Y
11111111111111111111111111121     3981  3981 Y
11111111111111111111111111122     39A2  39A2 Y
11111111111111111111111111211     C1A1  C1A1 Y
11111111111111111111111112111     4DC1  C10E N
11111111111111111111111121111     5DE1  5DE1 Y
11111111111111111111111211111     7201  7201 Y
1234567890ABCDEFGHIJKLMNOPQRS      C3E   C3E Y
55555555555555555555555555555     CF34  CF34 Y
AAAAAAAAAAAAAAAAAAAAAAAAAAAAA     9D10  9D10 Y
BBBBBBBBBBBBBBBBBBBBBBBBBBBBB     C38D  C38D Y
```

The checksum of payload `11111111111111111111111112111` is the only one that doesn't match.

Assuming that the checksum is anyway a linear function, there are two possibilities:

1. The coefficients are not correct, this is possible, because at the moment the system (a system of linear equations) is underdetermined. We have 30 unknowns (29 betas and 1 constant) and only 13 equations (13 samples, that is).
2. There is a typo in the given checksum of `11111111111111111111111112111`.

If you can produce a total of 30 samples (a fully determined system), all unknowns (29 betas and 1 constant) can be confirmed by solving a system of linear equations.

• Thank you for your time and help! I am checking these now, as you have correctly guessed, there was a typo in that checksum, the correct one is 4DC1 instead of C10E. I will apply this algorithm to various byte sequences and reply back shortly – astralmaster May 30 '14 at 19:11