首页
论坛
课程
招聘
[原创]CRC32 算法分析、逆向(附源码)
2010-9-8 01:10 29487

[原创]CRC32 算法分析、逆向(附源码)

2010-9-8 01:10
29487
CRC32 算法分析、逆向(附源码)

前几天发了个工具CRC32编辑器:
http://bbs.pediy.com/showthread.php?t=119765&highlight=
有些朋友不知道什么用途
1,让自己的好看点(自我安慰)
2,遇到校验的可能有用,自己写程序的时候也能用用

现在略微整理下算法和分析过程,拿出来共享和交流。

下面是我的全分析过程.

' ******************** CRC验证 ********************
'返回验证码                                二进制 串                                               
Public Function CRC32(ByRef bArrayIn() As Byte, ByVal lLen As Long) As Long
    Dim lCurPos As Long
    Dim lTemp As Long
    Dim crcTable(0 To 255) As Long
    Dim i As Long, x As Long, crc As Long
    Const Limit = &HEDB88320
   
    For i = 0 To 255
        crc = i
        For x = 0 To 7
            If crc And 1 Then
                crc = (((crc And &HFFFFFFFE) \ 2) And &H7FFFFFFF) Xor Limit
            Else
                crc = ((crc And &HFFFFFFFE) \ 2) And &H7FFFFFFF
            End If
        Next x
        crcTable(i) = crc
    Next i
    '以上初始化 出来一个表(是固定的)
    If lLen < 0 Then Exit Function
    lTemp = &HFFFFFFFF

    For lCurPos = 0 To lLen
        lTemp = (((lTemp And &HFFFFFF00) \ &H100) And &HFFFFFF) Xor (crcTable((lTemp And 255) Xor bArrayIn(lCurPos)))
            '前三位*3 xor 表(第四位*1 xor 新字节*1)*4
    Next lCurPos
   
    '取反输出结果 -->结果取其十六进制标记就是我们常见的CRC32了
    CRC32 = lTemp Xor &HFFFFFFFF
End Function

      

   关键部分就再循环,他做了什么呢
它每次加入一个新字节,和先前计算的结果4字节进行计算

先前由(高到底):   A1 A2 A3 A4
新加入的字节:              B(n)
计算结果    :     C1 C2 C3 C4

计算方式:(注意 ^ 为 异或计算)

┌→A1 A2 A3 A4 →A4 ^  B(n)
│   ↘ ↘ ↘      ↘ ↙
│  00 A1 A2 A3      X  
│  ^  ^  ^  ^      ↓(查表)
│  T1 T2 T3 T4 ←←T(X)         
│  ↓ ↓ ↓ ↓
└─T1 C2 C4 C4                 
    ↓ ↓ ↓ ↓(最后一次完成后取反)
    R1 R2 R3 R4         ;CRC32 结果

新值C经过一次计算后,他的最高位C1没变,是查表的最高位T1
那么这个表T1的值是不是唯一的呢,我们把表打印出来(见文章末尾),看一下
可喜的是,最高位(00-FF)都是一对一得关系,从00到FF没有重复,那么逆向推导就成为可能了

现在我们知道了文件得CRC32,
  那么就知道最后一次循环后得值(取反可得),这个值得最高位,就是它最后一次查表的值
  由于这个表和查表是一一对应关系,我们可以知道两点
1.  T1 可以得到 T(X) 也就是 T1 T2 T3 T4
2.  T1 可以得到 X    也就是 A4 ^ B(n)

由 T(X) 和 C 我们可以得到 A1 A2 A3 ,这是倒数第一次循环计算的高位3字节,
用同样的方法我们可以得到
   倒数第二次循环计算的高位2字节
   倒数第三次循环计算的高位1字节
   倒数第四次循环计算的高位0字节 (也就是说4次这样的循环计算后,再前面的结果就是任意的了)

一次循环,会模糊掉一个字节位的crc32校验,4次循环会模糊掉四字节的CRC32校验

这样只要指定最后4个字节,我们就可以达到修改出任意CRC32

现在,我们要把一个CRC校验文件添加4字节
CE037B28 转换为 09635B62  
   (这也是我最初的实验,很痛苦;计算试了几次没成功,从算法上看又可行,因为自己一没注意就计算错了)

