首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 峰会 看雪商城 证书查询
  1. 社区
  2. CTF对抗
    3. 发新帖
2
[原创]CTF2018第七题分析(qwertyaa)
发表于: 2018-6-28 19:58 3262

[原创]CTF2018第七题分析(qwertyaa)

qwertyaa 活跃值
10
2018-6-28 19:58
3262

0x0,0x1,0x2

0x3,0x4,0x0

0x5,0x6,0x0

0x5,0x7,0x1

0x4,0x6,0x1

0x8,0x2,0x3

0x9,0x2,0x4

0x7,0xa,0x3

0x8,0xc,0x5

0xb,0xd,0x6

0xc,0xd,0x7

0xb,0xe,0x9

0xe,0x8,0xa

0xf,0x9,0xa

0xf,0xb,0xc

0xf,0xd,0xe

f_y,z(x)=box2[x][y][z]

f_x,z(y)=box2[x][y][z]

f_x,y(z)=box2[x][y][z]

y[i]=box2[x[p[i][0]]][x[p[i][1]]][x[p[i][2]]]

y[i]=box2[x[p[i][0]]][x[p[i][1]]][x[p[i][2]]]，i=0,1,2...15 

这样我们先预处理出p和p中的依赖关系表和“知2求1”的过程：

逆向部分

这道题非常友好，还给了提示，不过这里“每个人都会在另外2个人的帮助下开启一个房间”，似乎应该是“每个人都会在3个人的帮助下开启一个房间”。
程序不长，我们先按着提示，把这个程序用IDA分析，并完整的逆出来，最后可以随便输出一个串和IDA动态调试（在没有反调试、花指令的前提下，用IDA的源码级调试非常方便）的结果比对来验证逆的对不对，如下：
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
void doPause(){
#ifdef linux
    printf("Press enter to exit.");
    fflush(stdout);
    system("read unusedVar");
#else
    system("pause");
#endif
}
typedef unsigned char uchar;
typedef unsigned int uint;
uchar key[16]={0x14,0x22,0x1E,0x10,0x38,0x30,0x18,0x10,0x4,0x1A,0x24,0x8,0x2,0x26,0x38,0x2A};
char trans[]="abcdefghijklmnopqrstuvwxyz+-ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
char input[20];
uchar box1[16][16],box2[64][64][64];
void judge(){
    uchar box[22][16];
    for(int i=0;i<16;i++){
        int j=0;
        while(j<64&&trans[j]!=input[i])j++;
        if(j>=64) {
            puts("input error");
            doPause();
            exit(-1);
        }
        box[0][i]=j;
    }
    puts("");
    for(int i=0;i<20;i++){
        for(int j=0;j<16;j++){
            int a[3]={0},p=0;
            for(int k=0;k<16;k++){
                int l=(k+j)%16;
                if(box1[j][l])
                    a[p++]=box[i][l];
            }
            box[i+1][j]=box2[a[0]][a[1]][a[2]];
        }
    }
    for(int i=0;i<16;i++)if(key[i]!=box[19][i]){
        puts("serial error");
        return;
    }
    for(int i=0;i<16;i++)printf("%c",trans[box[9][i]>>1]);
    puts("");
}
void readFile(const char*fn,void*buf){
    FILE*f=fopen(fn,"rb");
    fseek(f,0,SEEK_END);
    uint size=ftell(f);
    fseek(f,0,SEEK_SET);
    fread(buf,size,1,f);
    fclose(f);
}
int main(){
    readFile("dump.hex",box1);
    readFile("dump2.hex",box2);
 
    puts("Only 'a'-'z','A'-'Z','0'-'9' accepted.");
    puts("Only 16 chars accepted.");
    printf("Serial:");
    scanf("%17s",input);
    if(strlen(input)>16)input[0]=0;//ployfill for scanf_s
    judge();
 
    doPause();
    return 0;
}
其中这里的dump.hex原本是judge函数里的一个局部变量v24，可用IDA直接dump下来，dump2.hex原本是全局变量byte_139FEF0，同样可直接dump下来。
dump可用这样一段IDC代码来实现（来源于网络）：
1
2
3
4
5
6
auto fp, begin, end, i;
fp = fopen("dump2.hex", "wb");
begin = 0x139FEF0;
end = begin+64*64*64;
for ( i = begin; i < end; i ++ ) fputc(Byte(i), fp);
fclose(fp);

