游戏安全实验室 首页 活动 查看内容

【答案推荐】复赛第一题社会组android

发布于:2017-8-8 16:10   |    79472次阅读 作者: 管理员    |   原作者: 何垚   |   来自: 原创

​感谢社会组何垚提供的答题过程



前言

从第一题题目来看,感觉这次的题目都出得很灵活,主要考的是密码学这一块的东西。这道题目也不例外,由于不是科班出身,根本没有接触过密码学,那只能现学现卖,其中踩了不少坑,但是不要怕,我们可以慢慢爬出来再继续踩。初一看这道题后面的“双重保镖”很是霸气,很容易被吓跑,但是仔细认真做了之后会发现,Oh,hash碰撞也不是那么难的。好了,废话扯多了估计要被拉黑,我选择的依旧是安卓的题目,下面进入正题,我将此题分成两大部分,主要阐述这两大部分。


0x1 拉开帷幕


官方具体表演如下:


1. 判断指定路径有没有so,没有或者是打开失败就跪。

2. zapus_get符号,符号表里没有就跪。

3. 有了的话,把该函数初始化的指针带进到图中的sub_F90函数,然后开始计算。

4. 小插曲,这里说一下这个题目第一次发的有一个bug,解密后的代码与固定两个字符串的指针进行了比较,

导致每次对比的值是变的,我做到这里的时候怀疑了一下人生。what?比较的值还是变的?还不能改程序内存?在心中无限崩溃循环中还好官网出来及时修补了bug

计算过程如下:



程序将输入的16bytes(也就是128bit),记为inputbuffer的大小是2048bytes,分成了128128bit,记为x[0]x[127],根据之前的运算,input将和x数组进行128次运算,每一次运算生成1bit,一共分成128bit,即16节,这16字节就是最后算出来的结果,也是需要比较的结果。


其实是一个1281次的异或方程组,采用高数中的高斯消元法来求解,这个我没学过密码学也会,因为这就是高数中的内容啊,熟悉吗?矩阵化简,想起来了吗?对于高数课逃课的同学,关于高斯消元法,给个链接:


https://en.wikipedia.org/wiki/Gaussian_elimination


这里已经非常详细

然后根据本题目的特征google一下就能搜到不少解该类方程组的模板,选取一个,代码如下:

再根据IDA中看到的信息,确认正确答案的前面7字节是"GSLab17",最后四字节是pid,编写代码如下:


再调试看看结果,自己挖了什么坑自己填填坑,即可过第

一关,进入下一关。



0x2 孪生兄弟


接下来来到孪生兄弟把守的最后一关,只要越过这道防

线,就可以飞向光明顶。



之所以说它是孪生兄弟,是因为它对程序进入了hash值的校验,并且是两种校验,两个校验值都必须值为0x614C5347,就是“GSLa”


什么是hash函数?


Hash函数H将可变长度的数据M作为输入,产生固定长度的Hashh

Hash函数,哈希函数,散列函数,杂凑函数它们说的都是同一个含义,后续我们都称之为Hash函数。


定义


Hash函数H将可变长度的数据M作为输入,产生固定长度的Hashh

Hash函数,哈希函数,散列函数,杂凑函数它们说的都是同一个含义,后续我们都称之为Hash函数。


h=H(M)


单向性


给定输入M,通过函数H可以很容易计算出输出h;但如果给定h,则找到M在计算上不可行。


数据完整性


输入数据M中任何1bit发生变化,都将导致输出M发生很大的变化。

Hash冲突(突破本题的关键)


Hash函数中,M称之为h原像,,因为H函数是一个多对一的映射,,对于任意给定的Hash

h,,可能会有多个原像,,如果满足如下条件, 则称之为发生了哈希碰撞,也就是哈希冲突

x!=yandH(x)==H(y)


一个优良的Hash函数必须满足如下几个性质:

任意y,找x,使得H(x) = y,非常困难

给定x1, x2, 使得H(x1) == H(x2), 非常困难

找任意的x1, x2, 使得H(x1) == H(x2), 非常困难


这里感觉本题是第一条或者第二条,如果是第三条的话

(可惜本题并不是),可以参考生日定理来解题,这里放

个链接:

https://en.wikipedia.org/wiki/Birthday_problem


介绍完基本概念,回归正传,本题目的两个校验是crc32校验和fnvhash函数校验,这里再给两个链接:


crc32http://blog.csdn.net/zhaodm/article/details/3711034

fnvhashhttp://blog.csdn.net/taochenchang/article/details/7319739

通过分析代码可以得到:

1.crc32 校验


标准算法没改动过:


unsigned long calc_crc(unsigned char *p, unsigned int len)

{

register unsigned long crc;

unsigned int count=0;

crc = 0xFFFFFFFF;

while (count < len){

crc = (crc>>8) ^ crc_table[ (crc^p[count++]) & 0xFF ];

}

return( crc^0xFFFFFFFF );

}

单独改crc32是没问题的,附件里有代码。


2.fnv_hash


标准算法没改动过


unsigned long calc_fnvhash(unsigned char *p, unsigned int len)

{

register unsigned long hash;

unsigned int count=0;

hash = 0x811C9DC5;

while (count < len){

hash = 0x1000193 * (p[count++] ^ hash);

}

return hash;

}


因为crc32的值是可以求出来的,再给个链接,其实这篇文章最早在看雪:

http://www.cnblogs.com/thinksea/articles/2024199.html

所以思路就变成了暴力碰撞fnvhash的值即可。分析完了,写代码进行碰撞,关键代码:


//8字节碰撞

unsigned char byte[4] ;

unsigned char byte2[4] ;

srand( (unsigned) time(NULL) * getpid());

long i =0;

while(1)

{

byte[0]=rand()%256 + byte[1] ;

byte[1]=rand()%256 + byte[2];

byte[2]=rand()%256 + byte[3]; ;

byte[3]=rand()%256 + byte2[0]; ;

byte2[0]=rand()%256 + byte2[1];

byte2[1]=rand()%256 + byte2[2];

byte2[2]=rand()%256 + byte2[3] ;

byte2[3]=rand()%256 + byte[0] ;

*(unsigned int*)(filemap+offset -4) = *(unsigned int*)byte;

*(unsigned int*)(filemap+offset -8) = *(unsigned int*)byte2;


tweakcrc(filemap, filestat.st_size, crc, offset); //修改crc32 值为

固定值

fnvhash=calc_fnvhash_op(filemap+filestat.st_size -12, 12);

if (fnvhash >= 0x614C5340 && fnvhash <= 0x614C5349)

{

printf("$$$$$$$$$$$$$$ near success $$$$$$$$$$$$$\n");

printf("%x %x %x %x\n", byte[0],byte[1],byte[2],byte[3]);

printf("%x %x %x %x\n", byte2[0],byte2[1],byte2[2],byte2[3]);

printf("calc_fnvhash_op: 0x%X\n", fnvhash);

printf("$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$\n");

if (fnvhash == 0x614C5347)

{

printf("********************************\n");

printf("**************success***********\n");

printf("********************************\n");

printf("%x %x %x %x\n", byte[0],byte[1],byte[2],byte[3]);

printf("%x %x %x %x\n", byte2[0],byte2[1],byte2[2],byte2[3]);

printf("calc_fnvhash_op: 0x%X\n", fnvhash);

break;

}

}

i++;

if (i % 100000000 == 0)

{

printf("已经碰撞%ld 继续努⼒\n", i);

}

}


优化后的crc32fnvhash函数的计算,代码对比如下,这里的值只针对我自己的so进行的优化:


//crc

unsigned long calc_crc(char *p, unsigned int len)

{

register unsigned long crc;

unsigned int count=0;

crc = 0xFFFFFFFF;

while (count < len){

crc = (crc>>8) ^ crc_table[ (crc^p[count++]) & 0xFF ];

}

return( crc^0xFFFFFFFF );

}

unsigned long calc_crc_op(char *p, unsigned int len)

{

register unsigned long crc;

unsigned int count=0;

crc = 0x81820a5b;

while (count < len){

crc = (crc>>8) ^ crc_table[ (crc^p[count++]) & 0xFF ];

}

return( crc^0xFFFFFFFF );

}

//fnvhash

unsigned long calc_fnvhash(unsigned char *p, unsigned int len)

{

register unsigned long hash;

unsigned int count=0;

hash = 0x811C9DC5;

while (count < len){

hash = 0x1000193 * (p[count++] ^ hash);

}

return hash;

}

unsigned long calc_fnvhash_op(unsigned char *p, unsigned int len)

{

register unsigned long hash;

unsigned int count=0;

hash = 0x799362BC;

while (count < len){

hash = 0x1000193 * (p[count++] ^ hash);

}

return hash;

}


这里再说明一下,一开始没有优化算法,导致计算缓慢

(被卡了一波,标记,其实也是没做出来的主要原因,自己挖了个坑,一直在挂机,没注意到错误,以为hash碰撞很难,但是过了很久没跑出结果我就跟了一下,解决掉坑,到达胜利光明顶),优化算法后效率提升了大概2100倍,大概1秒钟碰撞1E次,瞬间得出解。跑了大概半分钟,得出4个解(感觉一天给1-2W个解也是没有压力的),如下:

1.

9a 14 7 99

56 8c 8 1f

calc_fnvhash_op: 0x614C5347

2.

84 1e 16 23

92 18 3c 34

calc_fnvhash_op: 0x614C5347

3.

5a f5 69 0

a0 d1 39 29

calc_fnvhash_op: 0x614C5347

4.

28 f0 98 98

a1 82 b0 e7

calc_fnvhash_op: 0x614C5347


经过此役,发现hash碰撞很有趣,做题使人快速学习新东西,复习老东西。


分享到:
踩1 赞0

收藏

上一篇:【答案推荐】复赛第一题学生组PC

下一篇:【答案推荐】复赛第一题社会组PC

最新评论
B Color Image Link Quote Code Smilies

发表评论

top 问题反馈

返回顶部