XTEA算法及例题总结

算法详解

在TEA中，密钥是直接分成4个32位部分（总共128位），每轮加密过程中使用这些部分直接参与计算。密钥在整个加密过程中的使用比较固定，没有变化。这样，攻击者只需要通过分析固定密钥的几轮加密就能发现模式，从而降低了加密算法的安全性。

在XTEA中，以及密钥并不是每轮加密中直接使用固定的部分。相反，XTEA通过密钥的不同部分在每一轮加密中进行动态调度，密钥在加密过程中会经过多次变换，从而增强了密钥的复杂性和加密过程的不可预测性。

加密流程示意图：

代码实现

下面是XTEA算法加密过程的C语言函数实现

void encrypt(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 < 64; i++) // XTEA默认循环64轮，与TEA不同，题目也可能修改循环次数
    {
        v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]); 
        sum += delta;
        v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
        // 此处对key的索引方式与TEA不同
    }
    v[0]=v0; v[1]=v1;
}

下面是XTEA算法解密过程的C语言代码实现

void decipher(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 key[4] = 
    {
        // 此处存放密钥
    };  
    uint32_t temp[2];  // 存储每组密文
    uint8_t flag[32] = 
    {
        // 此处存放要解密的数据
    };
    for (int i = 0; i < 32; i += 8)// 有多少字节的密文，就填i<多少（此处为32）
    {  
        temp[0] = *(uint32_t*)&flag[i];
        temp[1] = *(uint32_t*)&flag[i + 4];

        decrypt(temp, key);// 调用解密函数

        for (int j = 0; j < 2; j++) // 输出解密后的数据
        {
            for (int m = 0; m < 4; m++) 
            {
                printf("%c", temp[j] & 0xff);  // 按字节输出，恢复原始字符
                temp[j] >>= 8;
            }
        }
    }
    return 0;
}

例题

[HNCTF 2022 WEEK3]Try2debugPlusPlus

前半部分是反调试的处理，不是这里的重点，动调时根据判断的条件patch或nop一下就好。

得到密钥后分析反汇编代码

int __cdecl main(int argc, const char **argv, const char **envp)
{
  int v4[52]; // [rsp+20h] [rbp-60h] BYREF
  char v5[32]; // [rsp+F0h] [rbp+70h] BYREF
  int v6[4]; // [rsp+110h] [rbp+90h] BYREF
  int m; // [rsp+120h] [rbp+A0h]
  int k; // [rsp+124h] [rbp+A4h]
  int j; // [rsp+128h] [rbp+A8h]
  int i; // [rsp+12Ch] [rbp+ACh]

  _main();
  srand(0x66u);
  if ( IsDebuggerPresent() )
  {
    puts("Don't debug me!");
    exit(0);
  }
  v6[0] = 18;
  v6[1] = 52;
  v6[2] = 86;
  v6[3] = 120;
  dododo(v6);
  puts("Please input your flag");
  scanf("%s", v5);
  for ( i = 0; i <= 11; ++i )
    v4[i] = v5[i];
  for ( j = 0; j <= 3; ++j )
    ;
  for ( k = 0; k <= 5; ++k )
    tea_encrypt(&v4[2 * k], v6);
  for ( m = 0; m <= 11; ++m )
  {
    if ( v4[m] != enc[m] )
    {
      printf("error!");
      exit(0);
    }
  }
  printf("yes!");
  printf("flag is NSSCTF{input()}");
  return 0;
}

可知核心的加密算法在tea_encrypt()处，跟进查看

__int64 __fastcall tea_encrypt(unsigned int *a1, __int64 a2)
{
  __int64 result; // rax
  unsigned __int64 i; // [rsp+8h] [rbp-18h]
  unsigned int v4; // [rsp+14h] [rbp-Ch]
  unsigned int v5; // [rsp+18h] [rbp-8h]
  unsigned int v6; // [rsp+1Ch] [rbp-4h]

  v6 = *a1;
  v5 = a1[1];
  v4 = 0;
  for ( i = 0i64; i <= 0x1F; ++i )
  {
    v6 += (((v5 >> 5) ^ (16 * v5)) + v5) ^ (*(_DWORD *)(4i64 * (v4 & 3) + a2) + v4);
    v4 += 2042207799;
    v5 += (((v6 >> 5) ^ (16 * v6)) + v6) ^ (*(_DWORD *)(4i64 * ((v4 >> 11) & 3) + a2) + v4);
  }
  *a1 = v6;
  result = v5;
  a1[1] = v5;
  return result;
}

由&3和>>11等特征确认是XTEA加密算法，根据获得的密钥和enc处得到的密文写出解密代码：

void decrypt(uint32_t v[2], uint32_t const key[4])
{
    unsigned int i;
    uint32_t v0 = v[0], v1 = v[1], delta = 0x79B99E37, sum = delta * 32;
    for (i = 0; i < 32; 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 key[4] =
    {
        0x91,0x71,0x11,0xbb
    };
    uint32_t temp[2];  // 存储每组密文
    uint8_t flag[48] =
    {
        0xC5, 0xB6, 0xD5, 0xDA, 0x17, 0xF7, 0xE5, 0x0C, 0x6B, 0xAF, 0xE8, 0x8B, 0xB4, 0x6E, 0x4C, 0xD7,
        0xA0, 0xB5, 0xB8, 0xEE, 0xE0, 0x18, 0x76, 0xA0, 0xD0, 0x5F, 0x42, 0x1B, 0x41, 0x76, 0xB7, 0xC0,
        0xBE, 0xA9, 0x0F, 0xA3, 0x89, 0x50, 0x4F, 0xCB, 0x1D, 0xEC, 0xF9, 0xEB, 0x3D, 0xEF, 0x70, 0xF8
    };

    for (int i = 0; i < 48; i += 8)
    {
        temp[0] = *(uint32_t*)&flag[i];
        temp[1] = *(uint32_t*)&flag[i + 4];

        decrypt(temp, key);// 调用解密函数

        for (int j = 0; j < 2; j++) // 输出解密后的数据
        {
            for (int m = 0; m < 4; m++)
            {
                printf("%c", temp[j] & 0xff);  // 按字节输出，恢复原始字符
                temp[j] >>= 8;
            }
        }
    }
    return 0;
}