[原创]看雪.京东 2018CTF 第七题密室逃脱 Writeup-CTF对抗-看雪-安全社区|安全招聘|kanxue.com

[原创]看雪.京东 2018CTF 第七题密室逃脱 Writeup

2018-6-30 12:00 3708

[原创]看雪.京东 2018CTF 第七题密室逃脱 Writeup

poyoten

2018-6-30 12:00

3708

题目描述如下：

这是一个数字迷宫分为20层楼
16个人各选择一把初始钥匙开始游戏
16个人进入第一层按照一定的规则每个人都会在另外2个人的帮助下开启一个房间拿到1把第二层楼的钥匙
当16个人都拿到了各自的二层楼钥匙后一起上楼
第二层重复相同的操作，16个人再一起上到第三层
...
直至16个人拿到了的20层天台的钥匙
天台上有一架直升机，需要16把正确的钥匙才能开走
试试看你能否找出16把正确的初始钥匙

程序流程

程序开门见山。程序中的算法也如上所述。

int __cdecl main(int argc, const char **argv, const char **envp)
{
  printf("Only 'a'-'z','A'-'Z','0'-'9' accepted.\n");
  printf("Only 16 chars accepted.\n");
  printf("Serial:");
  scanf_s("%s", serial, 17);
  check();
  system("PAUSE");
  return 0;
}

函数check伪代码如下：

int check()
{
  signed int v0; // ebx
  signed int v1; // esi
  signed int i; // eax
  int v3; // eax
  char *v4; // ecx
  signed int row; // edi
  char *v6; // eax
  int v7; // esi
  int col1; // ecx
  int col2; // ecx
  int col4; // ecx
  signed int v11; // eax
  _BYTE *v13; // [esp+Ch] [ebp-258h]
  int v14; // [esp+10h] [ebp-254h]
  int v15; // [esp+14h] [ebp-250h]
  char idx[4]; // [esp+18h] [ebp-24Ch]
  int v17; // [esp+1Ch] [ebp-248h]
  char key_table[20][16]; // [esp+20h] [ebp-244h]
  char f_table[16][16]; // [esp+160h] [ebp-104h]

  v0 = 0;
  *(_QWORD *)&f_table[0][0] = 0x10101i64;
  *(_QWORD *)&f_table[0][8] = 0i64;
  *(_QWORD *)&f_table[1][0] = 0x101000001i64;
  *(_QWORD *)&f_table[1][8] = 0i64;
  *(_QWORD *)&f_table[2][0] = 282574488338433i64;
  *(_QWORD *)&f_table[2][8] = 0i64;
  *(_QWORD *)&f_table[3][0] = 0x100010000000100i64;
  *(_QWORD *)&f_table[3][8] = 0i64;
  *(_QWORD *)&f_table[4][0] = 0x1000100000100i64;
  *(_QWORD *)&f_table[4][8] = 0i64;
  *(_QWORD *)&f_table[5][0] = 0x1010000i64;
  *(_QWORD *)&f_table[5][8] = 1i64;
  *(_QWORD *)&f_table[6][0] = 0x100010000i64;
  *(_QWORD *)&f_table[6][8] = 0x100i64;
  *(_QWORD *)&f_table[7][0] = 0x100000001000000i64;
  *(_QWORD *)&f_table[7][8] = 0x10000i64;
  *(_QWORD *)&f_table[8][0] = 0x10000000000i64;
  *(_QWORD *)&f_table[8][8] = 0x100000001i64;
  *(_QWORD *)&f_table[9][0] = 0x1000000000000i64;
  *(_QWORD *)&f_table[9][8] = 0x10001000000i64;
  *(_QWORD *)&f_table[10][0] = 0x100000000000000i64;
  *(_QWORD *)&f_table[10][8] = 0x10100000000i64;
  *(_QWORD *)&f_table[11][0] = 0i64;
  *(_QWORD *)&f_table[11][8] = 0x1000001000100i64;
  *(_QWORD *)&f_table[12][0] = 0i64;
  *(_QWORD *)&f_table[12][8] = 0x1000000010001i64;
  *(_QWORD *)&f_table[13][0] = 0i64;
  *(_QWORD *)&f_table[13][8] = 0x100000000010100i64;
  *(_QWORD *)&f_table[14][0] = 0i64;
  *(_QWORD *)&f_table[14][8] = 0x100000101000000i64;
  *(_QWORD *)&f_table[15][0] = 0i64;
  *(_QWORD *)&f_table[15][8] = 0x101010000000000i64;
  v1 = 0;
  do
  {
    for ( i = 0; ; ++i )
    {
      if ( i >= 64 )
      {
        printf("input error\n");
        system("PAUSE");
        exit(-1);
      }
      if ( table_64[i] == (unsigned __int8)serial[v1] )
        break;
    }
    key_table[0][v1++] = i;
  }
  while ( v1 < 16 );
  printf("\n");
  v3 = 16;
  v17 = 16;
  v15 = 2 - (_DWORD)key_table[1];
  do
  {
    v4 = (char *)key_table + v3;
    v13 = (char *)key_table + v3;
    row = 0;
    do
    {
      v6 = idx;
      v7 = (int)&v4[v15];
      v14 = 4;
      do
      {
        col1 = (v7 - 2) % 16;
        if ( f_table[row][col1] )
          *v6++ = *((_BYTE *)&v14 + col1 + v17);// result_table[16*i][j]
        col2 = (v7 - 1) % 16;
        if ( f_table[row][col2] )
          *v6++ = *((_BYTE *)&v14 + col2 + v17);
        if ( f_table[row][v7 % 16] )
          *v6++ = *((_BYTE *)&v14 + v7 % 16 + v17);
        col4 = (v7 + 1) % 16;
        if ( f_table[row][col4] )
          *v6++ = *((_BYTE *)&v14 + col4 + v17);
        v7 += 4;
        --v14;
      }
      while ( v14 );
      *v13 = v_table[64 * ((unsigned __int8)idx[1] + ((unsigned __int8)idx[0] << 6)) + (unsigned __int8)idx[2]];// v_table[idx[0]][idx[1]][idx[2]]
      ++row;
      v4 = v13++ + 1;
    }
    while ( row < 16 );
    v15 -= 16;
    v3 = v17 + 16;
    v17 = v3;
  }
  while ( v3 < 0x140 );
  v11 = 0;
  do
  {
    if ( (unsigned __int8)key_table[19][v11] != check_str[v11] )
      return printf("serial error\n");
    ++v11;
  }
  while ( v11 < 16 );
  do
    printf("%c", (unsigned __int8)table_64[(unsigned int)(unsigned __int8)key_table[9][v0++] >> 1]);
  while ( v0 < 16 );
  return printf("\n");
}

