猜测CRC校验和算法

逆向工程 去混淆 解密 联网
2021-06-16 05:15:42

我正在尝试对一个不再受支持也没有可用源代码的相对较旧(10 年)的 LAN 游戏的 16 位校验和算法进行逆向工程。看起来,数据包在放置校验和字节时没有标准结构:

Example 1:

1f456e01

第一个字节1f似乎在每个数据包中重复出现,我认为它不参与生成校验和。

接下来的两个字节456e表示校验和,大概是CRC-CCITT非标准多项式的变体

最后,01字节代表数据。

以下是具有各种数据值的数据包的更多示例:

1f466e02
1f496e05
1f4b6e07
1f4c6e08

我希望我可以发布更多不同的值,但到目前为止我只能捕捉到这些值。

我尝试摆弄reveng以使用以下命令对多项式进行逆向工程:

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

在这里,校验和字节在最后重新定位,因为 reveng 期望它们采用这种格式。但这没有结果。

我曾尝试使用在线计算器将这些校验和与大多数(如果不是全部)常见的 crc 算法进行比较,但它们都没有给出与上述算法相近的输出。

老实说,我不知道还能去哪里找。

任何提示/帮助或任何东西都非常感谢。

编辑:

我设法捕获了更多样本,但是它们在结构方面略有不同:

示例 1:

0e ed76 00 312e362e37544553540000000000000000000000000000000000000000 00

这里的第一个字节0E代表一种索引,我仍然认为它不参与生成校验和。然后是两个字节的校验和,ED76然后是00某种分隔符(换行符?)字节,我也认为它不参与计算校验和。之后是数据序列:312e362e37544553540000000000000000000000000000000000000000最后是通过00终止字符进行的,我也认为与校验和无关。

我可以使用此字节序列的数据部分进行操作,因此这里有更多示例:

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.

编辑 2: 添加了更多示例,校验和字节反转以显示实际的 16 位 int(小端)

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 

编辑 3:更多示例可能更容易查看模式:

Checksum     Data (ASCII)

3540         11111111111111111111111111111
3561         11111111111111111111111111112
3582         11111111111111111111111111113

3981         11111111111111111111111111121
39A2         11111111111111111111111111122

c1a1         11111111111111111111111111211
4DC1         11111111111111111111111112111

5de1         11111111111111111111111121111
7201         11111111111111111111111211111

编辑 4:

EDIT 3 个示例之一中有一个错字- 正确的校验和111111111111111111111111121114DC1而不是C10E. 编辑原始样本。向所有因此而失去时间的人道歉。

编辑 5:

事实证明,索引字节确实在计算校验和时起作用,这里有一个特殊的例子来证明它:

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)

更多示例:

INDEX   CHECKSUM    PAYLOAD

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

结语

请参阅接受的确切算法的答案。特别感谢EdwardnrzGuntram Blohm如果没有你们的帮助,解决这个问题将需要一生的时间!

3个回答

知道了。以下是计算方法,以您的第一个字符串为例:

1f456e01

首先,我们重新排列数据包,省略校验和。

1f 01

然后添加值 A3 02:

a3 02 1f 01

然后计算校验和,从总和为 0 开始,每次将总和乘以 33(十进制)并加上下一个字节的值。

这是用 C 语言编写的,其中包含一些用于插图的示例字符串。请注意,这假设是小端机器(例如 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;
}

这是该程序的输出:

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

更新:

我认为描述我如何得出这个答案可能会有用,以便将来可以帮助其他人。首先,正如其他答案所指出的,除了单个位之外,您的数据包在确定通用校验和算法(乘以 33 并添加下一个字节)方面是无价的。

剩下的就是确定可能包含第一个字节(您称之为索引字节的那个)和/或长度的起始位置当我比较除了索引字节之外的两个相同的数据包,并假设这些字节也具有线性关系时,很容易确定索引字节“紧邻”数据字节以进行计算。

