第十一题 伊甸园

做一半感觉这题质量有点低，不想做了，于是偷了个懒。

观察

题目（又⁴）给出了一个 32 位控制台 Windows 程序，运行一下发现还是经典的输入一个 key 告诉你对不对的题目。

分析

简单看一看会发现程序里面大量用到了 C++，MSVC 的 RTTI 信息暴露了一些类名出来，有 StrCheck、Base62、CTreeNode 等，另外字符串中有一些 pNode->Data().uOperatorIndex pNode->Data().uTagIndex 之类的东西，抛异常的时候用到了，可以作为辅助分析使用。

程序的主要逻辑在 004033B0 这个函数中，看 vtable 和对应的 RTTI 信息可以识别被 inline 进来的一些构造函数。其大致逻辑是：

1. 输入读到一个 std::string，记为 input。
2. 拼出 kB62Const0 + input + kB62Const1 + kB62Const2，其中 kB62Const0、kB62Const1、kB62Const2 是三个作为全局变量初始化的 std::string，要求长度为 17415。
3. 进行所谓的“Base62”解码，要求解码后的长度为 12715。
4. 调用 0040C720 parse 输入解码得到的字符串，得到一棵树表示的东西。
5. 调用 0040B670 对 parse 得到的结果进行某种变换。
6. 调用 00405410 将变换后的树输出成字符串。
7. 和预先定义的答案进行比较。
8. 如果一样，用输入作为 key 解密一个字符串并输出。

StrCheck 是最后解密成功提示的时候用的，暂时不用看。这个所谓的“Base62”，仔细看看会发现其实就是把值超过60的数用 "9A"、"9B"、"9C"、"9D" 来进行表示了，因此直接字符串替换一下就可以当成 base64 编码/解码：

def b62tob64(data):
  return data.replace('9D', '=').replace('9C', '/').replace('9B', '+').replace('9A', '9')

def b64tob62(data):
  return data.replace('9', '9A').replace('+', '9B').replace('/', '9C').replace('=', '9D')

观察最后比较的答案，大概是一个形如这样的东西：

/,-,*,-,-,/,-,*,/,/,/,-,*,*,*,Power_xa,-,Power_ax,58,x,x,33,-,*,Power_ax,58,x,Log,e,58,1,34,Log,/,Power_ax,100,*,*,*,Power_xa,-,Power_xa,*,Log,Power_ax,90,Log,/,

结合 parse 的代码看，似乎就是一棵表达式树的先序遍历（以逗号分隔的），可以简单写几行 Python 代码对应着读进来备用。
树中有三种节点，对应 type 0 到 2，参考题目中的异常错误信息字符串可以确定分别是 Operator、Tag 和 Immediate。其中 Operator 有 +,-,*,/,Log,Power_ax,Power_xa,Sin,Cos，Tag 有 x,e,pi，Immediate 就是个立即数，程序中是用 double 存的，不过给的表达式中都是整数。另外给的表达式中没有 Sin、Cos。

相信敏感的读者看到 Power_ax、Power_xa 竟然有区分这么古怪的事情的时候心中应该已经对那个“变换”是什么有点数了，不过姑且描述一下变换的过程：

1. 对于 Tag，x 替换为立即数 1，其他两种替换为立即数 0。
2. + 和 - 的话本身不变，对两边分别递归进去做变换。
3. * 的话变成 lhs * transform(rhs) + transform(lhs) * rhs 的形式。
4. / 的话变成 (lhs * transform(rhs) - transform(lhs) * rhs) / (rhs ^ 2)。
5. …………没必要继续列了吧

很明显是一个实现十分粗糙的对 x 的符号微分。

到这里检查的条件已经很明显了，就是把一个表达式中间抠掉了一部分，要求填充回去之后对其微分的结果等于给定的结果。由于给出的最终结果没有经过复杂的 simplify，所以我们当然是不用真的求积分的，稍微观察一下可以发现最终结果满足：

1. root 是个 / 的 operator。
2. root 的右操作数是个 Power_xa 的 operator，这里的 a 是整数2。

