看雪.深信服 2021 KCTF 春季赛第四题英雄救美 WP

试运行

此题是一个控制台程序，随便输入后，没有错误信息提示。

分析

程序的主业务流程全在主函数中，伪代码如下：

printf("\t\t\t看雪CTF大赛\r\n");
printf("\t\t祝愿看雪CTF大赛越办越好\r\n");
printf("Serial: ");
scanf_s("%s", &input, 81);
length = strlen(&input);
if ( length <= 64 && check_group_401240(length, &input, v15) == 1 && check_sudoku_401000(v15, length - 9) == 1 )
{
  _mm_storeu_si128((__m128i *)&hash, (__m128i)0i64);
  memset(&ctx, 0, 0x58u);
  v14 = 0;
  v13 = 0;
  ctx = 0x67452301;
  v10 = 0xEFCDAB89;
  v11 = 0x98BADCFE;
  v12 = 0x10325476;
  md5_update_4014E0((int)&input, (int)&ctx, length);
  md5_final_4015B0((int)&hash, (__m128i *)&ctx);
  subkey_401ED0(v4, (unsigned __int8 *)&hash);
  v8 = (void (*)(void))VirtualAlloc(0, 0x620u, 0x1000u, 0x40u);
  v5 = (__m128i *)v8;
  v6 = 0x62;
  do
  {
    _mm_storeu_si128(v5, _mm_loadu_si128((__m128i *)((char *)v5 + &unk_4181A0 - (_UNKNOWN *)v8)));
    AES_de_4028B0((int)v15, (unsigned __int8 *)v5);
    ++v5;
    --v6;
  }
  while ( v6 );
  v8();
}
return 0;

结构比较简单明了。先大致看了下，if的三个条件应该是校验条件，下面似乎是校验无关。后详细看了下if中的两个函数，才明白：程序的校验实际上是分两部分，一是数独部分，二是AES解密代码并显示出正常的对话框。

函数check_group_401240是将输入通过一个字符表转换成一串0-9的数字。了解了这个，再看函数check_sudoku_401000就很容易明白其功能了：将0-9数字依次填充到9*9矩阵的0值位上，并使用数独的规则进行数独求解成功是否的校验。
本来有长度要求再加上数独校验，就能出唯一解了，就无需后面的部分了。不知道作者是想增加点难度还是出于其它考虑，函数check_group_401240的转换并不能由数独解反算出唯一输入，所以就有了后面的校验部分。

后面部分的校验主要是将原始输入取md5的hash作为密钥，对大小为0x610大小的加密代码进行AES解密，成功解密则调用这部分解密代码，猜测应该是提示输入正确。

具体看下函数check_group_401240，其伪代码如下：

  _mm_storeu_si128((__m128i *)table, _mm_load_si128((const __m128i *)&xmmword_416280));
  pos = 0;
  _mm_storeu_si128((__m128i *)&table[16], _mm_load_si128((const __m128i *)&xmmword_4162A0));
  idx1 = 0;
  v11 = a1;
  v10 = a2;
  out = a3;
  table[80] = 'q';
  _mm_storeu_si128((__m128i *)&table[32], _mm_load_si128((const __m128i *)&xmmword_416270));
  _mm_storeu_si128((__m128i *)&table[48], _mm_load_si128((const __m128i *)&xmmword_416290));
  _mm_storeu_si128((__m128i *)&table[64], _mm_load_si128((const __m128i *)&xmmword_416260));
  if ( a1 <= 0 )
    return 1;
  v5 = 0;
  while ( 1 )
  {
    ch_l = a2[idx1];
    if ( ch_l > 0x30 && ch_l <= 0x39 )
      break;
    idx2 = v5;
    if ( v5 >= 0x51 )
      return 0;
    while ( ch_l != table[idx2] )
    {
      if ( (unsigned int)++idx2 >= 0x51 )
        return 0;
    }
    v9 = idx2 % 9 + 1;
    if ( v9 == -1 )
      return 0;
    *out = v9;
    a2 = v10;
    ++pos;
    ++out;
    a1 = v11;
LABEL_13:
    if ( ++idx1 >= a1 )
      return 1;
  }
  if ( pos + ch_l == 0x39 )
  {
    pos = 0;
    v5 += 9;
    goto LABEL_13;
  }
  return -1;

此函数通过搜索81个元素的字符表，并进行计算后将输入转换成0-9。具体的遍历输入的过程如下：先检查输入字符是否是数字字符，如果是且与某个位置计数相加为0x39，则位置计数清零，字符表查询范围减少9个字符，否则则结束遍历，失败返回。如输入字符不是数字字符，则搜表得到该字符在表中位置值，经过模9加1计算后记录，作为数独的求解结果。这里在求解的时候要猜下作者意图，不然这部分的反解结果就太多了。根据对程序的意图理解，再结合数独的一些知识，可以猜测，输入中的数字字符是为了将输入分成9组，每组对应数独的一行；还可以猜测到，81个元素的字符表也是分成9组，每组9个字符，第i组的输入字符在出现在第i组的字符表中。

求解

已知的数独如下：

0   4   0   7   0   0   0   0   0
9   2   0   0   0   0   6   0   7
8   3   0   0   0   5   4   0   0
0   1   0   0   0   3   0   0   0
0   0   0   2   0   1   0   0   0
0   0   0   5   0   0   0   4   0
0   0   4   9   0   0   0   7   1
3   0   5   0   0   0   0   9   4
0   0   0   0   0   8   0   6   0

为求解数独，随便搜了个在线的求解器，结果如下：

得到55个数字，有了这些数据，再加上上面部分的两个猜测，就可以直接反解输入了。代码如下：

table = "$BPV:ubfYp}]DtN>aT^MGmJQ#*Hr`O'wjic0!hdy{oZz-@n+?&%s_/g<e[W)XUxRFSLRA;.l=CEkvK-(q"
idx = [[5,6,1,9,2,3,8],[1,8,3,4,5],[7,6,2,1,9],
        [7,8,4,6,9,2,5],[4,5,3,9,7,8,6],[6,9,2,8,7,1,3],
        [2,8,5,6,3],[6,1,7,2,8],[1,7,9,3,4,5,2]]
length = 64
l = [0]*length
pos = 0
for i in range(9):
  n = len(idx[i])    
  for j in range(n):
    l[pos+j] = table[i*9+idx[i][j]-1]
 
  l[pos+n] = chr(0x39-n)   
  print chr(0x39-n) , 
  pos += n+1
  print ''.join(l[:pos])
 
print ''.join(l)