当我这样做时,您样本中的所有完整数据包都与我的计算值不同(长数据包全部为常量0xe905,短数据包为0x6a45)。由于校验和只有2个字节,我猜测可能会有2个字节的初始化值,于是简单写了一个小程序尝试所有组合。我选择了一种组合 (A3 02),但实际上,正好有八种组合有效——您所需要的只是最终计算结果为0x1505(5381 十进制)的组合。

我假设第一个字节是消息类型 ID,第二个和第三个字节是校验和,其余的是有效载荷。由于游戏可能是 i386 游戏,因此有效负载应该是小端的。现在,如果我们比较你的前 4 个例子,字节 2 和 3 写为 16 位整数,我们有:

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

在这些情况下,校验和总是 0x6E44 加上有效载荷字节。这对我来说看起来像一个简单的校验和算法,而不是一个 crc 算法。

(也许您的游戏名称可以缩写为 EN 或 NE,这可以解释为什么程序员使用 0x6E44 作为其校验和的种子?)

在您的示例 2 和 3 中,校验和的差异是 C38D-9D10=267C(9853 十进制),这比几个逐字节 +1 加法所解释的要多得多,因此字节可能会根据它们的位置乘以某些东西. 这意味着校验和是

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

我从 0 到字节数运行。

我首先将您的版本数据包设置为 11111,然后是 21111,然后是 31111、41111,然后是 12111、13111、14111、然后是 11211、11311、11411,......看看是否

  1. 在某个位置增加一个字节总是会导致校验和的相同差异
  2. 这些字节具有不同的权重,并找到字节位置将校验和增加多少的模式,以获得weight上述等式中值。

编辑

我有一个几乎可以工作的程序和往常一样,把它作为一个快速组合在一起的例子,而不是好的编程风格。最后一个字节的乘数为 1;每隔一个字节 (n) 的乘数是 (n+1) 的乘数的 33 (0x21) 倍。

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);
    }
}

它返回大多数测试字符串的校验和;您的校验和之一可能被复制/粘贴错误(请参阅我对您帖子的评论),最后 2 个似乎不匹配,真正丑陋的是初始校验和值取决于字符串的长度。我认为它也取决于类型字节(数据包中的第一个字节,在校验和之前),因此如果您可以将其添加到示例中可能会有所帮助。

编辑 2

@Edward 说的。将校验和初始化为 0,并在字符串前加上 A3 02 和类型字节,然后使用上述算法。

校验和非常简单,从 和 之间校验11111111111111111111111111111的最小差异可以看出11111111111111111111111111112,差异为 0x21(十进制为 33)。

那么,11111111111111111111111111121之间的差11111111111111111111111111111是0x441,也就是0x21^2。

