XXTEA

概述

XXTEA 是由剑桥大学的 David Wheeler 和 Roger Needham 于 1998 年提出的一种轻量级、无专利约束的块密码算法。它是 TEA（微型加密算法）和 XTEA 的改进版，旨在修正前代算法的安全弱点

核心特点

  • 轻量级与高效率：算法核心仅使用加法、异或和移位等基本运算，这使得其代码量非常小，执行速度快，尤其适合在资源受限的嵌入式系统或物联网设备中运行

  • 对称加密：加密和解密使用相同的 128 位密钥

  • 灵活的数据长度：与许多只能处理固定长度数据块的算法不同，XXTEA 可以加密任意长度的数据。其最小块大小为 64 位（两个字）

  • 结构：采用非平衡 Feistel 网络（UFN） 结构

工作原理

XXTEA 的加密过程核心在于一个名为 MX 的混淆函数

  • 分组与轮数：算法将数据按 32 位（一个 “字”）分组。加密的轮数（Rounds） 不是固定的，而是由数据块的数量（n，即字数）动态决定，通常为 6 + 52 / n 轮

  • 核心运算：在每一轮中，算法会利用一个累加的常量 DELTA (0x9E3779B9)，并结合当前数据块及其相邻块，通过 MX 函数进行复杂的位运算（移位、异或、加法），实现数据的混淆和扩散

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @brief XXTEA (Corrected Block TEA) 加解密核心函数
 * 
 * @param v   [输入/输出] 指向 32 位无符号整数数组的指针
 *            加密时：传入明文数据，函数执行后原地变为密文数据
 *            解密时：传入密文数据，函数执行后原地变为明文数据
 *            数据采用小端序（Little-Endian）存储
 * 
 * @param n   [输入] 数组中 32 位字的个数（即数据长度 / 4）
 *            - 若 n > 0：执行加密操作，处理 n 个字
 *            - 若 n < 0：执行解密操作，实际处理 |n| 个字（即取绝对值）
 *            - 注意：|n| 必须 >= 2（即最小数据块为 64 位 / 8 字节），否则算法不会生效
 * 
 * @param k   [输入] 128 位密钥，由 4 个 32 位无符号整数组成 (k[0]~k[3])
 *            密钥同样采用小端序存储
 * 
 * @return    void (无返回值)。处理结果直接覆盖在指针 v 所指向的内存中
 */
void btea(uint32_t *v, int n, uint32_t k[4]);

实战案例

babyre1（XXTEA）

pasted_1787292344729_72yk5b.png

IDA 反编译

pasted_1787293105084_5ka9lz.png

首先输入必须严格 16 个字符，然后调用了 sub_C00(v6,16,&ptr)，进去看看

pasted_1787293259145_57qwon.png

在这里面又调用了 sub_BE0()，负责把一个字符转换成十六进制数值

关键代码是 v1 = a1 - 48;，例如：'4' = 52 - 48 = 4

pasted_1787293377632_9tq7yo.png

接下来重点分析 sub_1180() 函数

  • 首先是长度检查：if ((a2 & 3)==0)，检查变量 a2 的最低两位（bit 0 和 bit 1）是否均为 0，也就是是否为 4 的倍数

  • 再复制数据 memcpy(v8, src, a2);

  • 然后调用 sub_CE0(v7,(a2/-4),a3);，因为前面 sub_C00(v6,16,&ptr) 中，一次取两个字符 v11 = sub_BE0(*v4);v12 = sub_BE0(v4[1]);，所以 a2 = 16 / 2 = 8

  • 最终调用结果是 sub_CE0(v7,-2,key)

这非常像 XXTEA decrypt，因为 XXTEA 的函数通常

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @brief XXTEA (Corrected Block TEA) 加解密核心函数
 * 
 * @param v   [输入/输出] 指向 32 位无符号整数数组的指针
 *            加密时：传入明文数据，函数执行后原地变为密文数据
 *            解密时：传入密文数据，函数执行后原地变为明文数据
 *            数据采用小端序（Little-Endian）存储
 * 
 * @param n   [输入] 数组中 32 位字的个数（即数据长度 / 4）
 *            - 若 n > 0：执行加密操作，处理 n 个字
 *            - 若 n < 0：执行解密操作，实际处理 |n| 个字（即取绝对值）
 *            - 注意：|n| 必须 >= 2（即最小数据块为 64 位 / 8 字节），否则算法不会生效
 * 
 * @param k   [输入] 128 位密钥，由 4 个 32 位无符号整数组成 (k[0]~k[3])
 *            密钥同样采用小端序存储
 * 
 * @return    void (无返回值)。处理结果直接覆盖在指针 v 所指向的内存中
 */
