【i春秋】第十届全国大学生信息安全大赛之逆向--填数游戏

skywilling

0x00前言
7月10号早晨8点，第十届全国大学生信息安全大赛正式落下帷幕（7月9号早晨8点正式开始）。大赛期间本着打助攻的心态，用了差不多6小时的时间，终于解出了这道价值200分的题目。再次声明，我只是一个外援，并不是正式的比赛人员。说这是因为，之前有人向我请教打CTF比赛的心得，毕竟不是专业打CTF的，所以心得的参考价值并不是很大。比赛当天上午出了两道逆向题目，一道PE逆向，一道Android逆向，我这里说的就是前者，到了下午，又出了两道，一道PE,一道Linux下的PE(对PE题目类型的划分可能有错误)，可能还有更多的逆向题目，我没办法看到。后续，我会在官方的writeup出来后，陆续将剩下的三个题目的writeup发布（官方的writeup比较简略，较难理解）。下面正式开始这道题目的讲解。
0x01检测
这步其实是可以跳过的，但是为了养成良好的习惯，当我拿到这道题目时，我的第一反应就是，检测一下有没有加壳，有没有使用常见的加密算法，如下图：

很显然无壳无常见加密算法。
0x02运行
接下来，我们需要运行软件来寻找一些特征字符串，方便我们定位到关键代码，如下图：

好吧，一个fail就把我们打发了。
0x03静态分析
首先放到IDA中看一下，

很容易我们就找到了程序的入口，定位到汇编代码

向下执行调用了方法___mingw_CRTStartup，点击进入

这里我们看到了_main，有人会说上面还有一个__main,比前者多了一个下划线，这里不要急，我们用F5神器看一下就知道，谁真谁假了，

很显然了，第二个main才是我们要找的，换句话说，标准的main函数是带参数的，所以就很好分辨了。
其实找到这个main函数还有一个更简单的方法，

直接在Function window中就能看见他了。
我们继续看main函数，下面是F5还原出来的c代码

[C] 纯文本查看 复制代码

int __cdecl main(int argc, const char **argv, const char **envp)
{
  std::string *v4; // [sp-14h] [bp-1B4h]@1
  int (*v5)[9]; // [sp-10h] [bp-1B0h]@1
  int v6; // [sp+0h] [bp-1A0h]@2
  char v7; // [sp+4h] [bp-19Ch]@1
  int v8; // [sp+8h] [bp-198h]@1
  int (__cdecl *v9)(int, int, int, int, _Unwind_Word, _Unwind_Context *); // [sp+1Ch] [bp-184h]@1
  int *v10; // [sp+20h] [bp-180h]@1
  char *v11; // [sp+24h] [bp-17Ch]@1
  void *v12; // [sp+28h] [bp-178h]@1
  std::string **v13; // [sp+2Ch] [bp-174h]@1
  char v14; // [sp+40h] [bp-160h]@1
  int v15; // [sp+184h] [bp-1Ch]@1
  char v16; // [sp+188h] [bp-18h]@1
  int *v17; // [sp+194h] [bp-Ch]@1

  v17 = &argc;
  v9 = __gxx_personality_sj0;
  v10 = dword_47CAB8;
  v11 = &v16;
  v12 = &loc_4015A5;
  v13 = &v4;
  _Unwind_SjLj_Register((SjLj_Function_Context *)&v7);
  __main();
  Sudu::Sudu(&v14);
  Sudu::set_data((int)&v14, (Sudu *)&_data_start__, v5);
  v8 = -1;
  std::string::string(&v15);
  v8 = 1;
  std::operator>><char,std::char_traits<char>,std::allocator<char>>((std::istream::sentry *)&std::cin, &v15);
  if ( (unsigned __int8)set_sudu((Sudu *)&v14, (const std::string *)&v15) ^ 1 )
  {
    std::operator<<<std::char_traits<char>>((std::ostream::sentry *)&std::cout, "fail");
    std::ostream::operator<<(std::endl<char,std::char_traits<char>>);
    v6 = 0;
  }
  else
  {
    if ( Sudu::check((Sudu *)&v14) )
    {
      v8 = 1;
      std::operator<<<std::char_traits<char>>((std::ostream::sentry *)&std::cout, "success");
      std::ostream::operator<<(std::endl<char,std::char_traits<char>>);
    }
    else
    {
      v8 = 1;
      std::operator<<<std::char_traits<char>>((std::ostream::sentry *)&std::cout, "fail");
      std::ostream::operator<<(std::endl<char,std::char_traits<char>>);
    }
    v6 = 0;
  }
  std::string::~string(v4);
  _Unwind_SjLj_Unregister((SjLj_Function_Context *)&v7);
  return v6;
}

