TEA系加密算法逆向分析

TEA

基本简介

TEA（Tiny Encryption Algorithm）是一种分组加密算法，它的实现非常简单，通常只需要很精短的几行代码。TEA 算法最初是由剑桥计算机实验室的 David Wheeler 和 Roger Needham 在 1994 年设计的。

TEA 算法使用 64 位的明文分组和 128 位的密钥，它使用 Feistel 分组加密框架，建议的迭代次数为 32 轮。该算法使用了一个常数 δ 作为倍数，它来源于黄金比率，以保证每一轮加密都不相同。但 δ 的精确值似乎并不重要，这里 TEA 把它定义为 δ=「(√5 - 1)231」（也就是程序中的 0×9E3779B9）。

之后 TEA 算法被发现存在缺陷，作为回应，设计者提出了一个 TEA 的升级版本——XTEA（有时也被称为“tean”）。XTEA 跟 TEA 使用了相同的简单运算，但它采用了截然不同的顺序，为了阻止密钥表攻击，四个子密钥（在加密过程中，原 128 位的密钥被拆分为 4 个 32 位的子密钥）采用了一种不太正规的方式进行混合，但速度更慢了。

常数：0x9e3779b9
DELTA：算是该加密算法的特征值，为黄金分割数（(√5 - 1)231」）/2与232的乘积，该值不影响算法，但能很好的避免一些算法错误。该数值在其他算法中也常有运用。
这个值换成任何一个值，都不影响算法的安全性

TEA算法每一次可以操作64bit，采用128bit作为key，算法采用迭代的形式，推荐的迭代轮数是64轮，最少32轮。

加密流程

![[assets/1197364-20201020100219717-1336396898.png]]

代码实现

加密函数

C - 20 lines

void encrypt(uint32_t* data, uint32_t* Key) {

    //分别加密数组中的前四个字节与后4个字节,4个字节为一组每次加密两组
    unint32_t v0 = Data[0];
    unint32_t v1 = Data[1];

    unint32_t sum = 0;
    unint32_t delta = 0x9E3779B9;
    
    //总共加密32轮
    for (int i = 0; i < 32; i++) {
        sum += delta;
        v0 += ((v1 << 4) + Key[0]) ^ (v1 + sum) ^ ((v1 >> 5) + Key[1]);
        v1 += ((v0 << 4) + Key[2]) ^ (v0 + sum) ^ ((v0 >> 5) + Key[3]);
    }
    
    //最后加密的结果重新写入到数组中
    data[0] = v0;
    data[1] = v1;
}

解密函数

解密思路：
x += xxx
y += xxx 这两个公式总共是执行了 32 轮，可以记作为
(x += xxx)32
(y += xxx)32
那么解密的适合肯定也是执行 32 轮，每次递减，且顺序变换过来
(y -= xxx)
(x -= xxx)
其中这里的 xxx 就是异或的公式，根据其特性我们不需要改公式中的内容
所以解密算法如下：

C - 25 lines

void decrypt(uint32_t* data, uint32_t* Key) {

    //分别加密数组中的前四个字节与后4个字节,4个字节为一组每次加密两组
    uint32_t v0 = data[0];
    uint32_t v1 = data[1];

    uint32_t sum = 0;
    uint32_t delta = 0x9E3779B9;

	//注意这里,sum = 32轮之后的黄金分割值. 因为我们要反序解密.
    sum = delta << 5;   
    
    //总共加密32轮 那么反序也解密32轮
    for (int i = 0; i < 32; i++) {
    
        // 先将y解开 然后参与运算在解x
        v0 -= ((v1 << 4) + Key[2]) ^ (v1 + sum) ^ ((v1 >> 5) + Key[3]);
        v1 -= ((v0 << 4) + Key[0]) ^ (v0 + sum) ^ ((v0 >> 5) + Key[1]);
        sum -= delta;
    }
    
    //最后加密的结果重新写入到数组中
    data[0] = v0;
    data[1] = v1;
}

主函数

C - 13 lines

