算法逆向2——CRC32识别

前言

本文如果出现错误，欢迎指出，感激不尽！

本文中的所有程序请在虚拟机中运行。

很早就学过CRC，但当时只是停留在模2除法运算，觉得CRC不过如此。当笔者第一次接触CRC数据表时，顿时感觉到不可思议，这是什么东西？不是模2除法运算吗？为什么会变成查表运算？于是笔者开始了深入研究，然后笔者就默默地打开淘宝，点开购物车，取消订单《数学之美》。

[size=18.6667px]预计用时：1.5h

参考资料：

《加密与解密实战全攻略》

https://www.cnblogs.com/dacainiao/p/5565046.html

http://blog.sina.com.cn/s/blog_715691110102wqbr.html

http://blog.csdn.net/watterwu/article/details/54615296

http://www.xjtudll.cn/Exp/273/

1. CRC算法介绍

CRC，即“循环冗余校验码”，是对数据的校验值，用于校验数据完整性。

1.1. 基本概念

CRC检验原理实际上就是在一个p位二进制数据序列之后附加一个r位二进制检验码(序列)，从而构成一个总长为n＝p＋r位的二进制序列；附加在数据序列之后的这个检验码与数据序列的内容之间存在着某种特定的关系。如果因干扰等原因使p中的某一位或某些位发生错误，这种特定关系就会被破坏。因此，通过检查这一关系，就可以实现对数据正确性的检验。

采用的运算方式是多项式模2运行：实际上是按位异或，也就是不考虑进位、借位的二进制加减运算。如：10011011 + 11001010 = 01010001。

生成多项式（generator polynomial）：当进行CRC检验时，需要事先约定一个除数，即生成多项式，一般记作G（x）。生成多项式比校验码多一位。生成多项式的最高位与最低位必须是1。虽然生成多项式可任意指定，但还是有一些常用的CRC码的生成多项式：

CRC8=X8+X5+X4+1

CRC16=X16+X15+X5+1

CRC32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1  

每一个生成多项式都可以与一个代码相对应，如上式中CRC32的对应码：

1 0000 0100 1100 0001 0001 1101 1011 0111

=0x1 04C1 1DB7

CRC32另一个常用的生成多项式对应码：

1 1110 1101 1011 1000 1000 0011 0010 0000

=0x1 EDB8 8320

1.2. CRC的计算与校验

设需要发送的信息为M = 0011 1110，使用CRC4，即多项式对应的代码为P = 10011，R＝4。在M后加4个0，然后对P做模2除法运算，得余数r(x)对应的代码：1110。故实际需要发送的数据是0011 1110 1110。

实际计算过程：

当接收方收到数据后，用收到的数据对P（事先约定的）进行模2除法，若余数为0，则认为数据传输无差错；若余数不为0，则认为数据传输出现了错误，由于不知道错误发生在什么地方，因而不能进行自动纠正，一般的做法是丢弃接收的数据。

1.3. CRC数据表1.3.1. CRC数据表的由来——由模2除法到异或

我们继续使用上一节提到的数据，在上一节中我们使用了模2除法的方式计算出CRC的值，现在我们将其中每一位的计算过程展开，得到下列的8次计算过程：

可以看到由第i步到第i+1步，进行计算的过程就是异或的过程，在第i步中，当数据最高位是0，就异或0x0 ；当数据最高位是1，就异或 多项式对应码左移相应位的值 。

那么上述计算过程就是8次异或计算的过程；

M^B^C^D^E^F^G^H^I，其中M=0011 1110 0000，我们将其分解为M1=0011 0000 0000和M2=1110 0000，M=M1^M2。根据异或运算的结合律，我们可以将异或过程分成两部分分别计算：（（M1^A^B^C^D）^M2）^E^F^G^H=（S1^M2）^E^F^G^H=S2^E^F^G^H:

我们先进行M1^A^B^C^D的计算,在计算时我们先忽略后面的0:

假设b=10011，如图A=b3=0 与运算 b =0,

                               B=b2=0 与运算 b =0，

                               C=b1=b 左移 1=100110,

                               D=b0=b 左移 0=100110。

可知A、B、C、D与M1的关系：

所以A、B、C、D的值只取决于M1和b，则M1^A^B^C^D的值只取决于M1和b，那么在已知生成多项式b的情况下，我们可以遍历M1生成一个数据表，对于每一个M1不需要计算，直接查表即可计算出M1^A^B^C^D。

如图，M1的有效值是0011=0x3，查表得到M1^A^B^C^D=0x5，继续计算S1^M2：

计算出S2=1101 0000，接下来计算S2^E^F^G^H又可以使用查表法.S2有效值是0xB，对应值是0xE=1110，这就是最终的CRC校验码。

在本次实例中，按4bit有效数据进行分解，分解出M1和M2，所以生成的数据表一共有24=16项，如果按照8bit进行分解，则得到的数据项数是28=256，CRC32中就是按照8bit进行分解的。

1.3.2. CRC数据表的生成

我们再次回顾M1^A^B^C^D的计算过程，并扩展出b4的计算过程：

可以发现，若M1最高位是0，bi最高位也是0，计算后的结果最高位是0；若M1最高位是1，bi最高位也是1，计算后的结果最高位还是0。M1和bi的最高位对计算的结果的最高位没有影响，那么我们就可以忽略CRC4多项式对应码从10011简化为0011。

