​感谢学生组PC参赛者张震分享的解题过程

1、程序分析

程序是一个main文件，是一个可以在android的native环境下的可执行文件。首先静态分析，找到start函数，发现start函数会调用一个sub_CA4的函数，进入一看，就是程序的核心代码。

核心代码当中有2个判断是决定是否打印“you lose”，如果都没打印”you lose”则会打印”you win”。这两个地方就是2个核心函数sub_F90和sub_10B0函数。可以分别命名为core1函数和core2函数。逐个分析。

2、core1分析

首先程序会调用名为”libZapus.so”的动态链接库中的”zapus_get”函数，其中zapus_get的参数是&v15，也就是说，zapus_get是用来设置v15的值，如图1所示。zapus_get设置了v15的值后，就会执行第一个核心函数sub_F90。

sub_F90函数的流程如下，首先会从main的相对偏移地址0x4230处读取2048字节，暂时命名为dest。开始没有仔细分析时，还以为是奇偶校验的算法；后来详细分析后，发现是类似与gf（2）的矩阵运算。而运算的矩阵是2048字节。一共是16384位，通过下面程序的分析，刚好是128*128的矩阵。而我们用zapus_get输入的16字节，将作为一个128位的向量与矩阵相乘。得到最后的结果就是和目标串（目标串是的4个整型是0x614c5347,0x373162,0x0, 进程的pid；共四个整型）比对。

3、core2分析

core是读取了libZapus.so文件。然后用sub_10b0对读入的libZpus.so进行运算。开始是定义了一个256个整型数组。然后分析图2中的C代码，查阅资料发现算法有点像CRC32，然后查看256个整型的数组和查阅CRC32的资料，发现256个整型数组就是CRC32运算的运算表，并且对so文件进行CRC32运算，最后的值和0x614c5347进行比对。即要求so的CRC32校验必定是0x614c5347。

4、解题思路

4.1 core1的解题思路

该题目是向量V1与矩阵A相乘，得到向量V2。因此我们已知向量V2，因此需要求出矩阵A的逆矩阵A^-1。由于矩阵是gf(2)的矩阵，在求逆矩阵的时候会方便很多。我利用的是高斯消元法来求逆矩阵。

1、首先是，构造一个单位矩阵amat，作为原矩阵A的右矩阵，作为最后结果的逆矩阵A^-1。

2、然后是去掉下三角。首先是从列row（0,1,2,…,127）开始判断，若第row行的第row列不为1，则向下遍历，并与第row列为1的行交换，amat也是执行同样的操作。

3、第row行向下进行异或运算，amat也执行同样的操作。

这样就可以构造成上三角矩阵，然后再反过来，从line(127,126,…,1,0)行开始向上异或，amat也执行同样的操作。

最后的amat可以得到逆向矩阵A^-1，再与向量V2相乘，则可以得到V1。V2是四个32为整型，分别是：

1、0x614c5347

2、0x373162

3、0x0

4、该进程的pid

V2与amta运算得到V1，其值赋予给传入的参数v15，即可过core1。详细内容请看源代码。

4.2 core2的解题思路

Core2是CRC32运算，因此是没办法还原so了。但是可以对so进行crc32碰撞，利用碰撞值使得so文件的crc32值为比对值0x914c5347。我们已知的是我们自己的so文件的crc32值，这里称为c1，和最终的目标crc32值（对比值），称为c2。因此我们需要碰撞得到c1和c2之间的中间值ct。

假设c1的值是ABCD4位，c2是WXYZ，ct是abcd。假定4个函数F(x),G(x),H(x),I(x)分别表示以x为索引查表,取出来的DWORD的从高位到低位的4个字节。有过程如下：

R0:A,B,C,D <m=D^d>

R1:F(m),A^G(m),B^H(m),C^I(m) <n=c^C^I(m)>

R2:F(n),F(m)^G(n),A^G(m)^H(n),B^H(m)^I(n) <o=b^B^H(m)^I(n)>

R3:F(o),F(n)^G(o),F(m)^G(n)^H(o),A^G(m)^H(n)^I(o) <p=a^A^G(m)^H(n)^I(o)>

R4:F(p),F(o)^G(p),F(n)^G(o)^H(p),F(m)^G(n)^H(o)^I(p)

m,n,o,p是crc32中表的引索值（成为中间变量）。而R4就是我们的c2值。可以得到如下的关系：

<1>

W=F(p);

X=F(o)^G(p);

Y=F(n)^G(o)^H(p);

Z=F(m)^G(n)^H(o)^I(p);

<2>

m=d^D;

n=c^C^I(m);

o=b^B^H(m)^I(n);

p=a^A^G(m)^H(n)^I(o);

如果要解出，就必须要得到F(x)函数的反函数RF(x)，而CRC32的表的F(x)的值刚好是一一映射。因此可以得到如下：

~<1>

p=RF(W);

o=RF(X^G(p));

n=RF(Y^G(o)^H(p));

m=RF(Z^G(n)^H(o)^I(p));

~<2>

d=m^D;

c=n^C^I(m);

b=o^B^H(m)^I(n);

a=p^A^G(m)^H(n)^I(o);

而这abcd就是我们要求得的中间值c2。因此我们可以根据公式，利用已知的ABCD(c2)和WXYZ(c2)来求abcd(ct)。

只要将这c2追加在so文件的末尾，就可以使得so文件的crc32的值为目标值了。详细内容请看源代码。