【逆向分析】tea,xtea,xxtea加密算法总结
2023-11-29 00:1:32 Author: 利刃信安攻防实验室(查看原文) 阅读量:4 收藏

a,xtea,xxtea加密算法总结

在逆向过程中,常常会遇到tea加密,本文将系统地总结一下tea,xtea,xxtea

简介

TEA加密算法是一种分组密码算法,其明文密文块为64比特,密钥长度为128比特。TEA算法利用不断增加的Delta(黄金分割率)值作为变化,使得每轮的加密是不同,该加密算法的迭代次数可以改变,建议的迭代次数为32轮。
值得一提的是Delta值一般为0x9E3779B9(-0x61C88647),这是判定TEA加密的特征之一。

代码实现

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

示例

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

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

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

void decrypt (uint32_t* v, uint32_t* k) {
uint32_t v0 = v[0], v1 = v[1];
uint32_t delta = 0x9e3779b9;
uint32_t sum = delta * 32;
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] = {0x3e8947cb,0xcc944639};
uint32_t k[4]= {0x1122,0x2233,0x3344,0x4455};
printf("Data is : %x %x\n", v[0], v[1]);
encrypt(v, k);
printf("Encrypted data is : %x %x\n", v[0], v[1]);
decrypt(v, k);
printf("Decrypted data is : %x %x\n", v[0], v[1]);
return 0;
}
/*
Data is : 3e8947cb cc944639
Encrypted data is : 35ef37b1 464adcc9
Decrypted data is : 3e8947cb cc944639
*/

Teakey是四个32位无符号整数,enc是两个32位无符号整数,我们需要牢记这一点。

出题思路:

要求输入flag 长度不定 格式为 flag{*-*}
编写flag格式验证代码
编写取出 v0 和 v1 的代码 并进行类型转换 hex2int
对输入的flag进行加密 得到enc
验证程序是否实现其功能
验证解题思路是否符合逻辑。

程序功能:

获取flag , 不指定长度 
验证flag格式 flag长度为6+1+8+8
按照格式要求 取出 v0 和 v1 如 E01a345b
key 内置
Tea加密
分段进行比较
第一段:
逐字节比较
第二段:
32位无符号数直接比较

解题思路

解题思路:
动态调试,看懂flag格式验证的策略
根据数据特征识别算法
动调 dump 出 key 和最后的 enc
编写解密脚本 得到 plain
根据格式要求代入程序进行验证

简介

XTEA是TEA的扩展,与TEA相比,XTEA使用更长的密钥和更多的迭代轮数,从而提高了安全性。XTEA使用128位密钥和64位块大小,而TEA使用64位密钥和64位块大小。

代码实现

#include <stdint.h>

/* take 64 bits of data in v[0] and v[1] and 128 bits of key[0] - key[3] */

void encrypt(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 decrypt(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;
}

示例

#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 encrypt(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 decrypt(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]={0x61657478,0x5f73695f,0x0};
uint32_t v1[2]={0x79736165,0x0};
uint32_t const k[4]={0X95C4C,0X871D,0X1A7B7,0X12C7C7};
unsigned int r=32;//num_rounds建议取值为32
// v为要加密的数据是两个32位无符号整数
// k为加密解密密钥,为4个32位无符号整数,即密钥长度为128位
printf("Data is:%s%s\n",(char*)v,(char*)v1);
encrypt(r, v, k);
encrypt(r, v1, k);
printf("Encrypted data is:%u %u %u\n",v[0],v[1],v1[0]);
decrypt(r, v, k);
decrypt(r, v1, k);
printf("Decrypted data is:%s%s\n",(char*)v,(char*)v1);
return 0;
}
/*
Data is:xtea_is_easy
Encrypted data is:543258208 1827651953 369487673
Decrypted data is:xtea_is_easy
*/

简介

XXTEA使用更复杂的运算方式,它的块大小可以是任意的,密钥也可以是任意长度的。在加密时,XXTEA会对明文进行分块,然后每个块都会进行加密,加密后的结果再进行拼接,最终形成密文。在解密时,XXTEA会对密文进行分块,然后每个块都会进行解密,解密后的结果再进行拼接,最终形成明文。

代码实现

#include <stdint.h>
#include <string.h>

#define DELTA 0x9E3779B9
#define MX (z >> 5 ^ y << 2) + (y >> 3 ^ z << 4) ^ (sum ^ y) + (k[(p & 3) ^ e] ^ z)

void xxtea_encrypt(uint32_t *v, uint32_t len, uint32_t *k) {
uint32_t n = len - 1;
uint32_t y, z, sum = 0, e, p, q;
q = 6 + 52 / len;
while (q-- > 0) {
sum += DELTA;
e = sum >> 2 & 3;
for (p = 0; p < n; p++) {
y = v[p + 1];
z = v[p] += MX;
}
y = v[0];
z = v[n] += MX;
}
}

