2020 KCTF秋季赛 | 第五题设计及解题思路
2020 KCTF正在如火如荼的进行中！已有超过5万人围观！第五题《紧急救援》历时4天，最终以 2 支战队破解的成绩落下帷幕。
在赛题即将结束的最后一天凌晨，k1ee 战队逆转直上，在凌晨2点42分攻击成功！并成功升至第二名的宝座，恭喜！ReZero战队随后也在7点左右提交答案，成为第二支挑战成功的战队，守住了第一的位置。
赛场如战场，各位选手不轻言弃，更是体现了高手过招的魅力！刀光剑影，是比拼更是成就，一招一式尽显各位英雄本色！
那么这道让众多团队都倍感遗憾的赛题，作者究竟都使用了哪些技术与tricks呢？让我们一起来看看吧！
一. 题目简介
逃离魔爪的你拖着疲惫的身心打算先找个地方安顿下来，了解目前的情况。
此时，脑海中第一个浮现的就是“他”——你的黑客挚友肖恩。肖恩是你任职于国家网络安全局时交到的唯一的朋友，跟你一样也是国安局的王牌。现在仍在职的他自然是收到了“破晓”的电子邀请函的。
但他不像你，自幼父母在事故中丧生，孤家寡人，无牵无挂。正是因为自己的女儿患先天疾病，被Norns判定为无资格登上方舟者，肖恩才毅然选择和家人们一起留在地球。
其实在“破晓”上检测到来自这座城市的异常信号时，你就猜测可能是肖恩的手笔了。
驱车赶往肖恩家，摁响门铃，迎接你的是肖恩的妻子。看到你的瞬间她瞪大了眼睛，惊讶、疑惑多种复杂的情绪快速变换着。你越过她朝家里扫视了一圈，心中的石头总算落下了，他们一家三口都平安无事，而且看起来都很正常。
但进了家门，你却越发觉得平静之下，暗藏波澜。肖恩妻女脸上的笑容总是很僵硬，平时对肖恩爱意满满的眼神如今却流露着不着痕迹的恐惧……肖恩却不以为然，微笑着夹起肉放在你的碗里。
饭桌上那说不出是温馨还是诡异的气氛让可口的饭菜都变得有些难以下咽。你抬头对上肖恩的视线，与刚才相比没有丝毫变化，就连嘴上扬起的弧度也如此标准而刻板。
你起了一身鸡皮疙瘩，再望向肖恩的妻子，她没有出声但好像在暗示你什么。你努力辨认她的口型，似乎是？
“快……逃……”
你站起来的瞬间，肖恩就朝你迎头一击，试图将你制服。你抄起刀与他对峙，发现他的伤口流出了仿生血液。
控制住他后，肖恩妻子告诉你，地球没有毁灭，但不知为何仿生人突然暴动，地球上大部分人类都被他们控制，而真正的肖恩也被他们抓走。
赶快利用仿生人肖恩的芯片寻找线索，定位肖恩的地理位置，解救他！
二. 出题团队简介
三. 看雪专家点评
点评由 HHHso 提供
本题防守方采用了多层VM的设计思路，比赛中VM常见，多层VM罕见，让攻击者欲罢不能。
当攻击者们在寻找快速方案如手解等方式拨开第一层VM后，发现后面还是VM，套娃感凸现，一望无际，定力稍有不慎，可能就会被吓住。这时候需要攻击者使用各种看家本领透视VM业务逻辑，层层击破，得到可阅读的代码。
当VM面纱都揭开时，高层VM对底层VM的运行时修改以及暗藏逻辑的触发联动机制也需要一一解开，才能联合起来得到完整的验证逻辑进行解题。高层VM对支撑其运作的低层VM修改和联动，除了套娃感，也略带虚拟逃逸感。总体设计非常优秀，相信各位攻击者都有所得。
四. 设计思路
设计思路由作者 ccfer 提供
题目类型：Window平台CrackMe
系统需求：WIN10/64
成功提示：Success!
题目答案：
AECCC0DE0C3256F75E37A6BFA227A2ED3D54AC964B43544632303230466C6167826B49EB0A305A72C2E92C18A0901280F47791BAE00932B0
设计说明
游戏原型是熄灯拼图，通过若干次的操作，每次切换某方块及其上下左右四个相邻方块的开关状态，直到全部状态完成翻转。
首先是个10*10的熄灯拼图，这规模小能直接搜到答案，需要最少44次操作，实现完全翻转，得到的解(开关操作位置图)是：
防止直接搜到答案，后面又加了一个40*40的，需要解线性方程组（用sage很快就跑出结果）。
详情参考：
hxxps://mathworld.wolfram.com/LightsOutPuzzle.html
然后这个10*10的解7位一组转成15个字节，每个字节最高位补充了校验位，最后再补充1个字节，变成16字节的key，用k表示。
为了压缩输入长度，40*40的解因为也是左右上下及对角线对称，可以用一个八分之一的局部三角形经三次镜像得到40*40的矩阵，输入只需要(1+19)*19/2=190位，8位一组转成24个字节用e表示。
整个完整key是56字节，可以表示为：
aaaakkkkkkkkkkkkkkkkbbbbccccddddeeeeeeeeeeeeeeeeeeeeeeee
其中aaaa、bbbb、cccc、dddd是固定常数，a部分的DWORD经过8轮Koopman多项式的crc运算。
k、b、c、d部分的28字节组成14个WORD，用ECC做一次点乘运算，ECC参数：p=65011，a=65008，b=6，G=(1,2)。
这个微型ECC直接穷举即可求解，每个点会有两个解，收集所有最高位排除多解
难度提升
算法用C语言实现，然后用一个简单的C编译器编译成opcode，再解释执行，相当于一个简单的虚拟机，感觉这个虚拟机也是相当简单了，于是把解释器也编译一遍，做一次嵌套的解释执行，大概意思是：从前有座山，山上有座庙，庙里有个老和尚，老和尚在给小和尚讲故事，故事讲的是......
解题思路
虚拟机比较简单，先把第一层opcode还原出来，发现逻辑竟然等同于解释器自身，只是opcode定义有些乱序，然后再还原出第二层和第三层，最后第四层里就只剩下简单的验证逻辑了然后ECC的p只有16位，直接穷举即可求解。
LightsOut求解直接用sage也是迅速得出结果。
crc暴力穷举会慢点，不过4字节得相当于可逆，有快速破解方法。
五. 解题思路
设计思路由作者 k1ee 提供
紧急救援
我真的没做过虚拟机题，这题套了4层虚拟机，属实给力，不能再用以前的手打虚拟机方法了，必须程序化。首先拖入IDA分析。
输入一段Hex Text，转为Hex Bytes。
建立缓冲区，复制虚拟机指令到如图位置。随后按以下结构体构造了虚拟机的参数
struct vm_sub
{
int param1; //6, 6, 6, 3
int param2; //ins1, ins2, ins3, input_hex
char* vm_ins;
int size;
int idk_0;
int id;
int idk7;
int idk8;
};
struct vm_fin
{
unsigned char* input_hex;
int* len_buf;
vm_sub* vmsub;
};
struct vm_context
{
vm_sub subs[4];
vm_fin fin;
};随后传入第一个虚拟机上下文参数(vm_sub)开始执行虚拟机，并由结果进行输出。
进入虚拟机函数，废话和弯路我就不多说了，直接分析可知
这是典型的压栈，再看后续指令
基本都是通过堆栈进行计算。经过两天的弯路后，我最终决定通过KeyStone还原各层虚拟机的源码。由于1，2，3层虚拟机的指令仅仅是替换而已，因此这里只分析第1层。（Butterfly为第0层，三个Buffer分别是1、2、3层，最后一层是关键代码）
只需要模仿通常静态分析手段扫过去就行了，然后按照对应OpCode生成汇编，然后再进行编译，贴上源码
#include <keystone/keystone.h>
...
void disassembly_vm1(vm_sub* ctx)
{
char* eip = ctx->vm_ins;
char* esp = eip + 2 * ctx->size;
ks_engine* ks;
ks_err err;
err = ks_open(KS_ARCH_X86, KS_MODE_32, &ks);
if (err != KS_ERR_OK)
{
cout << "Keystone open error." << endl;
return;
}
ostringstream dasm = ostringstream();
dasm << "push 6;" << endl;
dasm << "push 0x20000;" << endl;
dasm << "call vmins_0;" << endl;
dasm << "jmp vmins_ret;" << endl;
while (eip < ctx->vm_ins + 0x792)
{
int vm_offset = eip - ctx->vm_ins;
dasm << "vmins_" << vm_offset << ":" << endl;
int ins = *eip++;
switch (ins)
{
case 17:
{
dasm << "push ebx;" << endl;
break;
}
case 1:
{
uint8_t off = (uint8_t)*eip++;
dasm << "xor eax, eax;" << endl;
dasm << "mov al, " << (int)off << ";" << endl;
dasm << "lea ebx, [ebp+eax*4-400h];" << endl;
break;
}
case 13:
{
dasm << "mov ebx, [ebx];" << endl;
break;
}
case 3:
{
ecx = (uint8_t)*eip++;
dasm << "mov ebx, " << (int)ecx << ";" << endl;
break;
}
case 8:
{
uint32_t off = *(uint32_t*)eip;
dasm << "test ebx, ebx;" << endl;
dasm << "jz vmins_" << (int)(vm_offset + 1 + off) << ";" << endl;
dasm << "jmp vmins_" << (int)(vm_offset + 1 + 4) << ";" << endl;
eip += 4;
break;
}
case 21:
{
dasm << "pop ecx;" << endl;
dasm << "cmp ecx, ebx;" << endl;
dasm << "jnz vmins_" << vm_offset << "set0;" << endl;
dasm << "mov ebx, 1;" << endl;
dasm << "jmp vmins_" << vm_offset + 1 << ";" << endl;
dasm << "vmins_" << vm_offset << "set0:" << endl;
dasm << "mov ebx, 0;" << endl;
break;
}
case 15:
{
dasm << "pop edx;" << endl;
dasm << "mov [edx], ebx;" << endl;
break;
}
case 6:
{
uint32_t off = *(uint32_t*)eip;
//In disassembly mode we do not jump, but skip this instruction.
//eip += off;
if (off != 4)
dasm << "jmp vmins_" << (int)(vm_offset + 1 + off) << ";" << endl;
eip += 4;
break;
}
case 29:
{
dasm << "pop ecx;" << endl;
dasm << "add ebx, ecx;" << endl;
break;
}
case 30:
{
dasm << "pop eax;" << endl;
dasm << "sub eax, ebx;" << endl;
dasm << "mov ebx, eax;" << endl;
break;
}
case 14:
{
dasm << "xor ecx, ecx;" << endl;
dasm << "mov cl, [ebx];" << endl;
dasm << "mov ebx, ecx;" << endl;
break;
}
case 31:
{
dasm << "pop edx;" << endl;
dasm << "imul ebx, edx;" << endl;
break;
}
case 16:
{
dasm << "pop eax;" << endl;
dasm << "mov [eax], bl;" << endl;
dasm << "movsx ebx, bl;" << endl;
break;
}
case 33:
{
dasm << "pop eax;" << endl;
dasm << "xor edx, edx;" << endl;
dasm << "div ebx;" << endl;
dasm << "mov ebx, edx;" << endl;
break;
}
case 23:
{
dasm << "pop ecx;" << endl;
dasm << "cmp ecx, ebx;" << endl;
dasm << "jnb vmins_" << vm_offset << "set0;" << endl;
dasm << "mov ebx, 1;" << endl;
dasm << "jmp vmins_" << vm_offset + 1 << ";" << endl;
dasm << "vmins_" << vm_offset << "set0:" << endl;
dasm << "mov ebx, 0;" << endl;
break;
}
case 32:
{
dasm << "pop eax;" << endl;
dasm << "xor edx, edx;" << endl;
dasm << "div ebx;" << endl;
dasm << "mov ebx, eax;" << endl;
break;
}
case 24:
{
dasm << "pop edx;" << endl;
dasm << "cmp edx, ebx;" << endl;
dasm << "jbe vmins_" << vm_offset << "set0;" << endl;
dasm << "mov ebx, 1;" << endl;
dasm << "jmp vmins_" << vm_offset + 1 << ";" << endl;
dasm << "vmins_" << vm_offset << "set0:" << endl;
dasm << "mov ebx, 0;" << endl;
break;
}
case 18:
{
dasm << "pop ecx;" << endl;
dasm << "or ebx, ecx;" << endl;
break;
}
case 28:
{
dasm << "pop eax;" << endl;
dasm << "mov ecx, ebx;" << endl;
dasm << "shr eax, cl;" << endl;
dasm << "mov ebx, eax;" << endl;
break;
}
case 20:
{
dasm << "pop ecx;" << endl;
dasm << "and ebx, ecx;" << endl;
break;
}
case 19:
{
dasm << "pop ecx;" << endl;
dasm << "xor ebx, ecx;" << endl;
break;
}
case 27:
{
dasm << "pop edx;" << endl;
dasm << "mov ecx, ebx;" << endl;
dasm << "shl edx, cl;" << endl;
dasm << "mov ebx, edx;" << endl;
break;
}
case 22:
{
dasm << "pop eax;" << endl;
dasm << "cmp eax, ebx;" << endl;
dasm << "jz vmins_" << vm_offset << "set0;" << endl;
dasm << "mov ebx, 1;" << endl;
dasm << "jmp vmins_" << vm_offset + 1 << ";" << endl;
dasm << "vmins_" << vm_offset << "set0:" << endl;
dasm << "mov ebx, 0;" << endl;
break;
}
case 26:
{
dasm << "pop ecx;" << endl;
dasm << "cmp ecx, ebx;" << endl;
dasm << "jb vmins_" << vm_offset << "set0;" << endl;
dasm << "mov ebx, 1;" << endl;
dasm << "jmp vmins_" << vm_offset + 1 << ";" << endl;
dasm << "vmins_" << vm_offset << "set0:" << endl;
dasm << "mov ebx, 0;" << endl;
break;
}
case 0:
{
uint8_t off = (uint8_t)*eip++;
//ecx = (uint32_t)&eax[4 * off];
dasm << "xor edx, edx;" << endl;
dasm << "mov dl, " << (int)off << ";" << endl;
dasm << "lea ebx, [ebp+edx*4];" << endl;
break;
}
case 11:
{
uint32_t off = *(uint32_t*)eip;
//esp += 4 * off;
dasm << "mov eax, " << (int)(off * 4) << ";" << endl;
dasm << "add esp, eax;" << endl;
eip += 4;
break;
}
case 4:
{
ecx = *(uint32_t*)eip;
eip += 4;
dasm << "mov ebx, " << (int)ecx << ";" << endl;
break;
}
case 40:
{
//We do not execute
//char* buf = (char*)*((uint32_t*)esp + 2);
//uint32_t size = *(uint32_t*)esp;
//ecx = (uint32_t)buf;
//memset(buf, esp[4], size + (size & 3));
//eax = ebx;
dasm << "mov ecx, [esp+0];" << endl;
dasm << "xor eax, eax;" << endl;
dasm << "mov al, [esp+4];" << endl;
dasm << "mov edi, [esp+8];" << endl;
dasm << "mov ebx, edi;" << endl;
dasm << "rep stosb;" << endl;
break;
}
case 42:
{
//We do not execute
//ecx = (uint32_t) * ((uint32_t*)esp + 2);
//memcpy((void*)*((uint32_t*)esp + 2), (void*)*((uint32_t*)esp + 1), *((uint32_t*)esp));
//eax = ebx;
dasm << "mov ecx, [esp+0];" << endl;
dasm << "mov edi, [esp+8];" << endl;
dasm << "mov esi, [esp+4];" << endl;
dasm << "mov ebx, edi;" << endl;
dasm << "rep movsb;" << endl;
break;
}
case 9:
{
uint32_t off = *(uint32_t*)eip;
dasm << "test ebx, ebx;" << endl;
dasm << "jz vmins_" << (int)(vm_offset + 1 + 4) << ";" << endl;
dasm << "jmp vmins_" << (int)(vm_offset + 1 + off) << ";" << endl;
eip += 4;
break;
}
case 2:
{
uint32_t off = *(uint32_t*)eip;
//ecx = (uint32_t)&eax[4 * off];
eip += 4;
dasm << "mov ecx, " << (int)off << ";" << endl;
dasm << "lea ebx, [ebp+ecx*4];" << endl;
break;
}
case 7:
{
uint32_t off = *(uint32_t*)eip;
//push(esp, (uint32_t)eip + 4);
//In disassembly mode we do not jump, but skip this instruction.
//eip += off;
dasm << "call vmins_" << (int)(vm_offset + 1 + off) << ";" << endl;
dasm << "mov ebx, eax;" << endl;
eip += 4;
break;
}
case 10:
{
uint32_t off = *(uint32_t*)eip;
dasm << "push ebp;" << endl;
dasm << "mov ebp, esp;" << endl;
dasm << "sub esp, " << off * 4 << ";" << endl;
eip += 4;
break;
}
case 12: // return
{
dasm << "mov eax, ebx;" << endl;
dasm << "mov esp, ebp;" << endl;
dasm << "pop ebp;" << endl;
dasm << "ret;" << endl;
break;
}
case 43:
{
dasm << "mov eax, [esp];" << endl;
dasm << "ret;" << endl;
goto finished;
}
default:
{
cout << "Error";
break;
}
}
}
finished:
dasm << "vmins_ret:" << endl;
dasm << "push ebx;" << endl;
dasm << "mov eax, [esp];" << endl;
dasm << "ret;" << endl;
unsigned char* output;
size_t outlen = 0;
size_t outcnt = 0;
string disasm = dasm.str();
ofstream fout = ofstream("./disasm_vm1.txt", ios_base::ate);
fout << disasm;
fout.flush();
fout.close();
const char* code = disasm.c_str();
if (ks_asm(ks, code, 0, &output, &outlen, &outcnt) != KS_ERR_OK)
{
ks_err err = ks_errno(ks);
cout << err;
}
fout = ofstream("./disasm_vm1.bin", ios_base::ate | ios_base::binary);
fout.write((const char*)output, outlen);
fout.flush();
fout.close();
ks_free(output);
ks_close(ks);
}需要注意的是，除了第1层的40和42，以及后续层的这两个位置的指令，其他各层都相同，因此分析后面的只需要改一下case就行了。额外，第2、3层的这两个指令加了不少其他代码，但是我发现不对增加的代码进行增补也可以解题，后面细说。除此之外，还需要注意把lea esp的地方改为add/sub esp，不然IDA不认（非标准
分析完4层指令后，贴上关键的反编译函数。
第1层
第2层
第3层
最终分析目标函数（第4层）
首先获取了前面几层的指令指针
这里其实调用了memcpy系列函数，不过被优化了，由于我偷懒，并没有为每层更改memcpy，memset系列函数的实现，因此看到这个指令，就可以认为调用了Host的那个地方的函数，转而看前面层的代码就可以了。在这里，经过提取分析，得到这里memcpy对前4字节的CRC32
int vm3_memcpy(char* dst, char* src, int len)
{
vm_fin* v18 = &ctx.fin;
unsigned char * v17 = v18->input_hex;
int* v16 = new int[10];
v16[2] = 0xDEC0CCAE;
*(v16 + 2) = crc32(0xFFFFFFFF, v16 + 2);
*(v16 + 2) = crc32(0xFFFFFFFF, v16 + 2);
*(v16 + 2) = crc32(0xFFFFFFFF, v16 + 2);
*(v16 + 2) = crc32(0xFFFFFFFF, v16 + 2);
*(v16 + 2) = crc32(0xFFFFFFFF, v16 + 2);
*(v16 + 2) = crc32(0xFFFFFFFF, v16 + 2);
*(v16 + 2) = crc32(0xFFFFFFFF, v16 + 2);
*(v16 + 2) = crc32(0xFFFFFFFF, v16 + 2);
if (*(v16 + 2) == 0xDE05629C)
return 1;
return 0;
}经过爆破，可以得出前4字节为AE CC C0 DE。
result = d54b1112 target = de05629c result = 5ba49ea3 target = d54b1112 result = f16f3846 target = 5ba49ea3 result = 84b4f299 target = f16f3846 result = 3731ce56 target = 84b4f299 result = 74f3e321 target = 3731ce56 result = 20558f1 target = 74f3e321 result = dec0ccae target = 20558f1 result = f812fce7 target = dec0ccae
随后分析下一个函数
这里修改了上层Host的指令，可以看出是修改了一些立即数（前后对照），因此在还原函数的时候稍加注意即可，对于第一个memset，提炼出关键校验函数有：
int vm3_memset_1(char* dst, char val, int len)
{
vm_fin* v18 = &ctx.fin;
char* hex = (char *)v18->input_hex;
int* v16 = v18->len_buf;
int* v6 = v16 + 4;
*v6 = sub_E21(hex); // equals D540
v6 = v16 + 2;
*v6 = sub_109A(hex + 4, (char*)v16 + 256);
memset(v16 + 1024, 1, 100);
sub_1517((char*)v16 + 256, (char*)v16 + 4096);
return 0;
}sub_E21完成了某种变换，可以通过爆破还原，并计算了一个值(D540)避免多解，随后由于前4字节已经计算出，带偏移传入sub_109A
unsigned int __cdecl sub_109A(char* a1, char* a2)
{
int v3; // [esp+3ECh] [ebp-14h]
char* v4; // [esp+3F0h] [ebp-10h]
unsigned __int8 v5; // [esp+3F4h] [ebp-Ch]
unsigned int v6; // [esp+3F8h] [ebp-8h]
unsigned int v7; // [esp+3FCh] [ebp-4h]
v4 = a2;
v7 = 0;
v3 = 0;
while (v7 < 15)
{
v6 = 0;
v5 = a1[v7];
v3 <<= 1;
v3 |= (unsigned int)v5 >> 7;
while (v6 < 7)
{
*v4 = v5 & 1;
v5 >>= 1;
++v4;
++v6;
}
++v7;
}
return (((v3 << 8) + ((unsigned int)(unsigned __int8)a1[14] >> 2)) << 8) + (unsigned __int8)a1[15];
}前14个字节以及15字节的低2位变成10*10矩阵，随后初始化棋盘，使用sub_1517进行解密。
完成的是根据输入，从左上角依次访问棋盘，并对访问位置及其相邻的元素进行异或，最终使得全1变为全0。这里算法不多说，可以去看文章。完成求解
此时根据这里的防止多解，完成前8个int的求解
AE CC C0 DE 0C 32 56 F7 5E 37 A6 BF A2 27 A2 ED 3D 54 AC 96 4B 43 54 46 32 30 32 30 46 6C 61 67
最后分析最后6个int，和前面棋盘大同小异，192比特的前190比特以三角形的方式放入矩阵，并将三角形复制8次填满矩阵，然后求解使得棋盘翻转。
int vm3_memset_2(char* dst, char val, int len)
{
vm_fin* v18 = &ctx.fin;
char* v17 = (char *)v18->input_hex;
int* v16 = v18->len_buf;
int* v6 = v16 + 2;
*v6 = sub_179A(v17 + 32, (char *)v16 + 64*4);
if (*v6 == 2)
{
memset(v16 + 1024, 1, 1600);
sub_2FB9((char*)v16 + 4*64, (char*)v16 + 4*1024);
}
return 0;
}*v6 == 2指的是剩余2比特（高2位），因此求解该矩阵
uint32_t limit = pow(2, 20) - 1;
for (uint32_t val = 0; val <= limit; ++val)
{
for (int i = 0; i < 20; ++i)
{
uint8_t bit = (val >> i) & 0b1;
mat[0][i] = bit;
mat[0][39 - i] = bit;
}
memset(table, 1, sizeof(table));
for (int i = 0; i < 40; ++i)
{
for (int k = 0; k < 40; ++k)
{
uint8_t bit = mat[i][k];
table[i][k] ^= bit;
if (i > 0)
table[i - 1][k] ^= bit;
if (i < 39)
table[i + 1][k] ^= bit;
if (k > 0)
table[i][k - 1] ^= bit;
if (k < 39)
table[i][k + 1] ^= bit;
}
if (i != 39)
{
for (int k = 0; k < 40; ++k)
{
mat[i + 1][k] = table[i][k];
}
}
}
if (memcmp(table, truth, sizeof(truth)) == 0)
{
printf("Result\n");
printf("arr = []\n");
for (int i = 0; i < 40; ++i)
{
printf("arr.append([");
for (int k = 0; k < 40; ++k)
{
printf("%d%s", mat[i][k], k == 39 ? "" : ", ");
}
printf("]\n");
}
}
}最终完成求解
拿脚本解出来
因此最终Flag为
1 |
|