分析部分

观察可知，box1是每行只有三个元素的01矩阵，每行为1的位置恰有3个，每行为1的元素分布如下（由于题目中搜索这个矩阵的时候每行都是从(0+行号)%16到(15+行号)%16，下面也是按这个顺序给出，同时我们将下面这个表记为p[16][3]）：

0x0,0x1,0x2

0x3,0x4,0x0

0x5,0x6,0x0

0x5,0x7,0x1

0x4,0x6,0x1

0x8,0x2,0x3

0x9,0x2,0x4

0x7,0xa,0x3

0x8,0xc,0x5

0xb,0xd,0x6

0xc,0xd,0x7

0xb,0xe,0x9

0xe,0x8,0xa

0xf,0x9,0xa

0xf,0xb,0xc

0xf,0xd,0xe

接着我们观察box2，发现恰好等于x的字节恰有4096个，于是猜测并成功验证（其实我只验证了一部分，不过够了）：

f_y,z(x)=box2[x][y][z]

f_x,z(y)=box2[x][y][z]

f_x,y(z)=box2[x][y][z]

都是双射函数，也就是说对于方程box2[a][b][c]=d，我们知道a,b,c中的2个可以直接求余下的1个。
而题目中每层的变换如下（由x[16]到y[16]）：

y[i]=box2[x[p[i][0]]][x[p[i][1]]][x[p[i][2]]]

所以我们倒着来的时候每层相当于有如下16元方程组（求x[16],其余为已知变量）：

y[i]=box2[x[p[i][0]]][x[p[i][1]]][x[p[i][2]]]，i=0,1,2...15 

观察p可知，如果我们知道x[0]、x[1]、x[3]，剩下的每个x我们都可以通过box2“知2求1”的特性求出（这里对于每个方程都有三个依赖，依赖减掉两个之后就可以求出这个方程的余下一个了，这过程有点类似于拓扑排序）。

