用户
搜索
  • TA的每日心情
    慵懒
    2019-9-3 13:38
  • 签到天数: 287 天

    连续签到: 1 天

    [LV.8]以坛为家I

    i春秋作家

    Rank: 7Rank: 7Rank: 7

    31

    主题

    127

    帖子

    6239

    魔法币
    收听
    3
    粉丝
    12
    注册时间
    2015-11-20

    i春秋签约作者春秋文阁

    发表于 2017-12-20 09:29:53 1528628
    本帖最后由 icq5f7a075d 于 2017-12-30 12:49 编辑

    本文原创作者:icq5f7a075d,本文属i春秋原创奖励计划,未经许可禁止转载!
    本文如果出现错误,欢迎指出,感激不尽!
    本文中的所有程序请在虚拟机中运行。

    很早就学过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。
    实际计算过程:
    图片1.png
    当接收方收到数据后,用收到的数据对P(事先约定的)进行模2除法,若余数为0,则认为数据传输无差错;若余数不为0,则认为数据传输出现了错误,由于不知道错误发生在什么地方,因而不能进行自动纠正,一般的做法是丢弃接收的数据。

    1.3. CRC数据表1.3.1. CRC数据表的由来——由模2除法到异或
    我们继续使用上一节提到的数据,在上一节中我们使用了模2除法的方式计算出CRC的值,现在我们将其中每一位的计算过程展开,得到下列的8次计算过程:
    图片2.png
    可以看到由第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:
    图片3.png
    我们先进行M1^A^B^C^D的计算,在计算时我们先忽略后面的0:
    图片4.png
    假设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/b3
    0
    M1 bit7=0
    b左移3bit
    M1 bit7=1
    B/b2
    0
    M1 bit6=0
    b左移2bit
    M1 bit6=1
    C/b1
    0
    M1 bit5=0
    b左移1bit
    M1 bit5=1
    D/b0
    0
    M1 bit4=0
    b左移0bit
    M1 bit4=1
    所以A、B、C、D的值只取决于M1和b,则M1^A^B^C^D的值只取决于M1和b,那么在已知生成多项式b的情况下,我们可以遍历M1生成一个数据表,对于每一个M1不需要计算,直接查表即可计算出M1^A^B^C^D。
    索引
    M1的有效值
    M1^b0^b2^b3^
    0
    0x00
    0x00
    1
    0x01
    0x03
    2
    0x02
    0x06
    3
    0x03
    0x05
    4
    0x04
    0x0C
    5
    0x05
    0x0F
    6
    0x06
    0x0A
    7
    0x07
    0x09
    8
    0x08
    0x0B
    9
    0x09
    0x08
    10
    0xA
    0x0D
    11
    0xB
    0x0E
    12
    0xC
    0x07
    13
    0xD
    0x04
    14
    0xE
    0x01
    15
    0xF
    0x02

    如图,M1的有效值是0011=0x3,查表得到M1^A^B^C^D=0x5,继续计算S1^M2:
    图片5.png
    计算出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的计算过程:
    图片6.png
    可以发现,若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数据表生成源码:
    [C++] 纯文本查看 复制代码
    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算法实现
    前面整个章节介绍的,实际上只是CRC校验和CRC数据表,并不是CRC32算法,CRC32算法是在此基础上设计的算法,其使用查表法实现CRC校验,具体步骤如下:
    (1)取上次计算出的CRC校验码最后一个字节与新的要校验的字节进行XOR 运算,生成新的索引;CRC校验码的初始值为0xFFFFFFFF;
    (2)将上次计算出的CRC校验码右移一个字节,生成临时校验码;
    (3)用新的索引在预先生成码表中进行索引,获取对应的值(称为余式);
    (4)用临时校验码和余式进行XOR 运算,生成新的校验码;
    (5)如果要校验的数据已经处理完,则第(4)步的结果XOR 0xFFFFFFFF就是最终的CRC校验码。如果还有数据要进行处理,则再转到第(1)步运行。

    源码:
    [C++] 纯文本查看 复制代码
    unsigned CRC32(char *c,int len){
    unsigned i,j;
    unsigned crc_i=0xFFFFFFFF;
    for(i=0;c!='\0';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,弹出错误提示:
    图片7.png
    在OD中查找文本字符串,没有什么收获,在IDA中分析,扫一眼函数列表,发现了MessageBoxA,Ctrl+x交叉引用查看哪些函数调用了MessageBoxA,跟进去,立刻有了喜人的收获:
    图片8.png
    看来这里就是关键位置了,这里处于sub_4042A8函数内,sub_4042A8就是我们我们要逆向的关键算法。
    sub_4042A8的流程还是比较清晰,但是看函数调用关系,很复杂,这就注定我们不能跟进每个call,详细分析每个call了,要尽量猜测call函数的含义。
    图片9.png 图片10.png
    3.2. 算法分析
    ①开辟存放字符串的空间
    程序首先会调用GetWindowTextLengthA获取Name字符串的长度,在这期间调用的sub_402DE8,sub_402ED8都比较复杂,不需要详细分析,使用OD查看运行效果就可以发现,sub_402DE8申请了一内存,sub_402ED8向内存里写入Name字符串的长度的空格字符,空格字符来源于dword_4043EC。所以这里相当于开辟了存放字符串的空间:
    图片11.png
    ②判断字符串长度,拼接字符串,进行CRC32计算
    首先获取Name字符串,并判断长度是否小于5,如果小于5则进入错误处理流程;之后在Name字符串前添加字符串“DiKeN”生成新的字符串,例如,输入的name是ichunqiu,则生成的字符串是DiKeNichunqiu;之后就对新的字符串进行CRC32计算:
    图片12.png
    ③CRC32计算
    计算的过程很清晰,和第二章中的代码几乎吻合,就不赘述了,可以对照前面的源码看
    图片13.png
    ④计算code字符串
    code字符串的预处理方式与Name字符串相同,先开辟空间,然后拼接字符串,在code字符串前添加字符‘0’;在sub_404224中用新的算法处理新生成的字符
    图片14.png
    ⑤sub_404224:code字符串转化为整数
    图片15.png
    计算过程很简单,直接上源码:
    [C++] 纯文本查看 复制代码
    unsigned calc_code(char *c,int len){
    unsigned i,j=0;
    for(i=0;c!='\0';i++){
    j=j*2*5;
    j=j+(int)c-0x30;
    }
    printf("%x,\n",j);
    return j;
    }
    ⑥比较
    没什么说的,就是比较Name的CRC32值和输入的值是否相同,如果相同就通过注册:
    图片16.png
    图片17.png

    3.2.1. 注册机
    注册机完整源码:
    [C++] 纯文本查看 复制代码
    #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!='\0';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!='\0';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 ;
    }

    附件:
    crc32crackme.rar (11.15 KB, 下载次数: 12, 售价: 5 魔法币)

    评分

    参与人数 1魔法币 +30 收起 理由
    aoe + 30 感谢发布原创作品,i春秋论坛因你更精彩!.

    查看全部评分

    本帖被以下淘专辑推荐:

    发表于 2017-12-20 15:59:01
    66666666666666666
    使用道具 举报 回复
    路过看看
    使用道具 举报 回复
    发表于 2017-12-22 16:41:48
    支持原创
    使用道具 举报 回复
    继续学习!
    使用道具 举报 回复
    路过看看
    使用道具 举报 回复
    666666666666
    使用道具 举报 回复
    算法逆向2——CRC32识别
    使用道具 举报 回复
    膜拜一下,学习学习。
    使用道具 举报 回复
    谢谢分享,学习一下算法
    使用道具 举报 回复
    发表于 2018-8-18 13:37:46
    学习一下~
    使用道具 举报 回复
    附件是啥
    使用道具 举报 回复
    发表于 2018-10-12 19:38:49
    6666666666t111111
    使用道具 举报 回复
    发表于 2018-11-29 18:01:41
    哎呦不错哦
    使用道具 举报 回复
    发表于 2019-3-29 09:01:22
    谢谢分享,学习了
    使用道具 举报 回复
    12下一页
    发新帖
    您需要登录后才可以回帖 登录 | 立即注册