题解作者：emc2314
出题人、验题人、文案设计等：见 Hackergame 2023 幕后工作人员。
-
题目分类：binary
-
题目分值：C++ 退出逆向界！（300）+ 已经完全看破了吗（350）
2077 年，Hackergame 研究院。
暗中进行多年的最高机密项目，代号：「往日之影」（Phantom Liberty），最近终于取得了重要的阶段性突破。
这项研究的最终目标是将任何 CTF 竞赛的题目全自动归约成一个可供游玩的 FPS RPG 游戏。只要玩家能够在游戏中成功通关，再根据特定算法进行反演，就能获得完整的解题流程。
不幸的是，Hackergame 研究院遭到了以 R****e、M**x 和 4******7 为首的某神秘势力入侵。他们泄露了研究院内部的 HG-0 级别的机要文件，其中包括一些用于验证「往日之影」项目的 SHA3 Benchmark 程序。
而幸运的是，负责保密的研究院暗部早有防备。院内使用的编译器的 pipeline 中加入了一个特殊的优化 Pass，可以将一串字符串作为水印嵌入到二进制文件中。只要能够将泄漏文件中的隐藏信息提取出来，就能追溯到具体的泄漏点。
可是，正是在 Hackergame 研究院面临着前所未有的挑战之际，由于到了 1024 程序猿节，负责这项工作的人员决定奖励自己一个 14 天的小长假。迫于无奈，Hackergame 研究院只能把这些嵌有水印的二进制文件和编译机制公之于众，以 flag 作为悬赏，拜托给了诸位。
按照惯例，若任务中任何参赛选手，被上文中的神秘势力发现或者捕获，Hackergame 研究院将宣称对此行动全不知情。
你可以通过 nc 202.38.93.111 11110 来连接题目，或者点击下面的「打开/下载题目」按钮通过网页终端与远程交互。
如果你不知道
nc是什么，或者在使用上面的命令时遇到了困难，可以参考我们编写的 萌新入门手册：如何使用 nc/ncat？
这道题源于出题人久候新版 IDA leak 而不至的烦恼。目前能搞到的最新版 IDA 是 7.7，之前听说 8.1 的安装包也 leak 出来，但是并没有密码所以也无济于事。Hex-rays 自然知道在程序中无论加入什么反盗版机制都会被破解，所以在分发的二进制中加入了水印信息，使得用户不会轻易自己泄漏自己的程序文件。IDA 使用了何种水印技术不得而知，本题则做出了一个给 binary 嵌入水印的尝试。
一个最直接的想法便是在程序的无关之处嵌入一些无用数据。但是这种做法往往非常明显，只要找到两个不同水印的二进制对比即可轻易去除。所以我们会更希望能够把水印嵌入到具体的程序的代码逻辑中，这样即使被发现也很难完全去除。那么可能很容易想到，我们可以在代码中嵌入一些无用指令，比如 nop 或者 jmp $rip+2 之类的代码。但实际上这和增加额外数据没有本质区别，程序中的这种无用指令也会显得非常突兀。此外，考虑到软件需要支持各种不同的 ISA，我们也希望能有一种 ISA-independent 的方法嵌入信息进去。
于是我们自然而然地把目光转向编译时基于 IR 的各种代码变换规则。当然这会有一个风险，因为很多 IR 级别的信息很难完整地存留在编译结果的二进制文件中，从二进制中想精确还原 IR 也非常困难。这在二进制分析中各种 lifting 算法的复杂实现里可见一斑。即使仅仅只还原 IR 的 CFG 也没法轻易做到。一个例子可能是 LLVM IR 中存在 select 指令，但是编译器会编译成 cmov 还是条件跳转不仅取决于后端 ISA 支持与否，还会因其他的因素而变化，除此之外还有非常常见的 switch 指令也不太容易被妥善处理。
当然我们和完全的反编译不同的是，我们在提取水印时拥有完整的源代码，可以在编译中对比前后的区别。所以我们可以比如通过一个函数是否打开某个优化 pass 来隐藏信息。但是这样的话，单靠穷举所有 pass 的组合来还原一个函数的信息的工作量可能过于庞大，这也和在函数中能够嵌入的信息量大小相冲突，使得这种做法不太容易适用于比较小的程序文件。
在本题中，我们采用了另一种相对没那么 trivial 的途径：通过 Basic Block 的排序来隐写信息。本题的 LLVM Pass 源代码可见于 src/bw.cpp 文件。首先我们通过 constructBW 函数利用一个随机的 base64 表来把输入的字符串转化为一个 vector，在前面加入 5 bit 的长度信息以及 1 bit 的 parity。再根据这 6 个 bit 随机打乱这个 vector。这一部分的代码其实并无太多必要，只是单纯增加一个函数以供枯燥的逆向过程中可以有一个阶段性的成就感。
而后我们会利用康托展开这一方法，将 n 个 basic block 的排列顺序和 0~(n!-1) 之间的数对应起来。我们根据一个函数中 basic block 的大小来确定从 vector 中取走多少个 bit (不超过 128 位所以用 __int128_t 存储），之后再交给 encode 函数将基本块依照 Cantor 展开的结果来进行排列。当然其中有一些细枝末节的处理，可以参看源码详细了解。
那么其实逆向完成后还原起来也非常简单，我们只需要找到二进制中 Basic Block 和源程序编译出 IR 的 basic block 的对应关系，还原出 Cantor 数，再逆向会 MT19937 随机数产生的乱序，就能得到原始水印。不过令人惊讶的是，作出本题的三位选手中竟然只有一位同学把这个过程给自动化处理起来。可能是时间有所不及的缘故，不过设计上本题的自动化处理应当远不如逆向本身困难。
实际的 exp 文件可以看 src/exp.ipynb。其中使用了 Binary Ninja 作为二进制分析框架。其实使用什么框架并不重要，IDA 或者 GHIDRA 甚至 angr 都可以做到类似的事情，因为我们主要分析出 CFG 的结构即可。实际上，我们甚至可以通过 Dynamic Binary Instrumentation 或者 tracing 的方法，在动态执行中将 basic block 的执行顺序存储下来简单对比即可还原 Basic Block 的对应关系。
在出题人的解题脚本中，本来打算尝试 Small Prime Product 的方法来识别基本块对应（在 BinDiff 较早期的论文中提出了这一方法，大致上是把不同种类的指令当成不同的质数，然后将一个基本块的各个质数相乘得到的数就是这个基本块的特征。因为乘法具有交换性，这一方法可以忽略掉指令乱序的前提下快速匹配），但是发现实际效果并不佳，因为在代码中可能有两个汇编完全相同的基本块。所以出题人加入了一个基于 DFS 稍作改动的遍历 CFG 的方法，给每一个 Basic Block 赋予了一个或者多个 depth 信息，作为新的 small prime 乘入，才可以完美匹配。
在随机数 shuffle 还原的问题上，考虑到直接使用 python 复现 std-c++ 的 shuffle 代码的话过于复杂，所以使用 c++ 编译出来一个 librng.so 文件直接通过 ctypes 调用。不过对于能作出本题的选手，这种细节也许确实不足道也吧。