安卓逆向-md5算法

一、md5

1. C实现md5

1.1 大致流程

由三个函数来完成md5的加密操作；分别是MD5Init、MD5Update、MD5Final；

void MD5Init (MD5_CTX *mdContext);
void MD5Update (MD5_CTX *mdContext, char *inBuf, unsigned int inLen);
void MD5Final (MD5_CTX *mdContext);
void Transform (UINT4 *buf, UINT4 *in);

MD5Init
- 进行初始化，传入的参数是一个结构体；
MD5Update
- 第一个参数依然是结构体，第二个参数是明文，第三个参数是明文的长度；
MD5Final
- 第一个参数为结构体，第二个参数就是返回值；

注：一个字节=8位（8个二进制位）1Byte=8bit；一个十六进制=4个二进制位。一个字节=2个十六进制。

1.2 明文处理

首先对明文进行Hex编码；
- xiaojianbang ==> 78 69 61 6f 6a 69 61 6e 62 61 6e 67

注：Hex编码（也称为十六进制编码）是一种将数据转换为十六进制表示形式的编码方法。与Base64编码不同，Hex编码使用16个字符来表示数据，这16个字符分别是0-9的数字和A-F的字母（不区分大小写，即a-f和A-F是等价的）。

填充
- 把明文填充到448bit
  先填充一个1，后面跟对应个数的0
- 附加消息长度
  用64bit表示消息长度也就是明文长度
  00 00 00 00 00 00 00 60 转小端序 60 00 00 00 00 00 00 00
  如果内容过长，64个比特放不下。就取低64bit。所以MD5输入长度可以无限大，SHA3算法也是无限大，其他哈希算法不是；
明文的结果：

78 69 61 6f 6a 69 61 6e 62 61 6e 67 80 ...... 60 00 00 00 00 00 00 00
明文 填充 明文长度

MD5输入数据无限大，不可能一起处理，需要分组
MD5分组长度为512bit，数据需要处理到512的倍数，因此需要填充
填充位数为1-512bit，如果明文长度刚好448bit，那么就填充512bit
MD5算法使用的是小端字节序

把处理后的明文分成16块 M1-M16，用于后续计算；

1.3 初始化常量

MD5的初始化常量一共有四个：

A: 01 23 45 67
B: 89 ab cd ef 
C: fe dc ba 98
D: 76 54 32 10

上面说了md5是小端序，所以输入的值不可能是01234567，所以需要传的值是：

四个初始化常量：
A: 0x67452301;
B: 0xEFCDAB89;
C: 0x98BADCFE;
D: 0x10325476;

常量是固定的，如果修改了那就不是一个标准算法，也就是魔改了，这也是魔改md5最多的位置。

1.4 MD5Transform

正式计算；
流程图如下：

关于流程解释如下：

    MD5总共64轮，每一轮都会把旧的D直接给新的A，旧的B直接给新的C，旧的C直接给新的D，也就是每一轮只计算一个新的B
图中的田代表相加
图中的F函数并不是一个函数，而是由四个函数组成
K表里面的值由公式计算的，但体现在代码中一般都是常量 大多数都是直接给的常量值
<<<s代表循环左移
最后把四个初始化常量不断变化后的值，拼接得到最终的摘要结果

通过对上图的理解，每一轮的流程为：

A + F(B、C、D) + Mi + Ki
循环左移
+B

F是一个函数，但并不是固定的一个，而是四个，每16轮一个函数；
在update中，并未直接进行计算，如果传入的参数大于64个字节，直接就去计算，如果没有超过则只进行拷贝，后续再进行填充；

1.5 源码实现

main.cpp

#include <iostream>
#include <memory.h>
#include <string.h>
#include "MD5.h"

using namespace std;