验证一下可以发现这确实是应用除法定则弄出来的一个结构，直接把其中的 f，g 抠出来，则 f / g 即为原函数。然而我们发现 f / g 的表示远没有 12715 字符这么长。仔细观察一下被扣掉一部分的输入，会发现里面有大量的 Log,x,x 和 *,1,XXX 会在求微分过程中被这个程序给化简掉。因此这样没法直接还原出原始输入。不过简单观察一下（写个程序画成树的形式或者脑补），可以发现这个表达式里面有大量重复的子结构，有点像是本身就是这个程序对某个比较简单的输入重复跑了几次之后的输出，对着观察一下基本能确定被扣掉的部分开头是 pi,75。考虑到被抠掉的部分不长（计算一下可以知道解码后对应 59 个字符），不妨试试被抠的部分是不是在原来的输入串的其他部分也有出现过。

kB62Const0 = ... # 0044DFF0
kB62Const1 = ... # 0044E3F8
kB62Const2 = ... # 00450340

alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789'

encodedlen = 17415 - (len(kB62Const0) + len(kB62Const1) + len(kB62Const2))

def b62tob64(data):
  return data.replace('9D', '=').replace('9C', '/').replace('9B', '+').replace('9A', '9')

def b64tob62(data):
  return data.replace('9', '9A').replace('+', '9B').replace('/', '9C').replace('=', '9D')

part1 = (b62tob64(kB62Const0) + '==').decode('base64')
part2 = (b62tob64(kB62Const1 + kB62Const2)[1:]).decode('base64')
piecelen = 12715 - len(part1) - len(part2)

vis = set()
for i in xrange(1, len(part2)-piecelen+1):
  if part2[i-1] == ',' and part2[i+piecelen-1] == ',':
    piece = part2[i:i+piecelen]
    if piece.startswith('pi,75'):
      processed = b64tob62((part1 + piece + part2[:20]).encode('base64').replace('\n',''))
      assert processed.startswith(kB62Const0)
      processed = processed[len(kB62Const0):]
      assert kB62Const1[:8] in processed
      processed = processed[:processed.rfind(kB62Const1[:8])]
      if len(processed) != encodedlen or processed in vis:
        continue
      vis.add(processed)
      print str(i) + '\t' + piece + '\t' + processed

运行可以得到五个可能的答案：

1072    pi,75,x,+,Power_xa,/,+,*,Power_ax,68,x,x,x,x,2,Log,x,x,Log,     BpLDc1LHgsKyxQb3dlcl9A4YSwvLCssKixQb3dlcl9AheCw2OCx4LHgseCx4LDIsTG9AnLHgseCxMb2c
2003    pi,75,x,x,*,*,Log,x,x,pi,75,+,*,Power_ax,68,x,x,x,99,Log,*,     BpLDc1LHgseCwqLCosTG9AnLHgseCxwaSw3NSwrLCosUG9A3ZXJfYXgsNjgseCx4LHgsOTksTG9AnLCo
2793    pi,75,+,*,Power_ax,68,x,x,x,8,x,/,Power_xa,+,/,Power_ax,44,     BpLDc1LCssKixQb3dlcl9AheCw2OCx4LHgseCw4LHgsLyxQb3dlcl9A4YSwrLC8sUG9A3ZXJfYXgsNDQ
4036    pi,75,+,*,Power_ax,68,x,x,x,x,*,Power_ax,68,x,x,/,Power_xa,     BpLDc1LCssKixQb3dlcl9AheCw2OCx4LHgseCx4LCosUG9A3ZXJfYXgsNjgseCx4LC8sUG9A3ZXJfeGE
10580   pi,75,Log,*,-,Power_ax,23,-,Power_xa,+,Log,Power_ax,90,Log,     BpLDc1LExvZywqLC0sUG9A3ZXJfYXgsMjMsLSxQb3dlcl9A4YSwrLExvZyxQb3dlcl9AheCw5MCxMb2c

都输入原来的程序试一下，对于最后一个，程序输出了：

N:\pediy\11>伊甸园.exe
please input the key
BpLDc1LExvZywqLC0sUG9A3ZXJfYXgsMjMsLSxQb3dlcl9A4YSwrLExvZyxQb3dlcl9AheCw5MCxMb2c
checking the result ...
You solved the calculus encryption problem(._.)
请按任意键继续. . .

看来赌中了，所以这就是答案了。

没仔细看那个求符号微分的代码，我猜可能结合里面的化简对于 *,Log,x,x,XXX 和直接的 XXX 求出来的结果还是不一样的，所以大概还是能正经解的吧。不过最后那个解密成功提示的部分就有点强行避免多解了，没仔细看，前面部分多解的解空间要是足够大的话说不定还是能构造出来多解来着，呵呵。

吐槽

本题质量有点低，不过看了看出题团队的背景，好像也情有可原吧。

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