菜鸡学逆向——常见编码,加密算法逆向总结_逆向加密算法

最近打CTF太郁闷了，总是被逆向出来自己见过但又偏偏想不起来的算法。这次总结个大个的
具体算法的原理博客上许多大佬们已经讲解的十分详细。本文不再赘述仅仅做一些加密算法特征的总结。若有错误的地方还望各位读文章的师傅们指出。
文中部分代码转载自：https://kabeor.cn

Base64

代码参考52pojie论坛的kabeo大佬，原文地址：https://www.52pojie.cn/thread-793420-1-1.html

#include <stdio.h>
#include "string.h"
#include "stdlib.h"

const char base[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=";
static char find_pos(char ch);
char *base64_encode(const char* data, int data_len,int *len);

/**
 *找到ch在base中的位置
 */
static char find_pos(char ch)
{
    //the last position (the only) in base[]
    char *ptr = (char*)strrchr(base, ch);
    return (ptr - base);
}

/**
 *BASE64编码
 */
char *base64_encode(const char* data, int data_len,int *len)
{   //Length change to prior 3/4
    int prepare = 0;
    int ret_len;
    *len=0;
    int temp = 0;
    char *ret = NULL;
    char *f = NULL;
    int tmp = 0;
    char changed[4];
    int i = 0;
    ret_len = data_len / 3; //确定最后的 =
    temp = data_len % 3;  //
    if (temp > 0)
    {
        ret_len += 1;
    }
    //最后一位以''结束
    ret_len = ret_len*4 + 1;  //加上‘\0’
    ret = (char *)malloc(ret_len); //确定编码后的长度

    if ( ret == NULL)
    {
        printf("No enough memory.n");
        exit(0);
    }
    memset(ret, 0, ret_len);
    f = ret;
    //tmp记录data中移动位置
    while (tmp < data_len)
    {
        temp = 0;
        prepare = 0;
        memset(changed, 0, 4);
        while (temp < 3) //每次读取三位
        {
            if (tmp >= data_len)
            {
                break;
            }
            //将data前8*3位移入prepare的低24位
            prepare = ((prepare << 8) | (data[tmp] & 0xFF));//作用是变为二进制
            tmp++;
            temp++; //作为计数器
        }
        //将有效数据移到以prepare的第24位起始位置
        prepare = (prepare<<((3-temp)*8));

        for (i = 0; i < 4 ;i++ )
        {
            //最后一位或两位
            if (temp < i)
            {
                changed[i] = 0x40;
            }
            else
            {
                //24位数据
                changed[i] = (prepare>>((3-i)*6)) & 0x3F;
            }
            *f = base[ changed[ i ] ];
            f++;
            (*len)++;
        }
    }
    strcpy(f,"");
    return ret;
}
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

编译出文件，拖进IDA中：

void *__fastcall base64_encode(__int64 a1, int a2, _DWORD *a3)
{
  _DWORD *v4; // [rsp+8h] [rbp-48h]
  char v5[4]; // [rsp+24h] [rbp-2Ch]
  void *s; // [rsp+28h] [rbp-28h]
  int i; // [rsp+30h] [rbp-20h]
  int v8; // [rsp+34h] [rbp-1Ch]
  _BYTE *v9; // [rsp+38h] [rbp-18h]
  int v10; // [rsp+44h] [rbp-Ch]
  int v11; // [rsp+48h] [rbp-8h]
  int v12; // [rsp+4Ch] [rbp-4h]

  v4 = a3;
  v12 = 0;
  *a3 = 0;
  s = 0LL;
  v9 = 0LL;
  v8 = 0;
  i = 0;
  v11 = a2 / 3;
  if ( a2 % 3 > 0 )
    ++v11;
  v11 = 4 * v11 + 1;
  s = malloc(v11);
  if ( !s )
  {
    printf("No enough memory.n");
    exit(0);
  }
  memset(s, 0, v11);
  v9 = s;
  while ( v8 < a2 )
  {
    v10 = 0;
    v12 = 0;
    memset(v5, 0, 4uLL);
    while ( v10 <= 2 && v8 < a2 )
    {
      v12 = (v12 << 8) | *(unsigned __int8 *)(v8++ + a1);
      ++v10;
    }
    v12 <<= 8 * (3 - v10);
    for ( i = 0; i <= 3; ++i )
    {
      if ( v10 >= i )
        v5[i] = (v12 >> 6 * (3 - i)) & 0x3F;
      else
        v5[i] = 64;
      *v9++ = base[v5[i]];
      ++*v4;
    }
  }
  *v9 = 0;
  return s;
}
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

下面来对Base64算法的特诊进行分析：

1. 往往数据段有编码表，如下图所示
   有时候题目中会改这个表，更改里面的某些字符或者顺序。如果你碰到别(shi)出(fen)心(bian)裁(tai)的出题者把编码表给加密了，那就老老实实地去解吧…

2. 编码过程中，读取每次读取八位，编码每次编码六位
   

3. 以六位结果进行编码表的映射
   

Base32

Base32与Base64相似，Base32的编码表内是32个字符,每次取5位进行映射

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//base32 表包含 0~9 以及小写字母 (去除'a','i','l','o')，
//共 32 个字符
static const char base32_alphabet[32] = {
        '0', '1', '2', '3', '4', '5', '6', '7',
        '8', '9', 'b', 'c', 'd', 'e', 'f', 'g',
        'h', 'j', 'k', 'm', 'n', 'p', 'q', 'r',
        's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
};

/*
 * 匹配 base32_alphabet
 */
int find_number(char m) {
    int i;
    for(i = 0; i < 32; ++i)
    {
        if(m == base32_alphabet[i])
            return i;
    }
    return -1;
}

/*
 * base32 编码
 */

char* base32_encode(char *bin_source){
    int i;
    int j = 0;
    static char str[10];

    for(i=0;i<strlen(bin_source);++i){
        if((i+1)%5==0){
            j++;
            int num = (bin_source[i]-'0')+(bin_source[i-1]-'0')*2\
            +(bin_source[i-2]-'0')*2*2+(bin_source[i-3]-'0')*2*2*2\
            +(bin_source[i-4]-'0')*2*2*2*2;
            str[j-1] = base32_alphabet[num];
        }

    }
    return str;
}

/*
 1. base32 解码
 */
int* base32_decode(char *str_source){
    int i,j;
    static int dec[50];
    int count=0;
    for(i=0;i<strlen(str_source);++i){
        for(j=5-1;j>=0;--j){
            count++;
            //位运算十进制转二进制
            dec[count-1] = find_number(str_source[i])>>(j%5)&1;
        }
    }
    return dec;
}
int main()
{
    char *p=base32_encode("1001101010");
    printf("%s",p);
    return 0;
}
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

1. 编码表长度为32，0~9，小写英文字母去除a、i、l、o
2. 编码过程每次以五位读取进行编码
   

Base16

所有的Base家族本质上是换汤不换药
Base16按照4位二进制进行编码，编码表0~9外加a ~ f,其余相似

如果说上面的算法是可以使用IDA插件FindCrypt找到的话，以下部分则需要用自己眼睛判断了

国密SM4

参考资料：《应用密码学》张仕斌，万武南，张金全，孙宣东著，西安电子科技大学出版社
由于网上的对于SM4算法的解释太少了，于是就参考了密码学课本…

---

算法特征

 1. 分组长度为128比特，在代码中也就是16个“字符”。密文输出同样为182比特
 2. 轮密钥总共32个，每个轮密钥32比特。由初始密钥(共128bit)和系统参数(128bit)一起生成初始的key0,1,2,3。
 3. 加密与解密算法完全相同，不同的是使用轮密钥的顺序不同（加密使用顺序key0,key1,key2.....key31,解密顺序key31,key30,key29....key0)
