-
-
[原创微型加密算法实现及逆向分析
-
2019-8-13 19:11
-
微型加密算法实现及逆向分析
0、前言
这篇文章是之前学习TEA算法写下来的，由于本人水平有限，对于文中可能出现的些许错误敬请指正，文章主要是对TEA系列算法的简单分析，另外本文切实本人原创，但并非首发于看雪，另外对于文中引用的图片和些许代码，若有侵权，务必联系本人。
1、关于TEA系列算法
微型加密算法（Tiny Encryption Algorithm，TEA）是一种易于描述和执行的块密码，通常只需要很少的代码就可实现。其设计者是David Wheeler、Roger Needham
TEA的分组长度为64位，密钥长度为128位，采用Feistel网络，建议32次循环加密即64轮
XTEA是TEA的扩展，同样是一个64位块的Feistel密码，使用128位密钥，建议64轮
XXTEA是一个非平衡Feistel网络分组密码，在可变长度块上运行，这些块是32位大小的任意倍数（最小64位），使用128位密钥
TEA系列算法典型特征是采用密钥调度常数0x9e3779b9
2、加解密实现
1.TEA加解密实现
#include <stdio.h>
void encrypt(unsigned int* v, unsigned int* key) {
unsigned int l = v[0], r = v[1], sum = 0, delta = 0x9e3779b9;
for (size_t i = 0; i < 32; i++) {
sum += delta;
l += ((r << 4) + key[0]) ^ (r + sum) ^ ((r >> 5) + key[1]);
r += ((l << 4) + key[2]) ^ (l + sum) ^ ((l >> 5) + key[3]);
}
v[0] = l;
v[1] = r;
}
void decrypt(unsigned int* v, unsigned int* key) {
unsigned int l = v[0], r = v[1], sum = 0, delta = 0x9e3779b9;
sum = delta *32;
for (size_t i = 0; i < 32; i++) {
r -= ((l << 4) + key[2]) ^ (l + sum) ^ ((l >> 5) + key[3]);
l -= ((r << 4) + key[0]) ^ (r + sum) ^ ((r >> 5) + key[1]);
sum -= delta;
}
v[0] = l;
v[1] = r;
}
int main(int argc, char const *argv[])
{
//test
unsigned int v[2]={1,2},key[4]={1,2,3,4};
printf("%u,%u\n",v[0],v[1]);
encrypt(v,key);
printf("%u,%u\n",v[0],v[1]);
decrypt(v,key);
printf("%u,%u\n",v[0],v[1]);
return 0;
}
2.XTEA加解密实现
#include <stdio.h>
void encrypt(unsigned int* v, unsigned int* key) {
unsigned int l = v[0], r = v[1], sum = 0, delta = 0x9e3779b9;
for (size_t i = 0; i < 32; i++) {
l += (((r << 4) ^ (r >> 5)) + r) ^ (sum + key[sum & 3]);
sum += delta;
r += (((l << 4) ^ (l >> 5)) + l) ^ (sum + key[(sum >> 11) & 3]);
}
v[0] = l;
v[1] = r;
}
void decrypt(unsigned int* v, unsigned int* key) {
unsigned int l = v[0], r = v[1], sum = 0, delta = 0x9e3779b9;
sum = delta * 32;
for (size_t i = 0; i < 32; i++) {
r -= (((l << 4) ^ (l >> 5)) + l) ^ (sum + key[(sum >> 11) & 3]);
sum -= delta;
l -= (((r << 4) ^ (r >> 5)) + r) ^ (sum + key[sum & 3]);
}
v[0] = l;
v[1] = r;
}
int main(int argc, char const *argv[])
{
//test
unsigned int v[2]={1,2},key[4]={1,2,3,4};
printf("%u,%u\n",v[0],v[1]);
encrypt(v,key);
printf("%u,%u\n",v[0],v[1]);
decrypt(v,key);
printf("%u,%u\n",v[0],v[1]);
return 0;
}
3.XXTEA加解密实现
#include <stdbool.h>
#include <stdio.h>
#define MX \
((z >> 5 ^ y << 2) + (y >> 3 ^ z << 4) ^ (sum ^ y) + (k[p & 3 ^ e] ^ z))
bool btea(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) { /* Coding Part */
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) { /* Decoding Part */
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[]) {
// test
unsigned int v[2] = {1, 2}, key[4] = {1, 2, 3, 4};
printf("%u,%u\n", v[0], v[1]);
btea(v, 2, key);
printf("%u,%u\n", v[0], v[1]);
btea(v, -2, key);
printf("%u,%u\n", v[0], v[1]);
return 0;
}
3、XXTEA逆向分析
文件来源：2019RCTF babyre
该题大致为输入一个16位字符串经过多次变换最终输出Bingo! 即可，由于题目的原因出现多解，故还需满足md5(rctf{flag})==5f8243a662cf71bf31d2b2602638dc1d，此处不作解释，由于主要是讲解XXTEA的逆向分析，其他过程暂且不细说，我们看到其中最关键的加密函数sub_55A0DF892CE0。
signed __int64 __fastcall sub_55A0DF892CE0(int *a1, signed int a2, __int64 a3)
{
v3 = a3;
v4 = a2;
v5 = *a1;
v43 = a2;
if ( a2 > 1 )
{
v6 = a2 - 1;
v7 = &a1[a2 - 1];
v8 = 0;
v9 = *v7;
v10 = ((a2 - 4) & 0xFFFFFFFE) + 2;
v45 = 0x9E3779B9 * (52 / a2) - 0x4AB325AA;
do
{
v8 -= 0x61C88647;
v11 = v8 >> 2;
if ( v43 <= 3 )
{
v14 = 0;
}
else
{
v12 = *a1;
v13 = a1;
v14 = 0;
do
{
v15 = v13[1];
v13 += 2;
v16 = (v9 ^ *(_DWORD *)(v3 + 4LL * (((unsigned __int8)v14 ^ (unsigned __int8)v11) & 3))) + (v15 ^ v8);
v17 = v14 + 1;
v14 += 2;
v18 = v12 + ((((v9 >> 5) ^ 4 * v15) + ((v15 >> 3) ^ 16 * v9)) ^ v16);
v12 = *v13;
*(v13 - 2) = v18;
v9 = v15
+ (((4 * v12 ^ (v18 >> 5)) + (16 * v18 ^ (v12 >> 3))) ^ ((v12 ^ v8)
+ (v18 ^ *(_DWORD *)(v3
+ 4LL
* (((unsigned __int8)v11 ^ v17) & 3)))));
*(v13 - 1) = v9;
}
while ( v10 != v14 );
}
v19 = &a1[v14];
do
{
v20 = v19[1];
v21 = v11 ^ v14++;
++v19;
v22 = *(v19 - 1)
+ (((v9 ^ *(_DWORD *)(v3 + 4LL * (v21 & 3))) + (v20 ^ v8)) ^ ((16 * v9 ^ (v20 >> 3)) + ((v9 >> 5) ^ 4 * v20)));
*(v19 - 1) = v22;
v9 = v22;
}
while ( v6 > v14 );
v9 = *v7
+ (((v22 ^ *(_DWORD *)(v3 + 4LL * (((unsigned __int8)v6 ^ (unsigned __int8)v11) & 3))) + (*a1 ^ v8)) ^ ((4 * *a1 ^ (v22 >> 5)) + (16 * v22 ^ ((unsigned int)*a1 >> 3))));
*v7 = v9;
}
while ( v8 != v45 );
return 0LL;
}
result = 1LL;
if ( a2 < -1 )
{
v24 = -a2;
v25 = 0x9E3779B9 * (52 / v24 + 6);
if ( v25 )
{
v26 = &a1[v24 - 1];
v27 = ~v4;
v44 = &a1[~v4];
v28 = ~v4 - 2 - ((~v4 - 3) & 0xFFFFFFFE);
do
{
v29 = v25 >> 2;
if ( v27 <= 2 )
{
v31 = v27;
}
else
{
v30 = v44;
v31 = v27;
v32 = *v44;
do
{
v33 = *(v30 - 1);
v30 -= 2;
v34 = v32;
v32 = *v30;
v35 = ((v5 ^ v25) + (v33 ^ *(_DWORD *)(v3 + 4LL * (((unsigned __int8)v31 ^ (unsigned __int8)v29) & 3)))) ^ ((4 * v5 ^ (v33 >> 5)) + ((v5 >> 3) ^ 16 * v33));
v36 = v31 - 1;
v31 -= 2;
v37 = v34 - v35;
v38 = *v30;
v30[2] = v37;
v5 = v33
- (((16 * v38 ^ (v37 >> 3)) + ((v32 >> 5) ^ 4 * v37)) ^ ((v32 ^ *(_DWORD *)(v3
+ 4LL
* (((unsigned __int8)v29 ^ v36) & 3)))
+ (v25 ^ v37)));
v30[1] = v5;
}
while ( v28 != v31 );
}
v39 = &a1[v31];
do
{
v40 = *(v39 - 1);
--v39;
v5 = v39[1]
- (((v5 ^ v25) + (v40 ^ *(_DWORD *)(v3 + 4LL * (((unsigned __int8)v29 ^ (unsigned __int8)v31) & 3)))) ^ (((v5 >> 3) ^ 16 * v40) + ((v40 >> 5) ^ 4 * v5)));
v39[1] = v5;
--v31;
}
while ( v31 );
v41 = *a1
- (((((unsigned int)*v26 >> 5) ^ 4 * v5) + (16 * *v26 ^ (v5 >> 3))) ^ ((*(_DWORD *)(v3 + 4LL * (v29 & 3)) ^ *v26)
+ (v25 ^ v5)));
v42 = v25 == 0x9E3779B9;
v25 += 0x61C88647;
v5 = v41;
*a1 = v41;
}
while ( !v42 );
}
return 0LL;
}
return result;
}
我们可以看到反编译的伪代码也是十分清晰的，纵观整个函数，整个函数过程都围绕着0x9E3779B9这个魔数，相信很多人都有似曾相识的感觉，没错！该函数与上文的XXTEA加解密实现结构基本相同，实现了XXTEA加解密。接下来我们看到函数的调用
sub_55A0DF892CE0(v, -(v10 >> 2), key); // stea(v,-2,key)
结合其他有关信息可以简单看出函数参数v为两个32位无符号数， -(v10 >> 2)的值为-2，key为128位密钥，它们是0xE0C7E0C7, 0xC6F1D3D7, 0xC6D3C6D3, 0xC4D0D2CE，此处调用了XXTEAdecode对两个32位无符号数进行解密，解密结果与之后的常量异或后比较判断
整个题目的核心算法就是XXTEA，只要识别出该算法，那么逆向将变得非常简单，逻辑无非就是输入一个16进制字符串之后hexencode，得到一个64位无符号数（即2个32位无符号数），然后将之2个32位无符号数xxteadecrypt得到新的64位无符号数，此处要求最后一个字节的值小于0x4，并将第（8-最后一个字节的值+1）字节的值置为00，而后将之经下一个函数进行一些位操作验证结果是否等于0x69e2,这一步并不改变原有值无视之，最终验证按字节与0x17异或出来结果是否为Bingo!，结合上面猜测第7字节的值为00，最后一个字节值为0x02，且md5(rctf{flag})==5f8243a662cf71bf31d2b2602638dc1d，由此可以确定最终解密后的64位无符号数的值为0x02XX367870797e55(小端序)，直接写脚本就可以爆破次高8位即可，依次就可以得到该题的flag了
#include <openssl/md5.h>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;
// -lcrypto
string MD5(const string& src) {
MD5_CTX ctx;
string md5_string;
unsigned char md[16] = {0};
char tmp[33] = {0};
MD5_Init(&ctx);
MD5_Update(&ctx, src.c_str(), src.size());
MD5_Final(md, &ctx);
for (int i = 0; i < 16; ++i) {
memset(tmp, 0x00, sizeof(tmp));
sprintf(tmp, "%02X", md[i]);
md5_string += tmp;
}
return md5_string;
}
string aaa(unsigned int* v) {
string str;
for (size_t i = 0; i < 2; i++) {
for (size_t j = 0; j < 8; j += 2) {
unsigned char cur = v[i] & 0xff;
str += ((cur & 0xf0) >> 4) < 10 ? (((cur & 0xf0) >> 4) + 0x30)
: (((cur & 0xf0) >> 4) + 0x57);
str += (cur & 0x0f) < 10 ? ((cur & 0x0f) + 0x30) : ((cur & 0x0f) + 0x57);
v[i] >>= 8;
}
}
return str;
}
#define MX \
((z >> 5 ^ y << 2) + (y >> 3 ^ z << 4) ^ (sum ^ y) + (k[p & 3 ^ e] ^ z))
bool btea(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) { /* Coding Part */
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) { /* Decoding Part */
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() {
// 55 7e 79 70 78 36 xx 02
unsigned int t[2] = {0x70797e55, 0x02003678};
unsigned int v[2] = {0, 0};
unsigned int key[4] = {0xE0C7E0C7, 0xC6F1D3D7, 0xC6D3C6D3, 0xC4D0D2CE};
string flagmd5 = "5F8243A662CF71BF31D2B2602638DC1D";
for (unsigned long long i = 0x0; i <= 0xff; i += 0x1) {
v[0] = t[0];
v[1] = t[1] | (i << 16);
string flag = "";
flag += "rctf{";
btea(v, 2, key);
flag += aaa(v);
flag += "}";
cout << flag << endl;
if (MD5(flag) == flagmd5) {
cout << "success!" << endl;
cout << flag << endl;
return 0;
}
}
return 0;
}
4、TX TEA魔改算法
TX 将TEA算法魔改成16轮（TEA保密的最低要求）并且广泛应用
相关内容可以看这里腾讯TEA加密算法
主要就是将加密轮次改为16轮，并且采用改进的CBC模式加密
5、总结
对于TEA系列算法的识别只要依据常数0x9e3779b9并且其相关加密结构就可以很容易判断是TEA、XTEA亦或XXTEA，之后只要找到其密文以及加密密钥辅以以上加解密实现代码就可以很快解密了，TEA算法在逆向分析中，IDA反编译以后一般都是比较清晰的，只要有一定的了解就能轻而易举的识别出对应算法，而后动态调试验证即可，至于findcrypto3插件识别也是依据常数识别的，所以只要知道这个特征即可。
6、附件
7、参考文献
加密与解密第四版—TEA算法
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
最后于 2019-8-13 19:12
被丿feng编辑
，原因：
|
|
|---|---|
|
|
|
|
|
流程图只是一轮的，流程图对应的代码是 ((z >>5^ y <<2)+(y >>3^ z <<4) ^ (sum^ y)+(k[p &3^ e] ^ z)) z += MX
最后于 2019-8-13 23:03
被丿feng编辑
，原因：
|
|
|
|
看场雪
