KCTF2019_q4_第十题

KCTF2019_q4_第十题_幕后之王
2019-12-31 16:49:26 Author: bbs.pediy.com(查看原文) 阅读量:135 收藏

[原创]KCTF2019_q4_第十题_幕后之王: 23小时前 275

这个迷宫题目还是挺有意思的，后来发现可以多解碰撞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;
}

[公告] 《安卓高级研修班(网课)》上线啦！

最后于 19小时前被ccfer编辑，原因：

文章来源: https://bbs.pediy.com/thread-256969.htm
如有侵权请联系:admin#unsafe.sh

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