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

1f456e01


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

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

最后,01字节代表数据。

以下是一些具有各种数据值的数据包的示例:

1f466e02
1f496e05
1f4b6e07
1f4c6e08


我希望我可以发布更多不同的值,但是到目前为止,这些只是我能够捕捉到的值。 >
reveng -w 16 -s 01456e 02466e 05496e


在这里,校验和字节在结尾处重定位,因为reveng希望采用这种格式。但这没有任何结果。 >老实说,我不知道该在哪里找。

任何提示/帮助或任何其他内容都非常感谢。 >我设法捕获了更多样本,但是它们在结构上略有不同:

示例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:

编辑3个样本之一中有错字-11111111111111111111111112111的正确校验和为4DC1而不是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


结尾

请查看可接受的答案以获取确切的算法。特别感谢Edward,nrz和Guntram Blohm;如果没有您的帮助,解决此问题将需要一生!

评论

您找不到例程,例如通过内存读/写breeakpoint吗?

不幸的是,使用PEID进行的快速扫描显示主要可执行文件与ASProtect 1.2x-1.3x打包在一起。我可以尝试将其拆包,然后按照您的建议进行操作,但我认为有人可能已经意识到crc算法中的模式

当您从右边更改校验和为c10e的第4位时,您确定您的示例正确吗?我有一个主意,但这需要此校验和为4dc1。复制/粘贴该校验和时,也许您丢失了一个字节/两个十六进制数字?

在查看数据包时,它看起来像一个数据包计数器,以确保您不注入数据包而不是校验和。

@astralmaster:在您的Edit 2数据中,每个数据包的第一个字节是否总是与原始数据包一样为0x1f?也就是说,当您编写“ 0xBC00 0x1BF4”时,我将其解释为来自最初是1f f4 1b bc 00的数据包。这是正确的吗?

#1 楼

得到它了。下面是使用第一个字符串作为简单示例的计算方法:

1f456e01


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

1f 01


然后将值A3 02放在前面: (十进制)每次,并加上下一个字节的值。

这里是C语言,带有一些示例字符串供说明。请注意,这里假设使用的是低位字节序机器(例如x86)。

a3 02 1f 01


这是该程序的输出:

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


更新:

我认为描述我如何提出此答案可能很有用,以便将来对其他人有所帮助。首先,正如其他答案所指出的那样,除了单个位以外,其他相同的数据包对于确定常规校验和算法(乘以33并添加下一个字节)非常有用。

剩下的就是确定起始位置,该起始位置可能包含第一个字节(您正在调用的索引字节)和/或长度。当我比较两个除了索引字节外都是相同的数据包,并假设这些字节也具有线性关系时,很容易确定索引字节在数据字节“旁边”是出于计算目的。

当我这样做时,样本中的所有完整数据包都与我的计算值有所不同(长数据包全部为常量0xe905,而短数据包则为0x6a45)。由于校验和仅为2个字节,因此我猜可能会有一个2个字节的初始化值,并只是编写了一个小程序来尝试所有组合。我选择了一种组合(A3 02),但实际上,实际上有八种组合可以工作-您所需要的只是最终评估为0x1505(十进制5381)的内容。

评论


做得好!打败我25分钟

–贡特拉姆·布洛姆(Guntram Blohm)
2014年5月30日在21:01

我凝视了一段时间。拼图很有趣!

–爱德华
2014年5月30日在21:03

靶心!很好地抓住了那个索引字节伙伴!确实,拼图很有趣!现在唯一让我感到困惑的是,我不能不赞成一次您的答案)))

–astralmaster
2014年5月30日在21:15

@astralmaster:我认为其他答案也很有价值,因为它们很好地解释了侦查的过程。我将在回答中添加一些内容以解释我是如何实现的,希望它可以帮助下一个人对未知数据包进行逆向工程。

–爱德华
2014年5月30日在21:23

我想补充一点,该算法称为DJB2。

– Xcelled
14年8月14日在1:50

#2 楼

我假设第一个字节是消息类型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,....以查看是否


在增加一个字节某个位置始终会导致校验和的相同差异
那些字节具有不同的权重,并找到一个字节位置将校验和增加多少的模式,以得到上述公式中的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

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

评论


有趣!谢谢你,我现在尝试这些

–astralmaster
2014年5月27日下午16:20

是的,确实,索引字节确实参与了计算校验和。检查我对原始帖子的最后修改

–astralmaster
2014年5月30日19:48

#3 楼

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

然后,1111111111111111111111111112111111111111111111111111111111之间的差异为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


我们已经从有效负载b2911111111111111111111111111111之间的校验和之差得知11111111111111111111111111112为0x21。从有效载荷b2811111111111111111111111111121之间校验和的差中我们还知道11111111111111111111111111111为0x441。让我们假设系数以相反的顺序遍历时乘以0x21,即从b29(0x21)开始,然后从b28(0x441)开始,...在某些时候会出现16位整数的溢出,但这确实没关系,我们只需要最低的16位。

现在我们有了所有系数b1 ... b29的概念。我们只需要找出常数c即可。好吧,这很容易,它是正确的校验和与c = 0计算的校验和之间的差。对于11111111111111111111111111111c == 0的校验和为0x5ded,因此,请从0x3540(正确的校验和)中减去所计算的校验和0x5ded以获得正确的常数c。因此,c的值为0x3540 - 0x5ded = -0x28ad。要为所有给定的示例尝试此解决方案(这些beta b1 ... b29和此常数c),我编写了一个简单的Common Lisp程序,下面是代码: br />
(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*))


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

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


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

假设校验和仍然是线性函数,则有两种可能性:


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

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

评论


感谢您的时间和帮助!我现在正在检查这些,正如您已经正确猜到的那样,该校验和中有一个错字,正确的是4DC1而不是C10E。我将这种算法应用于各种字节序列,并在不久后回复

–astralmaster
2014年5月30日19:11