这样我们先预处理出p和p中的依赖关系表和“知2求1”的过程：

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
//p和p中的依赖关系
int p[16][3];
int rp[16][4]={0};
for(int j=0;j<16;j++){
    int q=0;
    for(int k=0;k<16;k++){
        int l=(k+j)%16;
        if(box1[j][l])
            p[j][q++]=l,rp[l][rp[l][3]++]=j;
    }
}
//“知2求1”的过程
uchar rbox1[64][64][64],rbox2[64][64][64],rbox3[64][64][64];
for(int i=0;i<64;i++){
    for(int j=0;j<64;j++){
        for(int k=0;k<64;k++)rbox1[box2[i][j][k]][j][k]=i;
    }
}
for(int i=0;i<64;i++){
    for(int j=0;j<64;j++){
        for(int k=0;k<64;k++)rbox2[i][box2[i][j][k]][k]=j;
    }
}
for(int i=0;i<64;i++){
    for(int j=0;j<64;j++){
        for(int k=0;k<64;k++)rbox3[i][j][box2[i][j][k]]=k;
    }
}
然后写出先暴力枚举x[0]、x[1]、x[3]然后求余下的x[i]逆并用剩下的方程校对枚举的x[i]是否正确的过程：
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
uchar rbox1[64][64][64],rbox2[64][64][64],rbox3[64][64][64];
int p[16][3];
int rp[16][4]={0};
bool test(uchar x,uchar y,uchar z,uchar key[16],uchar res[16]){
    const int A=0,B=1,C=3;
    res[A]=x;
    res[B]=y;
    res[C]=z;
    uchar d[16];
    for(int i=0;i<16;i++)d[i]=3;
    bool vt[16]={0};
    vt[A]=vt[B]=vt[C]=1;
    for(int z=0;z<3;z++)d[rp[A][z]]--;
    int q[20]={A,B,C};
    int f=0,l=2;
    while(f<l){
        f++;
        for(int z=0;z<3;z++){
            int v=rp[q[f]][z];
            d[v]--;
            if(d[v]<=1){
                l++;
                int a0=p[v][0];
                int a1=p[v][1];
                int a2=p[v][2];
                int k=key[v];
                if(!vt[a0]){
                    res[a0]=rbox1[k][res[a1]][res[a2]];
                    vt[a0]=1;
                    q[l]=a0;
                }else if(!vt[a1]){
                    res[a1]=rbox2[res[a0]][k][res[a2]];
                    vt[a1]=1;
                    q[l]=a1;
                }else if(!vt[a2]){
                    res[a2]=rbox3[res[a0]][res[a1]][k];
                    vt[a2]=1;
                    q[l]=a2;
                }else{
                    if(k!=box2[res[a0]][res[a1]][res[a2]])return false;
                    l--;
                }
            }
        }
    }
    return l==15;
}
void rev(uchar key[16],uchar res[16]){
    int cnt=0;
    for(int i=0;i<64;i++){
        for(int j=0;j<64;j++){
            for(int k=0;k<64;k++){
                if(test(i,j,k,key,res))return;
            }
        }
    }
}
这样我们就可以得出最终的flag为 rPFf9bJl3tXj93ZJ。
而最后输出的内容实际上由第10层开启的房间的编号得出（这恰好和pdb目录信息中的 MidPointVerify 吻合），内容是 yourserialisgood。我猜作者大概就是先写好了这串内容后逆推出一开始的flag的。（当然由于kanxue的要求，这里要恰好没有’+‘、‘-’出现）
完整的逆推程序如下：
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
typedef unsigned char uchar;
typedef unsigned int uint;
uchar key[16]={0x14,0x22,0x1E,0x10,0x38,0x30,0x18,0x10,0x4,0x1A,0x24,0x8,0x2,0x26,0x38,0x2A};
char trans[]="abcdefghijklmnopqrstuvwxyz+-ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
char input[20];
uchar box1[16][16],box2[64][64][64],rbox1[64][64][64],rbox2[64][64][64],rbox3[64][64][64];
void judge(){
    uchar box[22][16];
    for(int i=0;i<16;i++){
        int j=0;
        while(j<64&&trans[j]!=input[i])j++;
        box[0][i]=j;
    }
    for(int i=0;i<20;i++){
        for(int j=0;j<16;j++){
            int a[3]={0},p=0;
            for(int k=0;k<16;k++){
                int l=(k+j)%16;
                if(box1[j][l])
                    a[p++]=box[i][l];
            }
            box[i+1][j]=box2[a[0]][a[1]][a[2]];
        }
    }
    for(int k=0;k<=19;k++){
        for(int i=0;i<16;i++)printf("%02x ",box[k][i]);
        puts("");
    }
    for(int i=0;i<16;i++)if(key[i]!=box[19][i])puts("serial error");
 
    for(int i=0;i<16;i++)printf("%c",trans[box[9][i]>>1]);
    puts("");
}
void readFile(const char*fn,void*buf){
    FILE*f=fopen(fn,"rb");
    fseek(f,0,SEEK_END);
    uint size=ftell(f);
    fseek(f,0,SEEK_SET);
    fread(buf,size,1,f);
    fclose(f);
}
int p[16][3];
int rp[16][4]={0};
bool test(uchar x,uchar y,uchar z,uchar key[16],uchar res[16]){
    const int A=0,B=1,C=3;
    res[A]=x;
    res[B]=y;
    res[C]=z;
    uchar d[16];
    for(int i=0;i<16;i++)d[i]=3;
    bool vt[16]={0};
    vt[A]=vt[B]=vt[C]=1;
    for(int z=0;z<3;z++)d[rp[A][z]]--;
    int q[20]={A,B,C};
    int f=0,l=2;
    while(f<l){
        f++;
        for(int z=0;z<3;z++){
            int v=rp[q[f]][z];
            d[v]--;
            if(d[v]<=1){
                l++;
                int a0=p[v][0];
                int a1=p[v][1];
                int a2=p[v][2];
                int k=key[v];
                if(!vt[a0]){
                    res[a0]=rbox1[k][res[a1]][res[a2]];
                    vt[a0]=1;
                    q[l]=a0;
                }else if(!vt[a1]){
                    res[a1]=rbox2[res[a0]][k][res[a2]];
                    vt[a1]=1;
                    q[l]=a1;
                }else if(!vt[a2]){
                    res[a2]=rbox3[res[a0]][res[a1]][k];
                    vt[a2]=1;
                    q[l]=a2;
                }else{
                    if(k!=box2[res[a0]][res[a1]][res[a2]])return false;
                    l--;
                }
            }
        }
    }
    return l==15;
}
void rev(uchar key[16],uchar res[16]){
    int cnt=0;
    for(int i=0;i<64;i++){
        for(int j=0;j<64;j++){
            for(int k=0;k<64;k++){
                if(test(i,j,k,key,res))return;
            }
        }
    }
}
void runOnce(uchar key[16]){
    for(int j=0;j<16;j++){
        int a[3]={0},p=0;
        for(int k=0;k<16;k++){
            int l=(k+j)%16;
            if(box1[j][l])
                a[p++]=key[l];
        }
        printf("%02x ",box2[a[0]][a[1]][a[2]]);
    }
    puts("");
}
int main(){
    readFile("dump.hex",box1);
    readFile("dump2.hex",box2);
 
    for(int j=0;j<16;j++){
        int q=0;
        for(int k=0;k<16;k++){
            int l=(k+j)%16;
            if(box1[j][l])
                p[j][q++]=l,rp[l][rp[l][3]++]=j;
        }
    }
    for(int i=0;i<64;i++){
        for(int j=0;j<64;j++){
            for(int k=0;k<64;k++)rbox1[box2[i][j][k]][j][k]=i;
        }
    }
    for(int i=0;i<64;i++){
        for(int j=0;j<64;j++){
            for(int k=0;k<64;k++)rbox2[i][box2[i][j][k]][k]=j;
        }
    }
    for(int i=0;i<64;i++){
        for(int j=0;j<64;j++){
            for(int k=0;k<64;k++)rbox3[i][j][box2[i][j][k]]=k;
        }
    }
 
    uchar res[22][16];
    memcpy(res[19],key,sizeof key);
    for(int i=19;i>0;i--){
        for(int j=0;j<16;j++)printf("%02x ",res[i][j]);puts("...");
        rev(res[i],res[i-1]);
        for(int j=0;j<16;j++)printf("%02x ",res[i-1][j]);puts("");
        runOnce(res[i-1]);
    }
    char flag[17];flag[16]=0;
    for(int i=0;i<16;i++){
        flag[i]=trans[res[0][i]];
    }
    puts(flag);
 
    strcpy(input,flag);
    judge();
    return 0;
}