CE037B28 -> 09635B62  ;目的CRC
'取反
31FC84D7 -> F69CA49D
            ↓↓↓↓
            ↓9CA49D
            F6B9265B   D5 {表} F6查表→D5(X的值)
            ↓↓↓↓   ↓        →F6B9265B(T的值)
            F62582C6   ↓
去掉最高位  F6         ↓
             ↙↙↙  ↙  ; 向高位移动
            2582C6[*D5]         ; N1 xor old1 =x1
            
2582C6[^D5];
   82C6 [^D5]
25 6FD2 A0      B2   {表}
   
25 ED14 [^D5^A0]

ED14 [^D5^A0] [^B2]

EDB88320      =80     {表}

  AC[^D5^A0^83][^A5^20][^6D]

  AC   BC       F9     40      2B   {表}
[^D5^A0^83^BC][^B2^20^F9][^80^40][^2B]

31             FC         84      D7      ;与原来的31FC84D7再次异或
7B             97         44      FC      ;这是最后添加的4个字节

为什么到最后要这样再异或一次呢,
    因为A^B=C → A^C=B → B^C=A
原来CRC取反      A1 A2 A3 A4     A
修改4字节CRC取反 B1 B2 B3 B4     B
目的CRC取反      C1 C2 C3 C4     C   
    要的到A^B=C  我们已知A,C 异或一下就得到我们需要的B了,虽然还需要经过一段运算

认真的读者会发现,CRC32逆运算更容易得到想要的CRC的值,而正运算几乎是不可能的,
因为我们每加一新数据时候,只能确定CRC4字节中的1字节,而其他字节都会有影响的。
=========================================

问题二:
如何在文件中任意部分覆盖4字节得到想要的CRC值呢,假定一个文件长度为len,覆盖位置offset,文件最后CRC结果为d(取反结果为D)

首先我们想,如果覆盖掉最后4字节的话,
  我们只需要先计算文件前面 len-4 字节CRC,再添加4字节就行了,这个很简单。

如果在文件中央,
我们要使文件最后的CRC满足条件D,而我们可以控制的地方只有(offset~offset+3)4字节区域,
分成3部分:
前部分,覆盖部分(4字节),后面部分

    前部分:CRC可以计算出来
    后面部分,如果知道最终的目标CRC,又知道它每一次计算的B(n),
那么倒数任何次的A1 A2 A3 A4 ,T1 T2 T3 T4,X,C1 C2 C3 C4都可以计算出来的,
计算方法和我们上面分析的 X 是不可以确定的,用他 X ^  B(n) 就得出A4了

    那么我们 覆盖掉这4字节的任务就是这样了,后面部分要达到CRC结果为D的,那到覆盖部分的尾端时候需要的为C,
    而前面覆盖部分可以直接计算得到结果A,覆盖部分只要把A调整为C(而不是直接调整为D)

思路好了,我附上原代码吧,知道大家都喜欢这个

2022 KCTF春季赛【最佳人气奖】火热评选中!快来投票吧~

上传的附件:
收藏
点赞1
打赏
分享
最新回复 (16)
雪    币: 2081
活跃值: 活跃值 (183)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
exile 活跃值 1 2010-9-8 09:04
2
0
顶 不过现在都不太用CRC了。。
雪    币: 213
活跃值: 活跃值 (11)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
永垂不朽 活跃值 2010-9-22 08:56
3
0
这个windows api有现成的函数可以直接调用,效率很高。不用自己编写。