程序流程是：

输入16字节，记为m
输入m根据64字节的表转换为16字节ascii码不大于64的数据c
每次根据不同的常量作为序号，取c中的三个值，并将其作为坐标查64*64*64的表v_table，进行16次，得到新的c
循环3操作，共18次
最后的c值与常量对比校验，如果校验不通过则打印错误信息并返回
利用第9次的c输出成功信息

校验算法分析

对数据及校验过程分析后，有这么几个发现：

64*64*64的表，所有值都不大于64，且是完全均匀分布的且有规律。这个表是由4096组0-63的排列数组组成，每组数组各不相同，数组内排列及数组间有着某种规律。
成功信息是由中间的结果生成的，也就是说，输入及最后的校验其实是通过成功信息构造的，这才是原本计算的开始。也就是说这个查表替换的算法或者是可逆的，或者是循环的。

想到循环，测试为先，计算前贴下常量值。
64字节的表为：

abcdefghijklmnopqrstuvwxyz+-ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789

16次的取值的序号为：

0,1,2
3,4,0
5,6,0
5,7,1
4,6,1
8,2,3
9,2,4
7,10,3
8,12,5
11,13,6
12,13,7
11,14,9
14,8,10
15,9,10
15,11,12
15,13,14

开始计算，先试初始值为全0。因为完全分布均匀，那应该64轮后循环。

  data = file('vtable.bin','rb').read()
  vdata = [ord(i) for i in data]
  fdata = [0,1,2,   3,4,0,    5,6,0,    5,7,1,    4,6,1,    8,2,3,    9,2,4,     7,10,3,
          8,12,5,   11,13,6,   12,13,7,  11,14,9,  14,8,10,  15,9,10,  15,11,12,  15,13,14]
  cdata = [20, 34, 30, 16, 56, 48, 24, 16, 4, 26, 36, 8, 2, 38, 56, 42] 
  m = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
  c = list(m)
  d = [0 for i in range(16)]
  print '0',c
  for i in range(128):
    for j in xrange(16):
      tmp = c[fdata[3*j]]*4096+c[fdata[3*j+1]]*64+c[fdata[3*j+2]]
      d[j] = vdata[tmp]     
    c = list(d)
    if c == cdata:
      print '%d'%(i+1),c

