Bxb0's blog

vnctf2021

Posted on In
Symbols count in article: 4k Reading time ≈ 4 mins.

就对其中感觉有意思的2个逆向题做一下记录，也是复现，当时没做出来。

其中第一个是当时算法写不来，太弱了。另外一是app使用hook更改了密钥，但是我对程序重打包后，这个hook失效了，导致一直解密出错又找不到原因。

FilpGame

整个程序就一个main函数。

输入长度要小于214，对输入的每2个先进行一个int(x, 16)操作，然后进行程序的关键操作，也就是奇数位才操作：

image-20210421134509045

在进行的关键操作开始前就要求我们输入的每2个位进行hex.decode()操作后的值是递增序列，从后面可以知道，这里实际就是规定了我们输入坐标是顺序，递增。

image-20210421134750425

后面就是关键处理输入的地方了，程序的关键，就是位操作。

image-20210421190532649

先熟悉一个知识点：

  • x ^ 0 = x
  • x ^ 1 = !x

然后其实上面的就是操作一个16*16的矩阵，只不过用了16个word型数据的每一个bit位进行存储（真是个好想法），对输入坐标和它上下左右进行bit反转，0变1，1变0。

最后程序的比较就是整个16*16的矩阵全为1，这其实是一个点灯游戏/翻转游戏，典型的算法题了，但时间要求上宽松了不少。。

太弱了，写不来，比赛时也卡在了这里，赛后发现大家有的竟然直接是找了网上现成的脚本，搜索的重要性。。

看了wp，采用爆破第一行的所有可能（2^16），接着推出第二行的情况，依次进行下去，如果最后一行都是1则满足条件。

这种想法确实可行，而且实现起来也不难，其实就是把所有可能翻的情况穷举，然后找最小解。

而这种做法如果不用搜索来做的话，有一个问题，如何穷举第一行的所有情况呢，一个好办法：因为【0-2^16-1】每个数的二进制位都不一样，且只有16位，那么每次向右移位【0-15】，如果为1就反转，这样就实现了。

image-20210421200351125

最后整体代码：

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <stdio.h>
#include <string.h> 

int min = 500, cnt, flag;
int dx[] = {0, 0, -1, 1, 0}, dy[] = {-1, 0, 0, 0, 1};
int a[16][16], b[16][16], fi;
char ans[1000], tmp[1000];

char to_hex(int a)
{
	return a >= 10 ? a-10+65:a+48;
}

void filp(int x, int y)
{
	int i;
	cnt++;
	tmp[fi++] = to_hex(y), tmp[fi++] = to_hex(x);
	for(i = 0; i < 5; i++)
	{
		int x1 = x+dx[i];
		int y1 = y+dy[i];
		if(x1 >= 0 && x1 < 16 && y1 >=0 && y1 < 16)
			b[x1][y1] ^= 1;  
	} 
}

int fun()
{
	int i, j, k;
	
	for(i = 0; i < (1 << 16); i++)
	{
		cnt = 0, flag = 0, fi = 0;
		memset(tmp, 0, sizeof(tmp));
		memcpy(b, a, sizeof(a));
		for(j = 0; j < 16; j++)
		{
			if((i >> j)&1)
				filp(0, j);
		}
		for(j = 0; j < 15; j++)
		{
			for(k = 0; k < 16; k++)
			{
				if(b[j][k] == 0)
					filp(j+1, k);	
			}
		}
		
		for(j = 0; j < 16; j++)
		{
			if(b[15][j] == 0)
			{
				flag = 1;
				break;
			}
		}
		if(flag)
			continue;
		if(cnt < min)
		{
			memcpy(ans, tmp, 1000);
			min = cnt;
		}
	}
	
	if(min == 500)
		return -1;
	
	return min;
}

