TEA 加密算法

请问你今天要来杯茶吗？🍵

1. TEA 加密简介

TEA（Tiny Encryption Algorithm）由剑桥计算机实验室的 Roger Needham 和 David Wheeler 于 1994 年发明。它是一种分组加密算法，速度快，实现简单，占用资源少，常见于嵌入式系统等。一个具体应用是 QQ 和微信的一部分加密协议。

TEA 使用 64 bits (8 bytes) 的明文分组和 128 bits (16 bytes) 的密钥进行加密。采用 Feistel 分组密码结构和迭代形式，将明文分为两部分，每一轮迭代后 “交换” 位置再执行运算。该算法推荐的迭代次数为 64 轮，最少不少于 32 轮。下图示意 TEA 的两轮迭代（或计为一个循环 (Cycle)），其中密钥被分为四个子密钥 $K_i$：

（来源：Tiny Encryption Algorithm - Wikipedia）

阅读说明：（绿色）田字格表示 “加法”，（红色）田字圆表示异或。

TEA 引入了一个神秘常数 $\delta$，每轮迭代使用 $\delta$ 的不同倍数以保证每一轮加密都不相同。这个神秘常数的推荐数值为 $\lfloor \frac{2^{32}}{\phi} \rfloor, \phi=\frac{1+\sqrt{5}}{2}$，以十六进制表示为 0x9E3779B9。这个常数的值可以替换，但采用推荐值可以避免一些算法问题。另外，这个常数在迭代过程中不能更改。

TEA 存在密钥表攻击的问题。为了解决算法的缺陷，设计者提出了更先进的算法：从 XTEA 和 Block TEA，到 XXTEA。

• XTEA：使用与 TEA 相近的运算，但四个子密钥采取不太正规的方式进行混合，密钥的移位、异或与加法运算也经过重新组合。

  

  （来源：XTEA - Wikipedia）

• Block TEA：和 XTEA 同时提出，可以对 32 位的任意整数倍长度的明文块进行加解密操作。该算法将 XTEA 中的轮循函数依次应用于块中的每个字 (32 bits)，并且将它与最左侧的邻字进行加法组合。

• XXTEA：是 Block TEA 的改良版（所以它的英文全称为 “Corrected Block TEA”），换用具有两个输入量的 MX 函数作为轮循函数，在处理块中的每个字时利用了相邻的两个字。

  

  （来源：XXTEA - Wikipedia）

2. TEA 系列算法加密流程分析

2.1 TEA

以下是 David Wheeler 和 Roger Needham 公开发布的 TEA 加密和解密的 C 语言参考程序的改编：

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

#include <stdint.h>

void encrypt (uint32_t v[2], const uint32_t k[4]) {
   uint32_t v0=v[0], v1=v[1], sum=0, i;           /* set up */
   uint32_t delta=0x9E3779B9;                     /* a key schedule constant */
   uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[3];   /* cache key */
   for (i=0; i<32; i++) {                         /* basic cycle start */
       sum += delta;
       v0 += ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
       v1 += ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
   }                                              /* end cycle */
   v[0]=v0; v[1]=v1;
}

void decrypt (uint32_t v[2], const uint32_t k[4]) {
   uint32_t v0=v[0], v1=v[1], sum=0xC6EF3720, i;  /* set up; sum is (delta << 5) & 0xFFFFFFFF */
   uint32_t delta=0x9E3779B9;                     /* a key schedule constant */
   uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[3];   /* cache key */
   for (i=0; i<32; i++) {                         /* basic cycle start */
       v1 -= ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
       v0 -= ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
       sum -= delta;
   }                                              /* end cycle */
   v[0]=v0; v[1]=v1;
}

（来源：Tiny Encryption Algorithm - Wikipedia）

• 在加密函数 encrypt 中，
  • 数组 v 是明文，分为 v[0] 和 v[1] 两部分。数组 k 是密钥，分为 k[0] ~ k[3] 四个子密钥。sum 对应 delta 的不同倍数。
  • 整数类型使用 uint32_t，即无符号的 32 位整数。由于范围限制，sum 会遇到整数溢出的情况，程序截断数值后会改变 sum 的值，对 sum 进行混淆。
  • 接下来是 32 次循环。
  • 循环结束，将密文写回数组 v。
• 在解密函数 decrypt 中，
  • 数组 v 是密文，分为 v[0] 和 v[1] 两部分。数组 k 是密钥，分为 k[0] ~ k[3] 四个子密钥。
  • 解密是加密的逆操作。此时要从最后一次迭代开始逆向迭代，逐步获取明文。这里 sum 的初始值由 (delta << 5) & 0xFFFFFFFF 确定，计算得到 0xC6EF3720。（也可以直接用 delta * 32 得到）

2.2 XTEA

