CTF-i春秋欢乐赛-登山者

题目

提示:求二维矩阵左上往下走,可以向下,也可以向右下的最大值。(动态规划dp的数学三角形最大和)

x86平台的exe,未加壳。

题目地址:i春秋

工具

IDA和OD

分析

先用IDA反汇编分析。主要函数有initcheck两个函数,init初始化了一个1014*1014大小的三角矩阵,这个大小可以从传给memset的参数能看出来,也可以看for循环的条件。

然后用字符串序列A1ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/,打乱A1的顺序生成A2,然后得到一个A1和A2的对应关系表R,三者关系是A2.indexOf(A1[i]) = R[i]或者A2[R[i]] = A1[i]

这段可能在IDA里比较乱,OD里分析一下之后,只需要得到最后的A1和A2以及R这三个序列就行,不用关注具体算法。

check用来验证用户输入的字符,根据字符判断向下还是右下走,然后走到最后的和只要大于某个值就能成功,这个值应该是卡的最大值。

可以从check函数中看到getstep(a1[i / 6], i),分析后可知一个字符控制6步,一共要走1024步,所以最后答案应该有1024/6=169个字符。
观察get_step中判断方向的逻辑,a1依次传入用户输入的字符(每个传6遍),v2R[A1.indexOf(a1)],暂用i表示A1.indexOf(a1)v5为32,return可以变成R[i] & (32 >> a2 % 6),其中a2 % 6的值分析可知在[0,1,2,3,4,5]循环,暂假设ja2 % 6C表示32 >> j,即[32, 16, 8, 4, 2, 1]。该return的结果根据a1得到R[i],然后判断R[i]里是不是有C[j]对应的二进制位。

还原

在OD中对init单步调试后,理清了初始化思路,首先通过一个伪随机数函数生成了矩阵,创建原始序列A1的副本A2,根据伪随机数函数进行打乱顺序,最后创建一个map表示A1和A2的对应关系。
生成大小为1014*1014矩阵的逻辑用C代码表示如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*...省略...*/

static unsigned _int64 matrix[1014*1014] = {0};

/*...省略...*/

void init()
{
for(int m = 0; m < 1014; m++) {
for(int n = 0; n < m+1; n++) {
matrix[m*1014+n] = my_rand();
}
}

/*...省略...*/
}

/*...省略...*/

int main()
{
init();

/*...省略...*/

return 0;
}

其中伪随机数生成的函数逻辑如下:

1
2
3
4
5
6
7
static unsigned int myseed = 0x1234567u;

int my_rand()
{
myseed = (myseed*0x3b9aca07u+0x3b9aca09u)%0x989677u;
return myseed;
}

myseed是随机数种子,因为这个数全局固定不变,所以每次运行程序生成的随机数序列都是固定的。
将生成的矩阵写入到文件,方便观察:

1
2
3
4
5
6
7
8
9
10
11
void write2file()
{
FILE *fw = fopen("matrix.txt", "w");
for(int k = 0; k < 1014; k++) {
for(int t = 0; t < 1014; t++) {
fprintf(fw, "%0.8X ", matrix[k*1014+t]);
}
fprintf(fw, "\n");
}
fclose(fw);
}

打开matrix.txt能够很明显观察出这是一个三角矩阵。

然后打乱顺序生成A2的算法通过C代码表示如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 /*...省略...*/

static const size_t len = 64;
static const char *a1 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
static char *a2;

/*...省略...*/

void init()
{
/*...省略...*/
a2 = (char *)malloc(64);
memcpy(a2, a1, len);

for(int i = 0; i<len; i++) {
int j = i+my_rand()%(len-i);
char aux = a2[j];
a2[j] = a2[i];
a2[i] = aux;
}
}

/*...省略...*/

int main()
{
init();

/*...省略...*/

return 0;
}

运行后生成A2为EIFd6gwN42LR1vGrBYCnzHTStDqm+kxZpQVioj9O78es3UlAKhXcfybPM5W/0aJu

init函数在最后利用map做出A1A2序列的对应关系,用C代码表示如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*...省略...*/
static std::map<const char, int> r;

void init()
{
/*...省略...*/

for(int p = 0; p < len; p++) {
char *ptr = (char *)memchr(a2, a1[p], len);
r[a1[p]] = ptr-a2;
//printf("0x%x ", r[a1[p]]);
}
//printf("\n");
}

到此,init函数结束了,还有一个check函数,中间用一个getstep函数得到走的方向:0:向下、1:向右下,写出大概的check函数的C代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*...省略...*/
static _int64 max_v = 0x1BEBAAB51;

int getstep(const char a, int b)
{
int num = r[a];
//printf("(%c,%d,%x,%d) ",a,b,num,(32>>(b%6)&num) != 0);
return (32>>(b%6)&num) != 0;
}

int check(const char *input)
{
size_t len = strlen(input);

if(len != 1014/6) return 0;

int d = 0;

for(int i = 0; i < 1014; i++)
{
d += getstep(input[i/6], i);
max_v -= matrix[i*1014+d];
}

if(max_v <= 0) return 1;
return 0;
}
/*...省略...*/

其中,max_v就是最大值。这个值需要从OD中拿到,需要注意的是int64存储的值需要分两个32位的空间存储,需要注意拼接。

拼起来就是max_v的值,也可以直接在IDA里拿。

到此,这个题的C源码已经分析出来了,具体代码放在了github上,vc++6.0运行。

解题

首先通过上面的代码得到matrix.txt,里面存储了那个矩阵,然后写代码找最大值,代码中用到的算法属于动态规划类,动态规划最关键的是找到一个递推或者递归关系。下面是描述递推关系的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void count_dp()
{
dp[0] = matrix[0];

for(int k = 1; k < 1014; k++) {
dp[k*1014] = dp[(k-1)*1014]+matrix[k*1014];
}

for(int i = 1; i < 1014; i++) {
for(int j = 1; j < i+1; j++) {
dp[i*1014+j] = max(dp[(i-1)*1014+j-1], dp[(i-1)*1014+j])+matrix[i*1014+j];
if(dp[(i-1)*1014+j-1] > dp[(i-1)*1014+j]) choose[i*1014+j] = 1; // 从左上来
else choose[i*1014+j] = 0; // 从上来
}
}
}

通过生成的dp数组最后得到flag。

具体代码放在了github上。





root@kali ~# cat 重要声明
本博客所有原创文章,作者皆保留权利。转载必须包含本声明,保持文本完整,并以超链接形式注明出处【Techliu】。查看和编写文章评论都需翻墙,为了更方便地获取文章信息,可订阅RSS,如果您还没有一款喜爱的阅读器,不妨试试Inoreader.
root@kali ~# Thankyou!