526互联

Tea系列算法及Tea系列算法在IDA中的识别

发布时间 2023-06-20 12:27:20作者: Qsons

Tea系列算法及Tea系列算法在IDA中的识别

一、Tea算法简介

TEA算法由剑桥大学计算机实验室的David Wheeler和Roger Needham于1994年发明。它是一种分组密码算法，其明文密文块为64比特，密钥长度为128比特。TEA算法可以利用不断增加的Delta(黄金分割率)值作为变化，使得每轮的加密是不同，该加密算法的迭代次数可以改变，建议的迭代次数为32轮。TEA算法的加密和解密过程是相同的，只是密钥的使用顺序不同。其拥有一个叫做Feistel结构的密码学结构。这种密码学结构通俗的来讲就是将加密的明文分成L、R两部分

Tea算法最关键的是要找到DELTA值和128位的key。其中DELTA是存在0x9e3778b9，但是也存在魔改delta后的代码.

二、初级TEA算法

代码如下所示:

#include <stdint.h>
#include <stdio.h>

void tea_encrypt(uint32_t* v, uint32_t* k) //一个指向包含要加密数据的64位无符号整数数组的指针v,一个指向包含128位密钥的无符号整数数组的指针k
{
    uint32_t v0 = v[0], v1 = v[1], sum = 0, delta = 0x9e3779b9;//v0和v1存储要加密的二个32位部分，sum用于迭代的累加和，delta是算法的常量
    uint32_t k0 = k[0], k1 = k[1], k2 = k[2], k3 = k[3];//k1，k2，k3，k4表示存储128位密钥的四个32位部分

    for (int i = 0; i < 32; i++) {      //迭代32次，执行TEA算法的加密操作
        sum += delta;
        v0 += ((v1 << 4) + k0) ^ (v1 + sum) ^ ((v1 >> 5) + k1);
        /*
        (v1 << 4) + k0：将 v1 左移4位，然后与 k0 相加。这一步是一个简单的移位和加法操作。
        (v1 + sum)：将 v1 与 sum 相加。这一步是简单的加法操作。
        ((v1 >> 5) + k1)：将 v1 右移5位，然后与 k1 相加。这一步是一个简单的移位和加法操作。
        上述三个结果使用异或操作 ^ 连接起来，得到一个中间结果。
        v0 += 表示将 v0 与上述中间结果相加，更新 v0 的值。
        */
        v1 += ((v0 << 4) + k2) ^ (v0 + sum) ^ ((v0 >> 5) + k3);//跟上一步类似
    }

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

void tea_decrypt(uint32_t* v, uint32_t* k) {
    uint32_t v0 = v[0], v1 = v[1], sum = 0xC6EF3720, delta = 0x9e3779b9;
    //sum = delta << 5
    uint32_t k0 = k[0], k1 = k[1], k2 = k[2], k3 = k[3];

    for (int 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;
}

int main() {
    uint32_t v[2] = { 0x01234567, 0x89ABCDEF }; // Plain text 定义一个包含要加密的数据块的64位无符号整数数组'v',初始值位'0x1234567'和'0x89ABCDEF'.
    uint32_t k[4] = { 0xA56BABCD, 0xFEDCBA98, 0x546ACBDF, 0x13579BCE }; // Key 一个包含128位密钥的无符号整数数组k
	
    //Encrypt每次只是加密4字节数组中的两组(也就是每次加密8个字节) 如果你数据多。可以来个for循环来进行循环加密，但是Entrypt内部还有32次循环，所以速度上还是会有影响
    printf("Plain text: 0x%08X%08X\n", v[0], v[1]);
    tea_encrypt(v, k);
    printf("Encrypted:  0x%08X%08X\n", v[0], v[1]);
    tea_decrypt(v, k);
    printf("Decrypted:  0x%08X%08X\n", v[0], v[1]);

    return 0;
}

加密过程中:

  • 存在一个delta值，不断的增加到sum之中，形成一种循环的效果
  • 传入的v0，v1会和传入的key0,key1运算。v1优先参与，并且会有一个位移->与密钥相机 - > 异或的过程
  • v0 = 原先的v1值套公式，v1 = 变化后的v0套用公式
  • 参与delta的sum值也会参与

由于是一个类似delta状态变化+异或加密的过程，所以整个流程反过来写即可得到解密。

三、XTEA算法

XTEA算法是一种对称加密算法，它使用一个128位的密钥对数据进行加密和解密。它的加密和解密过程都是基于一个32位的块进行的。XTEA算法的加密和解密过程都是由多轮迭代完成的。

每轮迭代包含以下四个步骤:

  • 轮密钥加
  • 代换
  • 置换
  • 轮密钥加

其中，代换和置换是XTEA算法的核心部分。XTEA算法是TEA算法的魔改算法。XTEA算法四个子密钥采取不正规的方式进行混合以组织密钥表进行攻击。

代码如下:

#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;
}

可以看到:

  • 由之前的((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加密的中间

四、XXTEA算法

XXtea算法的基本原理是将明文分成若干个固定长度的块，然后对每个块进行加密。加密过程中，使用一个密钥对每个块进行加密，然后将加密后的块拼接在一起形成密文。

解密过程与加密过程相反。使用相同的密钥对密文进行解密，然后将解密后的拼接在一起形成明文。

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)            /* 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 = DELTA << rounds;
        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为加密解密密钥，为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;
}

五、题目中TEA算法的特征:

  • 可能存在针对64bit以及128bit数字的操作(输入的message和key)
  • 存在先位移，后异或的类似操作。比如((z >> 5 ^ x <<4) ^ (y << 4 & q >> 5))等混合变换
  • 全部你一个复杂的混合变换的结构可能会叠加到另一个值上，两者相互叠加(Feistel结构)
  • 获取密钥的时候，会使用某一个常量值作为下标 (key [ (sum >> 11) & 3])
  • 一开始会在算法定义一个delta，并且不断参与算法，但是不会受到输入的影响。

int __cdecl sub_4118D0(unsigned int a1, unsigned int *a2, int a3)
{
int result; // eax
unsigned int v4; // [esp+DCh] [ebp-2Ch]
unsigned int v5; // [esp+E8h] [ebp-20h]
unsigned int v6; // [esp+F4h] [ebp-14h]
unsigned int i; // [esp+100h] [ebp-8h]

__CheckForDebuggerJustMyCode(&unk_41C028);
v6 = a2;
v5 = a2[1];
v4 = 0;
for ( i = 0; i < a1; ++i )
{
v6 += ((_DWORD )(a3 + 4 * (v4 & 3)) + v4) ^ (v5 + ((v5 >> 5) ^ (16 * v5)));
v4 -= 1640531527;
v5 += ((_DWORD *)(a3 + 4 * ((v4 >> 11) & 3)) + v4) ^ (v6 + ((v6 >> 5) ^ (16 * v6)));
}
*a2 = v6;
result = 4;
a2[1] = v5;
return result;
}

初级Tea算法:

XTEA算法:

XXTEA算法:

六、TEA系列算法在IDA中的识别

Tea初级算法:

源代码在上面已经给出:

  • Vs2022,Debug32位
//main函数代码
int __cdecl main_0(int argc, const char **argv, const char **envp)
{
  int v4[6]; // [esp+D0h] [ebp-28h] BYREF
  char v5[4]; // [esp+E8h] [ebp-10h] BYREF
  int v6; // [esp+ECh] [ebp-Ch]

  __CheckForDebuggerJustMyCode(&unk_41C024);
  *(_DWORD *)v5 = 0x12345678;
  v6 = 0x78563412;
  v4[0] = 1;
  v4[1] = 2;
  v4[2] = 3;
  v4[3] = 4;
  sub_4110D2("Data is : %x %x\n", 0x78);
  sub_41100A(v5, v4);
  sub_4110D2("Encrypted data is : %x %x\n", v5[0]);
  sub_4113B1(v5, v4);
  sub_4110D2("Decrypted data is : %x %x\n", v5[0]);
  return 0;
}

不难看出

  • sub_4110D2就是我们源代码中的两个printf函数
  • sub_41100A是我们的Tea_encrypt函数
  • sub_4113B1是我们的Tea_decrypt函数

sub_41100A函数

int __cdecl sub_41100A(int a1, int a2)
{
  return sub_411910(a1, a2);
}

int __cdecl sub_411910(unsigned int *a1, _DWORD *a2)
{
  int result; // eax
  int i; // [esp+D0h] [ebp-68h]
  unsigned int v4; // [esp+118h] [ebp-20h]
  unsigned int v5; // [esp+124h] [ebp-14h]
  int v6; // [esp+130h] [ebp-8h]

  __CheckForDebuggerJustMyCode(&unk_41C024);
  v6 = 0;
  v5 = *a1;
  v4 = a1[1];
  for ( i = 0; i < 32; ++i )
  {
    v6 -= 1640531527;
    v5 += (a2[1] + (v4 >> 5)) ^ (v6 + v4) ^ (*a2 + 16 * v4);
    v4 += (a2[3] + (v5 >> 5)) ^ (v6 + v5) ^ (a2[2] + 16 * v5);
  }
  *a1 = v5;
  result = 4;
  a1[1] = v4;
  return result;
}

注意点:

  • 这里的v6是一直-=一个常数1640531627，如果我们把这个转为16进制的话，可以发现这个常数就是我们tea算法中的delta，即0x9e3779b9
  • 这里可以看到有很明显的移位+异或的运算(Tea算法常见结构)
  • 以及运算后将变量赋给另一个值上(Feistal结构)
  • 这里的16 * v4其实就相当于<< 4了。

Xtea算法:

源码在上面已经给出:

  • Debug32位，Vs2022
//IDAmain函数
int __cdecl main_0(int argc, const char **argv, const char **envp)
{
  int v4[6]; // [esp+DCh] [ebp-28h] BYREF
  char v5[4]; // [esp+F4h] [ebp-10h] BYREF
  int v6; // [esp+F8h] [ebp-Ch]

  __CheckForDebuggerJustMyCode(&unk_41C028);
  *(_DWORD *)v5 = 1;
  v6 = 2;
  v4[0] = 2;
  v4[1] = 2;
  v4[2] = 3;
  v4[3] = 4;
  sub_4110CD((char *)&byte_417B30, 1);
  sub_411186(32, v5, v4);
  sub_4110CD((char *)&byte_417B4C, v5[0]);
  sub_4110FF(32, v5, v4);
  sub_4110CD((char *)&byte_417B68, v5[0]);
  return 0;
}
  • sub_4110CDprintf函数
  • sub_411186为Tea_encrypt函数
  • sub_4110FF为Tea_decrypt函数

sub_411186函数

// attributes: thunk
int __cdecl sub_411186(int a1, int a2, int a3)
{
  return sub_4118D0(a1, a2, a3);
}

int __cdecl sub_4118D0(unsigned int a1, unsigned int *a2, int a3)
{
  int result; // eax
  unsigned int v4; // [esp+DCh] [ebp-2Ch]
  unsigned int v5; // [esp+E8h] [ebp-20h]
  unsigned int v6; // [esp+F4h] [ebp-14h]
  unsigned int i; // [esp+100h] [ebp-8h]

  __CheckForDebuggerJustMyCode(&unk_41C028);
  v6 = *a2;
  v5 = a2[1];
  v4 = 0;
  for ( i = 0; i < a1; ++i )
  {
    v6 += (*(_DWORD *)(a3 + 4 * (v4 & 3)) + v4) ^ (v5 + ((v5 >> 5) ^ (16 * v5)));
    v4 -= 1640531527;
    v5 += (*(_DWORD *)(a3 + 4 * ((v4 >> 11) & 3)) + v4) ^ (v6 + ((v6 >> 5) ^ (16 * v6)));
  }
  *a2 = v6;
  result = 4;
  a2[1] = v5;
  return result;
}
  • 1640531527为我们xtea算法中的Delta常数
  • xtea算法与tea算法不同的是xtea算法的核心算法是在于取轮密钥，而不是像tea算法中，通过常数影响轮密钥
  • (v5 + ((v5 >> 5) ^ ( 16 * v5))) 等价于 (v1 + ((v1 >> 5) ^ (v1 << 4)))其他同理.

XXTEA算法:

  • Debug32位，Vs2022
//main函数代码
int __cdecl main_0(int argc, const char **argv, const char **envp)
{
  int v4[6]; // [esp+DCh] [ebp-28h] BYREF
  char v5[4]; // [esp+F4h] [ebp-10h] BYREF
  int v6; // [esp+F8h] [ebp-Ch]

  __CheckForDebuggerJustMyCode(&unk_41C029);
  *(_DWORD *)v5 = 1;
  v6 = 2;
  v4[0] = 2;
  v4[1] = 2;
  v4[2] = 3;
  v4[3] = 4;
  sub_4110CD((char *)&byte_417B30, 1);
  sub_4111E0((int)v5, 2, (int)v4);
  sub_4110CD((char *)&byte_417B4C, v5[0]);
  sub_4111E0((int)v5, -2, (int)v4);
  sub_4110CD((char *)&byte_417B68, v5[0]);
  return 0;
}
  • sub_4110CD对应printf函数
  • sub_4111E0对应的是Tea_encrypt和Tea_decrypt函数

sub_4111E0函数

// attributes: thunk
int __cdecl sub_4111E0(int a1, int a2, int a3)
{
  return sub_411770(a1, a2, a3);
}

int __cdecl sub_411770(unsigned int *a1, int a2, int a3)
{
  int result; // eax
  unsigned int v4; // eax
  int v5; // edx
  unsigned int v6; // edx
  unsigned int v7; // edx
  unsigned int v8; // edx
  int v9; // [esp+D4h] [ebp-44h]
  int v10; // [esp+D4h] [ebp-44h]
  int v11; // [esp+E0h] [ebp-38h]
  int v12; // [esp+E0h] [ebp-38h]
  unsigned int j; // [esp+ECh] [ebp-2Ch]
  int i; // [esp+ECh] [ebp-2Ch]
  unsigned int v15; // [esp+F8h] [ebp-20h]
  unsigned int v16; // [esp+F8h] [ebp-20h]
  unsigned int v17; // [esp+104h] [ebp-14h]
  unsigned int v18; // [esp+110h] [ebp-8h]
  int v19; // [esp+124h] [ebp+Ch]

  result = __CheckForDebuggerJustMyCode(&unk_41C029);
  if ( a2 <= 1 )
  {
    if ( a2 < -1 )
    {
      v19 = -a2;
      v12 = 52 / v19 + 6;
      v16 = -1640531527 << (52 / v19 + 6);
      v18 = *a1;
      do
      {
        v10 = (v16 >> 2) & 3;
        for ( i = v19 - 1; i; --i )
        {
          v7 = a1[i]
             - (((a1[i - 1] ^ *(_DWORD *)(a3 + 4 * (v10 ^ i & 3))) + (v18 ^ v16)) ^ (((16 * a1[i - 1]) ^ (v18 >> 3))
                                                                                   + ((4 * v18) ^ (a1[i - 1] >> 5))));
          a1[i] = v7;
          v18 = v7;
        }
        v8 = *a1
           - (((a1[v19 - 1] ^ *(_DWORD *)(a3 + 4 * v10)) + (v18 ^ v16)) ^ (((16 * a1[v19 - 1]) ^ (v18 >> 3))
                                                                         + ((4 * v18) ^ (a1[v19 - 1] >> 5))));
        *a1 = v8;
        v18 = v8;
        v16 += 1640531527;
        result = --v12;
      }
      while ( v12 );
    }
  }
  else
  {
    v11 = 52 / a2 + 6;
    v15 = 0;
    v17 = a1[a2 - 1];
    do
    {
      v15 -= 0x61C88647;
      v9 = (v15 >> 2) & 3;
      for ( j = 0; j < a2 - 1; ++j )
      {
        v4 = ((v17 ^ *(_DWORD *)(a3 + 4 * (v9 ^ j & 3))) + (a1[j + 1] ^ v15)) ^ (((16 * v17) ^ (a1[j + 1] >> 3))
                                                                               + ((4 * a1[j + 1]) ^ (v17 >> 5)));
        v5 = a1[j];
        a1[j] = v4 + v5;
        v17 = v4 + v5;
      }
      v6 = (((v17 ^ *(_DWORD *)(a3 + 4 * (v9 ^ j & 3))) + (*a1 ^ v15)) ^ (((16 * v17) ^ (*a1 >> 3))
                                                                        + ((4 * *a1) ^ (v17 >> 5))))
         + a1[a2 - 1];
      a1[a2 - 1] = v6;
      v17 = v6;
      result = --v11;
    }
    while ( v11 );
  }
  return result;
}
  • 常量如果不确定的话，可以用IDA的插件findcrypt进行识别
  • 见到移位+异或这种组合运算可以初步判断是tea系列算法
  • 如果针对于每轮的轮数有不同的算法的话，可以确定是xxtea算法。

参考文章: