tea、xtea、xxtea算法研究

「 密码学 」 January 03, 2020

tea、xtea、xxtea算法研究

Words count 47k Reading time 43 mins. Read count 0

一、Tea

先来看一波C语言实现的代码，通过代码学习更快理解原理：

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
#include <stdio.h>  
#include <stdint.h>  
  
//加密函数  
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 (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 v[2]={1,2},k[4]={2,2,3,4};  
    // v为要加密的数据是两个32位无符号整数  
    // k为加密解密密钥，为4个32位无符号整数，即密钥长度为128位  
    printf("加密前原始数据：%u %u\n",v[0],v[1]);  
    encrypt(v, k);  
    printf("加密后的数据：%u %u\n",v[0],v[1]);  
    decrypt(v, k);  
    printf("解密后的数据：%u %u\n",v[0],v[1]);  
    return 0;  
}

这里解释下一些知识点:

1
2
3
a<<4表示a乘以2的4次方
a>>5表示a除以2的5次方
a移动x位表示对a进行2的x次方操作

由于是eax寄存器，存储32位的无符号在整数，最大4字节，所以多出来的会省去，举个例子：如果是0x1b2ceed32f，则会看到0x2ceed32f，在这里先提个醒，下面直接分析加密算法：

1
2
3
4
5
6
7
8
9
10
11
void encrypt (uint32_t* v, uint32_t* k) {  //传入v是我们的input数组，k是key数组
    uint32_t v0=v[0], v1=v[1], sum=0, i;       //一次加密处理2个输入的大整数
    uint32_t delta=0x9e3779b9;                //这个是特征值0x9e3779b9 
    uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[3];   //key固定是128bit的数组，4个大整数，每个32位
    for (i=0; i < 32; i++) {                       //初始轮转数是32，但是可以自己设定其实
        sum += delta;                             //每一轮都加，溢出时直接舍去溢出部分，保留4字节
        v0 += ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1); //通过对v1加密得到v0,
        v1 += ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3); //通过对加密后的v0加密得到v1
    }                                              //就这样不停地轮转32次
    v[0]=v0; v[1]=v1;  //加密结束后，将v1和v0分别存储到v数组中得到密文
}

用个图解释下:

57260661074

知道了加密，其实解密就是反解就可：

1
2
3
4
5
6
7
8
9
10
11
12
void decrypt (uint32_t* v, uint32_t* k) {
    uint32_t v0=v[0], v1=v[1], sum=0xC6EF3720, i;  //0x9e3779b9*0x20=0x13C6EF3720，舍弃溢出位得到
    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;
}
//会发现真是只是倒着推一遍算法而已，轮转32次最后再次赋值即可

这就是初级的tea算法，其实知道了原理模改就变得很简单，下面是我魔改的加密和解密：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void encrypt (uint32_t* v, uint32_t* k) {  
    uint32_t v0=v[0], v1=v[1], sum=0, i;           /* set up */  
    uint32_t delta=0x458BCD42;                     /* a key schedule constant */  
    uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[3];   /* cache key */  
    for (i=0; i < 64; i++) {                       /* basic cycle start */  
        sum += delta;  
        v0 += ((((v1<<6) + k0) ^ (v1 + sum + 11) ^ ((v1>>9) + k1))^0x20);  
        v1 += ((((v0<<6) + k2) ^ (v0 + sum + 20) ^ ((v0>>9) + k3))^0x10);  
    }                                              /* end cycle */  
    v[0]=v0; v[1]=v1;  
}  
//解密函数  
void decrypt (uint32_t* v, uint32_t* k) {  
    uint32_t v0=v[0], v1=v[1], sum=0x62F35080, i;  /* set up */  
    uint32_t delta=0x458BCD42;                   /* a key schedule constant */  
    uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[3];   /* cache key */  
    for (i=0; i<64; i++) {                         /* basic cycle start */  
        v1 -= ((((v0<<6) + k2) ^ (v0 + sum + 20) ^ ((v0>>9) + k3))^0x10);  
        v0 -= ((((v1<<6) + k0) ^ (v1 + sum + 11) ^ ((v1>>9) + k1))^0x20);  
        sum -= delta;  
    }                                              /* end cycle */  
    v[0]=v0; v[1]=v1;  
}

这里改变特征值，然后加密算法微调，加了异或而已，就完成了魔改工作，简单的tea过了后，下面开始进阶。

这里搞上python脚本直接解：

1
2


二、Xtea

同样的学习过程，先来源码学习：

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;  
}  
//加密过程发现不同之处在于，加密算法变了，key的利用不同，同时多了轮转数的选择，其他的还是变化不大，还是一样可以逆推。 
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为加密解密密钥，为4个32位无符号整数，即密钥长度为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;  
}

这里在知道tea算法的基础上，再记住特征，key[sum&3]，还有轮转数的选择，就可以认出Xtea算法了，继续进阶：

三、XXtea

同样地，先看下源码：

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  
  