int main() {
    uint32_t Data[3] = { 0x4443,0x4241,0x4847,0x4645,0x0 };
    printf("待加密的数值 = %s\r\n", (char*)Data);

    uint32_t key[4] = { 0x11223344,0x55667788,0x99AABBCC,0xDDEEFF11 };

    //Encrypt每次只是加密4字节数组中的两组(也就是每次加密8个字节) 如果你数据多.可以来个for循环来循环加密,但是Entrypt内部还有32次循环,所以速度上还是会有点影响.
    Encrypt(Data, key);
    printf("加密后的数值 = %s\r\n", (char*)Data);
    Decrypt(Data, key);
    printf("解密后的数值 = %s\r\n", (char*)Data);
}

完整代码

C - 52 lines

#include <stdio.h>
void Encrypt(uint32_t* v, uint32_t key) {
    //分别加密数组中的前四个字节与后4个字节,4个字节为一组每次加密两组
    uint32_t x = v[0],y = v[1];
	uint32_t sum=0,i;
    uint32_t delta = 0x9E3779B9;
    uint32_t k0=key[0],k1=key[1],k2=key[2],k3=key[3];
    //总共加密32轮
    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(long* EntryData, long* Key) {
    //分别加密数组中的前四个字节与后4个字节,4个字节为一组每次加密两组 
    uint32_t v0 = v[0], v1 = v[1]; 
    uint32_t sum = 0x9E3779B9 * 32; // sum = 32轮之后的黄金分割值 
    uint32_t delta = 0x9E3779B9; 
    uint32_t k0 = key[0], k1 = key[1], k2 = key[2], k3 = key[3]; 
    
    // 总共解密32轮 
    for (int 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 data[2] = {1, 2};   // 待加密的数据 
    uint32_t key[4] = {0x12345678, 0x9ABCDEF0, 0x13579BDF, 0x2468ACE0}; // 加密密钥 
    printf("待加密的数值：%u %u\n", data[0], data[1]); 
    
    // Encrypt加密 
    Encrypt(data, key); 
    printf("加密后的数值：%u %u\n", data[0], data[1]); 
    
    // Decrypt解密 
    Decrypt(data, key); 
    printf("解密后的数值：%u %u\n", data[0], data[1]); 
    
    return 0;
}

例题

2024Moectf

XTEA

置换v0和v1的地位
为什么TEA系列的算法要单独拿出来讲
- TEA这个简单算法在中国如此有名，主要因为腾讯软件在大量协议和本地数据中使用这个算法。
  
  网上很多人甚至直接将TX的加密算法称为TEA算法。
DELTA：0x9e3779b9
左移4 或者右移5
普通TEA：
传入的数据分为两组进行加密，都为4字节
传入的数据称为v1和v0

基本简介

XTEA是TEA的扩展，与TEA相比，XTEA使用更长的密钥和更多的迭代轮数，从而提高了安全性。XTEA使用128位密钥和64位块大小。而TEA使用64位密钥和64位块大小。

![[assets 1/921830_48K7JHRW383FZWR 3.png]]

C - 11 lines

void encrypt(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;
}

解密函数

C - 10 lines

void decrypt(unsigned int num_rounds,unit32_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;
}

主函数

C - 6 lines

int main(){
	uint32_t v[2]={1,2};
	uint32_t const k[4]={2,2,3,4};
	unsigned int r=32;
	
}

完整代码

C - 24 lines

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

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是TEA的升级版，增加了更多的密钥表，移位和异或操作等等。

C - 24 lines

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

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;
}

例题

2024moectf

2024YLCTF [Round 2] 三点几啦饮茶先

XXTEA

XXTEA，又称Corrected Block TEA，是XTEA的升级版

DELTA：算是该加密算法的特征值，为黄金分割数（5对-2）2与232的乘积，该值不影响算法，但能很好的避免一些算法错误。该数值在其他算法中也常有运用。
MX：对照图例。MIX值（混合，混淆），在本例中请对照加密图解，算是算法的一部分。
n：对应明文或密文的数组长度。
v：明文或密文数组。对应图解中的x
key：密钥数组。对应图解中的k
rounds：加密循环的轮数
sum：对应图解中的D
e：对应图解中的（D>>2）
p：本例中用作明文或密文数组的索引
r：参照代码，类比p&3（该符号在图中而不在代码中）。3的二进制编码为11，任何数与其运算后，可能产生（00，01，10，11），对应（0，1，2，3）
图解符号：
- 方框：相加盒。将指向该盒的变量进行相加。
- 圆圈：异或盒。将指向该盒的变量进行异或
左移如何换算成乘法运算

![[assets/1586953-20220307161956986-999517630.png]]

C - 74 lines

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

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

void encrypt(uint32_t *v, int n, uint32_t const key[4]) {
    uint32_t y, z, sum;
    unsigned p, rounds, e;
    if (n < 2) return;
    rounds = 6 + 52/n;
    sum = 0;
    z = v[n-1];
    do {
        sum += 0x9E3779B9;
        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);
}

void decrypt(uint32_t *v, int n, uint32_t const key[4]) {
    uint32_t y, z, sum;
    unsigned p, rounds, e;
    if (n < 2) return;
    rounds = 6 + 52/n;
    sum = rounds * 0x9E3779B9;
    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 -= 0x9E3779B9;
    } while (--rounds);
}

