TEA

TEA类算法笔记

TEA

一、简述

TEA算法有64位的明文，128位的密钥以及一个常数 \(\delta\) 组成。\(\delta\)源自于黄金比例，但它的数值的精确度并不重要，于是被定义为 \(\delta\)=「($$5 - 1)231」(即程序里面的0×9E3779B9)

TEA是将明文每64位位一组进行加密，每次加密将这64位分为两部分，高32位和低32位(后面分别用Mup和Mdown来表示)，而密钥(Key)则拆分为4部分。

二、加密过程

加密过程：sum+= \(\delta\) \(\longrightarrow\)

Mup += ((Mdown<<4)+Key[0])(Mdown+sum)((Mdown>>5)+Key[1])\(\longrightarrow\)

Mdown += ((Mup<<4)+Key[2])(Mup+sum)((Mup>>5)+Key[3]).

一般反复32遍或者64遍，最后将结果覆写回去。

附上图解：img

三、TEA逆向

1、tea算法的特征就是DELTA值和十六个字节的密钥（也就是128位）。

2、在逆向程序的时候，可以利用ida的插件findcypto识别tea算法

3、x-=0x61c88647和x+=0x9e3779b9，这两个值是等价的，可能会在反汇编中看到

这里将上面测试的代码编译好拖入IDA中进行观察

可以看到δ就被反编译为v4 -= 1640531527;

TEA算法的变化技巧

​ 前面有提到关于"但δ的精确值似乎并不重要"，所以δ的值不一定需要0x9E3779B9，所以这里的话在加密解密的时候可以改变这个δ的 值，改了之后就会导致部分识别加密的工具失效来达到算法魔改的目的。

四、代码（\(\delta\)没有魔改）

加密代码如下：

1
2
3
4
5
6
7
8
9
10
11
void encrypt (uint32_t* v, uint32_t* k) {
    uint32_t v0=v[0], v1=v[1], sum=0, i;
    uint32_t delta=0x9e3779b9;
    uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[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;
}

abc很容易知道反向运行就能逆出来，cba(虽然不用反过来也是一样的)就得到原结果，所以就只需要将加密反过来即可得到解密代码:

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], i;
    uint32_t delta=0x9e3779b9;
    uint32_t sum = delta*32;
    uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[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算法分析

每次处理64位数据，使用128位密钥。数据和密钥都分割成32为无符号整型处理。

不同点：TEA标准中使用的32轮加密，而腾讯只用了16轮。

可以看到其他都一样的，就是迭代次数为16次

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
#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 < 16; 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], i;  /* set up */
    uint32_t delta=0x9e3779b9;                     /* a key schedule constant */
    uint32_t sum = delta << 4;
    uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[3];   /* cache key */
    for (i=0; i<16; 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;
}

XTEA

一、算法介绍

XTEA算法也被称作为Corrected Block TEA

XTEA是TEA的升级版，增加了更多的密钥表，移位和异或操作等等，设计者是Roger Needham, David Wheeler

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

二、算法图解

img

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

XXTEA

一、XXTEA算法介绍

XXTEA就被称作为Corrected Block TEA。

特点：原字符串长度可以不是4的倍数了

二、XXTEA算法图解

img

三、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
  #define MX (z>>5^y<<2) + (y>>3 ^ z<<4)^(sum^y) + (k[ i&3 ^ e] ^ z);
 
  long btea(long* v, long n, long* k) {
    unsigned long z=v[n-1], y=v[0], sum=0, e, DELTA=0x9e3779b9;
    long i, q ;
    if (n > 1) {         
      q = 6 + 52/n;
      while (q-- > 0) {
        sum += DELTA;
        e = (sum >> 2) & 3;
        for (i=0; i<n-1; i++){ 
            y = v[i+1];
            z = v[i] += MX;
        } 
        y = v[0];
        z = v[n-1] += MX;
      }
      return 0 ;
    } 
      
      
      else if (n < -1) { 
      n = -n;
      q = 6 + 52/n;
      sum = q*DELTA ;
      while (sum != 0) {
        e = (sum >> 2) & 3;
        for (i=n-1; i>0; i--) {
            z = v[i-1];
            y = v[i] -= MX;   
        }
        z = v[n-1];
        y = v[0] -= MX;
        sum -= DELTA;
      }
      return 0;
    }
    return 1;
  }
/*
 long btea(long* v, long n, long* k)
 
v是要加密的组元的起始地址，以32bit为单位，这里用long来实现。

n是要加密的组元个数，正数是加密，负数是解密。

k是密钥的起始地址，长度为4个组元，4*32=128bit。

返回值为0或1（对应n=0，没有计算）。

加密的结果会直接写回到v中。
*/

更新: 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
from ctypes import *

DELTA = 0x67616C66


def encrypt(v, n, k):
    rounds = 6 + int(52 / n)
    sum = c_uint32(0)
    z = v[n - 1].value
    while rounds > 0:
        sum.value += DELTA
        e = (sum.value >> 2) & 3
        p = 0
        while p < n - 1:
            y = v[p + 1].value
            v[p].value += (((z >> 5 ^ y << 2) + (y >> 3 ^ z << 4)) ^ ((sum.value ^ y) + (k[(p & 3) ^ e] ^ z)))
            z = v[p].value
            p += 1
        y = v[0].value
        v[n - 1].value += (((z >> 5 ^ y << 2) + (y >> 3 ^ z << 4)) ^ ((sum.value ^ y) + (k[(p & 3) ^ e] ^ z)))
        z = v[n - 1].value
        rounds -= 1

def decrypt(v, n, k):
    rounds = 6 + int(52 / n)
    sum = c_uint32(rounds * DELTA)
    y = v[0].value
    while rounds > 0:
        e = (sum.value >> 2) & 3
        p = n - 1
        while p > 0:
            z = v[p - 1].value
            v[p].value -= (((z >> 5 ^ y << 2) + (y >> 3 ^ z << 4)) ^ ((sum.value ^ y) + (k[(p & 3) ^ e] ^ z)))
            y = v[p].value
            p -= 1
        z = v[n - 1].value
        v[0].value -= (((z >> 5 ^ y << 2) + (y >> 3 ^ z << 4)) ^ ((sum.value ^ y) + (k[(p & 3) ^ e] ^ z)))
        y = v[0].value
        sum.value -= DELTA
        rounds -= 1


if __name__ == '__main__':
    key = [0x4DB, 0xE, 0x17, 0x2A6]
    enc = [3364074410, 133904720, 1975277913, 2058714663, 3223623680, 2913163091, 3206367551, 1846849284, 1182995140]
    v = []
    for i in enc:
        v.append(c_uint32(i))
    decrypt(v, len(v), key)
    flag = ''
    for i in range(len(v)):
        a = v[i].value
        for j in range(4):
            flag += chr(a & 0xff)
            a >>= 8
    print(flag)

四、算法标志

q = 6 + 52/n;

e = (sum >> 2) & 3;