void xxtea_decrypt(uint32_t *v, uint32_t len, uint32_t *k) {
uint32_t n = len - 1;
uint32_t y, z, sum, e, p, q;
q = 6 + 52 / len;
sum = q * DELTA;
while (sum != 0) {
e = sum >> 2 & 3;
for (p = n; p > 0; p--) {
z = v[p - 1];
y = v[p] -= MX;
}
z = v[n];
y = v[0] -= MX;
sum -= DELTA;
}
}

示例

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

#define DELTA 0x9E3779B9
#define MX (z >> 5 ^ y << 2) + (y >> 3 ^ z << 4) ^ (sum ^ y) + (k[(p & 3) ^ e] ^ z)

void xxtea_encrypt(uint32_t *v, uint32_t len, uint32_t *k) {
uint32_t n = len - 1;
uint32_t y, z, sum = 0, e, p, q;
q = 6 + 52 / len;
while (q-- > 0) {
sum += DELTA;
e = sum >> 2 & 3;
for (p = 0; p < n; p++) {
y = v[p + 1];
z = v[p] += MX;
}
y = v[0];
z = v[n] += MX;
}
}

void xxtea_decrypt(uint32_t *v, uint32_t len, uint32_t *k) {
uint32_t n = len - 1;
uint32_t y, z, sum, e, p, q;
q = 6 + 52 / len;
sum = q * DELTA;
while (sum != 0) {
e = sum >> 2 & 3;
for (p = n; p > 0; p--) {
z = v[p - 1];
y = v[p] -= MX;
}
z = v[n];
y = v[0] -= MX;
sum -= DELTA;
}
}

int main() {
// The message to encrypt and decrypt
char message[] = "xxtea_is_easy_too";
// The secret key for encryption and decryption
char key[] = "secret_key";

// Calculate the required lengths for the data and key
size_t message_len = strlen(message);
size_t key_len = strlen(key);

// Calculate the number of uint32_t values required to store the data and key
size_t data_len = (message_len + 3) / 4;
size_t key_data_len = (key_len + 3) / 4;

// Allocate memory for the uint32_t arrays for the data and key
uint32_t *data = calloc(data_len, sizeof(uint32_t));
uint32_t *key_data = calloc(key_data_len, sizeof(uint32_t));

// Copy the data and key into the uint32_t arrays
memcpy(data, message, message_len);
memcpy(key_data, key, key_len);

// Encrypt the data using the key
xxtea_encrypt(data, data_len, key_data);

// Print the encrypted data
printf("Encrypted data: ");
for (size_t i = 0; i < message_len; i++) {
printf("%02x", ((uint8_t*)data)[i]);
}
printf("\n");

// Decrypt the data using the key
xxtea_decrypt(data, data_len, key_data);

// Print the decrypted data
printf("Decrypted data: %s\n", (char*)data);

// Free the allocated memory
free(data);
free(key_data);

return 0;
}
/*
Original data:
xxtea_is_easy_too

Encrypted data:
1C178B4E 4A63ABD4 7B734D34 4B7B858C

Decrypted data:
78787465 615F6973 5F656173 795F746F
6F
可以看到,原始数据为字符串"xxtea_is_easy_too",经过XXTEA加密后得到了一组十六进制的密文,然后再将这个密文进行解密后,得到了原始数据。
需要注意的是,解密后的结果多出了一个0x6F,这是因为在加密时,为了填充满64位的数据块,加密函数对数据进行了填充。在解密时,需要将填充的字节去掉。在本例中,填充的是一个字节0x0F,因此在解密时会多出一个0x6F。
*/

通用解密脚本

#include <stdio.h>#include <stdbool.h>
#define MX ((z >> 5 ^ y << 2) + (y >> 3 ^ z << 4) ^ (sum ^ y) + (k[p & 3 ^ e] ^ z))
bool xxtea_decrypt(unsigned int *v, int n, unsigned int *k) { unsigned int z = v[n - 1], y = v[0], sum = 0, e, DELTA = 0x9e3779b9; unsigned int p, q; if (n > 1) { q = 6 + 52 / n; while (q-- > 0) { 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; } return 0; } else if (n < -1) { n = -n; q = 6 + 52 / n; sum = q * DELTA; while (sum != 0) { 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; } return 0; } return 1;}
int main(int argc, char const *argv[]) { unsigned int v[35] = {/*替换密文*/ 3880694563u, 3081185334u, 1506439138u, 2524759489u, 3883935348u, 1026381030u, 2325545814u, 2581382044u, 1881594093u, 1781792173u, 4103492874u, 1553756062u, 468045900u, 1730391575u, 1383114178u, 2890011402u, 2227070898u, 1885128569u, 1548828056u, 4214676013u, 571971141u, 1558401693u, 3515474427u, 3898332297u, 1942540575u, 1421197718u, 3061626000u, 555214026u, 2648963476u, 794468778u, 2816999933u, 3272437419u, 464379036u, 877899850u, 2460223225u }; unsigned int key[4] = {1, 2, 3, 4};/*替换密钥*/ xxtea_decrypt(v, -35, key); for (int i = 0; i < 35; i++) printf("%c", v[i]);}

在线代码运行网站

https://tool.lu/coderunner/https://code.y444.cn/cpphttps://www.nhooo.com/tool/cpp/https://c.runoob.com/compile/12/https://www.runoob.com/try/runcode.php?filename=helloworld&type=cpp

解决逆向题大部分出现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加密系列

[GDOUCTF2023]tea

查壳是64位无壳,ida64直接查看字符串

交叉引用一下you are right,定位到关键函数

__int64 sub_140016230()
{
char *v0; // rdi
__int64 i; // rcx
char v3[32]; // [rsp+0h] [rbp-20h] BYREF
char v4; // [rsp+20h] [rbp+0h] BYREF
int v5; // [rsp+24h] [rbp+4h]
int v6; // [rsp+44h] [rbp+24h]
int v7[12]; // [rsp+68h] [rbp+48h] BYREF
_DWORD v8[16]; // [rsp+98h] [rbp+78h] BYREF
int v9[31]; // [rsp+D8h] [rbp+B8h] BYREF
int j; // [rsp+154h] [rbp+134h]
int k; // [rsp+174h] [rbp+154h]
int l; // [rsp+194h] [rbp+174h]

v0 = &v4;
for ( i = 102i64; i; --i )
{
*(_DWORD *)v0 = -858993460;
v0 += 4;
}
sub_14001137F(&unk_140023009);
v5 = 32;
v6 = 0;
v7[0] = 1234;
v7[1] = 5678;
v7[2] = 9012;
v7[3] = 3456;
memset(v8, 0, 0x28ui64);
v9[15] = 0;
v9[23] = 0;
sub_1400113E8();
for ( j = 0; j < 10; ++j )
sub_1400111FE("%x", &v8[j]); // 读入16进制数组v8
sub_140011339(v7); // v7 = [2233,4455,6677,8899]
sub_140011145(v8, v9); // v8赋值给v9
sub_1400112B7(v8, v7); // xtea加密v8,v7为key
v6 = sub_140011352(v8);
// 判断v8是否等于[0x1A800BDA,0xF7A6219B,0x491811D8,0xF2013328,0x156C365B,
//0x3C6EAAD8,0x84D4BF28,0xF11A7EE7,0x3313B252,0xDD9FE279]
if ( v6 )
{
sub_140011195("you are right\n");
for ( k = 0; k < 10; ++k )
{
for ( l = 3; l >= 0; --l )
sub_140011195("%c", (unsigned __int8)((unsigned int)v9[k] >> (8 * l)));// 输出flag
}
}
else
{
sub_140011195("fault!\nYou can go online and learn the tea algorithm!");
}
sub_140011311(v3, &unk_14001AE90);
return 0i64;
}

简单分析如上,重点看一下xtea加密函数

__int64 __fastcall sub_140011900(__int64 a1, __int64 a2)
{
__int64 result; // rax
int v3; // [rsp+44h] [rbp+24h]
int i; // [rsp+64h] [rbp+44h]
unsigned int v5; // [rsp+84h] [rbp+64h]
unsigned int v6; // [rsp+C4h] [rbp+A4h]

result = sub_14001137F(&unk_140023009);
for ( i = 0; i <= 8; ++i )
{
v5 = 0;
v6 = 256256256 * i;
v3 = i + 1;
do
{
++v5;
*(_DWORD *)(a1 + 4i64 * i) += v6 ^ (*(_DWORD *)(a1 + 4i64 * v3)
+ ((*(_DWORD *)(a1 + 4i64 * v3) >> 5) ^ (16 * *(_DWORD *)(a1 + 4i64 * v3)))) ^ (v6 + *(_DWORD *)(a2 + 4i64 * (v6 & 3)));
*(_DWORD *)(a1 + 4i64 * v3) += (v6 + *(_DWORD *)(a2 + 4i64 * ((v6 >> 11) & 3))) ^ (*(_DWORD *)(a1 + 4i64 * i)
+ ((*(_DWORD *)(a1 + 4i64 * i) >> 5) ^ (16 * *(_DWORD *)(a1 + 4i64 * i))));
v6 += 256256256;
}
while ( v5 <= 0x20 );
result = (unsigned int)(i + 1);
}
return result;
}