int main() {
    uint32_t data[] = {1, 2, 3, 4};  // 待加密的数据
    uint32_t key[4] = {0x12345678, 0x9ABCDEF0, 0x13579BDF, 0x2468ACE0};  // 密钥
    int n = sizeof(data) / sizeof(data[0]);

    printf("待加密的数据：\n");
    for (int i = 0; i < n; i++) {
        printf("%u ", data[i]);
    }
    printf("\n");

    // 加密数据
    encrypt(data, n, key);

    printf("加密后的数据：\n");
    for (int i = 0; i < n; i++) {
        printf("%u ", data[i]);
    }
    printf("\n");

    // 解密数据
    decrypt(data, n, key);

    printf("解密后的数据：\n");
    for (int i = 0; i < n; i++) {
        printf("%u ", data[i]);
    }
    printf("\n");

    return 0;
}

特征识别

delta的值：通常delta的值是0x9e3779b9
tea每轮的加密特征，左移4、异或、右移5，以及一个变量sum会迭代+=delta32次。

左移4也可以替换为乘以16

XTEA每轮的加密特征，左移4，右移5，与TEA不同的是对key和sum的处理，key[(sum>>1)&3]，key[sum&3]。

XXTEA每轮的加密特征
sum+=delta; e=(sum>>2)&3;

((z>>5^y<<2)+(y>>3^z<<4))^((sum^y)+(key[(p&3)^e]^z))

魔改方法

1.将delta的值进行修改，并不再是默认的0x9e3779b9
2.在每轮的迭代加密中添加可逆运算。
3.在迭代完之后赋值回去的时候，添加可逆运算。

CBC模式：其实主要就是将明文分组与前一个密文分组进行异或运算，然后再进行加密，对于第一组的话就设置一个初始值来和第一组明文异或。

比如：（CBC模式循环加密64字节，每次循环加密8字节（v8和v1各4字节））

C - 12 lines

while(a3>7){
	v5=get_data(a2);
	data1^=v5;
	v6=get_data(a2+4);
	data2^=v6;
	tea(&data1,k);
	to_dst(a1,data1);
	to_dst(a1+4,data2);
	a2+=8;
	a1+=8;
	a3-=8;
}

每一轮是get_data取我们v0和v1，data1，data2和v0，v1异或，异或之后的data1和data2传入指针进行tea加密，之后再将解密之后的赋值回我们的v0和v1。

在理解了CBC模式的TEA之后，我们该如何去逆向它呢，首先我们是有每轮加密后的v0和v1的，就是加密数据，TEA我们也是能够逆向的，那么就剩下逆向每轮的data1^=v0和data2^=v1了，而后面的轮数的data1和data2是会被我们的加密结果更新的，我们只有第一轮的data1和data2，那么我们就从这个地方下手，先解密第一轮，得到第一轮的v0和v1明文，再重新去加密更新data1和data2用于下一轮的解密。

通过提取关键数据编写脚本进行解密

例题

TEA

XTEA

XXTEA

魔改TEA

2024极客大挑战

后言

参考：
参考：

0 comments

Anonymous

Error: Not Found.

Markdown is supported

Be the first person to leave a comment!

≡