Guessing CRC checksum algorithm

Question

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:  [email protected].

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          

0xAD00       0x1A05          

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!

Answer 1

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[1]));
    printf("calculated %4.4x, actual %4.4x\n", 
         verify(s2, sizeof(s2)-1), *(uint16_t *)(&s2[1]));
    printf("calculated %4.4x, actual %4.4x\n", 
         verify(s3, sizeof(s3)-1), *(uint16_t *)(&s3[1]));
    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).

Answer 2

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[0]<='2')         { sum=0x3283; }
    else if (l==2 && s[0]>='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[1]);
    } else if (argc==1) {
        allsums();
    } else {
        printf("bad args\n");
        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.

Answer 3

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*
             ((payload (first checksum-list))
              (computed-checksum (compute-checksum (ascii-to-numeric payload)))
              (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.