Featured image of post Tea

Tea

逆向算法复习第二弹:Tea系列算法

Tea算法

“TEA” 的全称为”Tiny Encryption Algorithm” 由于实现简单,加密安全(QQ和微信的一些协议中就是使用的Tea加密),深受ctf出题人的喜爱。因此tea算法成为ctf REer的一种必学算法。TEA算法使用64位的明文分组和128位的密钥,它使用Feistel分组加密框架,需要进行 64 轮迭代。该算法使用了一个神秘常数δ作为倍数,它来源于黄金比率2654435769 (0x9E3779B9),以保证每一轮加密都不相同。

Tea算法实现:

加密

加密代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
c
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;
}

解密

加密过程很清晰,那么解密过程我们只要把它倒过来写就好

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
}

不难看出其实Tea算法有很鲜明的特征:

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

即32或64轮加密,以及有一个关键的delta值,难点主要是如何从出题人魔改过的代码中找到v0,v1,delta以及加密过程。

解密脚本可以参考知识库中现有的脚本,改改加密方式,delta值这些就好

脚本:

 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
c
//tea
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
void Decrypt(uint32_t* data, uint32_t* key)
{
    uint32_t v0 = data[0], v1 = data[1];
    uint32_t delta = 0x9e3779b9;
    uint32_t sum = delta * 32;

    for (int i = 0; i < 32; i++)
    {
        v1 -= ((v0 << 4) + key[2]) ^ (v0 + sum) ^ ((v0 >> 5) + key[3]);
        v0 -= ((v1 << 4) + key[0]) ^ (v1 + sum) ^ ((v1 >> 5) + key[1]);
        sum -= delta;
    }

    data[0] = v0;
    data[1] = v1;
}

int main()
{
    uint32_t encryptedData[] = { 0xc873914f, 0x4a628600, 0x20c77a1c, 0x1a877aaa, 0xd6faa982, 0x60d1c964, 0xb9884c32, 0x2a08a862, 0xc74a0036, 0x8f2ee196, 0xef08a6a9, 0xa3850896 };
    uint32_t key[] = { 0x11111111, 0x11111111, 0x11111111, 0x11111111 };

    int dataSize = sizeof(encryptedData) / sizeof(encryptedData[0]);
    for (int i = 0; i < dataSize; i += 2)
    {
        Decrypt(&encryptedData[i], key);
    }
    int decryptedSize = dataSize * 4 + 1;
    char* decryptedString = (char*)malloc(decryptedSize);
    memset(decryptedString, 0, decryptedSize);
    for (int i = 0; i < dataSize; i++)
    {
        char* bytes = (char*)&encryptedData[i];
        decryptedString[i * 4] = bytes[0];
        decryptedString[i * 4 + 1] = bytes[1];
        decryptedString[i * 4 + 2] = bytes[2];
        decryptedString[i * 4 + 3] = bytes[3];
    }
    printf("Decrypted String: %s\n", decryptedString);
    free(decryptedString);
    return 0;
}

xTea算法

TEA 算法发布不久,被发现存在缺陷,作为回应,设计者提出了一个 TEA 的升级版本——XTEA(有时也被称为“tean”)。XTEA 跟 TEA 使用了相同的简单运算,但它采用了截然不同的顺序,为了阻止密钥表攻击,四个子密钥(在加密过程中,原 128 位的密钥被拆分为 4 个 32 位的子密钥)采用了一种不太正规的方式进行混合。总的来说 xTEA就是在TEA算法基础上加了一些内容,而加解密过程基本没变。

加解密:

 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 <stdio.h>
#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;
}

int main()
{
    uint32_t v[2]={1,2};
    uint32_t const k[4]={2,2,3,4};
    unsigned int r=32;//num_rounds建议取值为32
    // v为要加密的数据是两个32位无符号整数
    // k为加密解密密钥,为432位无符号整数,即密钥长度为128
    printf("加密前原始数据:%u %u\n",v[0],v[1]);
    encipher(r, v, k);
    printf("加密后的数据:%u %u\n",v[0],v[1]);
    decipher(r, v, k);
    printf("解密后的数据:%u %u\n",v[0],v[1]);
    return 0;
}

xxTea算法

相比TEA,xTEA算法,xxTEA算法的优势是原字符串长度可以不是4的倍数了

加密过程:

加密:

 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
#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 btea(uint32_t *v,int n,uint32_t const key[4])//n为v数组长度 
{
    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); 
    }
}     

解密过程:

