看雪.京东 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的源码级调试非常方便）的结果比对来验证逆的对不对，如下：
using namespace std;
void doPause(){
printf("Press enter to exit.");
fflush(stdout);
system("read unusedVar");
system("pause");
}
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的要求，这里要恰好没有’+‘、‘-’出现）
完整的逆推程序如下：
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安全开发者峰会
2018年7月21日，拥有18年悠久历史的老牌安全技术社区——看雪学院联手国内最大开发者社区CSDN，倾力打造一场技术干货的饕餮盛宴——2018 安全开发者峰会，将在国家会议中心隆重举行。会议面向开发者、安全人员及高端技术从业人员，是国内开发者与安全人才的年度盛事。此外峰会将展现当前最新、最前沿技术成果，汇聚年度最强实践案例，为中国软件开发者们呈献了一份年度技术实战解析全景图。
戳下图↓，立即购票，享5折优惠！