逆向算法复习第二弹：Tea系列算法
Tea算法
“TEA” 的全称为”Tiny Encryption Algorithm” 由于实现简单，加密安全（QQ和微信的一些协议中就是使用的Tea加密），深受ctf出题人的喜爱。因此tea算法成为ctf REer的一种必学算法。TEA算法使用64位的明文分组和128位的密钥，它使用Feistel分组加密框架，需要进行 64 轮迭代。该算法使用了一个神秘常数δ作为倍数，它来源于黄金比率2654435769 （0x9E3779B9），以保证每一轮加密都不相同。
Tea算法实现：
加密
加密代码：
c
void encrypt(uint32_t* v,uint32_t* key){
uint32_t v0=v[0],v1=v[1],sum=0,i;
uint32_t delta=0x9e3779b9;
uint32_t k0=key[0],k1=key[1],k2=key[2],k3=key[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;
}
解密
加密过程很清晰，那么解密过程我们只要把它倒过来写就好
void decrypt(uint32_t* v,uint32_t* key){
uint32_t v0=v[0],v1=v[1],sum=0xC6EF3720,i;
uint32_t delta=0x9e3779b9;
uint32_t k0=key[0],k1=key[1],k2=key[2],k3=key[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算法有很鲜明的特征：
可能存在针对64bit以及128bit数字的操作（输入的msg和key）
存在先进行位移，然后异或的类似操作（(z>>5^y<<2)这类混合变换）
前面一个复杂的混合变换的结果可能会叠加到另一个值上，两者相互叠加（Feistel 结构）
获取密钥的时候，会使用某一个常量值作为下标（key[(sum>>11) & 3]）
会在算法开始定义一个delta，并且这个值不断的参与算法，但是从来不会受到输入的影响（delta数值，根据见过的题目中很少会直接使用0x9e3779b9）
即32或64轮加密，以及有一个关键的delta值，难点主要是如何从出题人魔改过的代码中找到v0，v1，delta以及加密过程。
解密脚本可以参考知识库中现有的脚本，改改加密方式，delta值这些就好
脚本：
c
//tea
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
void Decrypt(uint32_t* data, uint32_t* key)
{
uint32_t v0 = data[0], v1 = data[1];
uint32_t delta = 0x9e3779b9;
uint32_t sum = delta * 32;
for (int i = 0; i < 32; i++)
{
v1 -= ((v0 << 4) + key[2]) ^ (v0 + sum) ^ ((v0 >> 5) + key[3]);
v0 -= ((v1 << 4) + key[0]) ^ (v1 + sum) ^ ((v1 >> 5) + key[1]);
sum -= delta;
}
data[0] = v0;
data[1] = v1;
}
int main()
{
uint32_t encryptedData[] = { 0xc873914f, 0x4a628600, 0x20c77a1c, 0x1a877aaa, 0xd6faa982, 0x60d1c964, 0xb9884c32, 0x2a08a862, 0xc74a0036, 0x8f2ee196, 0xef08a6a9, 0xa3850896 };
uint32_t key[] = { 0x11111111, 0x11111111, 0x11111111, 0x11111111 };
int dataSize = sizeof(encryptedData) / sizeof(encryptedData[0]);
for (int i = 0; i < dataSize; i += 2)
{
Decrypt(&encryptedData[i], key);
}
int decryptedSize = dataSize * 4 + 1;
char* decryptedString = (char*)malloc(decryptedSize);
memset(decryptedString, 0, decryptedSize);
for (int i = 0; i < dataSize; i++)
{
char* bytes = (char*)&encryptedData[i];
decryptedString[i * 4] = bytes[0];
decryptedString[i * 4 + 1] = bytes[1];
decryptedString[i * 4 + 2] = bytes[2];
decryptedString[i * 4 + 3] = bytes[3];
}
printf("Decrypted String: %s\n", decryptedString);
free(decryptedString);
return 0;
}
xTea算法
TEA 算法发布不久，被发现存在缺陷，作为回应，设计者提出了一个 TEA 的升级版本——XTEA（有时也被称为“tean”）。XTEA 跟 TEA 使用了相同的简单运算，但它采用了截然不同的顺序，为了阻止密钥表攻击，四个子密钥（在加密过程中，原 128 位的密钥被拆分为 4 个 32 位的子密钥）采用了一种不太正规的方式进行混合。总的来说 xTEA就是在TEA算法基础上加了一些内容，而加解密过程基本没变。
加解密：
#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算法
相比TEA,xTEA算法，xxTEA算法的优势是原字符串长度可以不是4的倍数了
加密过程：
加密：
#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])//n为v数组长度
{
uint32_t y,z,sum;
unsigned p,rounds,e;
if(n>1)
{
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];
v[p]+=MX;
z=v[p];
}
y=v[0];
z=v[n-1]+=MX;
}
while(--rounds);
}
}
解密过程：
解密：
#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 dtea(uint32_t *v,int n,uint32_t const key[4])//n为v数组长度
{
rounds = 6 + 52/n;
sum = rounds*DELTA;
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);
}
xxTea算法的特征：
1. key 128 bit
2. enc => 32*i(i=>2)
3. 特征量`0x9e3779b9`
4. 两层循环，通常记住最外层的循环为rounds=6+52/n
5. 5,2,3,4 左右移操作
解密脚本：
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) /* Encoding 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 = rounds*DELTA;
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;
}
//////////////////////同x/////////////////////////////
#include <stdint.h>
/* XXTEA加密算法的加密过程 */
void xxtea_encrypt(uint32_t *v, int n, uint32_t *key) {
uint32_t y, z, sum, delta, e;
uint32_t p, q, rounds, limit;
uint32_t *k = key;
rounds = 6 + 52 / n; // 计算加密轮数
sum = 0;
delta = 0x9E3779B9; // 初始化delta常数
limit = rounds * delta; // 计算sum的最大值
q = 6 + limit / delta;
while (q-- > 0) { // 执行加密轮数
sum += delta; // 更新sum
e = sum >> 2 & 3; // 计算e值
for (p = 0; p < n; p++) { // 对每个数据块执行加密操作
y = v[(p + 1) % n];
z = v[p] += ((v[(p + n - 1) % n] >> 5) ^ (y << 2)) + ((y >> 3) ^ (v[(p + n - 1) % n] << 4)) ^ ((sum ^ y) + (k[(p ^ e) & 3] ^ v[(p + n - 1) % n]));
// 计算加密后的数据块
}
}
}
/* XXTEA加密算法的解密过程 */
void xxtea_decrypt(uint32_t *v, int n, uint32_t *key) {
uint32_t y, z, sum, delta, e;
uint32_t p, q, rounds, limit;
uint32_t *k = key;
rounds = 6 + 52 / n; // 计算加密轮数
sum = rounds * 0x9E3779B9; // 初始化sum常数
delta = 0x9E3779B9; // 初始化delta常数
limit = rounds * delta; // 计算sum的最大值
q = 6 + limit / delta;
while (q-- > 0) { // 执行加密轮数
e = sum >> 2 & 3; // 计算e值
for (p = n - 1; p > 0; p--) { // 对每个数据块执行解密操作
z = v[(p + n - 1) % n];
y = v[p] -= ((v[(p + n - 1) % n] >> 5) ^ (v[(p + 1) % n] << 2)) + ((v[(p + 1) % n] >> 3) ^ (v[(p + n - 1) % n] << 4)) ^ ((sum ^ v[(p + 1) % n]) + (k[(p ^ e) & 3] ^ v[(p + n - 1) % n]));
// 计算解密后的数据块
}
z = v[(n + n - 1) % n];
y = v[0] -= ((v[(n + n - 1) % n] >> 5) ^ (v[(1) % n] << 2)) + ((v[(1) % n] >> 3) ^ (v[(n + n - 1) % n] << 4)) ^ ((sum ^ v[(1) % n]) + (k[(0 ^ e) & 3] ^ v[(n + n - 1) % n]));
// 特殊处理第一个和最后一个数据块
sum -= delta; // 更新sum
}
}
Tea系列算法特征总结：
根据上文对tea算法的源码分析，我们得出TEA算法的如下特征：
key 128 bit {2,2,3,4} 传入两个32位无符号整数 三个累加量，其中最后赋值给传入的参数 存在«4 , »5 , xor等操作 特征量：0x9e3779b9
至于xTEA,xxTEA等TEA算法的特殊变种，由于都是在原始TEA算法上做的局部改动，特征上与tea算法没有本质上的不同，只不过可能有位运算位数不同。具体区别如下：
相同点：
- key 128 bit特征量
0x9e3779b9 - 主要加密部分进行移位和异或操作
首先如果题目中出现常量
0x9e3779b9，那么肯定是Tea相关算法了。 区分： - Tea的主加密部分为
<<4,>>5,xor，循环32轮 - xTea的主加密部分
<<4,>>5,>>11,xor,循环次数不定，但通常也为32轮，需要传入3个参数 - xxTea的主加密部分
>>5,<<2,>>3,<<4,xor,循环次数为6+52/n，enc长度大于64
难点还是在代码审计部分，学好C语言非常重要
参考：
十分钟带你吃透TEA算法 这个视频挺适合入门