用户
搜索
  • TA的每日心情
    慵懒
    昨天 07:31
  • 签到天数: 203 天

    连续签到: 9 天

    [LV.7]常住居民III

    版主

    Rank: 7Rank: 7Rank: 7

    27

    主题

    109

    帖子

    4080

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

    i春秋签约作者春秋文阁

    发表于 2018-1-4 14:08:53 85195
    本文原创作者:icq5f7a075d,本文属i春秋原创奖励计划,未经许可禁止转载!
    本文如果出现错误,欢迎指出,感激不尽!
    本文中的所有程序请在虚拟机中运行。
    参考资料:
    《加密与解密实战攻略》
    《应用密码学》 曹天杰著

    不知不觉,这个系列已经写到第四篇,但是看到人好少啊,难过。说一下笔者为什么写这个系列吧,算法的逆向是软件逆向过程中重要的一环,而大多数软件使用的是已知算法或者已知算法的变形,快速识别出已知算法能够极大的减轻软件逆向的工作量。笔者写这个系列,一方面是为了能够掌握快速识别已知算法能力,另一方面是想提取已知算法的特征,写一个算法识别的工具。
    言归正传,开始今天的主题:SHA-1
    1. SHA-1简介
    SHASecure Hash Algorithm安全散列算法),是一个系列算法。SHA系列中含有五个算法,分别是SHA-1、SHA-224、SHA-256、SHA-384和SHA-512SHA-1也叫SHA-128,而SHA-224、SHA-256、SHA-384和SHA-512有时并称为SHA-2。
    当消息长度小于2^64位时,使用SHA-1和SHA-256;当消息长度小于2^128位时,使用SHA384和SHA512。分别产生160位,256位,384位,512位长度的散列。
    SHA算法基于MD4,其结构与MD5很相似。但SHA-1的输入小于2^64bit,输出是160bit,MD5输入没有长度限制,输出是128bit。
    2. SHA-1算法过程
    2.1. 基本过程
    (1)数据填充:
    与MD5的数据填充方式相似。首先是消息填充,在要处理的信息后面补上0x80,后面补充0,填充后的消息长度是512的某一倍数减64;然后添加消息长度,在消息后面补上64bit消息长度;同时将消息按照512bit进行分组;
    (2)初始化缓冲区:
    SHA-1使用160bit长的缓冲区存储中间结果和最终Hash值,缓冲区可表示为五个32bit长的寄存器A、B、C、D、E,分别将其初始化为:
    A=0x67452301
    B=0xEFCDAB89
    C=0x98BADCFE
    D=0x10325476
    E=0xC3D2E1F0
    (3)以分组为单位对消息进行处理:每一个分组都经过压缩函数处理,压缩过程由4轮处理过程构成,每一轮又由20步迭代组成。第80步迭代的输出再与第一轮的输入模2^32相加。
    (4)输出:消息的所有分组都被处理完后,最后一个分组的输出就是160bit的消息摘要。
    2.2. 压缩函数
    前文中提到了的压缩函数,接下来详细介绍压缩函数。压缩函数由4轮处理过程构成,每一轮又由20步迭代组成。
    4轮处理过程结构一样,但是所用的基本函数不同:
    ft(X,Y,Z) = (X & Y) | ((~X) & Z) ( 0 <= t <= 19)
    ft(X,Y,Z) = X^Y^Z (20 <= t <= 39)
    ft(X,Y,Z) = (X & Y)|(X & Z)|(Y & Z) (40 <= t <= 59)
    ft(X,Y,Z) =X^Y^Z (60 <= t <= 79)
    SHA-1每轮的输入为当前处理的消息分组和缓冲区A、B、C、D、E的当前值,输入仍然放在缓冲区以替代旧的A、B、C、D、E。每轮计算还需要加上一个加法常量Kt,其中0 <= t <= 79,t表示迭代的步数,它们如下:
    Kt = 0x5A827999 (0 <= t <= 19)
    Kt = 0x6ED9EBA1 (20 <= t <= 39)
    Kt = 0x8F1BBCDC (40 <= t <= 59)
    Kt = 0xCA62C1D6 (60 <= t <= 79).

    每次迭代过程可以表示为如下形式:
    A,B,C,D,E =(E+ft(B,C,D)+CLS5(A),Wt,Kt),A,CLS30(B),C,D
    +是模2^32加法,CLS是循环左移,Wt是32位字,W0,W1....,W15直接从分组中得到,其余的由公式Wt=CLS1(Wt-3 + Wt-8 + Wt-14 + Wt-16),同样是模2^32加法。
    综上,SHA-1的压缩函数的处理过程:
    第一轮:0 <= t <= 19,Kt = 0x5A827999:
    TEMP=(A<<<5)+f1(B,C,D)+E+Wt+Kt
    E=D,D=C,C=B<<<30,B=A,A=TEMP
    第二轮:20 <= t <= 39,Kt = 0x6ED9EBA1:
    TEMP=(A<<<5)+f2(B,C,D)+E+Wt+Kt
    E=D,D=C,C=B<<<30,B=A,A=TEMP
    第三轮:40 <= t <= 59,Kt = 0x8F1BBCDC:
    TEMP=(A<<<5)+f3(B,C,D)+E+Wt+Kt
    E=D,D=C,C=B<<<30,B=A,A=TEMP
    第四轮:60 <= t <= 79,Kt = 0xCA62C1D6:
    TEMP=(A<<<5)+f4(B,C,D)+E+Wt+Kt
    E=D,D=C,C=B<<<30,B=A,A=TEMP

    3. 程序逆向
    该程序和《算法逆向3》中的程序基本流程是相同的,只是所使用的算法不同。有了前一章的基础,我们很容易就可以定位到关键算法。
    程序首先进行了一些初始化工作,获取Name和Code数据,并在Name字符串前添加“DiKeN”,Code字符串前添加“0”。判断Name数据的长度,长度不大于0x1E,这样接下来计算SHA-1时,只需要考虑一个分组的情况。
    程序完成前期处理工作后正式进入SHA-1的过程。
    1)首先是消息填充:
    将消息(处理后的Name数据)存入buffer缓冲区,并在消息尾填充0x80,接着将消息长度填充进buffer最后8字节中。在实际分析中发现MD5填充消息长度的方式和SHA-1不同,上图是MD5填充下图是SHA-1,可以看到MD5填充的是0x68 0x00 0x00 0x00 0x00 0x00 0x00 0x00,SHA-1填充的是0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x68;
    图片1.png
    图片2.png
    2)计算W[t]
    W[0]-W[15]直接从消息中获取,其余的由公式W[t]=CLS1(W[t-3] + W[t-8] + W[t-14] + W[t-16])计算获取
    图片3.png
    3)执行压缩函数
    第一轮压缩函数:
    图片4.png
    有两个注意点:
    第一个注意点是循环左移,一般来说汇编中使用rol指令实现循环左移,但这个地方使用shl和shr两条指令实现循环左移,实现的过程等价于A<<<5=(A<<5)|(A>>0x1B);
    第二个要注意的地方是f1(B,C,D),在前文中我们提到f1(X,Y,Z)=(X & Y) | ((~X) & Z),但这里使用的f1(X,Y,Z)= ((Z^Y)&X)^Z,为什么会出现这种变化?这里使用了离散数学的知识,如果你的功底深厚,你就可以用公式推算出(X & Y) | ((~X) & Z)==((Z^Y)&X)^Z,如果你的功底不深厚,你就可以画三个圈推导出。笔者功力浅薄,就画圈吧-_-!
    首先画一个蓝色的圈,这个蓝色的圈表示X:
    图片5.png
    接着画一个红色的圈,这个红色的圈表示YX&Y就是两个圈相交的地方:
    图片6.png

    如此我们就可以用图形表示出(X & Y) | ((~X) & Z):X的圈和Y的圈相交的地方,再加上Z的圈中不包含X圈的地方,即图中1、3、5、7的区域:
    图片7.png
    用图形描述((Z^Y)&X)^Z,仍然是图中1、3、5、7的区域,如此我们可以确定(X & Y) | ((~X) & Z)==((Z^Y)&X)^Z;
    ②第二轮压缩函数:
    图片8.png
    这里就和前文提到的运算一模一样了;
    ③第三轮压缩函数:
    图片9.png
    这里使用的f3(X,Y,Z)=(X&Y)|((X|Y)&Z)与前文提到的(X & Y)|(X & Z)|(Y & Z)不相同,又需要祭出离散数学的知识来验证了,不过这次比较简单,使用分配律一步就能推导出来。
    ④第四轮压缩函数:
    图片10.png
    这里就和前文提到的运算也是一模一样;
    (5)压缩函数继续完后,将缓冲区数据加上最初缓冲区的数据
    图片11.png
    至此SHA-1计算完成。
    之后对SHA-1值进行处理,处理过程和《算法逆向3》中相同,最后得到的CODE=A^B^C^D^E。
    4. 注册机
    图片12.png
    程序已经分析完了,上注册机源码:
    [C++] 纯文本查看 复制代码
    #include<iostream>
    #include<string.h>
    using namespace std;
    unsigned T[65];
     
    void MD5Updata(unsigned &A,unsigned &B,unsigned &C,unsigned &D,unsigned &E,char *buffer);
     
    int main()
    {
        unsigned A=0x67452301,B=0xEFCDAB89,C= 0x98BADCFE,D= 0x10325476,E= 0xC3D2E1F0;
        char buffer[64]={'\0'};
        char t_Name[64],t_Code[64],Name[64]="DiKeN",Code[64]="0";
        unsigned len_tName,len_tCode,len_Name,len_Code;
        long len_byte_Name;
        cout<<"Name:";
        cin>>t_Name;
        len_tName=strlen(t_Name);
        strcat(Name,t_Name);
        if(Name[0]=='\0'||len_tName>0x1E){
                printf("%x,%x\n",(unsigned)Name[0],len_tName) ;
                cout<<"Error!"<<endl;
                return 1;
        }
         
        len_Name=strlen(Name);len_Code=strlen(Code);
        //消息填充 
            memcpy(&buffer,&Name,len_Name);
        buffer[len_Name]='\x80';
            len_byte_Name =len_Name<<3;//计算bit数 ,和MD5的不同 
            if(len_byte_Name>0xFF){
                    buffer[63]=(char)(len_byte_Name&0x000000FF);
                    buffer[62]=(char)(len_byte_Name&0x0000FF00);
            }
            else
                    buffer[63]=(char)len_byte_Name;
            MD5Updata(A,B,C,D,E,buffer);
            A=A^B^C^D^E;    
            printf("Code:%u",(unsigned)A);
        return 0;
    } 
     
    unsigned ROL(unsigned m,int size){
                    //printf("%X,%X,%d\n",(m >> (32 - size)), (m << size),size);
            return (m >> (32 - size)) | (m << size);
    }
    void MD5Updata(unsigned &A,unsigned &B,unsigned &C,unsigned &D,unsigned &E,char *buffer){
            //计算W[t]
            unsigned W[80];
            int i=0,j=0,t=0;
            for(t=0;t<80;t++){
                    if(t<16){
                            j=4*t;//string 转 un_int,大端到小端的转换, MD5中是直接取字节操作 
                            W[t]=((unsigned)buffer[j+3]&0x000000FF)+((unsigned)buffer[j+2]*0x100&0x0000FF00)+((unsigned)buffer[j+1]*0x10000&0x00FF0000)+((unsigned)buffer[j+0]*0x1000000&0xFF000000);   
                    }
                    else{
                            W[t]=ROL((W[t-3]^W[t-8]^W[t-14]^W[t-16]),1);
                    }
                    //printf("%x,",W[t]);
            }
            printf("%X,%X,%X,%X,%X\n",A,B,C,D,E); 
            //第一轮
            for(t=0;t<20;t++){
                    //printf("%X,%X,%X,%X\n",(D^C),(((D^C)&B)^D),((D^C)&B),E); 
                    unsigned TEMP=ROL(A,5)+(((D^C)&B)^D)+W[t]+0x5A827999+E;
                    E=D;
                    D=C;
                    C=ROL(B,30); 
                    B=A;
                    //貌似((X & Y) | ((~X) & Z) )  = (((Z^Y)&X)^Z)
                    A=TEMP;
                    //printf("%d:%X,%X,%X,%X,%X\n",(t+1),A,B,C,D,E); 
            }
            //第二轮
            for(t=20;t<40;t++){
                    unsigned TEMP=ROL(A,5)+(B^C^D)+W[t]+0x6ED9EBA1+E;
                    E=D;
                    D=C;
                    C=ROL(B,30); 
                    B=A;
                    A=TEMP;
                    //printf("%d:%X,%X,%X,%X,%X\n",(t+1),A,B,C,D,E);  
            }
            //第三轮
            //(X&Y)|(X&Z)|(Y&Z)==(X&Y)|((X|Y)&Z)
            for(t=40;t<60;t++){
                    unsigned TEMP=ROL(A,5)+((B&C)|(D&C)|(B&D))+W[t]+0x8F1BBCDC+E;
                    E=D;
                    D=C;
                    C=ROL(B,30); 
                    B=A;
                    A=TEMP;
                    //printf("%d:%X,%X,%X,%X,%X\n",(t+1),A,B,C,D,E);  
            }
            //第四轮
            for(t=60;t<80;t++){
                    unsigned TEMP=ROL(A,5)+(B^C^D)+W[t]+0xCA62C1D6+E;
                    E=D;
                    D=C;
                    C=ROL(B,30); 
                    B=A;
                    A=TEMP;
                    //printf("%d:%X,%X,%X,%X,%X\n",(t+1),A,B,C,D,E); 
            }
            A+=0x67452301;
            B+=0xEFCDAB89;
            C+=0x98BADCFE;
            D+=0x10325476;
            E+=0xC3D2E1F0;
            printf("%X,%X,%X,%X,%X\n",A,B,C,D,E); 
    }


    游客,如果您要查看本帖隐藏内容请回复


    本帖被以下淘专辑推荐:

    看的人少是因为看不懂 哈哈哈哈或
    使用道具 举报 回复
    小白看不太懂,感谢分享
    使用道具 举报 回复
    发表于 2018-1-6 07:36:42
    算法逆向4——SHA-1识别
    使用道具 举报 回复
    6666666666666
    使用道具 举报 回复
    发表于 2018-1-7 10:36:36
    大神牛逼666
    使用道具 举报 回复
    感谢分享
    使用道具 举报 回复
    发表于 2018-5-29 22:14:50

    谢谢分享
    使用道具 举报 回复
    发表于 2018-5-29 22:14:58

    谢谢分享
    谢谢分享
    谢谢分享
    谢谢分享
    使用道具 举报 回复
    发新帖
    您需要登录后才可以回帖 登录 | 立即注册