TEA系列加密解密

TEA加密解密

介绍

在密码学中，微型加密算法（Tiny Encryption Algorithm，TEA）是一种易于描述和执行的块密码，通常只需要很少的代码就可实现。

代码的特点：

  • 加密使用的数据为2个32位无符号整数，密钥为4个32位无符号整数即密钥长度为128位（当加密解密的对象是一串数组的时候，需要将这个32位无符号整数的数组每两个32位无符号整数划分为一组，对每一组数据单独加密解密得到结果）
  • 该算法使用了一个常数 δ 作为倍数，它来源于黄金比率，以保证每一轮加密都不相同。但 δ 的精确值似乎并不重要，这里 TEA 把它定义为 δ=「(√5 - 1)231」（也就是程序中的 0×9E3779B9）作为魔数

加密过程

拥有一个叫做Feistel 结构的密码学结构。这种密码学结构通俗的来讲就是会将加密的plaintext分成L、R两部分，并且满足 L_{i+1} = R_i, R_{i+1} = F(K_i,R_i) \oplus L_i 这种交换式的加密方式的一种结构。

image-20220228191440573

TEA加密算法的实现

参数要求：输入一定要是一个64bit的数字，或者可以写作一个拥有两个元素的32bit的数组。并且需要一个两倍长度的key（int[4]),即一个128位的数字（拥有四个元素的32bit的数组）

加密特征：存在一个delta值，这个值会不停的增加到sum之中，形成一种循环的效果；会有一个位移->与密钥相加->异或的过程；计算delta的sum状态值也会参与

1
2
3
4
5
6
7
8
9
10
11
void encrypt (uint32_t v[2], const uint32_t k[4]) {
    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;
}

TEA解密算法的实现

参数要求：输入一定要是一个64bit的数字，或者可以写作一个拥有两个元素的32bit的数组。并且需要一个两倍长度的key（int[4]),即一个128位的数字（拥有四个元素的32bit的数组）

1
2
3
4
5
6
7
8
9
10
11
12
13
//解密函数  
void decrypt (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 */  
    sum = delta << 5;   //32轮运算，所以是2的5次方；16轮运算，所以是2的4次方；8轮运算，所以是2的3次方
    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;  
}

示例代码

解密数组：{0x3e8947cb,0xcc944639,0x31358388,0x3b0b6893,0xda627361,0x3b2e6427}

key数组：{0x4445,0x4144,0x4245,0x4546}

因为在解密的过程之中会产生移位的运算，这个过程会产生溢出，所以每组解密的对象声明成 v1[3]={0x3e8947cb,0xcc944639,0x0} 这样的形式

解密的脚本：

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
#include <stdio.h>
#include <stdint.h>
void decrypt (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()
{
    uint32_t v1[3]={0x3e8947cb,0xcc944639,0x0},k[4]={0x4445,0x4144,0x4245,0x4546};
    uint32_t v2[3]={0x31358388,0x3b0b6893,0x0};
    uint32_t v3[3]={0xda627361,0x3b2e6427};
    decrypt(v1, k);
    decrypt(v2, k);
    decrypt(v3, k);
    printf("解密后的数据：%s %s %s\n",(char*)v1,(char*)v2,(char*)v3);   // 注意如何将一串数组以字符串的形式输出
    return 0;
}
输出的结果：fvBXQdEa rcbvhBPx cOA8Ag6J

补充：

printf(“<格式化字符串>”, <参量表>);

参数的格式

image-20220228193403698

XTEA加密解密

介绍

XTEA是TEA的升级版，增加了更多的密钥表，移位和异或操作

加密过程

image-20220228193746682

XTEA加密算法的实现

相较于TEA的变化：

  • 由之前的**((v1<<4) + k0) ^ ((v1>>5) + k1)** 变化成了 **((v1 << 4) ^ (v1 >> 5)) + v1)**，此时v1内部数据的加密变化不再受到密钥的影响。
  • 原先的v1 + sum变成了(sum + key[sum & 3])以及sum + key[(sum>>11) & 3]，密钥变成了轮转使用，而不是固定只针对某种数据进行加密（解密）。并且此时密钥的选取受到sum的影响
  • sum += delta的时机由每次加密开头就发生变化到v0，v1两个block加密的中间。