32次迭代的变体xtea加密,可以看出来delta值被魔改了,是v6=256256256

exp

def xtea_decrypt(data,key):
for j in range(8,-1,-1):
i = 0
delta = 256256256
sum = delta * (32 + j)
n = j + 1
while i <= 32:
i += 1
data[n] = (data[n] - (((key[(sum >> 11) & 3]) + sum) ^ (((data[j] << 4) ^ (data[j] >> 5)) + data[j]))) & 0xffffffff
data[j] = (data[j] - (((key[sum & 3] + sum) ^ ((data[n] << 4) ^ (data[n] >> 5)) + data[n]) ^ sum)) & 0xffffffff
sum -= delta
return data

v8 = [0x1A800BDA,0xF7A6219B,0x491811D8,0xF2013328,0x156C365B,
0x3C6EAAD8,0x84D4BF28,0xF11A7EE7,0x3313B252,0xDD9FE279]
key = [2233,4455,6677,8899]

flag = xtea_decrypt(v8,key)

for i in range(10):
for j in range(3,-1,-1):
print(chr((flag[i] >> (j * 8)) & 0xFF), end='')

有个地方要特别注意的就是读入的v8是16进制无符号32位整数
如果不进行& 0xffffffff,运行结果是乱码
这耗费了我好多时间检查,问题出在C和Python对无符号整数的处理方式不同。在C中,当无符号整数溢出时,它会回绕到0。但是,在Python中,当整数溢出时,它们会自动升级为长整数。所以需要通过& 0xffffffff来保证解密出来是无符号32位整数。
最终运行结果HZCTF{hzCtf_94_re666fingcry5641qq}
根据题目要求flagNSSCTF{hzCtf_94_re666fingcry5641qq}

flag

NSSCTF{hzCtf_94_re666fingcry5641qq}

[津门杯2021]GoodRe

把tea的运算操作都以函数形式呈现,耐心分析每个函数作用
然后重命名简化反汇编结果,以便分析

这是sub_1B30函数内部,通过分析各个函数可推断出是tea

exp

def tea_decrypt(data,key):
i = 0
delta = 0x830A5376 ^ 0x1D3D2ACF
sum = delta * 32 & 0xffffffff
while i < 32:
i += 1
data[1] -= ((data[0]<<4) + key[2]) ^ (data[0] + sum) ^ ((data[0]>>5) + key[3])
data[1] = data[1] & 0xffffffff
data[0] -= ((data[1]<<4) + key[0]) ^ (data[1] + sum) ^ ((data[1]>>5) + key[1])
data[0] = data[0] & 0xffffffff
sum -= delta
return data
code =[0x79AE1A3B, 0x596080D3, 0x80E03E80, 0x846C8D73,
0x21A01CF7,0xC7CACA32, 0x45F9AC14, 0xC5F5F22F]
key = [17,17,17,17]
flag = ''
for j in range(0,8,2):
endata = code[j:j+2]
dedata = tea_decrypt(endata,key)
flag += hex(dedata[0])[2:]
flag += hex(dedata[1])[2:]
print(flag.upper())
#7DEA3F6D3B3D6C0C620864ADD2FA2AE1A61F2736F0060DA0B97E8356D017CE59

flag

flag{7DEA3F6D3B3D6C0C620864ADD2FA2AE1A61F2736F0060DA0B97E8356D017CE59}

总结

这次学完了这个系列的算法,来总结一下,不要弄混淆了。

相同点:

  1. key 128 bit(当然还有很多算法的key=128bit)

  2. 特征量0x9e3779b9

  3. 主要加密部分进行移位和异或操作

首先如果题目中出现常量0x9e3779b9,那么肯定是Tea相关算法了。

区分:

  1. Tea的主加密部分为<<4,>>5,xor,循环32轮

  2. xTea的主加密部分<<4,>>5,>>11,xor,循环次数不定,但通常也为32轮,需要传入3个参数

  3. xxTea的主加密部分>>5,<<2,>>3,<<4,xor,循环次数为6+52/n,enc长度大于64

  • [1] TEA系列加密解密

  • [2] 维基百科TEA


文章来源: http://mp.weixin.qq.com/s?__biz=MzU1Mjk3MDY1OA==&mid=2247508212&idx=2&sn=44cb14bffb5c43b4ce727abe59493178&chksm=fbfb1039cc8c992f399e658b32b57dcc19c119e71df0203d41851f3e0a134933b5004f7b10e1&scene=0&xtrack=1#rd
如有侵权请联系:admin#unsafe.sh