unsigned char PADDING[] = {0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                           0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                           0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                           0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

void MD5Init(MD5_CTX *context) {
    context->count[0] = 0;
    context->count[1] = 0;
    context->state[0] = 0x67452301;
    context->state[1] = 0xEFCDAB89;
    context->state[2] = 0x98BADCFE;
    context->state[3] = 0x10325476;
}

void MD5Update(MD5_CTX *context, unsigned char *input, unsigned int inputlen) {
    unsigned int i = 0, index = 0, partlen = 0;
    index = (context->count[0] >> 3) & 0x3F;
    partlen = 64 - index;
    context->count[0] += inputlen << 3;
    if (context->count[0] < (inputlen << 3))
        context->count[1]++;
    context->count[1] += inputlen >> 29;

    if (inputlen >= partlen) {
        memcpy(&context->buffer[index], input, partlen);
        MD5Transform(context->state, context->buffer);
        for (i = partlen; i + 64 <= inputlen; i += 64)
            MD5Transform(context->state, &input[i]);
        index = 0;
    } else {
        i = 0;
    }
    memcpy(&context->buffer[index], &input[i], inputlen - i);
}

void MD5Final(MD5_CTX *context, unsigned char digest[16]) {
    unsigned int index = 0, padlen = 0;
    unsigned char bits[8];
    index = (context->count[0] >> 3) & 0x3F;
    padlen = (index < 56) ? (56 - index) : (120 - index);
    MD5Encode(bits, context->count, 8);
    MD5Update(context, PADDING, padlen);
    MD5Update(context, bits, 8);
    printf("%.8x\n",  context->state[0]);
    printf("%.8x\n",  context->state[1]);
    printf("%.8x\n",  context->state[2]);
    printf("%.8x\n",  context->state[3]);
    MD5Encode(digest, context->state, 16);

}
// 大端序到小端序
void MD5Encode(unsigned char *output, unsigned int *input, unsigned int len) {
    unsigned int i = 0, j = 0;
    while (j < len) {
        output[j] = input[i] & 0xFF;
        output[j + 1] = (input[i] >> 8) & 0xFF;
        output[j + 2] = (input[i] >> 16) & 0xFF;
        output[j + 3] = (input[i] >> 24) & 0xFF;
        i++;
        j += 4;
    }
}

//分组 分成m1-16
void MD5Decode(unsigned int *output, unsigned char *input, unsigned int len) {
    unsigned int i = 0, j = 0;
    while (j < len) {
        output[i] = (input[j]) |
                    (input[j + 1] << 8) |
                    (input[j + 2] << 16) |
                    (input[j + 3] << 24);
        i++;
        j += 4;
    }
}

void MD5Transform(unsigned int state[4], unsigned char block[64]) {
    unsigned int a = state[0];
    unsigned int b = state[1];
    unsigned int c = state[2];
    unsigned int d = state[3];
    unsigned int x[64];
    MD5Decode(x, block, 64);
    FF(a, b, c, d, x[0], 7, 0xd76aa478); /* 1 */
    FF(d, a, b, c, x[1], 12, 0xe8c7b756); /* 2 */
    FF(c, d, a, b, x[2], 17, 0x242070db); /* 3 */
    FF(b, c, d, a, x[3], 22, 0xc1bdceee); /* 4 */
    FF(a, b, c, d, x[4], 7, 0xf57c0faf); /* 5 */
    FF(d, a, b, c, x[5], 12, 0x4787c62a); /* 6 */
    FF(c, d, a, b, x[6], 17, 0xa8304613); /* 7 */
    FF(b, c, d, a, x[7], 22, 0xfd469501); /* 8 */
    FF(a, b, c, d, x[8], 7, 0x698098d8); /* 9 */
    FF(d, a, b, c, x[9], 12, 0x8b44f7af); /* 10 */
    FF(c, d, a, b, x[10], 17, 0xffff5bb1); /* 11 */
    FF(b, c, d, a, x[11], 22, 0x895cd7be); /* 12 */
    FF(a, b, c, d, x[12], 7, 0x6b901122); /* 13 */
    FF(d, a, b, c, x[13], 12, 0xfd987193); /* 14 */
    FF(c, d, a, b, x[14], 17, 0xa679438e); /* 15 */
    FF(b, c, d, a, x[15], 22, 0x49b40821); /* 16 */

    /* Round 2 */
    GG(a, b, c, d, x[1], 5, 0xf61e2562); /* 17 */
    GG(d, a, b, c, x[6], 9, 0xc040b340); /* 18 */
    GG(c, d, a, b, x[11], 14, 0x265e5a51); /* 19 */
    GG(b, c, d, a, x[0], 20, 0xe9b6c7aa); /* 20 */
    GG(a, b, c, d, x[5], 5, 0xd62f105d); /* 21 */
    GG(d, a, b, c, x[10], 9, 0x2441453); /* 22 */
    GG(c, d, a, b, x[15], 14, 0xd8a1e681); /* 23 */
    GG(b, c, d, a, x[4], 20, 0xe7d3fbc8); /* 24 */
    GG(a, b, c, d, x[9], 5, 0x21e1cde6); /* 25 */
    GG(d, a, b, c, x[14], 9, 0xc33707d6); /* 26 */
    GG(c, d, a, b, x[3], 14, 0xf4d50d87); /* 27 */
    GG(b, c, d, a, x[8], 20, 0x455a14ed); /* 28 */
    GG(a, b, c, d, x[13], 5, 0xa9e3e905); /* 29 */
    GG(d, a, b, c, x[2], 9, 0xfcefa3f8); /* 30 */
    GG(c, d, a, b, x[7], 14, 0x676f02d9); /* 31 */
    GG(b, c, d, a, x[12], 20, 0x8d2a4c8a); /* 32 */

    /* Round 3 */
    HH(a, b, c, d, x[5], 4, 0xfffa3942); /* 33 */
    HH(d, a, b, c, x[8], 11, 0x8771f681); /* 34 */
    HH(c, d, a, b, x[11], 16, 0x6d9d6122); /* 35 */
    HH(b, c, d, a, x[14], 23, 0xfde5380c); /* 36 */
    HH(a, b, c, d, x[1], 4, 0xa4beea44); /* 37 */
    HH(d, a, b, c, x[4], 11, 0x4bdecfa9); /* 38 */
    HH(c, d, a, b, x[7], 16, 0xf6bb4b60); /* 39 */
    HH(b, c, d, a, x[10], 23, 0xbebfbc70); /* 40 */
    HH(a, b, c, d, x[13], 4, 0x289b7ec6); /* 41 */
    HH(d, a, b, c, x[0], 11, 0xeaa127fa); /* 42 */
    HH(c, d, a, b, x[3], 16, 0xd4ef3085); /* 43 */
    HH(b, c, d, a, x[6], 23, 0x4881d05); /* 44 */
    HH(a, b, c, d, x[9], 4, 0xd9d4d039); /* 45 */
    HH(d, a, b, c, x[12], 11, 0xe6db99e5); /* 46 */
    HH(c, d, a, b, x[15], 16, 0x1fa27cf8); /* 47 */
    HH(b, c, d, a, x[2], 23, 0xc4ac5665); /* 48 */

    /* Round 4 */
    II(a, b, c, d, x[0], 6, 0xf4292244); /* 49 */
    II(d, a, b, c, x[7], 10, 0x432aff97); /* 50 */
    II(c, d, a, b, x[14], 15, 0xab9423a7); /* 51 */
    II(b, c, d, a, x[5], 21, 0xfc93a039); /* 52 */
    II(a, b, c, d, x[12], 6, 0x655b59c3); /* 53 */
    II(d, a, b, c, x[3], 10, 0x8f0ccc92); /* 54 */
    II(c, d, a, b, x[10], 15, 0xffeff47d); /* 55 */
    II(b, c, d, a, x[1], 21, 0x85845dd1); /* 56 */
    II(a, b, c, d, x[8], 6, 0x6fa87e4f); /* 57 */
    II(d, a, b, c, x[15], 10, 0xfe2ce6e0); /* 58 */
    II(c, d, a, b, x[6], 15, 0xa3014314); /* 59 */
    II(b, c, d, a, x[13], 21, 0x4e0811a1); /* 60 */
    II(a, b, c, d, x[4], 6, 0xf7537e82); /* 61 */
    II(d, a, b, c, x[11], 10, 0xbd3af235); /* 62 */
    II(c, d, a, b, x[2], 15, 0x2ad7d2bb); /* 63 */
    II(b, c, d, a, x[9], 21, 0xeb86d391); /* 64 */
    state[0] += a;
    state[1] += b;
    state[2] += c;
    state[3] += d;
}

int main(){

//    void MD5Init(MD5_CTX *context);
    MD5_CTX context;
    MD5Init(&context);
//    void MD5Update(MD5_CTX *context,unsigned char *input,unsigned int inputlen);
    unsigned char* plainText = (unsigned char *) "xiaojianbang";
    MD5Update(&context, plainText, strlen(reinterpret_cast<const char *>(plainText)));
//    void MD5Final(MD5_CTX *context,unsigned char digest[16]);
    unsigned char result[16];
    MD5Final(&context, result);

    char temp[2] = {0};
    char finalResult[33] = {0};
    for(int i = 0; i < 16; i++){
        int index = i;
        sprintf(temp, "%.2x", result[index]);
        strcat(finalResult, temp);
    }

    cout << finalResult << endl;

    return 0;
}

md5.h

#ifndef HOOKDEMO_MD5_H
#define HOOKDEMO_MD5_H

typedef struct {
    unsigned int count[2];
    unsigned int state[4];
    unsigned char buffer[64];
} MD5_CTX;

#define F(x,y,z) ((x & y) | (~x & z))
#define G(x,y,z) ((x & z) | (y & ~z))
#define H(x,y,z) (x^y^z)
#define I(x,y,z) (y ^ (x | ~z))
#define ROTATE_LEFT(x,n) ((x << n) | (x >> (32-n)))
#define FF(a,b,c,d,x,s,ac) \
          { \
          a += F(b,c,d) + x + ac; \
          a = ROTATE_LEFT(a,s); \
          a += b; \
          }
#define GG(a,b,c,d,x,s,ac) \
          { \
          a += G(b,c,d) + x + ac; \
          a = ROTATE_LEFT(a,s); \
          a += b; \
          }
#define HH(a,b,c,d,x,s,ac) \
          { \
          a += H(b,c,d) + x + ac; \
          a = ROTATE_LEFT(a,s); \
          a += b; \
          }
#define II(a,b,c,d,x,s,ac) \
          { \
          a += I(b,c,d) + x + ac; \
          a = ROTATE_LEFT(a,s); \
          a += b; \
          }
void MD5Init(MD5_CTX *context);
void MD5Update(MD5_CTX *context,unsigned char *input,unsigned int inputlen);
void MD5Final(MD5_CTX *context,unsigned char digest[16]);
void MD5Transform(unsigned int state[4],unsigned char block[64]);
void MD5Encode(unsigned char *output,unsigned int *input,unsigned int len);
void MD5Decode(unsigned int *output,unsigned char *input,unsigned int len);

#endif //HOOKDEMO_MD5_H

2. IDA中的md5

2.1 md5init

进入md5init函数，可以看到在上面提到的初始化常量；

可以发现和我们上面说的是不太一样的，这里是因为默认显示的是十进制，选中数字按下h即可转成16进制，或者右键选择Hexadecimal转换；

2.2 md5transform

接着进到md5transform函数中

可以发现k表有些值转换后和我们上面的值不太一样，可能是有无符号的问题，右键选择invert sign，转换一下就可以了；这里其实是f5插件识别的问题，在汇编中其实是正确的；
__ROR4__代表的是循环右移，ROL则是循环左移，那么在上面提到了运算是循环左移，这里为何是右移，其实在这里是一样的，对于32位的数据来说，循环右移25位就等于循环左移7位；

2.3 md5final

函数参数处理技巧

伪C/C++没有识别出函数参数的处理
    rename lvar        修改变量名
    set lvar type    修改变量类型
    set item type    修改函数类型
    force call type    重新识别函数

一、md5

1. C实现md5

1.1 大致流程

1.2 明文处理

1.3 初始化常量

1.4 MD5Transform

1.5 源码实现

2. IDA中的md5

2.1 md5init

2.2 md5transform

2.3 md5final

评论 (0)