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

前言

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

0x1 拉开帷幕

官方具体表演如下：

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

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

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

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

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

计算过程如下:

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

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

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

这里已经非常详细

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

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

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

一关，进入下一关。

0x2 孪生兄弟

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

线，就可以飞向光明顶。

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

什么是hash函数？

Hash函数H将可变长度的数据M作为输入，产生固定长度的Hash值h。

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

定义

Hash函数H将可变长度的数据M作为输入，产生固定长度的Hash值h。

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

h=H(M)

单向性

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

数据完整性

输入数据M中任何1个bit发生变化，都将导致输出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函数校验，这里再给两个链接：

crc32：http://blog.csdn.net/zhaodm/article/details/3711034

fnvhash：http://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);

}

}

优化后的crc32和fnvhash函数的计算，代码对比如下，这里的值只针对我自己的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碰撞很有趣，做题使人快速学习新东西，复习老东西。