自己编写的往往没人家效率高,而且还容易有错误和漏洞。
雪    币: 96
活跃值: 活跃值 (166)
能力值: ( LV13,RANK:357 )
在线值:
发帖
回帖
粉丝
瞧红尘 活跃值 2 2010-9-30 20:38
4
0
我这个只是逆向的.....
雪    币: 201
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
doctorly 活跃值 2010-11-23 08:58
5
0
TMD 正好需要逆向算法,谢谢~~~
雪    币: 106
活跃值: 活跃值 (17)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
vitha 活跃值 2012-1-9 14:31
6
0
谢谢分享,正在研究这个东西呢。正是时候,找到了。
雪    币: 16225
活跃值: 活跃值 (745)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
atompure 活跃值 2012-3-15 18:09
7
0
Thank you very much
雪    币: 130
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
hogan 活跃值 2012-3-22 17:01
8
0
谢谢分享,我最近也在学习这个知识!
雪    币: 7
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
ysclwjxv 活跃值 2012-3-29 11:08
9
0
这个对我很有帮助,感谢分享哦。
雪    币: 141
活跃值: 活跃值 (13)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
jinxuelong 活跃值 2012-4-1 07:25
10
0
谢谢分享,我最近也在学习这个知识!
雪    币: 122
活跃值: 活跃值 (16)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
butian 活跃值 2012-4-1 07:40
11
0
前来学习个……
雪    币: 201
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
XinDOS 活跃值 2012-4-6 11:45
12
0
感谢分享,下来学习
雪    币: 124
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
gecyilin 活跃值 2012-11-10 01:58
13
0
有利学习,谢了。
雪    币: 7502
活跃值: 活跃值 (3489)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
zhczf 活跃值 2012-11-15 18:52
14
0
来学习一下经验啊
雪    币: 96
活跃值: 活跃值 (166)
能力值: ( LV13,RANK:357 )
在线值:
发帖
回帖
粉丝
瞧红尘 活跃值 2 2020-5-14 14:17
15
0
收到邮件问c++源码的,以前刚好写过.

#include <stdio.h>
#include <string.h>


#pragma pack(push, 1) 
struct t_CRCdata
{
       unsigned char Num1;
       unsigned char Num2;
       unsigned char Num3;
       unsigned char Num4;
};
#pragma pack(pop)

