吾爱破解 - LCG - LSG |安卓破解|病毒分析|破解软件|www.52pojie.cn

 找回密码
 注册[Register]

QQ登录

只需一步,快速开始

搜索
查看: 3015|回复: 25

[原创] Base-N算法及逆向方法初探

  [复制链接]
kabeo 发表于 2018-9-7 21:27
本帖最后由 kabeo 于 2018-9-8 17:50 编辑

Base-N算法及逆向方法初探

这里说的逆向仍然是CTF逆向,这篇文章是我对CRC逆向算法的一个浅显的总结,如有不足,请多担待。

如有转载,请注明出处,博客地址: https://kabeor.cn

上次研究了 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中常见的变化位置有下面几个

  1. table

这个上面提到了。。

  1. 移位数据变化

从例子可以看出决定了题中Base-N的N是多少的是移位个数和移位距离
只要抓住算法的核心思想就能很快识别出来

  1. 组合

很多题都会通过组合加密的方式来提升题目难度,Base中应该就是加密密文和table了


总结

差不多就是这样了,Base-N相对来说只要熟悉模板就能很快识别了。

就这样,
希望自己能坚持下去,分析不同的算法:)



免费评分

参与人数 10威望 +2 吾爱币 +17 热心值 +10 收起 理由
叶pp123 + 1 + 1 我很赞同!
siuhoapdou + 1 + 1 谢谢@Thanks!
sunnylds7 + 1 + 1 热心回复!
快乐大笨 + 1 + 1 鼓励转贴优秀软件安全工具和文档!
Sound + 2 + 9 + 1 欢迎分析讨论交流,吾爱破解论坛有你更精彩!
gink + 1 + 1 热心回复!
淡蓝色的花 + 1 + 1 用心讨论,共获提升!
二逼159 + 1 + 1 谢谢@Thanks!
山郭 + 1 + 1 热心回复!
peter_king + 1 谢谢@Thanks!

查看全部评分

本帖被以下淘专辑推荐:

发帖前要善用论坛搜索功能,那里可能会有你要找的答案或者已经有人发布过相同内容了,请勿重复发帖。

 楼主| kabeo 发表于 2018-9-8 08:30
Hmily 发表于 2018-9-7 22:15
[ i]换成这样的,中间加个空格吧,discuz没法禁用这个。

或者勾选禁用编辑器代码试试

好。我试试
七宗罪丶 发表于 2018-9-10 12:42
IDA 对经过编译器优化过的四则运算识别度还是很有限  所以才会有大量位移的伪代码
淡蓝色的花 发表于 2018-9-7 21:36
Hmily 发表于 2018-9-7 22:15
[ i]换成这样的,中间加个空格吧,discuz没法禁用这个。

或者勾选禁用编辑器代码试试
linuxprobe 发表于 2018-9-7 22:18
看了之后想放弃的感觉。
sxzx 发表于 2018-9-7 22:30
学习了,谢谢分享
胖子哦 发表于 2018-9-7 22:48

学习了,谢谢分享
liuhaitao52PJ 发表于 2018-9-7 22:50
内容 有点多,我要慢慢学,谢谢楼主分享!
zz931205 发表于 2018-9-7 23:21
感谢大佬,学习中
头像被屏蔽
freemoredoom1 发表于 2018-9-8 00:07
提示: 作者被禁止或删除 内容自动屏蔽
山郭 发表于 2018-9-8 07:20
谢谢了,学习
您需要登录后才可以回帖 登录 | 注册[Register]

本版积分规则 警告:禁止回复与主题无关内容,违者重罚!

快速回复 收藏帖子 返回列表 搜索

RSS订阅|小黑屋|联系我们|吾爱破解 - LCG - LSG ( 京ICP备16042023号 | 京公网安备 11010502030087号 )

GMT+8, 2019-10-19 08:09

Powered by Discuz!

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表