附件内容是上文所述的dump.hex和dump2.hex。
这道题非常友好，还给了提示，不过这里“每个人都会在另外2个人的帮助下开启一个房间”，似乎应该是“每个人都会在3个人的帮助下开启一个房间”。
程序不长，我们先按着提示，把这个程序用IDA分析，并完整的逆出来，最后可以随便输出一个串和IDA动态调试（在没有反调试、花指令的前提下，用IDA的源码级调试非常方便）的结果比对来验证逆的对不对，如下：
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
void doPause(){
#ifdef linux
    printf("Press enter to exit.");
    fflush(stdout);
    system("read unusedVar");
#else
    system("pause");
#endif
}
typedef unsigned char uchar;
typedef unsigned int uint;
uchar key[16]={0x14,0x22,0x1E,0x10,0x38,0x30,0x18,0x10,0x4,0x1A,0x24,0x8,0x2,0x26,0x38,0x2A};
char trans[]="abcdefghijklmnopqrstuvwxyz+-ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
char input[20];
uchar box1[16][16],box2[64][64][64];
void judge(){
    uchar box[22][16];
    for(int i=0;i<16;i++){
        int j=0;
        while(j<64&&trans[j]!=input[i])j++;
        if(j>=64) {
            puts("input error");
            doPause();
            exit(-1);
        }
        box[0][i]=j;
    }
    puts("");
    for(int i=0;i<20;i++){
        for(int j=0;j<16;j++){
            int a[3]={0},p=0;
            for(int k=0;k<16;k++){
                int l=(k+j)%16;
                if(box1[j][l])
                    a[p++]=box[i][l];
            }
            box[i+1][j]=box2[a[0]][a[1]][a[2]];
        }
    }
    for(int i=0;i<16;i++)if(key[i]!=box[19][i]){
        puts("serial error");
        return;
    }
    for(int i=0;i<16;i++)printf("%c",trans[box[9][i]>>1]);
    puts("");
}
void readFile(const char*fn,void*buf){
    FILE*f=fopen(fn,"rb");
    fseek(f,0,SEEK_END);
    uint size=ftell(f);
    fseek(f,0,SEEK_SET);
    fread(buf,size,1,f);
    fclose(f);
}
int main(){
    readFile("dump.hex",box1);
    readFile("dump2.hex",box2);
 
    puts("Only 'a'-'z','A'-'Z','0'-'9' accepted.");
    puts("Only 16 chars accepted.");
    printf("Serial:");
    scanf("%17s",input);
    if(strlen(input)>16)input[0]=0;//ployfill for scanf_s
    judge();
 
    doPause();
    return 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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
void doPause(){
#ifdef linux
    printf("Press enter to exit.");
    fflush(stdout);
    system("read unusedVar");
#else
    system("pause");
#endif
}
typedef unsigned char uchar;
typedef unsigned int uint;
uchar key[16]={0x14,0x22,0x1E,0x10,0x38,0x30,0x18,0x10,0x4,0x1A,0x24,0x8,0x2,0x26,0x38,0x2A};
char trans[]="abcdefghijklmnopqrstuvwxyz+-ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
char input[20];
uchar box1[16][16],box2[64][64][64];
void judge(){
    uchar box[22][16];
    for(int i=0;i<16;i++){
        int j=0;
        while(j<64&&trans[j]!=input[i])j++;
        if(j>=64) {
            puts("input error");
            doPause();
            exit(-1);
        }
        box[0][i]=j;
    }
    puts("");
    for(int i=0;i<20;i++){
        for(int j=0;j<16;j++){
            int a[3]={0},p=0;
            for(int k=0;k<16;k++){
                int l=(k+j)%16;
                if(box1[j][l])
                    a[p++]=box[i][l];
            }
            box[i+1][j]=box2[a[0]][a[1]][a[2]];
        }
    }
    for(int i=0;i<16;i++)if(key[i]!=box[19][i]){
        puts("serial error");
        return;
    }
    for(int i=0;i<16;i++)printf("%c",trans[box[9][i]>>1]);
    puts("");
}
void readFile(const char*fn,void*buf){
    FILE*f=fopen(fn,"rb");
    fseek(f,0,SEEK_END);
    uint size=ftell(f);
    fseek(f,0,SEEK_SET);
    fread(buf,size,1,f);
    fclose(f);
}
int main(){
    readFile("dump.hex",box1);
    readFile("dump2.hex",box2);
 
    puts("Only 'a'-'z','A'-'Z','0'-'9' accepted.");
    puts("Only 16 chars accepted.");
    printf("Serial:");
    scanf("%17s",input);
    if(strlen(input)>16)input[0]=0;//ployfill for scanf_s
    judge();
 
    doPause();
    return 0;
}
其中这里的dump.hex原本是judge函数里的一个局部变量v24，可用IDA直接dump下来，dump2.hex原本是全局变量byte_139FEF0，同样可直接dump下来。

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课

最后于 2018-6-28 23:27 被qwertyaa编辑 ，原因： 把知2求1的过程预处理写道程序中
上传的附件：
收藏
免费 ・2
支持
分享
赞赏记录
参与人
雪币
留言
时间
PLEBFE
为你点赞~
2022-7-27 02:00
心游尘世外
为你点赞~
2022-7-27 00:05
最新回复 (0)
游客
登录 | 注册 方可回帖
回帖 表情 雪币赚取及消费
高级回复
返回

账号登录
验证码登录

忘记密码？
没有账号？立即免费注册
我已同意 《看雪服务条款》 《看雪课程免责声明》 《看雪隐私政策》