结果是：

0 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
32 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
64 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
96 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
128 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

竟然32轮就循环了，重点是确实循环了。

将数据换成校验值，这次循环轮数更大了，但是64的倍数：

 0 [20, 34, 30, 16, 56, 48, 24, 16, 4, 26, 36, 8, 2, 38, 56, 42]
448 [20, 34, 30, 16, 56, 48, 24, 16, 4, 26, 36, 8, 2, 38, 56, 42]
896 [20, 34, 30, 16, 56, 48, 24, 16, 4, 26, 36, 8, 2, 38, 56, 42]
1344 [20, 34, 30, 16, 56, 48, 24, 16, 4, 26, 36, 8, 2, 38, 56, 42]
1792 [20, 34, 30, 16, 56, 48, 24, 16, 4, 26, 36, 8, 2, 38, 56, 42]
2240 [20, 34, 30, 16, 56, 48, 24, 16, 4, 26, 36, 8, 2, 38, 56, 42]
2688 [20, 34, 30, 16, 56, 48, 24, 16, 4, 26, 36, 8, 2, 38, 56, 42]
3136 [20, 34, 30, 16, 56, 48, 24, 16, 4, 26, 36, 8, 2, 38, 56, 42]
3584 [20, 34, 30, 16, 56, 48, 24, 16, 4, 26, 36, 8, 2, 38, 56, 42]
4032 [20, 34, 30, 16, 56, 48, 24, 16, 4, 26, 36, 8, 2, 38, 56, 42]

打印循环前数据：

422 [52, 12, 6, 22, 30, 12, 0, 18, 24, 54, 24, 20, 10, 42, 42, 32]
423 [53, 7, 3, 37, 1, 35, 21, 11, 33, 33, 49, 43, 17, 41, 29, 27]
424 [6, 6, 20, 16, 12, 4, 40, 40, 28, 48, 60, 40, 50, 60, 14, 56]
425 [63, 9, 17, 17, 41, 59, 27, 7, 61, 47, 45, 33, 13, 15, 1, 41]
426 [16, 40, 48, 2, 48, 34, 48, 28, 36, 26, 50, 32, 46, 16, 26, 28]
427 [59, 25, 57, 29, 11, 29, 1, 63, 3, 51, 49, 27, 35, 23, 9, 13]
428 [44, 26, 8, 48, 4, 0, 18, 12, 50, 58, 52, 50, 48, 12, 18, 8]
429 [17, 43, 33, 5, 63, 1, 37, 11, 57, 19, 51, 9, 63, 57, 53, 37]
430 [32, 48, 50, 22, 50, 18, 6, 50, 60, 26, 22, 24, 48, 34, 36, 30]
431 [33, 31, 23, 3, 39, 43, 41, 1, 21, 31, 27, 5, 37, 57, 53, 35]
432 [46, 34, 36, 14, 42, 54, 0, 14, 52, 42, 50, 0, 20, 32, 20, 8]
433 [19, 1, 39, 57, 47, 37, 27, 9, 45, 19, 17, 29, 49, 11, 55, 23]
434 [62, 10, 42, 2, 42, 8, 36, 30, 30, 58, 56, 30, 44, 42, 28, 60]
435 [53, 45, 49, 23, 59, 29, 41, 3, 33, 11, 11, 63, 5, 49, 17, 29]
436 [22, 46, 54, 16, 8, 40, 2, 32, 6, 0, 40, 14, 20, 10, 4, 34]
437 [37, 5, 31, 45, 39, 51, 25, 11, 1, 13, 33, 49, 21, 49, 59, 23]
438 [48, 28, 40, 34, 36, 8, 34, 16, 0, 22, 16, 36, 12, 28, 28, 6]
439 [39, 61, 37, 63, 45, 41, 25, 33, 39, 57, 51, 5, 23, 19, 13, 21]
440 [56, 30, 56, 42, 14, 22, 30, 42, 22, 44, 26, 30, 62, 16, 8, 40]
441 [25, 47, 3, 41, 21, 3, 17, 41, 21, 63, 51, 9, 31, 29, 35, 51]
442 [58, 18, 60, 14, 44, 60, 46, 8, 30, 34, 60, 18, 38, 24, 14, 14]
443 [15, 31, 51, 13, 43, 43, 25, 25, 63, 51, 53, 45, 39, 27, 17, 7]
444 [12, 54, 22, 6, 6, 38, 4, 46, 12, 12, 58, 16, 16, 22, 54, 34]
445 [15, 7, 13, 21, 35, 63, 63, 25, 17, 13, 3, 37, 55, 59, 25, 49]
446 [58, 38, 0, 58, 52, 6, 44, 60, 14, 30, 10, 38, 36, 24, 60, 24]
447 [15, 11, 7, 11, 53, 3, 25, 31, 11, 49, 59, 51, 3, 7, 21, 55]
448 [20, 34, 30, 16, 56, 48, 24, 16, 4, 26, 36, 8, 2, 38, 56, 42]
449 [27, 39, 39, 1, 1, 37, 15, 7, 57, 17, 23, 25, 11, 31, 55, 39]

