内容简介:算法分析虽说根据维基百科的定义: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 严格意义上来说并不能算是加密算法,但的确应用方面来说还算是比较广,在 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 表,将原始字符的值一一替换。替换规则如下:
-
首先将每三个字节划分为一组,得到24个二进制位。
-
然后将这24个二进制位划分为4组,得到4组6个二进制位的大小。
-
在每组前面添加两个00,扩展成32个二进制位,也就是四个字节。
-
根据 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 解密 工具 进行解密将解密失败。
之后再把逆向分析的模块贴上来~
- End -
看雪ID: 顾何
https://bbs.pediy.com/user-757351.htm
本文由看雪论坛 顾何 原创
转载请注明来自看雪社区
热门图书推荐
戳 立即购买!
公众号ID:ikanxue
官方微博:看雪安全
商务合作:wsc@kanxue.com
↙ 点击下方“阅读原文”,查看更多干货
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- PageRank算法初探
- 关联分析Apriori算法和FP-growth算法初探
- 无监督学习——聚类(clustering)算法应用初探
- 根因分析初探:一种报警聚类算法在业务系统的落地实施
- 前后端完全分离初探
- thrift 初探
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。