深入理解CRC
0x01 引言
第一次逆向碰到CRC的算法，一开始看见不知道是在干嘛 还好有大佬指点 知道这是CRC 此处@这是大佬的博客 而且 我看了网上讲关于CRC的帖子 对镜像算法的实现都是引入逆转比特函数 显然不像我这道逆向题的代码 
0x02 算法分析
本文不是面向CRC小白，你需要先了解CRC基本信息，可以看这些帖子：
如果你已经理解了CRC的工作原理，那么你应该知道CRC的计算方法：直接计算法，驱动表法，镜像驱动表(还有两种变体 不重要)
那么你也理解CRC的驱动表法的工作原理：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<stdio.h>
#define LUT_LENGTH 8
#define CRC_LENGTH 8
#define CRC_POLY 0x04C11DB7
int main(){
int CRC_TBALE[1<<LUT_LENGTH];
for(int index=0;index<(1 << LUT_LENGTH);index++){
int temp = 0;
for(int j=LUT_LENGTH;j>0;j--){
if((index >> (j-1) ^ temp >> (CRC_LENGTH-1)) & 0x1){ //判断首位是不是1
temp = (temp << 1) ^ CRC_POLY; //是 左移 异或
}
else
temp = temp << 1; // 不是 直接左移
}
CRC_TBALE[i] = temp;
}
for(int i=0;i<(1 << LUT_LENGTH);i++){
printf("%x\n",CRC_TBALE[i]);
}
}
通过这种方法生成的表，叫做直接查询表。通过镜像算法生成的表，叫做‘正规查询表’，也是网上查到的表。
借用大佬的图，解释这两个图的关系： 
可以看出要想得到正规查询表 我们需要将输入镜像，然后将表的index镜像，然后将表的内容逆转 网上的镜像算法be like：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//“颠倒的直驱表法”的程序：
//同样要先做一个颠倒比特的子程序：
unsigned long int Reflect(unsigned long int ref, char ch)
{
unsigned long int value=0;
// 交换bit0和bit7，bit1和bit6，类推
for(int i = 1; i < (ch + 1); i++)
{
if(ref & 1)
value |= 1 << (ch - i);
ref >>= 1;
}
return value;
}
unsigned long int crc32_table[256];
unsigned long int ulPolynomial = 0x04c11db7;
unsigned long int crc,temp;
for(int i = 0; i <= 0xFF; i++) // 生成CRC32“正规查询表”
{
temp=Reflect(i, 8);
crc32_table[i]= temp<< 24;
for (int j = 0; j < 8; j++)
{
unsigned long int t1,t2;
unsigned long int flag=crc32_table[i]&0x80000000;
t1=(crc32_table[i] << 1);
if(flag==0)
t2=0;
else
t2=ulPolynomial;
crc32_table[i] =t1^t2 ;
}
crc=crc32_table[i];
crc32_table[i] = Reflect(crc32_table[i], 32);
}
可以看到该实现算法引入逆转bit函数，和我们逆的这个不能说差别很大，只能说一点都不像。
那我们看这道逆向题的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<stdio.h>
int main(){
unsigned int *puVar1;
unsigned long uVar2;
long lVar3;
unsigned int uVar4;
unsigned int arr[256];
unsigned int DAT_0079ac68 = 0xedb88320;
puVar1 = arr;
for (uVar2 = 0;
uVar4 = -((unsigned int)uVar2 & 1) & DAT_0079ac68 ^ (unsigned int)((uVar2 & 0xffffff) >> 1),
uVar4 = -(uVar4 & 1) & DAT_0079ac68 ^ uVar4 >> 1,
uVar4 = -(uVar4 & 1) & DAT_0079ac68 ^ uVar4 >> 1,
uVar4 = -(uVar4 & 1) & DAT_0079ac68 ^ uVar4 >> 1,
uVar4 = -(uVar4 & 1) & DAT_0079ac68 ^ uVar4 >> 1,
uVar4 = -(uVar4 & 1) & DAT_0079ac68 ^ uVar4 >> 1,
uVar4 = -(uVar4 & 1) & DAT_0079ac68 ^ uVar4 >> 1,
*puVar1 = -(uVar4 & 1) & DAT_0079ac68 ^ uVar4 >> 1
, uVar2 != 0xff; uVar2 = uVar2 + 1) {
puVar1 = puVar1 + 1;
}
for(int i=0;i<256;i++){
printf("%d %x\n",i,arr[i]);
}
}
该算法，首先将POLY逆转（0x04c11db7 -> 0xedb88320），但是没有明显的index逆转和表内容逆转 初步推测该算法直接实现了镜像算法，所以没有逆转比特的操作
下面我们来拆解一下这个算法：
1
2
3
for(uVar2=0;....;uVar2!=0xff;uVar=uVar + 1){
//整个外层循环控制index的范围
}
接着看内存循环，如果在for循环里看这段代码会很奇怪，但是如果你还记得驱动表的生成算法里的内层for循环的话，那我相信这也不难理解 大概率内层for循环被优化掉了，ghidr反编译，直接内联到外层for循环了（这里吐槽ida，ida识别出来真的灾难现场，代码那叫一个惨不忍睹。。。）
1
2
3
4
5
6
7
8
9
10
11
uVar4 = -((unsigned int)uVar2 & 1) & DAT_0079ac68 ^ (unsigned int)((uVar2 & 0xffffff) >> 1),
uVar4 = -(uVar4 & 1) & DAT_0079ac68 ^ uVar4 >> 1,
uVar4 = -(uVar4 & 1) & DAT_0079ac68 ^ uVar4 >> 1,
uVar4 = -(uVar4 & 1) & DAT_0079ac68 ^ uVar4 >> 1,
uVar4 = -(uVar4 & 1) & DAT_0079ac68 ^ uVar4 >> 1,
uVar4 = -(uVar4 & 1) & DAT_0079ac68 ^ uVar4 >> 1,
uVar4 = -(uVar4 & 1) & DAT_0079ac68 ^ uVar4 >> 1,
*puVar1 = -(uVar4 & 1) & DAT_0079ac68 ^ uVar4 >> 1
//这段我也是找了好久 没有找到相关直接镜像算法的例子 那只好我自己分析了
// 对比驱动表的算法还是有章可循的
先回忆一下驱动表的算法
1
2
3
4
5
6
7
for(int j=LUT_LENGTH;j>0;j--){
if((index >> (j-1) ^ temp >> (CRC_LENGTH-1)) & 0x1){ //判断首位是不是1
temp = (temp << 1) ^ CRC_POLY; //是 左移 异或
}
else
temp = temp << 1; // 不是 直接左移
}
镜像算法的原理是相似的，temp根据高位到低位的顺序一步步生成，镜像算法那就根据temp根据地位到高位的顺序生成呗。 下面解释内层循环第一层
1
2
3
4
5
6
7
8
9
10
11
uVar4 = -((unsigned int)uVar2 & 1) & DAT_0079ac68 ^ (unsigned int)((uVar2 & 0xffffff) >> 1),
// -((unsigned int)uVar2 & 1) 用来判断uVar2(相当于驱动表算法的index)的最低位是否为1（想不通的可以手动模拟一下）
// -((unsigned int)uVar2 & 1) & DAT_0079ac68
// -((unsigned int)uVar2 & 1) == 0 => -((unsigned int)uVar2 & 1) & DAT_0079ac68 = 0
// -((unsigned int)uVar2 & 1) == 1 => -((unsigned int)uVar2 & 1) & DAT_0079ac68 = DAT_0079ac68
// -((unsigned int)uVar2 & 1) & DAT_0079ac68 ^ (unsigned int)((uVar2 & 0xffffff) >> 1) 相当于 temp = (temp << 1) ^ CRC_POLY的镜像
uVar4 = -(uVar4 & 1) & DAT_0079ac68 ^ uVar4 >> 1
// -(uVar4 & 1) 同理
// -(uVar4 & 1) & DAT_0079ac68 ^ uVar4 >> 1 同理
// 到这里可以发现 uVar4 就是驱动表算法里的temp
// -(uVar4 & 1) & DAT_0079ac68 这个位运算我只能说妙啊 省一个if
0x03 算法总结
总结一下 镜像算法是如何实现表index镜像和表内容镜像的： 表index镜像和表内容镜像是一个东西，因为表的内容是由index产生的，index处理方式不同，表的内容就会不同 镜像算法先处理index低位，产生表内容的低位一次类推 写表操作通过*puVar1和puVar1 = puVar1 + 1递推往后写（举个例子 当前index是1，按驱动表法看就是80h，但是写的就是table[1],emmm,you know m3）
0x4 未完待续
这里其实也是CRC的一部分，并且是镜像版的”DIRECT TABLE ALGORITHM“，就是在驱动表上的数学优化 算法步骤： Shift the register left by one byte, reading in a new message byte. XOR the top byte just rotated out of the register with the next message byte to yield an index into the table ([0,255]). XOR the table value into the register. Goto 1 iff more augmented message bytes. 具体原理可以看我上面推荐第二篇，讲的很清楚
这里可以看到CRC对整个代码段做了计算，最后的取反也可以理解^0xFFFFFFFF,这是CRC32模型参数（XorOut=FFFFFFFF，表示还需要将结果值与0xffffffff进行XOR）
算法分析完毕！