假设我们有位数为4bit的register，将M1存入寄存器，我们每次会先检查register的最高位是否为1并将register左移一位(M1最高位对计算的结果的最高位没有影响)，如果为1，则将生成多项式（0011）与register进行异或操作（这每一次操作实际上就是一次除法）。将register左移一位的同时，将我们的数据拿一bit出来放到register的最低位。

当上面那个算法迭代一个字节后(8bits)，我们就能计算出M1^A^B^C^D。遍历M1，就能得到CRC数据表。

CRC32数据表生成源码：

int make_crc32_table() { unsigned c; int i = 0; int bit = 0; for(i = 0; i < 256; i++) { c = (unsigned)i; for(bit = 0; bit < 8; bit++)         { if(c&1) { c = (c >> 1)^(0xEDB88320); //这是生成常数，如果动态生成这张CRC32表，则必定会有这个数 } else { c = c >> 1; } }crc32_table = c; } } //这个算法，会产生包含有256个元素的CRC32表

2. CRC32算法实现

（1）取上次计算出的CRC校验码最后一个字节与新的要校验的字节进行XOR 运算，生成新的索引；CRC校验码的初始值为0xFFFFFFFF;
（2）将上次计算出的CRC校验码右移一个字节，生成临时校验码；

（3）用新的索引在预先生成码表中进行索引，获取对应的值（称为余式）；
（4）用临时校验码和余式进行XOR 运算，生成新的校验码；
（5）如果要校验的数据已经处理完，则第（4）步的结果XOR 0xFFFFFFFF就是最终的CRC校验码。如果还有数据要进行处理，则再转到第（1）步运行。

源码：

unsigned CRC32(char *c,int len){unsigned i,j;unsigned crc_i=0xFFFFFFFF;for(i=0;c!='';i++){j=(crc_i&0xFF) ^ (int)c;crc_i=(crc_i>>8)^crc32_table[j%256];}crc_i=crc_i^0xFFFFFFFF;return crc_i;}

3. CRC32程序算法逆向

终于步入正题了。。。。

3.1. 定位关键算法

随便输入name和code，弹出错误提示：

看来这里就是关键位置了，这里处于sub_4042A8函数内，sub_4042A8就是我们我们要逆向的关键算法。

sub_4042A8的流程还是比较清晰，但是看函数调用关系，很复杂，这就注定我们不能跟进每个call，详细分析每个call了，要尽量猜测call函数的含义。

①开辟存放字符串的空间

程序首先会调用GetWindowTextLengthA获取Name字符串的长度，在这期间调用的sub_402DE8，sub_402ED8都比较复杂，不需要详细分析，使用OD查看运行效果就可以发现，sub_402DE8申请了一内存，sub_402ED8向内存里写入Name字符串的长度的空格字符，空格字符来源于dword_4043EC。所以这里相当于开辟了存放字符串的空间：

首先获取Name字符串，并判断长度是否小于5，如果小于5则进入错误处理流程；之后在Name字符串前添加字符串“DiKeN”生成新的字符串，例如，输入的name是ichunqiu，则生成的字符串是DiKeNichunqiu；之后就对新的字符串进行CRC32计算：

③CRC32计算

计算的过程很清晰，和第二章中的代码几乎吻合，就不赘述了，可以对照前面的源码看

code字符串的预处理方式与Name字符串相同，先开辟空间，然后拼接字符串，在code字符串前添加字符‘0’；在sub_404224中用新的算法处理新生成的字符

unsigned calc_code(char *c,int len){unsigned i,j=0;for(i=0;c!='';i++){j=j*2*5;j=j+(int)c-0x30;}printf("%x,n",j);return j;}

⑥比较

没什么说的，就是比较Name的CRC32值和输入的值是否相同，如果相同就通过注册：

注册机完整源码：

include <iostream>#include<string.h>#include <stdlib.h>#include <stdio.h>using namespace std;unsigned crc32_table[256]; int make_crc32_table() { unsigned c; int i = 0; int bit = 0; for(i = 0; i < 256; i++) { c = (unsigned)i; for(bit = 0; bit < 8; bit++) { if(c&1) { c = (c >> 1)^(0xEDB88320); //这是生成常数，如果动态生成这张CRC32表，则必定会有这个数 } else { c = c >> 1; } } crc32_table = c; } } //这个算法，会产生包含有256个元素的CRC32表 //CRC的关键值计算算法：unsigned CRC32(char *c,int len){ unsigned i,j; unsigned crc_i=0xFFFFFFFF; for(i=0;c!='';i++){ j=(crc_i&0xFF) ^ (int)c; crc_i=(crc_i>>8)^crc32_table[j%256]; } crc_i=crc_i^0xFFFFFFFF; printf("CRC32:%x,n",crc_i); return crc_i;}unsigned calc_code(char *c,int len){ //字符串转化为整形 unsigned i,j=0; for(i=0;c!='';i++){ j=j*2*5; j=j+(int)c-0x30; } return j;}int main(){ unsigned i,j, k=0; make_crc32_table() ; char a[50]="DiKeN"; char str_n[30];char str_s[10]; printf("Name:"); cin>>str_n; strcat(a,str_n); i=CRC32(a,strlen(a)); printf("Code:%u",(unsigned)i); return 0 ;}

本文始发于微信公众号（疯猫网络）：算法逆向2——CRC32识别