微型加密算法及其逆向分析

Posted on

TEA、XTEA、XXTEA

关于TEA系列算法

微型加密算法（Tiny Encryption Algorithm，TEA）是一种易于描述和执行的块密码，通常只需要很少的代码就可实现。其设计者是David Wheeler、Roger Needham

TEA的分组长度为64位，密钥长度为128位，采用Feistel网络，建议32次循环加密即64轮

XTEA是TEA的扩展，同样是一个64位块的Feistel密码，使用128位密钥，建议64轮

XXTEA是一个非平衡Feistel网络分组密码，在可变长度块上运行，这些块是32位大小的任意倍数（最小64位），使用128位密钥

TEA系列算法典型特征是采用密钥调度常数0x9e3779b9

加解密实现

TEA加解密实现

img

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
#include <stdio.h>
void encrypt(unsigned int* v, unsigned int* key) {
  unsigned int l = v[0], r = v[1], sum = 0, delta = 0x9e3779b9;
  for (size_t i = 0; i < 32; i++) {
    sum += delta;
    l += ((r << 4) + key[0]) ^ (r + sum) ^ ((r >> 5) + key[1]);
    r += ((l << 4) + key[2]) ^ (l + sum) ^ ((l >> 5) + key[3]);
  }
  v[0] = l;
  v[1] = r;
}

void decrypt(unsigned int* v, unsigned int* key) {
  unsigned int l = v[0], r = v[1], sum = 0, delta = 0x9e3779b9;
  sum = delta *32;
  for (size_t i = 0; i < 32; i++) {
    r -= ((l << 4) + key[2]) ^ (l + sum) ^ ((l >> 5) + key[3]);
    l -= ((r << 4) + key[0]) ^ (r + sum) ^ ((r >> 5) + key[1]);
    sum -= delta;
  }
  v[0] = l;
  v[1] = r;
}

int main(int argc, char const *argv[])
{
    //test
    unsigned int v[2]={1,2},key[4]={1,2,3,4};
    printf("%u,%u\n",v[0],v[1]);
    encrypt(v,key);
    printf("%u,%u\n",v[0],v[1]);
    decrypt(v,key);
    printf("%u,%u\n",v[0],v[1]);
    return 0;
}

XTEA加解密实现

img

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
#include <stdio.h>
void encrypt(unsigned int* v, unsigned int* key) {
  unsigned int l = v[0], r = v[1], sum = 0, delta = 0x9e3779b9;
  for (size_t i = 0; i < 32; i++) {
    l += (((r << 4) ^ (r >> 5)) + r) ^ (sum + key[sum & 3]);
    sum += delta;
    r += (((l << 4) ^ (l >> 5)) + l) ^ (sum + key[(sum >> 11) & 3]);
  }
  v[0] = l;
  v[1] = r;
}

void decrypt(unsigned int* v, unsigned int* key) {
  unsigned int l = v[0], r = v[1], sum = 0, delta = 0x9e3779b9;
  sum = delta * 32;
  for (size_t i = 0; i < 32; i++) {
    r -= (((l << 4) ^ (l >> 5)) + l) ^ (sum + key[(sum >> 11) & 3]);
    sum -= delta;
    l -= (((r << 4) ^ (r >> 5)) + r) ^ (sum + key[sum & 3]);
  }
  v[0] = l;
  v[1] = r;
}

int main(int argc, char const *argv[])
{
    //test
    unsigned int v[2]={1,2},key[4]={1,2,3,4};
    printf("%u,%u\n",v[0],v[1]);
    encrypt(v,key);
    printf("%u,%u\n",v[0],v[1]);
    decrypt(v,key);
    printf("%u,%u\n",v[0],v[1]);
    return 0;
}

XXTEA加解密实现

img

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
#include <stdbool.h>
#include <stdio.h>
#define MX \
  ((z >> 5 ^ y << 2) + (y >> 3 ^ z << 4) ^ (sum ^ y) + (k[p & 3 ^ e] ^ z))