循环轮再往前数19，即429轮，应该就是输入转换的16字节数据了。

[17, 43, 33, 5, 63, 1, 37, 11, 57, 19, 51, 9, 63, 57, 53, 37]

验证如下：

  data = file('vtable.bin','rb').read()
  vdata = [ord(i) for i in data]
  fdata = [0,1,2,   3,4,0,    5,6,0,    5,7,1,    4,6,1,    8,2,3,    9,2,4,     7,10,3,
          8,12,5,   11,13,6,   12,13,7,  11,14,9,  14,8,10,  15,9,10,  15,11,12,  15,13,14]
  cdata = [20, 34, 30, 16, 56, 48, 24, 16, 4, 26, 36, 8, 2, 38, 56, 42] 
  m = [17, 43, 33, 5, 63, 1, 37, 11, 57, 19, 51, 9, 63, 57, 53, 37]
  c = list(m)
  str = string.lowercase+'-+'+string.uppercase+string.digits
  s = ''
  for i in m:
    s += str[i]
  print s  
  d = [0 for i in range(16)]
  print '0',c
  for i in range(19):
    for j in xrange(16):
      tmp = c[fdata[3*j]]*4096+c[fdata[3*j+1]]*64+c[fdata[3*j+2]]
      d[j] = vdata[tmp]     
    c = list(d)
    print '%d'%(i+1),c

输出结果为：