void btea(uint32_t *v, int n, uint32_t const key[4])  
{  
    uint32_t y, z, sum;  
    unsigned i, rounds, e;  
    if (n > 1)            //n作为加解密的选择，正数为加密，负数为解密
    {  
        rounds = 6 + 52/n; //轮转数的选择，是个特征值：6+52/n
        sum = 0;  
        z = v[n-1]; //先取出最后一个值  
        do  
        {  
            sum += DELTA;  //开始加密
            e = (sum >> 2) & 3;  //通过sum得到e，也是个特征值
            for (i=0; i<n-1; i++)  //轮转次数
            {  
                y = v[i+1];  //得到
                v[i] += (((z>>5^y<<2) + (y>>3^z<<4)) ^ ((sum^y) + (key[(i&3)^e] ^ z)));  
                z = v[i];
                //细细分析就会知道，首先通过v[n-1]和v[1]进行加密得到v[0]，然后通过v[0]和v[2]加密得到v[1]就会发现规律了：其实就是3个数为一组，通过左右两个数加密得到中间的数这里只会运算到v[n-2]
            }  
            y = v[0];  
            v[n-1] += (((z>>5^y<<2) + (y>>3^z<<4)) ^ ((sum^y) + (key[(i&3)^e] ^ z)));  
            z = v[n-1];//最后一个数v[n-1]的加密，拿到v[0]和v[n-2]进行加密得到,算法一样
        }  //第一轮结束，每个数都加密了一遍
        while (--rounds)；	//执行rounds轮，加密完全
    }  
    else if (n < -1)   //当负数时就是解密
    {  
        n = -n;  //首先把负数转成正数
        rounds = 6 + 52/n;  //确定轮转数
        sum = rounds*DELTA;  //根据轮转数计算sum
        y = v[0];  
        do  
        {  
            e = (sum >> 2) & 3;  
            for (i=n-1; i>0; i--) //逆序倒推
            {  
                z = v[i-1];  //先解密v[n-1]，需要知道v[0]和v[n-2]，
                v[i] -= (((z>>5^y<<2) + (y>>3^z<<4)) ^ ((sum^y) + (key[(i&3)^e] ^ z)));  
                y = v[i];//只会解密到v[1]
            }  
            z = v[n-1]; //对于第一个v[0]的解密，要知道v[n-1]和v[1] 
            v[0] -= (((z>>5^y<<2) + (y>>3^z<<4)) ^ ((sum^y) + (key[(i&3)^e] ^ z)));  
            y = v[0]; 
            sum -= DELTA;//sum的减减
        }  
        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为加密解密密钥，为4个32位无符号整数，即密钥长度为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;  
}

python脚本如下：

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
import struct  
  
_DELTA = 0x9E3779B9  
  
def _long2str(v, w):  
    n = (len(v) - 1) << 2  
    if w:  
        m = v[-1]  
        if (m < n - 3) or (m > n): return ''  
        n = m  
    s = struct.pack('<%iL' % len(v), *v)  
    return s[0:n] if w else s  
  
def _str2long(s, w):  
    n = len(s)  
    m = (4 - (n & 3) & 3) + n  
    s = s.ljust(m, "\0")  
    v = list(struct.unpack('<%iL' % (m >> 2), s))  
    if w: v.append(n)  
    return v  
  
def encrypt(str, key):  
    if str == '': return str  
    v = _str2long(str, True)  
    k = _str2long(key.ljust(16, "\0"), False)  
    n = len(v) - 1  
    z = v[n]  
    y = v[0]  
    sum = 0  
    q = 6 + 52 // (n + 1)  
    while q > 0:  
        sum = (sum + _DELTA) & 0xffffffff  
        e = sum >> 2 & 3  
        for p in xrange(n):  
            y = v[p + 1]  
            v[p] = (v[p] + ((z >> 5 ^ y << 2) + (y >> 3 ^ z << 4) ^ (sum ^ y) + (k[p & 3 ^ e] ^ z))) & 0xffffffff  
            z = v[p]  
        y = v[0]  
        v[n] = (v[n] + ((z >> 5 ^ y << 2) + (y >> 3 ^ z << 4) ^ (sum ^ y) + (k[n & 3 ^ e] ^ z))) & 0xffffffff  
        z = v[n]  
        q -= 1  
    return _long2str(v, False)  
  
def decrypt(str, key):  
    if str == '': return str  
    v = _str2long(str, False)  
    k = _str2long(key.ljust(16, "\0"), False)  
    n = len(v) - 1  
    z = v[n]  
    y = v[0]  
    q = 6 + 52 // (n + 1)  
    sum = (q * _DELTA) & 0xffffffff  
    while (sum != 0):  
        e = sum >> 2 & 3  
        for p in xrange(n, 0, -1):  
            z = v[p - 1]  
            v[p] = (v[p] - ((z >> 5 ^ y << 2) + (y >> 3 ^ z << 4) ^ (sum ^ y) + (k[p & 3 ^ e] ^ z))) & 0xffffffff  
            y = v[p]  
        z = v[n]  
        v[0] = (v[0] - ((z >> 5 ^ y << 2) + (y >> 3 ^ z << 4) ^ (sum ^ y) + (k[0 & 3 ^ e] ^ z))) & 0xffffffff  
        y = v[0]  
        sum = (sum - _DELTA) & 0xffffffff  
    return _long2str(v, True)  
  
if __name__ == "__main__":  
    print decrypt('\x8f\x51\xcd\x67\xb1\x2e\xea\xd7\x91\x7d\x79\x10', '16bytelongstring')

其实还有个集成库可以利用：

1
2
3
4
5
6
text = "\x4d\xd6\x48\x7b\x0e\x97\xb5\x11\x0b\x82\x87\x8c\x3e\x31\xfc\x16\x7c\xfa\xe5\x10"
key = "12345670".ljust(16,'\x00')
# encrypt_data = xxtea.encrypt(text, key)
# print encrypt_data.encode('hex')
decrypt_data = xxtea.decrypt(text, key)
print decrypt_data

还是xxtea比前面的两个更复杂，轮转数也更多，但是也更有趣，解密也一样这里就不重复说明了，记住特征值，

6 + 52/n和全部加密一次算一次轮转，2重循环。

以上三个关于tea的加密算法就了解到这里，后面继续学习re的知识，我觉得逆向就是对于算法的了解，静态分析+动态调试，找关键逻辑check函数，然后尝试进行解密即可。

V1ct0r

Where there is a will,there is a way！
0%