bool btea(unsigned int* v, int n, unsigned int* k) {
  unsigned int z = v[n - 1], y = v[0], sum = 0, e, DELTA = 0x9e3779b9;
  unsigned int p, q;
  if (n > 1) { /* Coding Part */
    q = 6 + 52 / n;
    while (q-- > 0) {
      sum += DELTA;
      e = (sum >> 2) & 3;
      for (p = 0; p < n - 1; p++)
        y = v[p + 1], z = v[p] += MX;
      y = v[0];
      z = v[n - 1] += MX;
    }
    return 0;
  } else if (n < -1) { /* Decoding Part */
    n = -n;
    q = 6 + 52 / n;
    sum = q * DELTA;
    while (sum != 0) {
      e = (sum >> 2) & 3;
      for (p = n - 1; p > 0; p--)
        z = v[p - 1], y = v[p] -= MX;
      z = v[n - 1];
      y = v[0] -= MX;
      sum -= DELTA;
    }
    return 0;
  }
  return 1;
}

int main(int argc, char const* argv[]) {
  // test
  unsigned int v[2] = {1, 2}, key[4] = {1, 2, 3, 4};
  printf("%u,%u\n", v[0], v[1]);
  btea(v, 2, key);
  printf("%u,%u\n", v[0], v[1]);
  btea(v, -2, key);
  printf("%u,%u\n", v[0], v[1]);
  return 0;
}

XXTEA逆向分析

文件来源：2019RCTF babyre

该题大致为输入一个16位字符串经过多次变换最终输出Bingo! 即可，由于题目的原因出现多解，故还需满足md5(rctf{flag})==5f8243a662cf71bf31d2b2602638dc1d，此处不作解释，由于主要是讲解XXTEA的逆向分析，其他过程暂且不细说，我们看到其中最关键的加密函数sub_55A0DF892CE0。

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
signed __int64 __fastcall sub_55A0DF892CE0(int *a1, signed int a2, __int64 a3)
{
  v3 = a3;
  v4 = a2;
  v5 = *a1;
  v43 = a2;
  if ( a2 > 1 )
  {
    v6 = a2 - 1;
    v7 = &a1[a2 - 1];
    v8 = 0;
    v9 = *v7;
    v10 = ((a2 - 4) & 0xFFFFFFFE) + 2;
    v45 = 0x9E3779B9 * (52 / a2) - 0x4AB325AA;
    do
    {
      v8 -= 0x61C88647;
      v11 = v8 >> 2;
      if ( v43 <= 3 )
      {
        v14 = 0;
      }
      else
      {
        v12 = *a1;
        v13 = a1;
        v14 = 0;
        do
        {
          v15 = v13[1];
          v13 += 2;
          v16 = (v9 ^ *(_DWORD *)(v3 + 4LL * (((unsigned __int8)v14 ^ (unsigned __int8)v11) & 3))) + (v15 ^ v8);
          v17 = v14 + 1;
          v14 += 2;
          v18 = v12 + ((((v9 >> 5) ^ 4 * v15) + ((v15 >> 3) ^ 16 * v9)) ^ v16);
          v12 = *v13;
          *(v13 - 2) = v18;
          v9 = v15
             + (((4 * v12 ^ (v18 >> 5)) + (16 * v18 ^ (v12 >> 3))) ^ ((v12 ^ v8)
                                                                    + (v18 ^ *(_DWORD *)(v3
                                                                                       + 4LL
                                                                                       * (((unsigned __int8)v11 ^ v17) & 3)))));
          *(v13 - 1) = v9;
        }
        while ( v10 != v14 );
      }
      v19 = &a1[v14];
      do
      {
        v20 = v19[1];
        v21 = v11 ^ v14++;
        ++v19;
        v22 = *(v19 - 1)
            + (((v9 ^ *(_DWORD *)(v3 + 4LL * (v21 & 3))) + (v20 ^ v8)) ^ ((16 * v9 ^ (v20 >> 3)) + ((v9 >> 5) ^ 4 * v20)));
        *(v19 - 1) = v22;
        v9 = v22;
      }
      while ( v6 > v14 );
      v9 = *v7
         + (((v22 ^ *(_DWORD *)(v3 + 4LL * (((unsigned __int8)v6 ^ (unsigned __int8)v11) & 3))) + (*a1 ^ v8)) ^ ((4 * *a1 ^ (v22 >> 5)) + (16 * v22 ^ ((unsigned int)*a1 >> 3))));
      *v7 = v9;
    }
    while ( v8 != v45 );
    return 0LL;
  }
  result = 1LL;
  if ( a2 < -1 )
  {
    v24 = -a2;
    v25 = 0x9E3779B9 * (52 / v24 + 6);
    if ( v25 )
    {
      v26 = &a1[v24 - 1];
      v27 = ~v4;
      v44 = &a1[~v4];
      v28 = ~v4 - 2 - ((~v4 - 3) & 0xFFFFFFFE);
      do
      {
        v29 = v25 >> 2;
        if ( v27 <= 2 )
        {
          v31 = v27;
        }
        else
        {
          v30 = v44;
          v31 = v27;
          v32 = *v44;
          do
          {
            v33 = *(v30 - 1);
            v30 -= 2;
            v34 = v32;
            v32 = *v30;
            v35 = ((v5 ^ v25) + (v33 ^ *(_DWORD *)(v3 + 4LL * (((unsigned __int8)v31 ^ (unsigned __int8)v29) & 3)))) ^ ((4 * v5 ^ (v33 >> 5)) + ((v5 >> 3) ^ 16 * v33));
            v36 = v31 - 1;
            v31 -= 2;
            v37 = v34 - v35;
            v38 = *v30;
            v30[2] = v37;
            v5 = v33
               - (((16 * v38 ^ (v37 >> 3)) + ((v32 >> 5) ^ 4 * v37)) ^ ((v32 ^ *(_DWORD *)(v3
                                                                                         + 4LL
                                                                                         * (((unsigned __int8)v29 ^ v36) & 3)))
                                                                      + (v25 ^ v37)));
            v30[1] = v5;
          }
          while ( v28 != v31 );
        }
        v39 = &a1[v31];
        do
        {
          v40 = *(v39 - 1);
          --v39;
          v5 = v39[1]
             - (((v5 ^ v25) + (v40 ^ *(_DWORD *)(v3 + 4LL * (((unsigned __int8)v29 ^ (unsigned __int8)v31) & 3)))) ^ (((v5 >> 3) ^ 16 * v40) + ((v40 >> 5) ^ 4 * v5)));
          v39[1] = v5;
          --v31;
        }
        while ( v31 );
        v41 = *a1
            - (((((unsigned int)*v26 >> 5) ^ 4 * v5) + (16 * *v26 ^ (v5 >> 3))) ^ ((*(_DWORD *)(v3 + 4LL * (v29 & 3)) ^ *v26)
                                                                                 + (v25 ^ v5)));
        v42 = v25 == 0x9E3779B9;
        v25 += 0x61C88647;
        v5 = v41;
        *a1 = v41;
      }
      while ( !v42 );
    }
    return 0LL;
  }
  return result;
}