1
2
3

轮密钥的生成

流程

1.期初输入128bit的密钥，与系统参数128bit进行异或
2.进入循环生成器，128bit分为4组ki,ki+1,ki+2,ki+3
3.分组1，2，3进行异或，再与固定参数进行异或
4.S盒置换（书中的这部分32bit分组为32bit后又合并回去了?...本菜鸡有些小迷茫）
5.自身与自身的循环左移，循环右移进行异或
6.再与最初的ki进行异或，得到最终的结果
1
2
3
4
5
6

特征总结（一）

由轮密钥生成机制，我们至少可以总结出逆向SM4算法的如下特征：
1.在执行过程中会有一个子程序，以32为周期进行某些运算
2.会出现<<<13和<<<23，还有三到四个进行了各（jing）种（shen）移（fen）位（lie）的后的同一个数一起异或
3.数据段里起码会有个16*16的S盒，和长度为32的固定参数
1
2
3
4

下图与上面对应：
1.

2.
3.置换表

固定参数：

虽然作为一个懒人已经不想翻书了， 但到目前位置依然不足以确定算法，有S盒有异或的算法多了去了
加密过程：

特别注意的算法L变换

其实也很简单，将送入L变换的Input进行如下操作

Output=Input^(Input<<<2)^(Input<<<10)^(Input<<<18)^(Input<<<24)
1