此 C 语言源代码，改编自 David Wheeler 和 Roger Needham 发布到公共领域的参考代码，使用 XTEA 进行加密和解密：

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

#include <stdint.h>

/* take 64 bits of data in v[0] and v[1] and 128 bits of key[0] - key[3] */

void encipher(unsigned int num_rounds, uint32_t v[2], uint32_t const key[4]) {
    unsigned int i;
    uint32_t v0=v[0], v1=v[1], sum=0, delta=0x9E3779B9;
    for (i=0; i < num_rounds; i++) {
        v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
        sum += delta;
        v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
    }
    v[0]=v0; v[1]=v1;
}

void decipher(unsigned int num_rounds, uint32_t v[2], uint32_t const key[4]) {
    unsigned int i;
    uint32_t v0=v[0], v1=v[1], delta=0x9E3779B9, sum=delta*num_rounds;
    for (i=0; i < num_rounds; i++) {
        v1 -= (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
        sum -= delta;
        v0 -= (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
    }
    v[0]=v0; v[1]=v1;
}

（来源：XTEA - Wikipedia）

2.3 XXTEA

以下 C 语言源代码根据 David Wheeler 和 Roger Needham 发布的原始源码改进而来，使用 XXTEA 进行加密和解密：

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

#include <stdint.h>
#define DELTA 0x9e3779b9
#define MX (((z>>5^y<<2) + (y>>3^z<<4)) ^ ((sum^y) + (key[(p&3)^e] ^ z)))

void btea(uint32_t *v, int n, uint32_t const key[4]) {
    uint32_t y, z, sum;
    unsigned p, rounds, e;
    // n是明文块数量，p对应密钥下标索引，e是sum>>2

    if (n > 1) {          /* Coding Part */
      rounds = 6 + 52/n;  // 控制迭代轮数，兼顾效率和安全性
      sum = 0;
      z = v[n-1]; // 明文的最后一个分块
      do {
        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;
      } while (--rounds);
    }
    else if (n < -1) {  /* Decoding Part */
      n = -n;
      rounds = 6 + 52/n;
      sum = rounds*DELTA;
      y = v[0];
      do {
        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;
      } while (--rounds);
    }
}

（来源：XXTEA - Wikipedia）

3. TEA 加密特征识别

• 可能存在针对 64 bits 以及 128 bits 数字的操作（分别是输入的 message 和 key），一般会以 uint32_t 的数组表示

• 存在先移位、后异或的类似操作。比如 ((z >> 5 ^ x <<4) ^ (y << 4 & q >> 5)) 等混合变换就是 XXTEA 加密的特征

• 前面一个复杂的混合变换的结果可能会叠加到另一个值上，两者相互叠加（即 Feistel 结构）

• 获取密钥的时候，会使用某一个常量值作为下标（如 key[(sum >> 11) & 3]），并且出现轮换形式，可以猜测是 XTEA 或 XXTEA。

• 一开始会在算法定义一个 delta（特别是值为 0x9E3779B9 时），并且不断参与算法，但是不会受到输入的影响。

• 常见代码片段：

  • TEA

    1 2 3

    sum += delta; v0 += ((v1 << 4) + k0) ^ (v1 + sum) ^ ((v1 >> 5) + k1); v1 += ((v0 << 4) + k2) ^ (v0 + sum) ^ ((v0 >> 5) + k3);

  • XTEA

    1 2 3

    v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]); sum += delta; v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum >> 11) & 3]);

  • XXTEA

    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

    #define MX ((z >> 5 ^ y << 2) + (y >> 3 ^ z << 4)) ^ ((sum ^ y) + (key[(p & 3) ^ e] ^ z)) sum += delta; e = (sum >> 2) & 3; `` ## 4. TEA 常见魔改方法 1. 更改 `delta` 的值，不再是 `0x9E3779B9` 2. 在每轮的迭代加密中添加可逆运算 3. 在迭代完成后赋值时添加可逆运算 ## 5. TEA 逆向方法 基本思路为通过提取关键数据编写脚本进行解密。 如果反编译出来的算法不是那么标准，那么尽力写一个正向的加密算法出来，然后将测试数据借用目标程序进行加密，通过比对结果来检验我们写的算法的正确性。由于解密是加密的逆运算，因此正向的加密解决了，逆向的解密也不成问题。 在解密 TEA 时，我们需要： - 提取常数 `delta` 的值，一般是一个 4 字节（32 位）大小的整数 - 查看每一轮的迭代加密是否添加了其他可逆运算 - 循环结束赋值回去前对密文有没有进一步加密 TEA 加密最好准备一个解密模板，当遇到 TEA 加密时就可以直接套数据，而不是复现整个解密流程。 ## 6. 习题示例 > [西电 CTF 终端 - 练习场 - 强壮逆向人 - ezTea](https://ctf.xidian.edu.cn/training/2?challenge=521) 本题为源码逆向，要求借助加密函数写出与之配套的解密函数。 源码： ```c #include <stdio.h> #include <stdint.h> void encrypt (uint32_t* v, uint32_t* k) { // 主要加密函数，试着搞定它 uint32_t v0 = v[0], v1 = v[1], sum = 0; uint32_t delta = 0xd33b470; for (int i = 0; i < 32; i++) { sum += delta; v0 += ((v1<<4) + k[0]) ^ (v1 + sum) ^ ((v1>>5) + k[1]); v1 += ((v0<<4) + k[2]) ^ (v0 + sum) ^ ((v0>>5) + k[3]); } v[0] = v0; v[1] = v1; } int main() { uint32_t k[4] = {1, 2, 3, 4}; int8_t input[33] = {0}; scanf("%32s", input); for (int i = 0; i < 32; i+=8) { uint32_t v[2] = {*(uint32_t *)&input[i], *(uint32_t *)&input[i+4]}; encrypt(v, k); for (int j = 0; j < 2; j++) { // 这一段主要是把 v 按单字节输出，另外可以了解一下 “大小端序” 在这题是如何体现的 for (int k = 0; k < 4; k++) { printf("%#x, ", v[j] & 0xff); // x:将无符号整数以十六进制形式输出，字母使用小写；#:表示输出时添加前缀 0x v[j] >>= 8; } } } return 0; }