void btea(uint32_t *v, int n, uint32_t k[4]);

因为 a = -2 < 0，所以可以确定这是解密函数

pasted_1787294006456_y3yyjk.png

现在需要去找 Key，但是 IDA 识别参数有问题

pasted_1787296058438_21vj7w.png

在 Linux x64 参数传递规则中

参数 寄存器
第1个 RDI
第2个 RSI
第3个 RDX
第4个 RCX
第5个 R8

而在函数内部，我们的 a3 就是 Key，参数的第三个，也就是去看传给 RDX 寄存器的值即可

pasted_1787296081134_mwvmea.png

这样就找到 Key 了

pasted_1787296292884_yrlcs6.png

提取出来是 c7e0c7e0d7d3f1c6d3c6d3c6ced2d0c4，GBK 编码后是 青青子衿悠悠我心

现在去看解密函数内部，代码中大量出现 1640531527，可以推测这就是常量 DELTA，几乎可以确定这就是 XXTEA 加密算法

特征 伪代码
delta 常量 ✅ 1640531527
MX公式 ✅ 位移+异或+加法
key[4] ✅ a3+4*i
n正负控制 ✅
52/n轮数 ✅

pasted_1787296414022_akqk6c.png

执行完 XXTEA 函数后还去除了 Padding

1
2
3
4
5
6
7
8
9
10
11
12
13
sub_CE0(v7, (a2 / -4), a3);

v9 = v7[a2 - 1];

v7[a2] = 0;

*a5 = a2;

if ( a2 > v9 && v9 <= 4 )
{
    *a5 = a2 - v9;
    v7[a2-v9]=0;
}

代码 v9 = v7[a2 - 1];，因为 a2 = 8，所以 v9 = v7[7]，也就是取解密结果的第 8 个字节

然后 if (a2 > v9 && v9 <= 4)，也就是说程序认为最后一个字节表示 Padding 长度

程序开头给了提示 __printf_chk(1, "Input right flag you can got 'Bingo!' :");

则实际有效数据是 Bingo!，6 个字节，缺少了两个字节，所以最后一个字节需要补齐 0x02

但还是缺少了解密后的数据，查看汇编发现后面调用了 sub_13D0 函数

sub_13D0() 是 CRC16-CCITT 校验函数，作用是对 XXTEA 解密后的数据计算 CRC16，用来进一步验证输入是否正确

代码中多次出现 v4 ^= 0x1021u;，对应着 CRC16-CCITT 的标准多项式 x^16 + x^12 + x^5 + 1

pasted_1787297490042_k3waew.png

继续往后看发现对每个字节都异或 0x17

pasted_1787297807962_08qske.png

对 Bingo! 进行异或 0x17

1
2
3
4
5
6
42 ^ 17 = 55
69 ^ 17 = 7e
6e ^ 17 = 79
67 ^ 17 = 70
6f ^ 17 = 78
21 ^ 17 = 36

明确了 6 个字节，但是 XXTEA 输出的是 8 字节，最后一字节在上面 Padding 确认是 0x02

第七个字节我们可以循环爆破，

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
import xxtea
import hashlib

# 固定密钥
KEY = bytes.fromhex(
    "c7e0c7e0d7d3f1c6d3c6d3c6ced2d0c4"
)

# 目标 MD5 哈希值
TARGET = "5f8243a662cf71bf31d2b2602638dc1d"

# 爆破最后一个字节（0~255）
for x in range(256):
    # XXTEA 待加密的 8 字节明文数据
    data = bytes([
        0x55,
        0x7e,
        0x79,
        0x70,
        0x78,
        0x36,
        x,
        0x02
    ])

    # 使用 XXTEA 加密（不填充）
    cipher = xxtea.encrypt(
        data,
        KEY,
        padding=False
    )

    # 构造 flag 字符串
    flag = "rctf{" + cipher.hex() + "}"

    # 检查 MD5 是否匹配目标
    if hashlib.md5(flag.encode()).hexdigest() == TARGET:
        print(flag)
        break

pasted_1787298673193_7ee2ri.png