算法分析

虽说base64严格意义上来说并不能算是加密算法，但的确应用方面来说还算是比较广，在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算法就是根据一个base64表，将原始字符的值一一替换。替换规则如下：

1. 首先将每三个字节划分为一组，得到24个二进制位
2. 然后将这24个二进制位划分为4组，得到4组6个二进制位的大小
3. 在每组前面添加两个00，扩展成32个二进制位，也就是四个字节。
4. 根据base64的表格对照替换得到base64编码
   表格如下：
   

定义为字符串数组如下：

"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"

如果需要编码的字节不能被三整除，则会多出1个或2个字节，处理方式是加上"="号，也就是平时我们看到的base64编码最后的"="或者"=="

代码实现

根据前面的算法分析，已经知道了base64具体的算法实现，接下来使用c语言实现它。
首先需要定义一个base64的字符串数组，用于替换。

const char base_table[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

接下来定义一个base64加密函数，命名为myEncode,参数有3个，1. 需要编码的字节 2.用于存放编码完成后的字符串 3. 需要编码字节的长度，函数原型如下：

static int myEncode( const uint8_t *bindata, char *base64, int binlength)

还是回到这张图

首先我们需要将第一个字母G的二进制位从8位截取到6位，我能想到的最直接的方法就是直接移位，将G>>2，前面自动补0则会得到00010001，也就是索引17，对应base64的表格得到字母R,第一个字母就替换完成了。

        current = (bindata[i] >> 2) ;
        current &= (uint8_t)0x3F;
        base64[j++] = base_table[(int)current];

很明显编码的第二个值是由G的最后两个二进制位和u的前面四个二进制位拼接起来的，也就是说接下来应该将这两部分组合起来。
如何得到第一个字母的最后两个字节呢，也是采用移位的方式：
首先将第一个字母左移4位得到01110000，我们这里需要取第一位的最后两位，也就是这里的第三四位。所以将01110000与0x30（十进制48，二进制00110000）得到：

        current = ( (uint8_t)(bindata[i] << 4 ) ) & ( (uint8_t)0x30 ) ;

接下来将第二个字节的前四个二进制位拼接过来即可。

同样的，先将第二个字节右移四位以此得到需要拼接的部分。然后以类似的思路处理第三个字节。处理完毕将会得到新的四个字符。

完整流程大致如下：

完整代码如下：

static int myEncode( const uint8_t *bindata, char *base64, int binlength)
{
    int i, j;
    uint8_t current;
    /*每次处理三个字符*/
    for ( i = 0, j = 0 ; i < binlength ; i += 3 ) {
        /*前6个bit 首先右移两位*/
        current = (bindata[i] >> 2) ;
        current &= (uint8_t)0x3F;
        base64[j++] = base_table[(int)current];
        /*第一个字节的最后两个二进制位*/
        current = ( (uint8_t)(bindata[i] << 4 ) ) & ( (uint8_t)0x30 ) ;
        if ( i + 1 >= binlength ) {
            base64[j++] = base_table[(int)current];
            base64[j++] = '=';
            base64[j++] = '=';
            break;
        }
        /*9~12bit, 并连接7~8bit*/
        current |= ( (uint8_t)(bindata[i+1] >> 4) ) & ( (uint8_t) 0x0F );
        base64[j++] = base_table[(int)current];
        /*13~16bit*/
        current = ( (uint8_t)(bindata[i+1] << 2) ) & ( (uint8_t)0x3C ) ;
        /*就此结尾*/
        if ( i + 2 >= binlength ) {
            base64[j++] = base_table[(int)current];
            base64[j++] = '=';
            break;
        }
        /*17~18bit, 并连接13~16bit*/
        current |= ( (uint8_t)(bindata[i+2] >> 6) ) & ( (uint8_t) 0x03 );
        base64[j++] = base_table[(int)current];
        /*19~24bit*/
        current = ( (uint8_t)bindata[i+2] ) & ( (uint8_t)0x3F ) ;
        base64[j++] = base_table[(int)current];
    }
    base64[j] = '\0';
    return j;
}

同理，解密函数需要四个字节一次性处理，逻辑一样。
我使用了原生的c语言实现，代码如下：

static int base64_decode( const uint8_t *bindata, char *base64, int binlength)
{

    int i, j;
    uint8_t current;
    //4个字母为一组一起处理
    int mybindata [4];
    for ( i = 0, j = 0 ; i < binlength ; i += 4 ){
        for(int h=0;h<64;h++)
        {
            if(bindata[i]==base_table[h])
            {
                mybindata[0] = h;
                break;
            }
        }
        for(int h=0;h<64;h++)
        {
            if(bindata[i+1]==base_table[h])
            {
                mybindata[1] = h;
                break;
            }
        }
        for(int h=0;h<64;h++)
        {
            if(bindata[i+2]==base_table[h])
            {
                mybindata[2] = h;
                break;
            }
        }
        for(int h=0;h<64;h++)
        {
            if(bindata[i+3]==base_table[h])
            {
                mybindata[3] = h;
                break;
            }
        }

        current = (mybindata[0] << 2) ;
        current |= ( (uint8_t)(mybindata[1] >> 4 ) ) & ( (uint8_t)0x03 ) ;
        base64[j++] = (char)current;

        current = (mybindata[1]<<4);
        current |= ( (uint8_t)(mybindata[2] >> 2) ) & ( (uint8_t)0x0F ) ;
        base64[j++] = (char)current;

        current = (mybindata[2]<<6);
        current |= ( (uint8_t)(mybindata[3]) ) ;
        base64[j++] = (char)current;
    }
    if(bindata[binlength-2]=='=')
    {
        base64[j-1]=' ';
        base64[j-2] = ' ';
        base64[j-2] = '\0';
        return j;

    }
    if(bindata[binlength-1]=='=')
    {
        base64[j-1]=' ';
        base64[j-1] = '\0';
        return j;

    }
    base64[j] = '\0';
    return j;
}

在main函数中调用：

int main (int argc, char **argv)
{
    char * str = "Guy";
    printf("input: %s \n", str);
    char *base64_str = calloc(1, 1024);
    myEncode(str, base64_str, strlen(str));
    printf("encode base64: %s \n", base64_str);

    char *debase64_str= calloc(1,1024);
    base64_decode(base64_str, debase64_str, strlen(base64_str));
    printf("decode base64: %s \n", debase64_str);

    free(debase64_str);
    free(base64_str);
    return 0;
}

结果如下：

将结果拿到base64网页解密：

通过分析过程，我们可以得知base64加解密中我们可控制也最方便控制的是base64的加密表。我们修改base64的加密表即可以实现base64的变异加密，实现起来非常很简单。
将之前的base_table修改为如下：
before：

const char base_table[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

after：

const char base_table[] = const char base_table[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/";

然后运行程序即可得到：

然后到网络上使用base64解密工具进行解密将解密失败。

明天再把逆向分析的模块贴上来~

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课