我们可以看到反编译的伪代码也是十分清晰的，纵观整个函数，整个函数过程都围绕着0x9E3779B9这个魔数，相信很多人都有似曾相识的感觉，没错！该函数与上文的XXTEA加解密实现结构基本相同，实现了XXTEA加解密。接下来我们看到函数的调用

1
sub_55A0DF892CE0(v, -(v10 >> 2), key);  // stea(v,-2,key)

结合其他有关信息可以简单看出函数参数v为两个32位无符号数， -(v10 >> 2)的值为-2，key为128位密钥，它们是0xE0C7E0C7, 0xC6F1D3D7, 0xC6D3C6D3, 0xC4D0D2CE，此处调用了XXTEAdecode对两个32位无符号数进行解密，解密结果与之后的常量异或后比较判断

整个题目的核心算法就是XXTEA，只要识别出该算法，那么逆向将变得非常简单，逻辑无非就是输入一个16进制字符串之后hexencode，得到一个64位无符号数（即2个32位无符号数），然后将之2个32位无符号数xxteadecrypt得到新的64位无符号数，此处要求最后一个字节的值小于0x4，并将第（8-最后一个字节的值+1）字节的值置为00，而后将之经下一个函数进行一些位操作验证结果是否等于0x69e2,这一步并不改变原有值无视之，最终验证按字节与0x17异或出来结果是否为Bingo!，结合上面猜测第7字节的值为00，最后一个字节值为0x02，且md5(rctf{flag})==5f8243a662cf71bf31d2b2602638dc1d，由此可以确定最终解密后的64位无符号数的值为0x02XX367870797e55(小端序)，直接写脚本就可以爆破次高8位即可，依次就可以得到该题的flag了

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
90
91
92
93
94
95
96
97
#include <openssl/md5.h>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;
// -lcrypto
string MD5(const string& src) {
  MD5_CTX ctx;

  string md5_string;
  unsigned char md[16] = {0};
  char tmp[33] = {0};

  MD5_Init(&ctx);
  MD5_Update(&ctx, src.c_str(), src.size());
  MD5_Final(md, &ctx);

  for (int i = 0; i < 16; ++i) {
    memset(tmp, 0x00, sizeof(tmp));
    sprintf(tmp, "%02X", md[i]);
    md5_string += tmp;
  }
  return md5_string;
}