原题所给 tutorial：

你需要做的是看看 main 函数中给 encrypt 传入的参数是什么，然后去分析加密的行为，并试着写出解密函数。

当你输入正确的 flag 时会输出这样的数据：

1 2 3

0x17, 0x65, 0x54, 0x89, 0xed, 0x65, 0x46, 0x32, 0x3d, 0x58, 0xa9, 0xfd, 0xe2, 0x5e, 0x61, 0x97, 0xe4, 0x60, 0xf1, 0x91, 0x73, 0xe9, 0xe9, 0xa2, 0x59, 0xcb, 0x9a, 0x99, 0xec, 0xb1, 0xe1, 0x7d

脚本：

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

#include <stdint.h>
#include <stdio.h>

void decrypt(uint32_t *v, uint32_t *k) {
  uint32_t delta = 0xd33b470;
  uint32_t v0 = v[0], v1 = v[1], sum = (32) * delta;
  for (int i = 31; i >= 0; i--) {
    v1 -= ((v0 << 4) + k[2]) ^ (v0 + sum) ^ ((v0 >> 5) + k[3]);
    v0 -= ((v1 << 4) + k[0]) ^ (v1 + sum) ^ ((v1 >> 5) + k[1]);
    sum -= delta;
  }
  v[0] = v0;
  v[1] = v1;
}

int main(void) {
  uint32_t k[4] = {1, 2, 3, 4};
  int8_t input[] = {0x17, 0x65, 0x54, 0x89, 0xed, 0x65, 0x46, 0x32,
                    0x3d, 0x58, 0xa9, 0xfd, 0xe2, 0x5e, 0x61, 0x97,
                    0xe4, 0x60, 0xf1, 0x91, 0x73, 0xe9, 0xe9, 0xa2,
                    0x59, 0xcb, 0x9a, 0x99, 0xec, 0xb1, 0xe1, 0x7d};
  for (int i = 0; i < 32; i += 8) {
    uint32_t v[2] = {*(uint32_t *)&input[i], *(uint32_t *)&input[i + 4]};
    decrypt(v, k);
    for (int j = 0; j < 2; j++) {
      for (int k = 0; k < 4; k++) {
        printf("%c", v[j] & 0xff);
        v[j] >>= 8;
      }
    }
  }
}

解密函数完全是加密函数的逆运算，所有的运算顺序都倒置了。

NewStar CTF 2024 - Week2 - Reverse 逆向工程 - drink_tea

先用 DIE 看看

64 位，无壳

然后用 IDA，直接跳到 main 函数处

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

int __fastcall main(int argc, const char **argv, const char **envp)
{
  __int64 v3; // rdx
  __int64 v4; // r8
  __int64 v6; // rdx
  __int64 v7; // r8
  int i; // [rsp+20h] [rbp-28h]
  __int64 v9; // [rsp+28h] [rbp-20h]

  sub_140001070(aPleaseInput, argv, envp);
  sub_140001120("%32s", byte_140004700);
  v9 = -1i64;
  do
    ++v9;
  while ( byte_140004700[v9] );
  if ( v9 == dword_140004078 )
  {
    for ( i = 0; i < dword_140004078; i += 8 )
      sub_140001180(&byte_140004700[i], aWelcometonewst);
    if ( !memcmp(byte_140004700, &unk_140004080, dword_140004078) )
      sub_140001070(aRight, v6, v7);
    else
      sub_140001070(aWrong_0, v6, v7);
    return 0;
  }
  else
  {
    sub_140001070(aWrong, v3, v4);
    return 0;
  }
}