到这里，我们就看到了我们想要的东西了，

我们的目的是让程序输出success,好了，明确了目标就好办了，我们开始分析每个条件语句

这是一个嵌套的条件选择语句，我们想要程序执行到我们想要的地方，就必须让第一个条件（划红色下划线）为假，接下来的条件为真才行
分析第一个条件，我们发现，方法set_sudu的返回值与1异或后才进行判断，想要条件为假，就是让方法set_sudu的返回值大于1，这里搞明白后，我们继续看方法set_sudu的实现过程

到这里，我们就需要找一下我们输入的字符串到底是哪个了，我们看到set_sudu方法的参数里面有一个const std::string *a2的参数，这十有八九就是我们输入数据的指针了，不确定的话，可以通过动态调试验证一下。由于这段还原的c代码有点混乱，下面看我还原的c代码：

这样就思路很清晰了，方法参数里面的in就是输入数据的指针，len是数据的长度，后面的a1是一个数组的指针，这里不得不重点说一说这个数组了，因为在我第一次分析的时候就被它坑了，当时认为它是一个变量。这个数组我们需要往前追溯一下了，我们在main函数中可以看到：

这里一共出现了3次，第3次就是我们刚才调用的数组了，所以说，前两次就是一些初始化之类的东西了，我们分别进入看一下：


第一个是申请数组空间，第二个是将_data_start__中的数据填充到数组a1中，填充过程具体是这样的：

第一个参数是待填充的数组指针，第二个是存储填充数据的数组指针，填充后的结果是：

接下来，我们回到set_sudu方法中，

里面又有一个set_number的方法，第一个参数是数组a1，第二个参数是行数，第三个参数是列数，第四个参数是减48之后的数值（0的ASCII码就是48），这个方法的返回值异或1后必须为假，所以这个方法的返回值必须为真。
我们进入set_number方法，看一下实现过程，直接上还原出来的c代码：

首先是判断c是否为0，如果为0，则返回真，否则，行号和列号要大于等于0小于等于8，并且a1数组的对应位置为0，还有c的值需要是非0数字才能返回真，同时将c填充到a1数组的对应位置，到这里，我们可以得出几个结论，第一，我们需要输入的是纯数字，第二，输入的长度是81（9x9)。
到这里，第一个大的条件就满足了。
我们再看第二个条件：

这里调用了check方法，我们进入分析一下，

在这里又调用了check_block,check_col,check_row这三个方法，因为用到了’与’的运算，所以这三个方法的返回值都需要为真，
下面我们逐个分析，

这个是检测块，块又是什么呢？其实就是3x3的矩阵，如图：

这里就是9个3x3的矩阵组成的大矩阵。
仔细分析代码，我们会发现，检测的内容是看是否每个块都由不重复的9个数字组成。

类似的，检测列和行，就是检测每列每行是否都由不重复的9个数字组成。
到这里，我们就可以得到最终的结论了，这其实就是一个数独的题目，初始化后的数组a1就是初始的数据，
这里，我们借助一个在线解数独的工具，得到答案：

最终的flag就是将已知的数替换为0即可。那么这道逆向题目到这里就结束了。
0x04结尾
老规矩，题目和c代码会在文章最后的附件中给出，下面献上成功的截图：

附件：http://pan.baidu.com/s/1skEgT2H 密码: zhde
版权声明：允许转载，但是一定要注明出处。

---

jasonyao

其实这道题很简单，我是直接从内存dump    _data_start__的数据，然后解数独就出来了。为了节约时间没有再去分析，不过楼主的wp写的十分严谨，很不错。

另外求助一下安卓逆向的思路，因为本人初学安卓逆向，应该那道题是加了壳把，望楼主多多指教，不胜感激

429338728

这次比赛我也参加了，可惜就是最后一道逆向题没做出来，我记得那道题的第一步求逆的01矩阵爆破出来后，我就没思路，不知道怎么对接下来的算法进行求逆了，唉。无缘决赛，你那一道题解出来了吗，我们可以探讨一下。

360573078

66666学到很多~谢谢!

夏雨微凉

紧跟大神的脚步~            

SharsDela

看不懂啊，只能膜拜~

大萌黑

膜拜大牛，还有很多路要走啊

我想破解

虽然不懂，但是简略了看了一下，慢慢学习

御剑行

题目吗？厉害

PJGeek

有逻辑~~~但是不会

jun57663796

虽然看不懂，还是支持下。

王美君

紧跟慢跟就是跟不上，基础就差，哎