int main(void)
{
	int i, j;
	int enc[] = {48885, 35772, 41193, 29456, 55568, 41901,
			 52406, 19934, 13388, 15318, 26385, 34447, 7290, 33829, 27405, 6988};
	for(i = 0; i < 16; i++)
	{
		for(j = 0; j < 16; j++)
		{
			a[i][j] = (enc[i] >> (15-j)) & 1;
		}
	}
	
	if(fun() > 0)
		puts(ans);
	else
		puts("not found!");
		
	return 0;
	
} 
//2050608090A0B0C0D02131417191A1B1527282B2D2E2F213234363B3D36494C4D4E415456575C5D5E50626566686C6F6071787B7C72838587898C8D81949596999B9C9F95A8AAAEA0B1B3B4B7B1C2C3C4C6C9CBCEC0D4D7D9DBDCDED0E1E3E4E5E6E8E9ECEEEFE3F7F8FBF

得到结果，最后md5一下。

又去搜集资料，可以看这个题作为参考filp game。然后想了很久递归的写法，思想其实还是一样，从第一行开始，一行一行的确定都是1，若达不到就回溯，直到最后一行，然后检查是否全为1。

上面说的只是加了每一行操作完后的判断，但仍然是全搜，16*16的规模还是太大了，不可行。

开始改进，使用爆破一样的思想，从第二行开始，当前一行的同列位置为0时才继续下去，否则就回溯。

image-20210424094440844

跑了一下改进后的，跑出一组解还是很快的，但要穷举后找到目标解，仍然要很久，，主要是这样搜索多了回溯的过程，对每一行要走的位置（当前一行的同列位置为0）进行了一个所有情况搜索。

这样，也没有继续在这个搜索算法上继续去改进了，继续改进不就和爆破一样了。。所以说这类问题，规模大以后，采用穷举第一行的所有情况，然后根据第一行情况依次爆破出后面的行是很好的办法了。

贴一下搜索算法（跑过规模小一些的，是可以的）：

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <stdio.h>
#include <string.h>
#include <stdlib.h> 

int c[2][5]= {0,0,-1,1,0,-1,0,0,0,1}, min1 = 999, t;
char Map[16][16];
char ans[1000];

char to_hex(int a)
{
	return a >= 10 ? a+55:a+48;   
}

void turn(int x, int y)
{
    for(int i = 0; i < 5; i++)
    {
        int dx = x + c[0][i];
        int dy = y + c[1][i];
        if(dx < 0 || dy < 0 || dx >= 16 || dy >= 16)
			continue;
        Map[dx][dy] ^= 1;
    }
}
 
int check()
{
    int i, j;
    for(i = 0; i < 16; i++)
        if(Map[15][i] == 0)
        	return 0;
    return 1;
}
 
void dfs(int x, int y, int s)
{
    if(s > 107)	//剪枝 
    	return ;
    
    if(y == 16)	//剪枝 
    {
    	if(x >= 1)
    		for(int k = 0; k < 16; k++)
    			if(Map[x-1][k] != 1)
    				return ;
    	x += 1;
		y = 0; 
	}
	 
    if(x == 16)
	{
		if(check())
		{
			puts(ans);
			exit(0);
		}
	 	return ;
	}
	if(x >= 1)	//剪枝 
		if(Map[x-1][y] == 1)
			goto next;
	
	turn(x, y);//翻转 

	ans[2*s] = to_hex(y), ans[2*s+1] = to_hex(x), ans[2*s+2] = 0;
	puts(ans);
	//printf("%d\n", s);
	
	dfs(x, y+1, s+1);

	turn(x, y);//回溯 
next:
	ans[2*s] = 0, ans[2*s+1] = 0, ans[2*s+2] = 0;
	
    dfs(x, y+1, s);
}
 
int main()
{
    int i;
    
    for(i = 0; i < 16; i++)
    	for(int j = 0; j < 16; j++)
        	scanf("%d", &Map[i][j]);
    dfs(0, 0, 0);
    
    if(min1 <= 16)
    {
        //printf("%d\n", min1);
        //puts(ans);
    }
    else
		printf("Impossible\n");
		
	return 0;
}

基本功还是不能丢。

Crackme1

-------------本文结束感谢您的阅读-------------