我们分析一下这个程序

• sub_140001120 函数后面出现了很明显的格式化字符串，应该是 scanf。

• aPleaseInput 点进去对应字符串 Please Input:。运行附件程序，发现这个是欢迎语，因此 sub_140001070 函数应为 printf。

• byte_140004700 是用户输入。dword_140004078 点进去发现其数值为 32。结合 for 语句的条件 i += 8，可以知道这里将明文分成四等份（每份 8 字节）来处理。

• unk_140004080 点进去发现疑似为一个数组，用 LazyIDA 提取后发现其长度为 32

• 重头戏是函数 sub_140001180。点进去：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

  __int64 __fastcall sub_140001180(unsigned int *a1, _DWORD *a2) { __int64 result; // rax unsigned int v3; // [rsp+0h] [rbp-38h] unsigned int v4; // [rsp+4h] [rbp-34h] int v5; // [rsp+8h] [rbp-30h] unsigned int i; // [rsp+Ch] [rbp-2Ch] v3 = *a1; v4 = a1[1]; v5 = 0; for ( i = 0; i < 32; ++i ) { v5 -= 0x61C88647; v3 += (a2[1] + (v4 >> 5)) ^ (v5 + v4) ^ (*a2 + 16 * v4); v4 += (a2[3] + (v3 >> 5)) ^ (v5 + v3) ^ (a2[2] + 16 * v3); } *a1 = v3; result = 4i64; a1[1] = v4; return result; }

  发现先移位、后异或的操作，并且使用 32 次循环。

  这里的 delta 似乎是 0x61C88647，但这里是递减。通过计算，发现 v5 -= 0x61C88647 和 v5 += 0x9E3779B9 等价，所以真正的 delta 仍然是 0x9E3779B9。

  推理：

  0x61C88647 + 0x9E3779B9 = 0xFFFFFFFF + 1 = 0x100000000

  由于 delta 是一个 uint32_t 型常量，因此计算结果被截断，实际存储为 0。

  则 0x9E3779B9 = -0x61C88647

  则 v5 = v5 - 0x61C88647 等价于 v5 = v5 + 0x9E3779B9

  这里用到的 a2 数组应该为密钥（因为被分成四份了），对应到 main 函数里是 aWelcometonewst，也就是 WelcomeToNewStar（16 字节）。这里还需要将字符串转成十六字节来让脚本处理。

  可以初步确定是 TEA 算法， 因为在对明文处理时没有在下标计算时使用 v5。

如果使用 IDA 的 Findcrypt 插件，可以直接 一眼丁真，鉴定为：TEA_DELTA_1400011C3

接下来着手写解密脚本（官方 WriteUp）

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

#include <stdio.h>
#include <stdint.h>

// 解密函数
void decrypt (uint32_t* v, uint32_t* k) {
    uint32_t v0 = v[0], v1 = v[1], i;
    uint32_t delta = 0x9E3779B9;
    uint32_t sum = (32)*delta;
    uint32_t k0 = k[0], k1 = k[1], k2 = k[2], k3 = k[3];
    for (i = 0; i < 32; i++) { // 解密时将加密算法的顺序倒过来，+= 变为 -=
        v1 -= ((v0 << 4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
        v0 -= ((v1 << 4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
        sum -= delta;
    }
    v[0] = v0; v[1] = v1; // 解密后再重新赋值
}


unsigned char keys[] = "WelcomeToNewStar";
unsigned char cipher[] = { 0x78,0x20,0xF7,0xB3,0xC5,0x42,0xCE,0xDA,0x85,0x59,0x21,0x1A,0x26,0x56,0x5A,0x59,0x29,0x02,0x0D,0xED,0x07,0xA8,0xB9,0xEE,0x36,0x59,0x11,0x87,0xFD,0x5C,0x23,0x24 };
int main()
{
    unsigned char a;
    uint32_t *v = (uint32_t*)cipher;
    uint32_t *k = (uint32_t*)keys;
    // v 为要加密的数据是 n 个 32 位无符号整数
    // k 为加密解密密钥，为 4 个 32 位无符号整数，即密钥长度为 128 位

    for (int i = 0; i < 8; i += 2)
    {
        decrypt(v + i, k);
        // printf("解密后的数据：%u %u\n", v[i], v[i+1]);
    }

    for (int i = 0; i < 32; i++) {
        printf("%c", cipher[i]);
    }

    return 0;
}

得到

1

flag{There_R_TEA_XTEA_and_XXTEA}