//CRC32编辑
//输入
//长度
//偏移:         <0 表示末尾添加,  其他值表示在某位偏移位置覆盖
//自己要的crc值
//填充的4字节值,把这个值覆盖到偏移位置就可以实现你要的crc
int CRC32Edit(unsigned char *byt,int bytLen,int lOffset, int lcrc,int &retlCRC)
{

    int crc32Result = 0;
       int i,j,dwCrc,iLookup,CRC32Edit2 = 0;
    int k;
       t_CRCdata cr1;
    //常数
       #define NumNum0                         0
       #define NumNum1                         0x1
       #define NumNum2                         0x2
       #define NumNum8                         0x8
       #define Num255                          0xFF
       #define Num256                          0x100
       #define Num16777215                     0xFFFFFF
       #define dwPolynomial                    0xEDB88320
       #define Num2147483647                   0x7FFFFFFF
       #define NumNegative1                    0xFFFFFFFF
       #define NumNegative2                    0xFFFFFFFE
       #define NumNegative256                  0xFFFFFF00

    //CRC32表
    int crc32Table[0x100];
       t_CRCdata CRCdata[256];
    
    //初始化CRC32表*****************************
    for(i = NumNum0 ; i <= Num255;i++)
       {
        dwCrc = i;
        for(j = NumNum8; j >= NumNum1; j+=NumNegative1)
               {
            if (dwCrc & NumNum1)
                       {
                               dwCrc = ((dwCrc & NumNegative2) / NumNum2) & Num2147483647;
                dwCrc = dwCrc ^ dwPolynomial;
                       }
            else{
                dwCrc = ((dwCrc & NumNegative2) / NumNum2) & Num2147483647;
                       }
        }
        crc32Table[i] = dwCrc;
        memcpy (&CRCdata[i], &crc32Table[i],4);
       }
    crc32Result = NumNegative1;//  '初始化
       if( lOffset < 0)
       {
               lOffset = bytLen;
       }else{
        if(lOffset > bytLen -1)
               {
            lOffset = bytLen;
        }
       }        
    if( lOffset > 0)
       {
        //'计算CRC32码*******************************
        for(i = 0; i<= lOffset - 1; i++){
            iLookup = (crc32Result & Num255) ^ byt[i] ;// '第四位 xor 新字节
            crc32Result = ((crc32Result & NumNegative256) / Num256) & Num16777215;// '前三位
            crc32Result = crc32Result ^ crc32Table[iLookup];// '前三位*3 xor 表(第四位*1 xor 新字节*1)*4
        }
       }      
               CRC32Edit2 = crc32Result ^ 0xffffffff;//    '计算前面的crc值,返回是什么样的       
//     //'计算后面的
               k = bytLen - 1 - lOffset - 3;
               if(k > 0 )
               {//   '后面是否有数据
                       int k2 = k;
                       k = lcrc ^ 0xffffffff;
               memcpy (&cr1, &k,4);
//         //'反向CRC计算
                       for(int j = k2 - 1; j>=0; j--)
                       {
                               for(int i = 0; i<=255; i++)
                               {
                                       if(cr1.Num4 == CRCdata[i].Num4)
                                       {
                                               break;
                                       }
                               }
                               cr1.Num4 = cr1.Num3 ^ CRCdata[i].Num3;
                               cr1.Num3 = cr1.Num2 ^ CRCdata[i].Num2;
                               cr1.Num2 = cr1.Num1 ^ CRCdata[i].Num1;
                               cr1.Num1 = i ^ byt[j + lOffset + 4];
                       }
               }
               else
               {
               k =  lcrc ^ 0xffffffff;
                       memcpy(&cr1, &k,4);
               }

//     //'要得出文件CRC值=lCRC32  之前部分的CRC必须满足的条件:cr1的值
//     //'计算
               for (j = 0; j <=3; j++){
                       for (int i = 0; i <=255; i++)
                       {
                               if(cr1.Num4 == CRCdata[i].Num4)
                                       break;
                       } 
                       cr1.Num4 = cr1.Num3 ^ CRCdata[i].Num3;
                       cr1.Num3 = cr1.Num2 ^ CRCdata[i].Num2;
                       cr1.Num2 = cr1.Num1 ^ CRCdata[i].Num1;
                       cr1.Num1 = i;
               } 
               memcpy( &k, &cr1,4);
               k = k ^ crc32Result;
               retlCRC = k; //'计算出来的是4字节覆盖的值,不是crc
       return CRC32Edit2;
}
雪    币: 96
活跃值: 活跃值 (166)
能力值: ( LV13,RANK:357 )
在线值:
发帖
回帖
粉丝
瞧红尘 活跃值 2 2020-5-14 14:34
16
0
int CRC32(unsigned char *byt,int bytLen)
{
       int lcrc = 0 ;
#define  Limit        0xEDB88320        
       bytLen--;
       int i,x,crc;
       int crcTable[256];
       for(i=0;i<=255;i++)
       {
               for(crc=i,x=0;x<8;x++)
               {
                       if(crc & 1)
                               crc=(((crc & 0xFFFFFFFE) / 2) & 0x7FFFFFFF) ^ Limit;
                       else 
                               crc=(crc & 0xFFFFFFFE) / 2;
               }
               crcTable[i] = crc;
       }
       if(bytLen<0)return 0;
       unsigned int crcResult = (~lcrc);
       for(i = 0;i<= bytLen;i++)
       {
               crcResult=(crcResult >> 8 ^ crcTable[((crcResult & 255) ^ byt[i]) & 255]);
       }
       return ~crcResult;
}

void main()
{

       unsigned char p1[] = {0x00,0x2C,0x00,0x01,0x45,0x36,0x30,0x0C,0x68,0x65,0x6C,0x6C,0x5F,0x64,0x65,0x66,0x61,0x75,0x6C,0x74,0x0C,0x68,0x65,0x6C,0x6C,0x5F,0x64,0x65,0x66,0x61,0x75,0x6C,
0x74,0x0C,0x68,0x65,0x6C,0x6C,0x5F,0x64,0x65,0x66,0x61,0x75,0x6C,0x74,0x00,0x20,0,0,0,0}; 

       int crcout;
       int CRC_I_WANT = 0;

       CRC32Edit(p1,48,-1,CRC_I_WANT,crcout);        //这里的填充位置是-1,末尾填充,  也就是  p[48]的位置填充

       printf("填充值为 %08X\n",crcout);
       
       memcpy(p1 + 48, &crcout,4); 
 
       int crc = CRC32(p1,48 + 4);

       printf("CRC的值 = %08X \n",crc);
}
雪    币: 216
活跃值: 活跃值 (693)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
gaoweb 活跃值 2020-5-14 17:14
17
0
111
游客
登录 | 注册 方可回帖
返回