首页
论坛
专栏
课程

[原创]KCTF2019_q4_第十题_幕后之王

2019-12-30 16:12 2534

[原创]KCTF2019_q4_第十题_幕后之王

ccfer
14
2019-12-30 16:12
2534
这个迷宫题目还是挺有意思的,后来发现可以多解碰撞crc,就觉得更有意思了

这个程序有tls和几处anti,还是要稍微小心一点
401660  CheckRemoteDebuggerPresent
4015E0  NtQueryInformationProcess
401710  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               //初始化几个大数,主要的是把输入的前18个字符拆分成两个大数x,y,还有一个固定的常数z
加密的迷宫初始数据,四个关卡,每关地图大小是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
这个检查的含义是输入的前18个字符组成的大数需要特定的值

所有游戏的主体就用输入的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;
}



[招生]科锐逆向工程师培训(3月6日远程教学班首开特惠, 第37期) !

最后于 2019-12-30 20:46 被ccfer编辑 ,原因:
最新回复 (3)
KevinsBobo 8 2019-12-30 18:17
2
0
感觉这道题的作者要女装一下才能补偿你呀
readyu 11 2019-12-30 23:02
3
0
很强大,膜拜
lelfei 21 2019-12-31 13:47
4
0
对ccfer的膜拜有如涛涛江水
游客
登录 | 注册 方可回帖
返回