解密:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#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 dtea(uint32_t *v,int n,uint32_t const key[4])//n为v数组长度 
{
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算法的特征:

1
2
3
4
5
1. key 128 bit
2. enc => 32*i(i=>2)
3. 特征量`0x9e3779b9`
4. 两层循环,通常记住最外层的循环为rounds=6+52/n
5. 5,2,3,4 左右移操作  

解密脚本:

  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
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
c
#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 btea(uint32_t *v, int n, uint32_t const key[4])
{
    uint32_t y, z, sum;
    unsigned p, rounds, e;
    if (n > 1)            /* Encoding 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()
{
    uint32_t v[2]= {1,2};
    uint32_t const k[4]= {2,2,3,4};
    int n= 2; //n的绝对值表示v的长度,取正表示加密,取负表示解密
    // v为要加密的数据是两个32位无符号整数
    // k为加密解密密钥,为432位无符号整数,即密钥长度为128
    printf("加密前原始数据:%u %u\n",v[0],v[1]);
    btea(v, n, k);
    printf("加密后的数据:%u %u\n",v[0],v[1]);
    btea(v, -n, k);
    printf("解密后的数据:%u %u\n",v[0],v[1]);
    return 0;
}

//////////////////////x/////////////////////////////
#include <stdint.h>
/* XXTEA加密算法的加密过程 */
void xxtea_encrypt(uint32_t *v, int n, uint32_t *key) {
    uint32_t y, z, sum, delta, e;
    uint32_t p, q, rounds, limit;
    uint32_t *k = key;
    rounds = 6 + 52 / n;        // 计算加密轮数
    sum = 0;
    delta = 0x9E3779B9;         // 初始化delta常数
    limit = rounds * delta;     // 计算sum的最大值
    q = 6 + limit / delta;
    while (q-- > 0) {           // 执行加密轮数
        sum += delta;           // 更新sum
        e = sum >> 2 & 3;       // 计算e值
        for (p = 0; p < n; p++) {   // 对每个数据块执行加密操作
            y = v[(p + 1) % n];
            z = v[p] += ((v[(p + n - 1) % n] >> 5) ^ (y << 2)) + ((y >> 3) ^ (v[(p + n - 1) % n] << 4)) ^ ((sum ^ y) + (k[(p ^ e) & 3] ^ v[(p + n - 1) % n]));
            // 计算加密后的数据块
        }
    }
}
/* XXTEA加密算法的解密过程 */
void xxtea_decrypt(uint32_t *v, int n, uint32_t *key) {
    uint32_t y, z, sum, delta, e;
    uint32_t p, q, rounds, limit;
    uint32_t *k = key;
    rounds = 6 + 52 / n;        // 计算加密轮数
    sum = rounds * 0x9E3779B9;  // 初始化sum常数
    delta = 0x9E3779B9;         // 初始化delta常数
    limit = rounds * delta;     // 计算sum的最大值
    q = 6 + limit / delta;
    while (q-- > 0) {           // 执行加密轮数
        e = sum >> 2 & 3;       // 计算e值
        for (p = n - 1; p > 0; p--) {   // 对每个数据块执行解密操作
            z = v[(p + n - 1) % n];
            y = v[p] -= ((v[(p + n - 1) % n] >> 5) ^ (v[(p + 1) % n] << 2)) + ((v[(p + 1) % n] >> 3) ^ (v[(p + n - 1) % n] << 4)) ^ ((sum ^ v[(p + 1) % n]) + (k[(p ^ e) & 3] ^ v[(p + n - 1) % n]));
            // 计算解密后的数据块
        }
        z = v[(n + n - 1) % n];
        y = v[0] -= ((v[(n + n - 1) % n] >> 5) ^ (v[(1) % n] << 2)) + ((v[(1) % n] >> 3) ^ (v[(n + n - 1) % n] << 4)) ^ ((sum ^ v[(1) % n]) + (k[(0 ^ e) & 3] ^ v[(n + n - 1) % n]));
        // 特殊处理第一个和最后一个数据块
        sum -= delta;           // 更新sum
    }
}

Tea系列算法特征总结:

根据上文对tea算法的源码分析,我们得出TEA算法的如下特征:

key 128 bit {2,2,3,4} 传入两个32位无符号整数 三个累加量,其中最后赋值给传入的参数 存在«4 , »5 , xor等操作 特征量:0x9e3779b9

至于xTEA,xxTEA等TEA算法的特殊变种,由于都是在原始TEA算法上做的局部改动,特征上与tea算法没有本质上的不同,只不过可能有位运算位数不同。具体区别如下:

相同点:

  1. key 128 bit特征量0x9e3779b9
  2. 主要加密部分进行移位和异或操作 首先如果题目中出现常量0x9e3779b9,那么肯定是Tea相关算法了。 区分:
  3. Tea的主加密部分为<<4,>>5,xor,循环32轮
  4. xTea的主加密部分<<4,>>5,>>11,xor,循环次数不定,但通常也为32轮,需要传入3个参数
  5. xxTea的主加密部分>>5,<<2,>>3,<<4,xor,循环次数为6+52/n,enc长度大于64

难点还是在代码审计部分,学好C语言非常重要

参考:

RE与算法-tea加密算法

TEA系列算法101

TEA/XTEA/XXTEA系列算法

TEA算法解析

十分钟带你吃透TEA算法 这个视频挺适合入门

Licensed under CC BY-NC-SA 4.0
Build by Oight
使用 Hugo 构建
主题 StackJimmy 设计