TEA加密算法及其变种详解

0x00 TEA算法概述

TEA (Tiny Encryption Algorithm) 是一种分组加密算法，由剑桥计算机实验室的David Wheeler和Roger Needham在1994年设计。

核心特性：

64位明文分组
128位密钥
使用Feistel分组加密框架
通常进行64轮迭代（32轮已足够安全）
使用黄金比率相关的神秘常数δ = 0x9E3779B9

0x01 标准TEA算法

加密过程

void encrypt(uint32_t* v, uint32_t* key) {
    uint32_t v0=v[0], v1=v[1], sum=0, i;
    uint32_t delta=0x9e3779b9;
    uint32_t k0=key[0], k1=key[1], k2=key[2], k3=key[3];
    
    for(i=0; i<32; i++) {
        sum += delta;
        v0 += ((v1<<4)+k0) ^ (v1+sum) ^ ((v1>>5)+k1);
        v1 += ((v0<<4)+k2) ^ (v0+sum) ^ ((v0>>5)+k3);
    }
    v[0]=v0; v[1]=v1;
}

解密过程

void decrypt(uint32_t* v, uint32_t* key) {
    uint32_t v0=v[0], v1=v[1], sum=0xC6EF3720, i; // 32轮后的sum值
    uint32_t delta=0x9e3779b9;
    uint32_t k0=key[0], k1=key[1], k2=key[2], k3=key[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;
}

0x02 xTEA算法

xTEA是TEA的改进版本，主要改变了子密钥的混合顺序。

加密过程

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], delta=0x9E3779B9, sum=delta*num_rounds;
    
    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;
}

0x03 xxTEA算法

xxTEA进一步改进，允许处理任意长度的数据（不限于4的倍数）。

加密过程

#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;
    
    if(n > 1) {
        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];
                v[p] += MX;
                z = v[p];
            }
            y = v[0];
            z = v[n-1] += MX;
        } while(--rounds);
    }
}

解密过程

void dtea(uint32_t* v, int n, uint32_t const key[4]) {
    uint32_t y, z, sum;
    unsigned p, rounds, e;
    
    if(n > 1) {
        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);
    }
}

0x04 算法特征总结

TEA家族共同特征

128位密钥
特征常量0x9e3779b9
主要加密部分进行移位和异或操作

各变种区别

算法	移位操作	轮数	数据长度要求
TEA	<<4, >>5	32轮	8字节倍数
xTEA	<<4, >>5, >>11	可自定义	8字节倍数
xxTEA	>>5, <<2, >>3, <<4	6+52/n轮	任意长度

0x05 CTF实战案例

案例1：标准TEA解密

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

void decrypt(uint32_t* v, uint32_t* key) {
    uint32_t v0=v[0], v1=v[1], sum=0xC6EF3720, i;
    uint32_t delta=0x9e3779b9;
    uint32_t k0=key[0], k1=key[1], k2=key[2], k3=key[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;
}

int main() {
    uint32_t v[] = {0x5585A199, 0x7E825D68, 0x944D0039, 0x71726943, 
                   0x6A514306, 0x4B14AD00, 0x64D20D3F, 0x9F37DB15};
    uint32_t k[4] = {0x6B696C69, 0x79645F65, 0x696D616E, 0x67626463};
    
    for(int i=0; i<8; i+=2) 
        decrypt(v+i, k);
    
    printf("%s", v);
    return 0;
}

案例2：xTEA变种解密

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

void XTEA_decrypt(uint32_t rounds, uint32_t* v, uint32_t* k) {
    uint32_t delta = 0x12345678; // 注意delta被修改
    uint32_t sum = rounds * delta;
    uint32_t v0 = v[0], v1 = v[1];
    
    for(int i=0; i<rounds; i++) {
        v1 -= (((v0<<4)^(v0>>5))+v0) ^ (sum+k[(sum>>11)&3]);
        sum -= delta;
        v0 -= (((v1<<4)^(v1>>5))+v1) ^ (sum+k[sum&3]);
    }
    v[0]=v0; v[1]=v1;
}

int main() {
    uint32_t rounds = 32;
    uint32_t v[2][2] = {{0x0ec311f0, 0x45c79af3}, {0xedf5d910, 0x542702cb}};
    uint32_t k[4] = {0x00010203, 0x04050607, 0x08090a0b, 0x0c0d0e0f};
    
    XTEA_decrypt(rounds, v[0], k);
    XTEA_decrypt(rounds, v[1], k);
    
    printf("%x-%x\n", v[0][0], v[0][1]);
    printf("%x-%x\n", v[1][0], v[1][1]);
}

案例3：xxTEA解密

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

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

void xxtea_decrypt(uint32_t* v, int n, uint32_t* key) {
    uint32_t y, z, sum;
    unsigned p, rounds, e;
    
    if(n > 1) {
        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);
    }
}

int main() {
    uint32_t cipher[] = {0xE74EB323, 0xB7A72836, 0x59CA6FE2, 0x967CC5C1, 
                        0xE7802674, 0x3D2D54E6, 0x8A9D0356, 0x99DCC39C};
    uint32_t key[] = {1, 2, 3, 4};
    
    xxtea_decrypt(cipher, 8, key);
    
    for(int i=0; i<8; i++) {
        printf("%c", (char)cipher[i]);
    }
}

0x06 识别技巧

查找特征常量：0x9E3779B9是TEA家族最明显的特征
分析移位操作：
- TEA：<<4, >>5
- xTEA：<<4, >>5, >>11
- xxTEA：>>5, <<2, >>3, <<4
轮数判断：
- TEA：固定32轮
- xTEA：可自定义轮数
- xxTEA：6+52/n轮

0x07 总结

TEA算法及其变种在CTF逆向题目中非常常见，掌握它们的标准实现和特征对于快速识别和解题至关重要。在实际分析中，遇到特征常量0x9E3779B9时，应优先考虑TEA家族算法，然后根据具体的移位操作和轮数判断具体变种。