校验和(我称之为y)显然是有效载荷(29 个字节,我称之为x1... x29的项(字节)的线性函数,每个字节都有自己的系数(乘数、beta、你命名它,我会称它们为b1... b29)然后有一个常数项(我会称它为c),形式如下:

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

我们已经知道这b29是 0x21,从有效载荷1111111111111111111111111111111111111111111111111111111112. 我们也知道它b28是 0x441,从有效载荷1111111111111111111111111112111111111111111111111111111111. 让我们假设系数在以相反的顺序通过它们时乘以 0x21,即从b29(0x21) 开始,然后是b28(0x441),......在某些时候,16 位整数会溢出,但这并不重要,我们只需要最低的 16 位。

现在我们有所有系数的想法b1... b29我们只需要找出常数c嗯,这很容易,就是正确的校验和和用c= 0计算的校验和之间的差异。因为11111111111111111111111111111校验和c == 0是 0x5ded,所以从 0x3540(正确的校验和)中减去计算出的校验和 0x5ded 以获得正确的常量c的值c,因此是0x3540 - 0x5ded = -0x28ad

为了对所有给定的样本尝试这个解决方案(这些测试版b1......b29和这个常量c),我编写了一个简单的 Common Lisp 程序,代码如下:

(defparameter *ascii-checksum-data* (list (list "111111111111111111111111111111" #x3540) ; OK。
                                          (列表“11111111111111111111111111112”#x3561);行。
                                          (列表“11111111111111111111111111113”#x3582);行。
                                          (列表“11111111111111111111111111121”#x3981);行。
                                          (列表“11111111111111111111111111122”#x39a2);行。
                                          (列表“11111111111111111111111111211”#xc1a1);行。
                                          (列表“11111111111111111111111112111”#xc10e);不匹配,产生 4dc1。
                                          (列表“11111111111111111111111121111”#x5de1);行!
                                          (列表“11111111111111111111111211111”#x7201);行。
                                          (列表“1234567890ABCDEFGHIJKLMNOPQRS”#x0c3e);行。
                                          (列出“5555555555555555555555555555”#xcf34);行。
                                          (列表“AAAAAAAAAAAAAAAAAAAAAAAAAAA”#x9d10);行。
                                          (列出“BBBBBBBBBBBBBBBBBBBBBBBBBBBBB”#xc38d)));行。

(defun ascii-to-numeric (my-string)
  “此函数将 ASCII 字符串转换为 ASCII 值列表。”
  (map 'list #'(lambda (x)
                 (char-code (coerce x 'character)))
       我的字符串))

(defun 计算校验和(字节列表)
  “此函数计算给定字节列表的校验和。”
  (让
    ((乘数#x21)
     (校验和 0))
    (循环 i 从(1-(长度字节列表))到 0
          做(计划
               (incf checksum (* multiplier (nth i bytes-list)))
               (setf 乘数 (* #x21 乘数))))
    (logand (+ checksum (- #x3540 #x5ded)) #xffff)))

(defun 计算所有校验和(校验和数据)
  “此函数计算并打印给定校验和数据列表的所有校验和。”
  (格式 t "~29a ~8x ~5x ~a~%" "payload" "computed" "given" "matches")
  (校验和数据中校验和列表的循环
        做(让*
             ((有效载荷(第一个校验和列表))
              (computed-checksum (compute-checksum (ascii-to-numeric payload)))
              (给定校验和(第二个校验和列表))
              (匹配(如果(eql计算校验和给定校验和)“Y”“N”)))
             (格式 t "~a ~8x ~5x ~a~%" 有效载荷计算校验和给定校验和匹配))))

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

至少用 SBCL 编译。然后(do-all)在 SBCL REPL 中运行会产生以下结果:

给定匹配计算的有效载荷
11111111111111111111111111111 3540 3540 是
11111111111111111111111111112 3561 3561 是
11111111111111111111111111113 3582 3582 是
11111111111111111111111111121 3981 3981 是
11111111111111111111111111122 39A2 39A2 是
11111111111111111111111111211 C1A1 C1A1 Y
11111111111111111111111112111 4DC1 C10E N
11111111111111111111111121111 5DE1 5DE1 Y
11111111111111111111111211111 7201 7201 是
1234567890ABCDEFGHIJKLMNOPQRS C3E C3E Y
5555555555555555555555555555 CF34 CF34 Y
AAAAAAAAAAAAAAAAAAAAAAAAAAAAA 9D10 9D10 是
BBBBBBBBBBBBBBBBBBBBBBBBBBBBB C38D C38D Y

有效载荷的校验和11111111111111111111111112111是唯一不匹配的。

假设校验和无论如何是一个线性函数,有两种可能性:

  1. 系数不正确,这是可能的,因为此时系统(线性方程组)是欠定的我们有 30 个未知数(29 个 beta 和 1 个常数)和只有 13 个方程(即 13 个样本)。
  2. 的给定校验和中有错字11111111111111111111111112111

如果您可以生成总共 30 个样本(一个完全确定的系统),则可以通过求解线性方程组来确认所有未知数(29 个 beta 和 1 个常数)。