string aaa(unsigned int* v) {
  string str;
  for (size_t i = 0; i < 2; i++) {
    for (size_t j = 0; j < 8; j += 2) {
      unsigned char cur = v[i] & 0xff;
      str += ((cur & 0xf0) >> 4) < 10 ? (((cur & 0xf0) >> 4) + 0x30)
                                      : (((cur & 0xf0) >> 4) + 0x57);
      str += (cur & 0x0f) < 10 ? ((cur & 0x0f) + 0x30) : ((cur & 0x0f) + 0x57);
      v[i] >>= 8;
    }
  }
  return str;
}

#define MX \
  ((z >> 5 ^ y << 2) + (y >> 3 ^ z << 4) ^ (sum ^ y) + (k[p & 3 ^ e] ^ z))
bool btea(unsigned int* v, int n, unsigned int* k) {
  unsigned int z = v[n - 1], y = v[0], sum = 0, e, DELTA = 0x9e3779b9;
  unsigned int p, q;
  if (n > 1) { /* Coding Part */
    q = 6 + 52 / n;
    while (q-- > 0) {
      sum += DELTA;
      e = (sum >> 2) & 3;
      for (p = 0; p < n - 1; p++)
        y = v[p + 1], z = v[p] += MX;
      y = v[0];
      z = v[n - 1] += MX;
    }
    return 0;
  } else if (n < -1) { /* Decoding Part */
    n = -n;
    q = 6 + 52 / n;
    sum = q * DELTA;
    while (sum != 0) {
      e = (sum >> 2) & 3;
      for (p = n - 1; p > 0; p--)
        z = v[p - 1], y = v[p] -= MX;
      z = v[n - 1];
      y = v[0] -= MX;
      sum -= DELTA;
    }
    return 0;
  }
  return 1;
}

int main() {
  // 55 7e 79 70 78 36 xx 02
  unsigned int t[2] = {0x70797e55, 0x02003678};
  unsigned int v[2] = {0, 0};
  unsigned int key[4] = {0xE0C7E0C7, 0xC6F1D3D7, 0xC6D3C6D3, 0xC4D0D2CE};
  string flagmd5 = "5F8243A662CF71BF31D2B2602638DC1D";

  for (unsigned long long i = 0x0; i <= 0xff; i += 0x1) {
    v[0] = t[0];
    v[1] = t[1] | (i << 16);
    string flag = "";
    flag += "rctf{";
    btea(v, 2, key);
    flag += aaa(v);
    flag += "}";
    cout << flag << endl;
    if (MD5(flag) == flagmd5) {
      cout << "success!" << endl;
      cout << flag << endl;
      return 0;
    }
  }
  return 0;
}

TX TEA魔改算法

TX 将TEA算法魔改成16轮（TEA保密的最低要求）并且广泛应用

相关内容可以看这里腾讯TEA加密算法

主要就是将加密轮次改为16轮，并且采用改进的CBC模式加密

总结

对于TEA系列算法的识别只要依据常数0x9e3779b9并且其相关加密结构就可以很容易判断是TEA、XTEA亦或XXTEA，之后只要找到其密文以及加密密钥辅以以上加解密实现代码就可以很快解密了，TEA算法在逆向分析中，IDA反编译以后一般都是比较清晰的，只要有一定的了解就能轻而易举的识别出对应算法，而后动态调试验证即可，至于findcrypto3插件识别也是依据常数识别的，所以只要知道这个特征即可。

附件

TEA系列算法源码

2019RCTF babyre

参考文献

Tiny Encryption Algorithm

XTEA

XXTEA

TEA、XTEA、XXTEA加密解密算法

加密与解密第四版—TEA算法

0%