selph
selph
Published on 2022-11-29 / 2,035 Visits
0
0

TEA加密算法的实现与逆向分析

TEA算法

“TEA” 的全称为"Tiny Encryption Algorithm" 是1994年由英国剑桥大学的David j.wheeler发明的。

TEA算法也算是一种微型加密算法的。

在安全学领域,TEA(Tiny Encryption Algorithm)是一种分组加密算法,它的实现非常简单,通常只需要很精短的几行代码。

TEA算法使用64位的明文分组和128位的密钥,它使用Feistel分组加密框架,需要进行64轮迭代,但是作者认为32轮已经足够了,所以32轮迭代加密后最后得到的密文就是64位​。

简单的说就是,TEA加密解密是以原文以8字节(64位bit)为一组,密钥16字节(128位bit)为一组,(char为1字节,int为4字节,double为8字节),该算法加密轮次可变,作者建议为32轮,因为被加密的明文为64位,所以最终加密的结果也是64位。

该算法使用了一个神秘常数δ作为倍数,它来源于黄金比率,以保证每一轮加密都不相同。但δ的精确值似乎并不重要,这里TEA把它定义为 ​​**δ=「(√5 - 1)231」,这个δ对应的数指就是0×9E3779B9,所以这个值在TEA加密或者解密中会有用到。**

image

代码实现

#include <iostream>

//加密函数
void encrypt(uint32_t* v, uint32_t* k) {
    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_tea(uint32_t* v, uint32_t* k) {
    uint32_t v0 = v[0], v1 = v[1], sum = 0xC6EF3720, 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 */
        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;
}

使用示例:

int main()
{
    char data[] = "password123456789";
    uint32_t key[] = {0x11111111,0x22222222,0x33333333,0x44444444};

    for (size_t i = 0; i < strlen(data)/8; i++) encrypt((uint32_t*)&data[i*8], key);
    printf("加密后:%s\n", data);

    for (size_t i = 0; i < strlen(data)/8; i++) decrypt((uint32_t*)&data[i*8], key);
    printf("解密后:%s\n", data);

}

IDA伪代码

VS2022 64位 release编译,IDA打开:

加密部分:可以看到,delta值的形式变了

image

解密部分:

image

Tips

  • TEA算法的特征是delta值和16字节的密钥(128位)以及32轮迭代

    • 这些东西可以魔改,如果没魔改过,插件可以识别出该算法,否则需要算法结构手动找
  • x-=0x61c88647和x+=0x9e3779b9,这两个值是等价的

XTEA算法

TEA 算法被发现存在缺陷,作为回应,设计者提出了一个 TEA 的升级版本——XTEA。

XTEA是TEA的扩展,也称做TEAN,它使用与TEA相同的简单运算,同样是一个64位块的Feistel密码,使用128位密钥,建议64轮,但四个子密钥采取不正规的方式进行混合以阻止密钥表攻击

image

代码实现

void encrypt_xtea(uint32_t num_rounds, uint32_t v[2], uint32_t const key[4]) {
	uint32_t 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 decrypt_xtea(uint32_t num_rounds, uint32_t v[2], uint32_t const key[4]) {
	uint32_t 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;
}

使用示例:

int main()
{
    char data[] = "password12345678";
    uint32_t key[] = {0x11111111,0x22222222,0x33333333,0x44444444};

    for (size_t i = 0; i < strlen(data) / 8; i++) encrypt_xtea(32,(uint32_t*)&data[i * 8], key);
    printf("加密后:%s\n", data);

    for (size_t i = 0; i < strlen(data) / 8; i++) decrypt_xtea(32,(uint32_t*)&data[i * 8], key);
    printf("解密后:%s\n", data);
}

IDA伪代码

加密部分:这编译出来居然给把循环平坦铺开了…

image

解密部分:依然是铺开了的循环

image

可以看到,和普通的TEA算法相比,差不多,但是异或的值出现了特征,就是这里计算的两个值,不管是加密还是解密,都出现了&3的操作,

Tips

  • 最显眼的特征:原先TEA算法的v1 + sum​变成了(sum + key[sum & 3])​以及sum + key[(sum>>11) & 3]
  • 可以魔改的点依然是Delta的值,轮数

XXTEA算法

在经历了块加密的问题之后,XTEA再度进化, 变成了支持块加密XXTEA​。

XXTEA是一个非平衡Feistel网络分组密码,在可变长度块上运行,这些块是32位大小的任意倍数(最小64位),使用128位密钥, 是目前TEA系列中最安全的算法,但性能较上两种有所降低。

image

代码实现

#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)            /* 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);
    }
}

使用示例:

int main()
{
    char data[] = "password12345678";
    uint32_t key[] = { 0x11111111,0x22222222,0x33333333,0x44444444 };

    int n = strlen(data)/8;
    // n的绝对值表示v的长度,取正表示加密,取负表示解密
    // v为要加密的数据是两个32位无符号整数
    // k为加密解密密钥,为4个32位无符号整数,即密钥长度为128位

    for (size_t i = 0; i < strlen(data) / 8; i++) btea((uint32_t*)&data[i*8], n, key);
    printf("加密后:%s\n", data);

    for (size_t i = 0; i < strlen(data) / 8; i++) btea((uint32_t*)&data[i*8], -n, key);
    printf("解密后:%s\n", data);
}

IDA伪代码

加密部分:

image

解密部分:

image

Tips

XXTEA算法的解密同样只是对加密算法的数据处理顺序进行倒置,同时加法改减法(减法改加法)

逆向处理思路

这类算法比较常见于逆向中,在分析二进制文件中的算法的时候有几个识别的特征:

  • 可能存在针对64bit以及128bit数字的操作(输入的msg和key)
  • 存在先进行位移,然后异或的类似操作((z>>5^y<<2)​这类混合变换)
  • 前面一个复杂的混合变换的结果可能会叠加到另一个值上,两者相互叠加(Feistel 结构)
  • 获取密钥的时候,会使用某一个常量值作为下标(key[(sum>>11) & 3]​)
  • 会在算法开始定义一个delta,并且这个值不断的参与算法,但是​从来不会受到输入的影响​(delta数值,根据见过的题目中很少会直接使用0x9e3779b9)

解决逆向题大部分出现TEA的场合都是【识别算法->编写对应解密程序】,将上述的算法进行逆推即可得到解密。

参考资料


Comment