首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 峰会 看雪商城 证书查询
  1. 社区
  2. 密码应用
    3. 发新帖
[原创]CRC32 算法分析、逆向（附源码）
发表于: 2010-9-8 01:10 33315

[原创]CRC32 算法分析、逆向（附源码）

瞧红尘 活跃值
2
2010-9-8 01:10
33315

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）

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


[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课

上传的附件：
收藏
免费 ・8
支持
分享
最新回复 (16)
exile
雪    币： 2105
活跃值： (424)
能力值： ( LV4，RANK：50 )
在线值：
发帖
回帖
粉丝
私信
2 楼
顶　不过现在都不太用CRC了。。
2010-9-8 09:04
0
永垂不朽
雪    币： 213
活跃值： (11)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
3 楼
这个windows api有现成的函数可以直接调用，效率很高。不用自己编写。

自己编写的往往没人家效率高，而且还容易有错误和漏洞。
2010-9-22 08:56
0
瞧红尘
雪    币： 166
活跃值： (392)
能力值： ( LV13，RANK：357 )
在线值：
发帖
回帖
粉丝
私信
4 楼
我这个只是逆向的.....
2010-9-30 20:38
0
doctorly
雪    币： 201
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
5 楼
TMD 正好需要逆向算法，谢谢～～～
2010-11-23 08:58
0
vitha
雪    币： 106
活跃值： (22)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
6 楼
谢谢分享，正在研究这个东西呢。正是时候，找到了。
2012-1-9 14:31
0
atompure
雪    币： 20897
活跃值： (4095)
能力值： ( LV3，RANK：20 )
在线值：
发帖
回帖
粉丝
私信
7 楼
Thank you very much
2012-3-15 18:09
0
hogan
雪    币： 130
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
8 楼
谢谢分享，我最近也在学习这个知识！
2012-3-22 17:01
0
ysclwjxv
雪    币： 7
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
9 楼
这个对我很有帮助，感谢分享哦。
2012-3-29 11:08
0
jinxuelong
雪    币： 141
活跃值： (13)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
10 楼
谢谢分享，我最近也在学习这个知识！
2012-4-1 07:25
0
butian
雪    币： 122
活跃值： (16)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
11 楼
前来学习个……
2012-4-1 07:40
0
XinDOS
雪    币： 201
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
12 楼
感谢分享，下来学习
2012-4-6 11:45
0
gecyilin
雪    币： 124
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
13 楼
有利学习，谢了。
2012-11-10 01:58
0
zhczf
雪    币： 11079
活跃值： (17607)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
14 楼
来学习一下经验啊
2012-11-15 18:52
0
瞧红尘
雪    币： 166
活跃值： (392)
能力值： ( LV13，RANK：357 )
在线值：
发帖
回帖
粉丝
私信
15 楼
收到邮件问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;
}
2020-5-14 14:17
0
瞧红尘
雪    币： 166
活跃值： (392)
能力值： ( LV13，RANK：357 )
在线值：
发帖
回帖
粉丝
私信
16 楼
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);
}
2020-5-14 14:34
0
gaoweb
雪    币： 6694
活跃值： (3514)
能力值： (RANK：10 )
在线值：
发帖
回帖
粉丝
私信
17 楼
111
2020-5-14 17:14
0
游客
登录 | 注册 方可回帖
回帖 表情 雪币赚取及消费
高级回复
返回
//