Base-N算法及逆向方法初探
这里说的逆向仍然是CTF逆向，这篇文章是我对CRC逆向算法的一个浅显的总结，如有不足，请多担待。
上次研究了 CRC校验
(https://www.52pojie.cn/thread-783879-1-1.html
https://kabeor.cn/CRC%E6%A0%A1%E9%AA%8C%E7%AE%97%E6%B3%95%E5%8F%8A%E9%80%86%E5%90%91%E6%96%B9%E6%B3%95%E5%88%9D%E6%8E%A2/)
，这次来看一下Base-N系列的算法吧
在CTF的算法逆向中Base系列算是最常见的了，各种组合和变体，下面就具体来说说吧。
算法分析
Base64
Base64是一种基于64个可打印字符来表示二进制数据的表示方法。由于2^6=64，所以每6个比特为一个单元，对应某个可打印字符。3个字节有24个比特，对应于4个Base64单元，即3个字节可由4个可打印字符来表示。它可用来作为电子邮件的传输编码。在Base64中的可打印字符包括字母A-Z、a-z、数字0-9，这样共有62个字符，此外两个可打印符号在不同的系统中而不同。一些如uuencode的其他编码方法，和之后BinHex的版本使用不同的64字符集来代表6个二进制数字，但是不被称为Base64。
Base64常用于在通常处理文本数据的场合，表示、传输、存储一些二进制数据，包括MIME的电子邮件及XML的一些复杂数据。 -----维基百科 https://zh.wikipedia.org/wiki/Base64
编码规则
第一步，将每三个字节作为一组，一共是24个二进制位
第二步，将这24个二进制位分为四组，每个组有6个二进制位
第三步，在每组前面加两个00，扩展成32个二进制位，即四个字节
第四步，根据下表，得到扩展后的每个字节的对应符号，这就是Base64的编码值
如果要编码的字节数不能被3整除，最后会多出1个或2个字节，那么可以使用下面的方法进行处理：先使用0字节值在末尾补足，使其能够被3整除，然后再进行Base64的编码。在编码后的Base64文本后加上一个或两个=号，代表补足的字节数。也就是说，当最后剩余两个八位字节（2个byte）时，最后一个6位的Base64字节块有四位是0值，最后附加上两个等号；如果最后剩余一个八位字节（1个byte）时，最后一个6位的base字节块有两位是0值，最后附加一个等号。 参考下表：
C代码实现
#include <stdio.h>
#include "string.h"
#include "stdlib.h"
const char base[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=";
static char find_pos(char ch);
char *base64_encode(const char* data, int data_len,int *len);
char *base64_decode(const char* data, int data_len,int *len);
/**
*找到ch在base中的位置
*/
static char find_pos(char ch)
{
//the last position (the only) in base[]
char *ptr = (char*)strrchr(base, ch);
return (ptr - base);
}
/**
*BASE64编码
*/
char *base64_encode(const char* data, int data_len,int *len)
{
int prepare = 0;
int ret_len;
*len=0;
int temp = 0;
char *ret = NULL;
char *f = NULL;
int tmp = 0;
char changed[4];
int i = 0;
ret_len = data_len / 3;
temp = data_len % 3;
if (temp > 0)
{
ret_len += 1;
}
//最后一位以''结束
ret_len = ret_len*4 + 1;
ret = (char *)malloc(ret_len);
if ( ret == NULL)
{
printf("No enough memory.n");
exit(0);
}
memset(ret, 0, ret_len);
f = ret;
//tmp记录data中移动位置
while (tmp < data_len)
{
temp = 0;
prepare = 0;
memset(changed, 0, 4);
while (temp < 3)
{
if (tmp >= data_len)
{
break;
}
//将data前8*3位移入prepare的低24位
prepare = ((prepare << 8) | (data[tmp] & 0xFF));
tmp++;
temp++;
}
//将有效数据移到以prepare的第24位起始位置
prepare = (prepare<<((3-temp)*8));
for (i = 0; i < 4 ;i++ )
{
//最后一位或两位
if (temp < i)
{
changed[i] = 0x40;
}
else
{
//24位数据
changed[i] = (prepare>>((3-i)*6)) & 0x3F;
}
*f = base[ changed[ i ] ];
f++;
(*len)++;
}
}
*f = '';
return ret;
}
//BASE64解码
char *base64_decode(const char *data, int data_len,int *len)
{
int ret_len = (data_len / 4) * 3+1;
int equal_count = 0;
char *ret = NULL;
char *f = NULL;
*len=0;
int tmp = 0;
int temp = 0;
char need[3];
int prepare = 0;
int i = 0;
if (*(data + data_len - 1) == '=')
{
equal_count += 1;
}
if (*(data + data_len - 2) == '=')
{
equal_count += 1;
}
ret = (char *)malloc(ret_len);
if (ret == NULL)
{
printf("No enough memory.n");
exit(0);
}
memset(ret, 0, ret_len);
f = ret;
while (tmp < (data_len - equal_count))
{
temp = 0;
prepare = 0;
memset(need, 0, 4);
while (temp < 4)
{
if (tmp >= (data_len - equal_count))
{
break;
}
prepare = (prepare << 6) | (find_pos(data[tmp]));
temp++;
tmp++;
}
prepare = prepare << ((4-temp) * 6);
for (i=0; i<3 ;i++ )
{
if (i == temp)
{
break;
}
*f = (char)((prepare>>((2-i)*8)) & 0xFF);
f++;
(*len)++;
}
}
*f = '';
if(data[data_len-1]=='=')
{
(*len)--;
}
/*
while(*(--f)=='')
{
(*len)--;
}
*/
return ret;
}
int main(){
char *former = "hello";
int len1,len2;
printf("%sn",former);
char *after = base64_encode(former, 5,&len1);
printf("%d %sn",len1,after);
former = base64_decode(after, len1,&len2);
printf("%d %sn",len2,former);
}
逆向识别后面一块说，先来看看Base32吧
Base32
编码规则
Base32这种数据编码机制，主要用来把二进制数据编码成可见的字符串，其编码规则是：任意给定一个二进制数据，以5个位(bit)为一组进行切分(base64以6个位(bit)为一组)，对切分而成的每个组进行编码得到1个可见字符。Base32编码表字符集中的字符总数为25=32个，这也是Base32名字的由来。
下面是Base32的table
C代码实现
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//base32 表包含 0~9 以及小写字母 (去除'a','i','l','o')，
//共 32 个字符
static const char base32_alphabet[32] = {
'0', '1', '2', '3', '4', '5', '6', '7',
'8', '9', 'b', 'c', 'd', 'e', 'f', 'g',
'h', 'j', 'k', 'm', 'n', 'p', 'q', 'r',
's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
};
/*
* 匹配 base32_alphabet
*/
int find_number(char m) {
int i;
for(i = 0; i < 32; ++i)
{
if(m == base32_alphabet[i])
return i;
}
return -1;
}
/*
* base32 编码
*/
char* base32_encode(char *bin_source){
int i;
int j = 0;
static char str[10];
for(i=0;i<strlen(bin_source);++i){
if((i+1)%5==0){
j++;
int num = (bin_source[i]-'0')+(bin_source[i-1]-'0')*2\
+(bin_source[i-2]-'0')*2*2+(bin_source[i-3]-'0')*2*2*2\
+(bin_source[i-4]-'0')*2*2*2*2;
str[j-1] = base32_alphabet[num];
}
}
return str;
}
/*
* base32 解码
*/
int* base32_decode(char *str_source){
int i,j;
static int dec[50];
int count=0;
for(i=0;i<strlen(str_source);++i){
for(j=5-1;j>=0;--j){
count++;
//位运算十进制转二进制
dec[count-1] = find_number(str_source[i])>>(j%5)&1;
}
}
return dec;
}
逆向分析
前面写了这么多，终于到重头戏逆向了，先简略概括一下基本运算法则吧
base64编码是用64（2的6次方）个ASCII字符来表示256（2的8次方）个ASCII字符，也就是三位二进制数组经过编码后变为四位的ASCII字符显示，长度比原来增加1/3。
同样，base32就是用32（2的5次方）个特定ASCII码来表示256个ASCII码。所以，5个ASCII字符经过base32编码后会变为8个字符（公约数为40），长度增加3/5.不足8n用“=”补足。
base16就是用16（2的4次方）个特定ASCII码表示256个ASCII字符。1个ASCII字符经过base16编码后会变为2个字符，长度增加一倍。不足2n用“=”补足
Base32在比赛中常见到，就拿Base32的题来举例了
两道题的完整wp都在博客里 ,(https://kabeor.cn/2017%E7%AC%AC%E4%BA%8C%E5%B1%8A%E5%B9%BF%E4%B8%9C%E7%9C%81%E5%BC%BA%E7%BD%91%E6%9D%AF%E7%BA%BF%E4%B8%8A%E8%B5%9BNonstandard/ ,
https://kabeor.cn/2018%E5%B7%85%E5%B3%B0%E6%9E%81%E5%AE%A2%E7%BD%91%E7%BB%9C%E5%AE%89%E5%85%A8%E6%8A%80%E8%83%BD%E6%8C%91%E6%88%98%E8%B5%9B%20RE(1)%20Simple%20Base-N/)
提取重点部分来说
1. 数据
Base系列的补位“=”算是最明显的提示标志了，搜索字符串时见到类似下图就可以考虑Base了
2. 反汇编伪代码
IDA F5，看到大量移位，如图
v14 = v13;
HIDWORD(v15) = v19;
LODWORD(v15) = v23 & 0xFFFFFFF8;
HIDWORD(v16) = v30 | ((unsigned __int64)(v18 & 1) >> 24);
LODWORD(v16) = (((v23 & 0xFFFFFFF8) << 8) + (v18 & 0xFFFFFFC0 | ((v23 & 7) << 8)) + (v18 & 0x3E)) << 8;
v17 = ((v14 & 0x1F)
+ __PAIR__(
HIDWORD(v14) | (unsigned int)((unsigned __int64)(v20 & 3) >> 24),
v14 & 0xFFFFFFE0 | ((v20 & 3) << 8))
+ ((__PAIR__(
v31 | (unsigned int)((unsigned __int64)(v21 & 0xF) >> 24),
v20 & 0xFFFFFF80 | ((v21 & 0xF) << 8))
+ ((__PAIR__(
(__PAIR__(v15 >> 24, (v23 & 0xFFFFFFF8) << 8)
+ __PAIR__(
v29 | (unsigned int)((unsigned __int64)(v23 & 7) >> 24),
v18 & 0xFFFFFFC0 | ((v23 & 7) << 8))
+ (v18 & 0x3E)) >> 24,
v21 & 0xFFFFFFF0 | ((v18 & 1) << 8))
+ v16) << 8)
+ (v20 & 0x7C)) << 8)) >> 32;
HIDWORD(v14) = (v14 & 0x1F)
+ (v14 & 0xFFFFFFE0 | ((v20 & 3) << 8))
+ (((v20 & 0xFFFFFF80 | ((v21 & 0xF) << 8))
+ (((v21 & 0xFFFFFFF0 | ((v18 & 1) << 8)) + (_DWORD)v16) << 8)
+ (v20 & 0x7C)) << 8);
*v24 = byte_403020[(unsigned __int8)v17 >> 3];
v24[1] = byte_403020[(__PAIR__(v17, HIDWORD(v14)) >> 30) & 0x1F];
v24[2] = byte_403020[(__PAIR__(v17, HIDWORD(v14)) >> 25) & 0x1F];
v24[3] = byte_403020[(__PAIR__(v17, HIDWORD(v14)) >> 20) & 0x1F];
v24[4] = byte_403020[(__PAIR__(v17, HIDWORD(v14)) >> 15) & 0x1F];
v24[5] = byte_403020[(__PAIR__(v17, HIDWORD(v14)) >> 10) & 0x1F];
LOBYTE(v16) = __PAIR__(v17, HIDWORD(v14)) >> 5;
v3 = v25;
v24[6] = byte_403020[v16 & 0x1F];
LOBYTE(v16) = byte_403020[BYTE4(v14) & 0x1F];
v2 = v32;
v24[7] = v16;
v24 += 8;
}
while ( v8 < v25 );
result = v28;
}
if ( v22 > 0 )
memset(&result[v26], 61u, v22);
*(&v28[v26] + v22) = 0;
result = v28;
}
return result;
}
核心算法提取出来了，我们看到了
LODWORD(v16) = (((v23 & 0xFFFFFFF8) << 8) + (v18 & 0xFFFFFFC0 | ((v23 & 7) << 8)) + (v18 & 0x3E)) << 8;
和
v24[1] = byte_403020[(__PAIR__(v17, HIDWORD(v14)) >> 30) & 0x1F];
v24[2] = byte_403020[(__PAIR__(v17, HIDWORD(v14)) >> 25) & 0x1F];
v24[3] = byte_403020[(__PAIR__(v17, HIDWORD(v14)) >> 20) & 0x1F];
v24[4] = byte_403020[(__PAIR__(v17, HIDWORD(v14)) >> 15) & 0x1F];
v24[5] = byte_403020[(__PAIR__(v17, HIDWORD(v14)) >> 10) & 0x1F];
每次取5个比特，分别赋给8个值，每个值5个位 ,显然的base32
3. table
table一般在核心算法的上一层函数，数据段也有所显现，当然table也许会被加密或者替换，但都是类似异或，转换进制，运算，奇偶位之类的，照着写脚本就好，
像下图这样就是经过了字母倒序，奇数小写偶数大写，尾部追加得到table
解密脚本
Python3脚本
s = "密文"
table = "表"
def find(x):
if(x=='='):
return 0
return table.index(x)
for i in range(len(s)//8):
p = s[i*8:i*8+8]
t = 0
for j in p:
t = t<<5
t += find(j)
for j in range(5):
print(chr((t&0xff00000000)>>32), end='')
t = t<<8
魔改Base
经过上面的分析也就可以知道Base中可变的几个部分
CTF中常见的变化位置有下面几个
- table
这个上面提到了。。
- 移位数据变化
从例子可以看出决定了题中Base-N的N是多少的是移位个数和移位距离
只要抓住算法的核心思想就能很快识别出来
- 组合
很多题都会通过组合加密的方式来提升题目难度，Base中应该就是加密密文和table了
总结
差不多就是这样了，Base-N相对来说只要熟悉模板就能很快识别了。
就这样，
希望自己能坚持下去，分析不同的算法：）
[复制链接]
发表于 2018-9-7 21:27
发表于 2018-9-7 22:15
|
发表于 2018-9-8 08:30
