看雪.京东 2018 CTF 第七题 密室逃脱 点评与解析

在淅淅沥沥的雨水中迎来周末，

气温有所下降，上海的温度正宜人。

各位小伙伴们可以开心的打CTF 比赛啦 ~

来看看过去的第七题结束后，

第七题出题者以被18人攻破的成绩，位列第二位

本题过后 攻击方前十名有略微的变动：

aps成功冲进前十位

AloneWolf 从第九名上升至第六名

oooAooo 也上升一位至前三名

革命尚未成功，朋友们仍需努力，

 加油！

看雪版主&评委 netwind 点评

本题作者提供了一个非常精彩的算法题目，一共进行了20轮变换操作，每轮变换都用了混淆函数运算和矩阵运算，每轮变换的输入是16个数据， 输出也是16个数据， 本轮输出数据作为下一轮输入，20轮变换之后 将变换结果与存储于程序中的理想结果进行比对 以确定输入序列号是否正确。分析出算法模型后便可以快速求解，或调用算法代码暴力枚举亦可解。

看雪.京东 2018 CTF 第七题 作者简介

看场雪

bbs.pediy.com/user-697893

第七题出题者简介：

ID：看场雪

星座：射手座

性格：追求完美

兴趣：白盒，芯片安全，BD，机器人，网络验证码，虚拟化安全

最喜欢的BGM：Supermassive Black Hole

看雪.京东 2018 CTF 第七题 设计思路

这是一个数字迷宫，分为20层楼。

16个人各选择一把初始钥匙，开始游戏。

16个人进入第一层，按照一定的规则，每个人都会在另外2个人的帮助下开启一个房间，拿到1把第二层楼的钥匙。

当16个人都拿到了各自的二层楼钥匙后，一起上楼。

第二层重复相同的操作，16个人再一起上到第三层。

...

直至16个人拿到了的20层天台的钥匙。

天台上有一架直升机，需要16把正确的钥匙才能开走。

试试看 你能否找出16把正确的初始钥匙

有人可能会想，只要砸碎直升机的门，不就可以把直升机开走了吗？

（那不算胜利哦）

在你开着直升机远去的时候，迷宫大楼的中间，那些曾经被你点亮的房间 会组成一个横幅。

只有在你拿到了正确钥匙的情况下，才会出现成功逃脱的横幅（那才算胜利哟）

程序运行起来后，请输入16个初始钥匙。

如果验证正确，最后会显示出正确的横幅。

否则，算作挑战失败。

看雪.京东 2018 CTF 第七题解析

＊本解析来自看雪论坛 qwertyaa

逆向部分

这道题非常友好，还给了提示，不过这里“每个人都会在另外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。

合作伙伴

京东集团是中国收入最大的互联网企业之一，于2014年5月在美国纳斯达克证券交易所正式挂牌上市，业务涉及电商、金融和物流三大板块。

 

京东是一家技术驱动成长的公司，并发布了“第四次零售革命”下的京东技术发展战略。信息安全作为保障业务发展顺利进行的基石发挥着举足轻重的作用。为此，京东信息安全部从成立伊始就投入大量技术和资源，支撑京东全业务线安全发展，为用户、供应商和京东打造强大的安全防护盾。

 

随着京东全面走向技术化，大力发展人工智能、大数据、机器自动化等技术，将过去十余年积累的技术与运营优势全面升级。面向AI安全、IoT安全、云安全的机遇及挑战，京东安全积极布局全球化背景下的安全人才，开展前瞻性技术研究，成立了硅谷研发中心、安全攻防实验室等，并且与全球AI安全领域知名的高校、研究机构建立了深度合作。

 

京东不仅积极践行企业安全责任，同时希望以中立、开放、共赢的态度，与友商、行业、高校、政府等共同建设互联网安全生态，促进整个互联网的安全发展。

CTF 旗帜已经升起，等你来战！

扫描二维码，立即参战！

看雪.京东 2018 CTF 

• 看雪.京东 2018 CTF 第一题点评与解析

• 看雪.京东 2018 CTF 第二题点评与解析

• 看雪.京东 2018 CTF 第三题点评与解析

• 看雪.京东 2018 CTF 第四题点评与解析

• 看雪.京东 2018 CTF 第五题点评与解析
  

看雪2018安全开发者峰会

2018年7月21日，拥有18年悠久历史的老牌安全技术社区——看雪学院联手国内最大开发者社区CSDN，倾力打造一场技术干货的饕餮盛宴——2018 安全开发者峰会，将在国家会议中心隆重举行。会议面向开发者、安全人员及高端技术从业人员，是国内开发者与安全人才的年度盛事。此外峰会将展现当前最新、最前沿技术成果，汇聚年度最强实践案例，为中国软件开发者们呈献了一份年度技术实战解析全景图。

戳下图↓，立即购票，享5折优惠！

戳原文，立刻加入战斗！