rPFf9bJl3tXj93ZJ
0 [17, 43, 33, 5, 63, 1, 37, 11, 57, 19, 51, 9, 63, 57, 53, 37]
1 [32, 48, 50, 22, 50, 18, 6, 50, 60, 26, 22, 24, 48, 34, 36, 30]
2 [33, 31, 23, 3, 39, 43, 41, 1, 21, 31, 27, 5, 37, 57, 53, 35]
3 [46, 34, 36, 14, 42, 54, 0, 14, 52, 42, 50, 0, 20, 32, 20, 8]
4 [19, 1, 39, 57, 47, 37, 27, 9, 45, 19, 17, 29, 49, 11, 55, 23]
5 [62, 10, 42, 2, 42, 8, 36, 30, 30, 58, 56, 30, 44, 42, 28, 60]
6 [53, 45, 49, 23, 59, 29, 41, 3, 33, 11, 11, 63, 5, 49, 17, 29]
7 [22, 46, 54, 16, 8, 40, 2, 32, 6, 0, 40, 14, 20, 10, 4, 34]
8 [37, 5, 31, 45, 39, 51, 25, 11, 1, 13, 33, 49, 21, 49, 59, 23]
9 [48, 28, 40, 34, 36, 8, 34, 16, 0, 22, 16, 36, 12, 28, 28, 6]
10 [39, 61, 37, 63, 45, 41, 25, 33, 39, 57, 51, 5, 23, 19, 13, 21]
11 [56, 30, 56, 42, 14, 22, 30, 42, 22, 44, 26, 30, 62, 16, 8, 40]
12 [25, 47, 3, 41, 21, 3, 17, 41, 21, 63, 51, 9, 31, 29, 35, 51]
13 [58, 18, 60, 14, 44, 60, 46, 8, 30, 34, 60, 18, 38, 24, 14, 14]
14 [15, 31, 51, 13, 43, 43, 25, 25, 63, 51, 53, 45, 39, 27, 17, 7]
15 [12, 54, 22, 6, 6, 38, 4, 46, 12, 12, 58, 16, 16, 22, 54, 34]
16 [15, 7, 13, 21, 35, 63, 63, 25, 17, 13, 3, 37, 55, 59, 25, 49]
17 [58, 38, 0, 58, 52, 6, 44, 60, 14, 30, 10, 38, 36, 24, 60, 24]
18 [15, 11, 7, 11, 53, 3, 25, 31, 11, 49, 59, 51, 3, 7, 21, 55]
19 [20, 34, 30, 16, 56, 48, 24, 16, 4, 26, 36, 8, 2, 38, 56, 42]

投机取巧的非预期解法。

[培训]二进制漏洞攻防（第3期）；满10人开班；模糊测试与工具使用二次开发；网络协议漏洞挖掘；Linux内核漏洞挖掘与利用；AOSP漏洞挖掘与利用；代码审计。

最后于 2018-6-30 13:59 被poyoten编辑，原因：加转义

收藏・1

点赞・1

打赏

最新回复 (2)
ccfer 雪币： 8188 活跃值： (4243) 能力值： ( LV15，RANK：2459 ) 在线值：发帖 84 回帖 1475 粉丝 103 关注私信	ccfer 16 2018-6-30 16:06 2 楼 0 你这个解法厉害
poyoten 雪币： 13713 活跃值： (2851) 能力值： ( LV15，RANK：2663 ) 在线值：发帖 68 回帖 74 粉丝 35 关注私信	poyoten 22 2018-6-30 16:08 3 楼 0 ccfer 你这个解法厉害见笑
	游客登录 \| 注册方可回帖　回帖　表情雪币赚取及消费高级回复

poyoten

发帖

回帖

2663

RANK

关注

私信

他的文章

[原创]看雪 2022·KCTF 秋季赛第二题盗贼作乱 WP

[原创][看雪.众安 2021 KCTF 秋季赛]第二题迷失丛林 WP

[原创]看雪.深信服 2021 KCTF 春季赛第九题平定战乱 WP

[原创]看雪.深信服 2021 KCTF 春季赛第八题众叛亲离 WP

[原创]看雪.深信服 2021 KCTF 春季赛第六题寻回宝剑 WP

关于我们

联系我们

企业服务

看雪公众号

最新回复 (2)
ccfer 雪币： 8188 活跃值： (4243) 能力值： ( LV15，RANK：2459 ) 在线值：发帖 84 回帖 1475 粉丝 103 关注私信	ccfer 16 2018-6-30 16:06 2 楼 0 你这个解法厉害
poyoten 雪币： 13713 活跃值： (2851) 能力值： ( LV15，RANK：2663 ) 在线值：发帖 68 回帖 74 粉丝 35 关注私信	poyoten 22 2018-6-30 16:08 3 楼 0 ccfer 你这个解法厉害见笑
	游客登录 \| 注册方可回帖　回帖　表情雪币赚取及消费高级回复

[原创]看雪.京东 2018CTF 第七题 密室逃脱 Writeup

程序流程

校验算法分析

[原创]看雪.京东 2018CTF 第七题密室逃脱 Writeup