-
-
[推荐]2019 KCTF 总决赛 | 第十题《幕后之王》点评及解题思路
-
发表于: 2020-1-6 11:37
-
1、题目简介
再次睁眼，我躺在一只玩具熊上面。
突然这只玩具熊动了动：“醒醒，万金斯！”
我的脸上带着护具，我摸了一下脑后，是一个开关，我试图调了一下，突然升高的温度让我差点儿喘不过气来。
似乎是一个温控开关。我的眼前出现一块蓝色显示屏，数字显示“18：10”，然后时间开始一分分向前。
“恭喜你来到最后的关卡。这次的任务是找出系统的创造者。
”听起来还挺简单的，不就是找个人嘛，之前那么难的关卡我都过来了，这算什么。
“你还有两个小时的时间，如果你在这段时间里不能完成任务的话，护具将升温把你变成系统的的程序，再也无法回到现实世界。”
我猛然意识到事情的严重性，再看看屏幕，留给我的时间已经不多了。
[说明：本题是一道Windows逆向题]
2.2.5 多解罚分 = 此题难度分 × 多解罚分系数（20% ）。如果防守题被发现多解，则给防守方1次修改机会，并扣多解罚分。若修改后又多解，则下线退赛，攻击方在此题获得的成绩保留不受影响。
扣除防守方题目20%成绩，即240-240*20%=200分。在得分相同的情况下，以破解次数排序；破解次数相同时，以破解时间排序；以上都相同时，以提交时间排序。
经过最终评定，该道题的防守方团队排名第二。
接下来让我们一起来看一下这道题的点评和详细解析吧。
2、看雪评委crownless点评
3、出题团队简介
团队简介：
lelfei，业余的crack爱好者。学生时代对电脑产生了浓厚的兴趣，经历了很长时间的游戏沉迷后，开始慢慢转向学习技术，工作后自学了ASM，VB，VC，HTML，ASP，Python等语言的入门。工作原因上网较少，对单机的逆向分析、算法比较感兴趣，但是由于缺少系统的学习，水平处于“入行较早层次较低知识较杂”的阶段。
4、设计思路
预设答案：sBXI5MQArEuDiC3jbrGgEoiQ7x8w7hOog8YiiG8wwg78hYoiUbwh8ib8w7YogiihYaXilxwxRwRIYRiSwRYiigLywwYRiX8LbwRYiiOwbX8Yi4Hi
设计说明：
设计灵感来源于某手游里的一个小迷宫（看看有多少人知道这个手游？），目标是收集迷宫中的4把钥匙，并从迷宫中走出来。
迷宫一共有4层，每层有5*6个格子，每个格子的地面属性有4种：平地，洞，上楼梯，下楼梯。格子上的物品属性有4种：空，柱子，乱石堆，钥匙。
角色行动规则：角色只能在空地上通过，不能从有洞的地方通过；角色不能从石堆通过，但可以从柱子边通过；柱子可以推动，如果柱子推到洞口会掉到洞里，正好能把洞填平，可以让角色从该格通过；柱子从楼上的洞中掉下来时，会把楼下的物品砸碎。
迷宫初始化数据为：
01 11 01 00 00 -03 01 11 01 01 -03 11 21 00 00 -03 00 00 00 31
01 01 01 00 00 -00 00 00 01 00 -01 01 00 00 31 -11 00 11 00 00
00 00 01 00 01 -00 11 00 01 00 -01 00 00 00 00 -01 00 01 01 01
00 01 01 00 11 -01 00 00 00 00 -01 00 00 00 00 -00 00 00 11 00
21 00 00 01 00 -00 00 00 00 01 -00 11 01 00 01 -00 00 01 00 00
31 00 00 01 02 -00 11 01 00 02 -11 01 01 00 02 -31 01 00 00 02
角色初始化位于一层的左上角，读取用户输入的指令开始行动，集齐迷宫中的4把钥匙，并通过迷宫第四层，即可获得胜利。
先把秘籍附上：（I为移动柱子，X为移动角色，注意坐标从1开始，先纵坐标再横坐标）
一楼：I(1,2)-(4,4)掉 I(4,5)-(3,3) X上
二楼：I(3,2)-(4,2)掉 I(1,3)-(5,1)砸 X下
一楼：I(4,2)-(5,2)掉 X(6,1)钥 I(3,3)-I(4,4) I(5,1)-(5,4) X上
二楼：X上
三楼：I(1,2)-(5,1)掉掉 X下
二楼：X下
一楼：I(4,4)-(4,2) I(5,1)-(5,2) I(5,4)-(3,3) X上
二楼：I(6,2)-(4,1) X下
一楼：I(5,2)-(5,1) X上
二楼：I(4,1)-(5,1) X下
一楼：I(4,2)-(5,4) I(3,3)-(4,4) X上
二楼：X上
三楼：I(5,2)-(5,4)掉 I(6,1)-(2,2) X上
四楼：I(2,3)-(1,3)砸 X下
三楼：I(1,3)-(1,4)掉 X下
二楼：I(1,4)-(1,5) I(5,4)-(1,4) X上
三楼：X(2,5)钥 X下
二楼：I(1,4)-(5,4) X上
三楼：X上
四楼：I(4,4)-(2,5)掉 X(1,5)钥 X下
三楼：X下
二楼：I(5,4)-(1,4) X上
三楼：I(2,2)-(5,1) I(2,5)-(4,1) X下
二楼：I(1,4)-(5,4) X上
三楼：X上
四楼：X(6,1)钥 X下
三楼：I(4,1)-(2,2) I(5,1)-(5,4) X上
四楼：I(2,1)-(5,5)掉 X上
为了加大难度，又定义了3个大数，前2个num1和num2从用户输入数据中取出，第3个num3固定为0x9B87A982A0380，幕后之王的血量numSum初始化为3，当收集第一把钥匙时numSum为0x37，收集第二把钥匙时numSum=num1-num2-num3，收集第三把钥匙时numSum=num1*num1-num2*num2-num3*num3，收集齐四把钥匙后numSum=num1*num1*num1-num2*num2*num2-num3*num3*num3。numSum发生变化时用numSum最低位对迷宫数据进行XOR加密。
当收集到钥匙的同时会增加角色能量值，初始化时能量值keyCount为3，每次收集到钥匙时能量值按照keyCount=((keyCount+2)//2)*3变换，即变化规律为3，6，12，21，33。
当通关时要求角色能量值与幕后之王的血量相等，即numSum=33。
为了避免多解，还计算了用户输入数据的CRC校验值，并限制输入长度为112字节以内，除去前18字节用于初始化大数，用户移动步骤只有94字节，移动柱子需要2字节，移动角色需要1字节，按通关秘籍正好一步都不能浪费，但是相同层的移动数据则可以前后交换，按上面的步骤，最多需要3072次枚举。
最后又添加了几个检测调试的函数，并“阴险”地把其中一个检测函数手工patch到程序入口位置，细心一点才能发现，希望你不要中招。
程序使用CodeBlocks设计，gcc编译，在win7x64下测试通过。
破解建议：
1. 找到keyCount变换的方式，并得到大数的立方差为33，然后上网搜索出x*x*x+y*y*y+z*z*z=33的标准答案。
2. 还原出迷宫数据，自己解出通关步骤或在网上找到答案。
3. 组合上面二个答案，进行简单变换后即为正确通关秘籍。
个人总结：
1. 移动角色或柱子需要设计自动寻路函数FindPath()，不只要找平地，还需要找下一层是柱子的洞。在这里耽搁了很长时间，最后试出了一种比较巧妙的方法：用一个数组记录找的方向，再增加一个数组记录移动过来的方向，当找完3个方向都没有路时，根据移动过来的方向返回到上一个格子继续找。
2. 在计算大数乘法时，按乘法竖式从低位向高位计算，优点是只需要申请一个变量记录进位，二次小循环就搞定。
3. 从开始设计这个crackme起就在断断续续的出差，时间不够了，不然会在AntiDebug方面挖更多的坑，交互提示也会更完善更友好。
文件说明：
lelfei - LastLord.rar 参赛文件src.rar 程序源码rnd.py 生成随机字符串序列bb.py 根据随机字符串序列，按移动步骤生成标准答案byteenc.py 把程序中预定义的“mov eax, 0x99999999”替换为随机花指令readme.txt 本说明文件
5、解题思路
本题解题思路由金左手战队 ccfer提供：
这个迷宫题目还是挺有意思的，后来发现可以多解碰撞crc，就觉得更有意思了。
这个程序有tls和几处anti，还是要稍微小心一点：
401660 CheckRemoteDebuggerPresent4015E0 NtQueryInformationProcess401710 GetThreadContext 检查drx之和401690 setjmp3/SetUnhandledExceptionFilter
输入处理：
.text:004B5370 sub eax, 004BA040h //"6GxRI4XlsLDQoVfb7pgE8hcYHaUtWZwKBPyNvuCSF3d0e2JA9q5jrTMOzknim1" .text:004B5375 test al, al .text:004B5377 mov [ebp+ebx+var_264], al //base64 decode ... .text:004B539E sub eax, 12h //前18个字符 .text:004B53A1 cmp eax, 5Dh //后93个字符 .text:004B53A4 ja loc_4B55EC //输入总长度不超过112 ... .text:004B53AA lea ecx, [ebp+var_1E4] .text:004B53B0 mov [ebp+var_298], 1 .text:004B53BA call sub_4017A0 //初始化迷宫数据 .text:004B53BF lea eax, [ebp+var_25B] .text:004B53C5 lea ecx, [ebp+var_1E4] .text:004B53CB mov [esp+2C8h+var_2C4], eax .text:004B53CF lea eax, [ebp+var_264] .text:004B53D5 mov [esp+2C8h+var_2C8], eax .text:004B53D8 call sub_401BD0
加密的迷宫初始数据，四个关卡，每关地图大小是6x5：
02 13 00 00 07 07 04 05 0B 0A 09 08 0E 0E 0C 0C 12 13 11 01 36 16 15 15 1B 2B 19 18 1E 1C 1E 1D 32 23 20 20 27 26 24 24 2B 3B 29 29 2F 2F 2D 2C 33 32 31 30 37 36 34 34 2A 3B 39 3A 3C 2F 1C 3C 43 43 40 40 47 77 44 44 4B 4A 49 49 4F 4E 4D 4C 53 43 50 50 56 47 54 55 5B 58 5A 58 5F 5E 6C 4D 63 73 61 60 66 66 64 65 6A 6A 69 68 7E 6E 6D 6C 72 72 71 41 76 76 75 76
几个关键函数：
sub_401DE0 会被多处调用的函数，调试分析得知是个寻路判断函数，返回值表示两个点之间是可到达，同时也可看到迷宫数据解密算法，算法比较简单xor个密钥再xor个索引序号。
先用初始迷宫密钥3解密出明文迷宫数据，方便后面描述：
01 11 01 00 00 01 01 01 00 00 00 00 01 00 01 00 01 01 00 11 21 00 00 01 00 31 00 00 01 02 03 01 11 01 01 00 00 00 01 00 00 11 00 01 00 01 00 00 00 00 00 00 00 00 01 00 11 01 00 02 03 11 21 00 00 01 01 00 00 31 01 00 00 00 00 01 00 00 00 00 00 11 01 00 01 11 01 01 00 02 03 00 00 00 31 11 00 11 00 00 01 00 01 01 01 00 00 00 11 00 00 00 01 00 00 31 01 00 00 02
从上面寻路判断函数中可以分析出：地图中的数值低4位是1表示该点可走，如果是0且下一层是1x表示空洞下面被垫高了也可同样可走。
sub_402460 走到指定位置，如遇到道具会自动拾取，0x31道具可以改变密钥。
sub_402460()
{
...
if ( (v10 & 0xF) == 1 )
{
*((_DWORD *)v2 + 2) = x;
*((_DWORD *)v2 + 3) = y;
if ( (signed int)v10 >> 4 == 3 ) //0x31类型道具
{
v23[20] = v19 ^ (v22 + y) ^ ((v22 + y) ^ v9) & 0xF;
v12 = *((_DWORD *)v2 + 0x65) == 1;
*((_DWORD *)v2 + 4) = 3 * ((*((_DWORD *)v2 + 4) + 2) >> 1); //w = (w+2)/2*3，w初始值是3，经过3次迭代会等于十进制的33
if ( v12 && v19 == 3 )
{
v2[0x198] = 0x37; //第一次拾取0x31道具，修改迷宫密钥为k = 0x37
v13 = 0x37;
}
else
{
sub_401AB0(v2 + 0x110, v2 + 0x110, v2 + 0x8C); //大数乘法 a *= x
sub_401AB0(v2 + 0x13C, v2 + 0x13C, v2 + 0xB8); //大数乘法 b *= y
sub_401AB0(v2 + 0x168, v2 + 0x168, v2 + 0xE4); //大数乘法 c *= z
sub_4019F0(v2 + 0x194, v2 + 0x110, v2 + 0x13C, v2 + 0x168); //修改密钥 k = a - b - c
v13 = v2[0x198];
}
//变更密钥后，需要对数据用新密钥重新加密
v14 = v2 + 0x32;
v15 = v2 + 0xAA;
v16 = v13 ^ v19;
do
{
v17 = v14 - 30;
do
{
v18 = (int)(v17 + 5);
do
*v17++ ^= v16;
while ( v17 != (_BYTE *)v18 );
}
while ( v17 != v14 );
v14 += 30;
}
while ( v14 != v15 );
}
}
return 0;
}sub_4026A0 指定位置使用道具，从使用道具的函数里可以分析出：迷宫是逐个关卡从低到高立体层叠的，0x11道具可以从空洞掉落到下一层，下一层是空洞会继续掉落下去。
sub_402400 判断是否可进入上一关，如果可到达，则会来到上一关的右下角坐标(5,4)。
sub_402380 判断是否可进入下一关，如果可到达，则会来到下一关的左上角坐标(0,0)。
.text:004023CE movzx eax, byte ptr [ebx+198h].text:004023D5 cmp [ebx+10h], eax //检查最终密钥 if (k == w).text:004023D8 jnz short loc_4023F0
所有游戏的主体就用输入的key控制走路过程，从每层的左上角走到右下角进入下一关，直到第4关通关。
单独看每一关的话，6x5的地图，似乎也并不复杂，就手动走着玩玩。
因为高层的道具会掉落下去的原因，有时需要返回前面低级关卡，处理给适当的位置垫高的问题。
开始也是拾取过第一关的道具，走到第三关后没路走不下去了。
多次尝试后，发现拾取道具是个负担，无视道具反而容易看清路线，就想到了试试不拾取0x31道具能不能走通。
竟然真的走通了，路线步骤，如下：
01 12 13 06 3B 0B 0D 1E 06 17 3B 02 12 3B 01 10 1E 1E 10 06 3B 0D 0B 1E 06 10 17 0C 3B 0B 10 1E 10 1C 0C 17 3B 1A 12 1E 1C 11 3B 12 10 3B 19 17 15 17 3B 05 06 07 17 12 18 3B
每个步骤转成平面坐标表示是(v/5,v%5)。
其中那些小于0x1E步骤都是两个一组，从一个位置拿到0x11类型的箱子，扔到另一个位置的0x00空洞里。
0x1E是回到上一关，0x3B是进入下一关。
迷宫虽然走通了，但是后面却有个crc判断：
.text:004B563A cmp [ebp+ok_v3], 0D1B623CDh .text:004B5644 jnz l_4B55EC_lost_ .text:004B564A mov [esp+2C8h+var_2C0], 16h .text:004B5652 mov [esp+2C8h+var_2C4], offset sz_4BA024_win ; "恭喜你打败了幕后之王！"
因为自己的这个伪key才58个字符，比最大93还差35个字符可利用进行碰撞，直觉上这碰撞没有道理不成立，也觉得这个还是有点意思的，就决定沿着这条路死磕到底了。
可惜直到比赛结束也没有解决这个crc问题，因为带着寻路算法碰撞效率太低，尝试了各种碰撞方法都没成功，当时也没有分心去解那组大数方程。
比赛结束后，作者也贴出了预设答案。
刚好晚上有空，继续思考碰撞，这次避开了在地图里碰撞需要寻路的产生的效率问题。
在自己的路线上，选取了一个在第一关里有13个自由落脚点的时机，把这13个点直接写成一个一维数组其它不可走的点直接扔掉。
当时第一关状态：
01 01 01 00 00 01 01 01 00 00 00 00 01 00 01 00 01 11 11 01 21 00 00 11 00 31 00 00 01 02
这样做个13进制的大数穷举，不需要寻路算法，应该速度快很多。
大致估算了一下理论依据：13的9次方就已经大于2的33次方了，超出crc空间范围的2倍多了，所以理论上9步的全排列就平均让每个crc值出现两次碰撞了。
最后20分钟左右，果然9步就碰撞成功，看了一下9步的空间大概推进到一半了，全跑完9步40分钟左右。
虽然前18个字符可以随意输入有效字符，但为了搞得漂亮一点，构造出这个key：
KCTF2019Q4LastLordGgEXiQVwXYixgiG7ww7XiVQwX7YoiQ7w7WoYiUgwWpTBJKNq9Aeig7iaYhYi4XlYgHi
最后才想到还有个大数是怎么回事，那个是 今年刚被解决的 3个数的立方和等于33的著名难题，百度找答案就可以了。
（8866128975287528）^3+（–8778405442862239）^3+（–273611468807040）^3=33
碰撞代码：
DWORD get_crc(BYTE *lpData, int nLen,DWORD crc0)
{
DWORD crc = crc0;
BYTE t;
int i,j;
for (j=0;j<nLen;j++)
{
t = lpData[j];
if (t >= 30)
{
if (t >= 60)
{
continue;
}
t -= 30;
}
crc ^= t;
for (i=0;i<8;i++)
{
if (crc & 1)
{
crc >>= 1;
crc ^= 0xEDB88320;
}
else
{
crc >>= 1;
}
}
}
return crc;
}
int crack_crc()
{
int rv = 0;
DWORD i;
BYTE key_head[] = {0x01,0x12,0x13,0x06,0x3B,0x0B,0x0D,0x1E,0x06,0x17,0x3B,0x02,0x12,0x3B,0x01,0x10,0x1E,0x1E,0x10,0x06,0x3B,0x0D,0x0B,0x1E,0x06,0x10,0x17,0x0C,0x3B,0x0B,0x10,0x1E,0x10,0x1C,0x0C,0x17,0x3B,0x1A,0x12,0x1E,0x1C,0x11};
BYTE key_tail[] = {0x3B,0x12,0x10,0x3B,0x19,0x17,0x15,0x17,0x3B,0x05,0x06,0x07,0x17,0x12,0x18,0x3B};
BYTE key_mid[35] = {0};
BYTE positions[] = {0x01,0x02,0x05,0x06,0x07,0x0C,0x0E,0x10,0x11,0x12,0x13,0x17,0x1C};
BYTE num[sizeof(key_mid)];
DWORD crc_head;
DWORD crc_mid;
DWORD crc_target = 0xD1B623CD;
DWORD base = sizeof(positions);
for (i=0;i<base;i++)
{
positions[i] += 30;
}
memset(num,0xFF,sizeof(num));
crc_head = get_crc(key_head,sizeof(key_head),0x77777777);
printf("crc_head = %08X\n",crc_head);
DWORD delta = 0x80000000; //故意加这个偏移，是因为已经跑出了结果，节省这步的演示时间
for (i=0;i<=0xFFFFFFFF;i++)
{
if (get_crc(key_tail,sizeof(key_tail),i+delta) == crc_target)
{
crc_mid = i + delta;
break;
}
}
printf("crc_mid = 0x%08X\n",crc_mid); //0x80FF5909
DWORD numlen = 0;
while(numlen < sizeof(key_mid))
{
if (crc_mid == get_crc(key_mid,numlen,crc_head))
{
printf("crc matched\n");
printf("key_mid[] = "); //35 20 2E 1F 23 31 30 2F 2C
for (i=0;i<numlen;i++)
{
printf("%02X ",key_mid[i]);
}
printf("\n");
return 1;
}
//next num
DWORD next = 1;
while (next)
{
next = 0;
for (i=0;i<sizeof(key_mid);i++)
{
if (num[i] == 0xFF)
{
num[i] = 0;
numlen++;
break;
}
else if (num[i] < base-1)
{
num[i]++;
break;
}
else
{
num[i] = 0;
}
}
key_mid[0] = positions[num[0]];
for (i=1;i<numlen;i++)
{
key_mid[i] = positions[num[i]];
if (key_mid[i] == key_mid[i-1])
{
next = 1;
break;
}
}
}
}
return rv;
}#END
[招生]科锐逆向工程师培训(2024年11月15日实地，远程教学同时开班, 第51期)
最后于 2020-1-7 16:24
被Editor编辑
，原因：
