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

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

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

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的源码级调试非常方便）的结果比对来验证逆的对不对，如下：
#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代码来实现（来源于网络）：
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”的过程：

//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]是否正确的过程：
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的要求，这里要恰好没有’+‘、‘-’出现）
完整的逆推程序如下：
#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的源码级调试非常方便）的结果比对来验证逆的对不对，如下：
#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;
}
#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下来。

[培训]科锐逆向工程师培训第53期2025年7月8日开班！

最后于 2018-6-28 23:27 被qwertyaa编辑 ，原因： 把知2求1的过程预处理写道程序中
上传的附件：
收藏
免费 ・2
支持
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
回帖 表情 雪币赚取及消费
高级回复
返回