加密流程

（此部分建议对照上图食用）

1.128bit的明文分为四组，每一组32bit
2.在第i轮取出Xi+1,Xi+2,Xi+3,轮密钥进行异或，并送入T变换(先S盒置换再进行L线性变换)
3.将结果与Xi置换后作为Xi+4,Xi+1至Xi+3下标不变
4.最后一轮，将X32，33，34，35顺序转为35，34，33，32
1
2
3
4

特征总结（二）

1.算法中会出现L变换
Input^(Input<<<2)^(Input<<<10)^(Input<<<18)^(Input<<<24)
通常循环左移用算法(Input<<<x)=(Input>>(32-x))|(Input<<x)代替
2.传入加密函数的其中一个值会送进某子程序进行32次的操作
1
2
3
4

IDEA加密算法

参考资料：https://github.com/razvanalex/IDEA-encryption-algorithm

IDEA算法其实在算法难度上并不是很高，主要有以下几个特点

子秘钥生成

IDEA的子秘钥生成比起其他算法先得略随意一点，子秘钥函数将初始的8 * 16bits直接当做第一轮秘钥，剩余的4*16bits作为最终输出前的运算秘钥。

特征：

• 秘钥初始输入128bits，分为八组；最终生成52 * 16bits ，其中8*16bits作为8轮加密函数的秘钥，剩余4 * 16bits作为最终输出前的运算秘钥。
• 轮秘钥生成函数以循环移位运算为主，循环的位数在部分题目中有变化
  
  由于C语言中没有相应的运算则使用：(x << n) | (x >> (s - n)) 等价于 x<<<n 使用IDA反汇编后的样子

加密过程

• 明文使用64bits作为输入，分为4个16bits的分组

• 运算过程中存在两种特殊的运算，a*b mod (216+1) 和 a+b mod(216)

a*b mod (2**16+1) 定义为：
if a == 0:
        return -b + 1;
if b == 0:
        return -a + 1; 
if a!=0 and b!=0:
	#[]为向下取整取整
	if a*b mod 2**16 >= a*b/2**16 :
		return a*b mod 2**16 - [a*b/2**16]
	else:
		return a*b mod 2**16 - a*b/2**16 +1
1
2
3
4
5
6
7
8
9
10
11

经过IDA反编译后：

• 加密过程进行8轮加密，每轮加密使用4 * 16bits的明文输入，6*16的子秘钥输入
• 本轮的加密结果会当做下一轮的输入进行