输入的参数：输入一定要是一个64bit的数字，或者可以写作一个拥有两个元素的32bit的数组。并且需要一个两倍长度的key（int[4]),即一个128位的数字（拥有四个元素的32bit的数组），注意这里循环的次数不是固定的了，是需要传入的参数num_rounds

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

XTEA解密算法的实现

输入的参数：输入一定要是一个64bit的数字，或者可以写作一个拥有两个元素的32bit的数组。并且需要一个两倍长度的key（int[4]),即一个128位的数字（拥有四个元素的32bit的数组），注意这里循环的次数不是固定的了，是需要传入的参数num_rounds

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

示例代码

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
#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[3]={0x73647979,0x726b6f5f,0x0};
    uint32_t v1[2]={0x646f675f,0x0};
    uint32_t const k[4]={0X95C4C,0X871D,0X1A7B7,0X12C7C7};
    unsigned int r=32;//num_rounds建议取值为32
    // v为要加密的数据是两个32位无符号整数
    // k为加密解密密钥，为4个32位无符号整数，即密钥长度为128位
    printf("加密前原始数据：%s%s\n",(char*)v,(char*)v1);
    encipher(r, v, k);
    encipher(r, v1, k);
    printf("加密后的数据：%u %u %u\n",v[0],v[1],v1[0]);
    decipher(r, v, k);
    decipher(r, v1, k);
    printf("解密后的数据：%s%s\n",(char*)v,(char*)v1);
    return 0;
}
结果：
加密前原始数据：yyds_okr_god
加密后的数据：3461349474 1314311102 3609197830
解密后的数据：yyds_okr_god

XXTEA加密解密

介绍

XTEA再度进化， 变成了支持块加密XXTEA

加密过程

image-20220228200301853

XXTEA加密解密算法的实现

特点：在可变长度块上运行，这些块是32位大小的任意倍数（最小64位），使用128位密钥, 是目前TEA系列中最安全的算法，但性能较上两种有所降低。

参数：输入的是至少拥有两个元素的32bit的数组，密钥的长度仍然是128位，即拥有4个元素32位长度的数组

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

示例代码

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
#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)            /* 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()
{
    uint32_t v[4]= {0x73647979,0x726b6f5f,0x646f675f,0x0};
    uint32_t const k[4]= {0X95C4C,0X871D,0X1A7B7,0X12C7C7};
    int n= 2; //n的绝对值表示v的长度，取正表示加密，取负表示解密
    // v为要加密的数据是两个32位无符号整数
    // k为加密解密密钥，为4个32位无符号整数，即密钥长度为128位
    printf("加密前原始数据：%s\n",(char*)v);
    btea(v, n, k);
    printf("加密后的数据：%u %u %u\n",v[0],v[1],v[3]);
    btea(v, -n, k);
    printf("解密后的数据：%s\n",(char*)v);
    return 0;
}
输出结果：
加密前原始数据：yyds_okr_god
加密后的数据：609835868 2980644312 0
解密后的数据：yyds_okr_god

逆向中TEA系列加密的识别

解决逆向题大部分出现TEA的场合都是【识别算法->编写对应解密程序】

分析二进制文件中的算法的时候有几个识别的特征

  • 可能存在针对64bit以及128bit数字的操作（输入的msg和key） ，一般会用无符号的32位的数组表示
  • 存在先进行位移，然后异或的类似操作（(z>>5^y<<2) 这类混合变换）**(z>>5^y<<2)就是xxtea加密了，存在(v0 << 4)** 和 **(v0 >> 5)**移位就是tea和xtea加密了
  • 前面一个复杂的混合变换的结果可能会叠加到另一个值上，两者相互叠加（Feistel 结构）
  • 获取密钥的时候，会使用某一个常量值作为下标（key[(sum>>11) & 3]）存在轮换的方式获得密钥 就是xtea或者xxtea了
  • 会在算法开始定义一个delta，并且这个值不断的参与算法，但是从来不会受到输入的影响（delta数值如果没有魔改就是0x9e3779b9）如果出现了0x9e3779b9这个数字一般就能确定是TEA加密系列

参考文章：

https://www.jianshu.com/p/4272e0805da3

https://www.anquanke.com/post/id/224198#h3-2