最近练习的时候做到 Google CTF 2019 quals 的一道题目，在做题的时候也学到了很多，在此记录一下解题经历。
Game
安装 APK 并运行，发现是个玩家控制移动类型的游戏：
很明显移动到旗子处就会进入下一关，初步推测通关可以获得 flag 或者在 flag 隐藏在游戏的某个细节中。本来想直接通过玩游戏来做题的但手残党玩了 20 分钟都没有过第一关2333，该想法放弃。
分析
既然上一个思路失败，那么只能继续分析提供的 apk 文件了。众所周知，apk 实际上是一个 zip 文件，直接用解压缩软件打开：
可以看到有这样几个文件比较引人注意：
-
assets目录下的level1.binlevel2.binlevel3.bin，推测可能为关卡相关的地图文件。 -
lib目录下的library.so文件，应该囊括了应用的 native 部分代码。
其余文件看上去价值不大，所以继续从 java 和 native 两个层面对代码进行分析。
java 类分析
用反编译工具（比如 jadx）打开 flaggybird.apk 文件，浏览包结构：
可以看到其中 com.badlogic.gdx 很明显是游戏的第三方库，发现来自 https://github.com/libgdx/libgdx， 和之对应的是 lib 下的 libgdx.so 文件，那么这部分必然不是我们关心的重点，重点必然在 google.ctf.game 这个包中。
简单梳理一下该包中的几个类：
-
AndroidLauncher– AndroudManifest.xml 中定义的应用入口 -
Checker– flag check 相关类 -
a– 绘制游戏背景scenery.png -
b– 绘制代表用户的bird.png -
c– 游戏变量定义 -
d– 地图渲染 -
e– 游戏控制类，以及会主动加载库文件library.so -
f– 解析地图文件，触发 flag 检查函数 -
g– 逻辑判断 -
h– 接口定义 -
i– UI 相关
其中有几个函数值得特别关注：
类 f 中的几个函数 a：
这两个函数验证了我们之前的猜想，即 level?.bin 表示的是关卡的地图文件，在通过 InflaterInputStream 读取后会转为游戏的地图数组。
另一个函数 void a()（为什么都是 a 主要是由于万恶的混淆）：
该函数会调用 Checker 类中的校验函数 a，如果校验通过的话，会将返回的字节流解析为地图文件，由函数 void a(byte[] bArr) 进行解析，游戏进入隐藏关卡（推测可能含有 flag）。
继续看 Checker 类，可以看到该类的逻辑非常简单：
- 数组需要通过
nativeCheck函数检验，如果不通过直接返回 null - 数组在 sha256 后的哈希值要与预设值
a匹配，否则同样返回 null - 如果通过以上两个要求，该数组会作为 AES 的密钥对数组
c进行解密，返回解密后的字节数组
为了验证之前理解的代码逻辑，我们可以再玩一次游戏。通过改包，将 level1.bin 的内容替换为 level3.bin 的内容，直接进入第三关：
可以看到第三关多了摆放 egg 的功能，按右边的 X 键，我们可以将某个 egg 放到指定的框中，然后可以在最上方触发相应的校验函数：
随意摆放 egg，然后触发校验函数，得到结果如下图所示，"Close, but no cigar." 和 void a 的输出一致，说明我们理解的逻辑无误：
继续回到 Java 代码，我们现在需要确认的是摆放 egg 的函数逻辑，可以在类 f 找到如下代码：
public void a(int i2, int i3) {
this.l[i2] = a[i3];
int i4 = -1;
for (int i5 = 0; i5 < this.m.size(); i5++) {
if (((Integer) this.m.get(i5)).intValue() == i2) {
if (i3 == 0) {
i4 = i5;
} else {
return;
}
}
}
if (i4 != -1) {
this.m.remove(i4);
}
if (i3 != 0) {
this.m.add(Integer.valueOf(i2));
if (this.m.size() > 15) {
this.l[((Integer) this.m.remove(0)).intValue()] = a.EGG_0;
}
}
}
简单解释下该函数的作用就是，确保总共 32 个可以放置 egg 的 holder 中，最多仅有 15 个能被设置成非 0 值。
至此，Java 层面的分析完毕，根据以上分析，可以得出游戏的验证逻辑如下：
- 游戏需要玩到第三关（或者作弊进入）
- 在第三关以指定的序列摆放 egg，然后可以触发相应的校验函数
- 校验函数会将 egg 的摆放关系转换成一个数组，如果该数组通过 native 函数校验以及 sha256 后的哈希值与预计的相符，则将该数组作为 AES 的密钥解密 flag 关卡的地图文件，进入 flag 关卡，获得 flag。
native 分析
第一步先定位到 library.so 的 Java_com_google_ctf_game_Checker_nativeCheck 函数，可以看到该函数先检查了数组长度是否为 32（这符合了之前 Java 代码中的定义，共有 32 个 holder 可以放 egg），之后将数组传入了函数 C:
int __fastcall Java_com_google_ctf_game_Checker_nativeCheck(JNIEnv *a1, int a2, int a3)
{
JNIEnv *v3; // r5
void *v4; // r4
jbyte *v5; // r0
int v7; // [sp+0h] [bp-30h]
v3 = a1;
v4 = (void *)a3;
if ( (*a1)->GetArrayLength(a1, (jarray)a3) != 32 )
return 0;
v5 = (*v3)->GetByteArrayElements(v3, v4, 0);
_aeabi_memcpy(&v7, v5, 32);
return C((char *)&v7);
}
下一步继续看函数 C:
int __fastcall C(char *a1)
{
int v1; // r1
signed int v2; // r4
int result; // r0
char v4[16]; // [sp+4h] [bp-1Ch]
int v5; // [sp+14h] [bp-Ch]
v1 = 0;
do
{
v4[v1] = a1[2 * v1] + a1[2 * v1 + 1];
++v1;
}
while ( v1 != 16 );
v2 = 0;
p = 0;
c = 1;
M(v4, 16);
if ( (unsigned __int8)v4[15] < 0x10u )
v2 = 1;
result = c != 0;
if ( _stack_chk_guard == v5 )
result &= v2;
return result;
}
可以看到该函数首先会将数组中的元素两两相加，将一个长度为 32 的数组转为长度为 16 的数组。然后，该函数会将这个新的数组传入函数 M，M 函数执行完成后，该函数会检查数组的最后一个元素是否小于 16，以及变量 c 是否在函数 M 执行过程中被修改为 0。
继续跟进函数 M，通过分析可以发现该函数实质上是一个由小到大排序的 merge sort，但和一般 merge sort 不同的是，该函数要求数组中的元素互不相等，而且每次元素比较的时候，元素的状态要和数组 d 中定义的一致。即 v11 >= v10 时，需要 d[p] == 0；相应的，当 v11 < v10 时，需要有 d[p] == 1。
因此，我们可以得出结论，native 层面的检查实际上要求的是一个长度为 16 的数组，数组是一个 0-15 的特定组合序列，该序列满足魔改后的 merge sort 的条件限制。
思路总结
综合 Java 层面和 native 层面的分析，可以得出以下结论：
我们需要找到一个特定的 egg 摆放顺序，该顺序满足以下要求：
- 形如
[(1,0),(2,0),(0,3),(4,0),...,(0,15)]的形式，两两相加后得到的新数组是 0-15 的特定组合序列。 - 新数组能通过魔改后的 merge sort 的校验
如果找到了这个数组，那么就可以用该数组作为 AES 密钥解密 flag 地图，然后通过改包等方式，我们可以进入 flag 关卡，获得 flag。
solve
native
首先需要找到一个能够通过魔改后的 merge sort 的合法输入，下面分享两种不同的解法：
解法 1
第一个思路是通过 ida 导出的 C 文件，修改后编译得到二进制文件，然后通过 angr 的符号执行，找到符合约束的合法输入：
// solve.c
#include <stdio.h>
#include <string.h>
int M(char *a1, int n);
int d[45] = {0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0};
int c = 1;
int p = 0;
int M(char *a1, int size) {
char *v2; // r11
unsigned int v3; // r10
signed int v4; // r9
char *v5; // r6
int v6; // r3
int v7; // r4
int v8; // r5
signed int v9; // r8
unsigned int v10; // r2
unsigned int v11; // r1
char v12; // r1
char v14[16]; // [sp+18h] [bp-30h]
int v15; // [sp+28h] [bp-20h]
v2 = a1;
v3 = size;
if ( size < 2 )
return 0;
v4 = (unsigned int)size >> 1;
M(a1, (unsigned int)size >> 1);
if ( !c )
return 0;
v5 = &v2[v3 >> 1];
M(&v2[v3 >> 1], v3 - (v3 >> 1));
if ( !c )
return 0;
v6 = v3 - (v3 >> 1);
if ( (signed int)(v3 - (v3 >> 1)) >= 1 )
{
v7 = 0;
v8 = 0;
v9 = 0;
while ( 1 )
{
v10 = v5[v8];
v11 = v2[v9];
if ( v11 >= v10 )
{
if ( v11 <= v10 || d[p] )
{
LABEL_21:
c = 0;
return 0;
}
++p;
v12 = v5[v8++];
}
else
{
if ( d[p] != 1 )
goto LABEL_21;
v6 = v3 - (v3 >> 1);
++p;
v12 = v2[v9++];
}
v14[v7++] = v12;
if ( v9 >= v4 || v8 >= v6 )
goto LABEL_16;
}
}
v9 = 0;
v8 = 0;
v7 = 0;
LABEL_16:
if ( v4 > v9 )
{
memcpy(&v14[v7], &v2[v9], v4 - v9);
v6 = v3 - (v3 >> 1);
v7 = v7 + v4 - v9;
}
if ( v8 < v6 )
memcpy(&v14[v7], &v2[v8 + v4], v3 - v8 - v4);
memcpy(v2, v14, v3);
return 0;
}
int main(int argc, char *argv[]) {
char buf[16];
read(0, buf, 16);
M(buf, 16);
if(c) {
printf("bingo!");
}
return 0;
}
# solve.py
import angr
import claripy
if __name__ == '__main__':
p = angr.Project('./a.out', load_options={'auto_load_libs': False})
sym = claripy.BVS('x', 16 * 8)
state = p.factory.entry_state(args=[p.filename], stdin=sym)
state.add_constraints(sym.get_byte(15) < 16)
for i in range(15):
state.add_constraints(sym.get_byte(i) < 30)
state.add_constraints(sum([sym.get_byte(x) for x in range(16)]) == 120)
ex = p.factory.simulation_manager(state)
ex.explore(find=lambda s: b"bingo" in s.posix.dumps(1))
f = ex.found[0].solver.eval(sym, cast_to=bytes)
print(list(f))
运行命令如下：
$ gcc solve.c
$ python solve.py
# [9, 8, 7, 2, 11, 15, 13, 10, 6, 5, 14, 4, 3, 0, 12, 1]
解法 2
思路参考了 empirectf 的思路和 jinmo 的 python 代码，简单说就是模拟 merge sort 的执行然后在每次执行失败时交换两个元素的位置，不断地调整最终得到可以通过的输入：
The method is to simply perform the merge sort just like the program. If a comparison fails, swap the two problematic elements around, then restart the sort. Repeat until the array is sorted completely without failing any of the comparison checks.
#include <stdio.h>
#include <string.h>
void swap(char *a, char *b);
int M(char *arr, int n);
int d[45] = {0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0};
int c = 1;
int p = 0;
void swap(char *a, char *b) {
char tmp = *a;
*a = *b;
*b = tmp;
}
int M(char *arr, int size) {
char *v2; // r11
signed int halfSize; // r9
char *v5; // r6
int v6; // r3
int v7; // r4
int v8; // r5
signed int v9; // r8
unsigned int v10; // r2
unsigned int v11; // r1
char v12; // r1
char v14[16]; // [sp+18h] [bp-30h]
int v15; // [sp+28h] [bp-20h]
v2 = arr;
if ( size < 2 || c == 0)
return 0;
halfSize = (unsigned int)size >> 1;
M(arr, halfSize);
if ( !c )
return 0;
v5 = &v2[halfSize];
M(&v2[halfSize], size - (halfSize));
if ( !c )
return 0;
v6 = size - (halfSize);
if ( (signed int)(size - (halfSize)) >= 1 )
{
v7 = 0;
v8 = 0;
v9 = 0;
while ( 1 )
{
v10 = v5[v8];
v11 = v2[v9];
if ( v11 >= v10 )
{
if ( v11 <= v10 || d[p] )
{
LABEL_21:
swap(&v5[v8], &v2[v9]);
c = 0;
return 0;
}
++p;
v12 = v5[v8++];
}
else
{
if ( d[p] != 1 )
goto LABEL_21;
v6 = size - (halfSize);
++p;
v12 = v2[v9++];
}
v14[v7++] = v12;
if ( v9 >= halfSize || v8 >= v6 )
goto LABEL_16;
}
}
v9 = 0;
v8 = 0;
v7 = 0;
LABEL_16:
if ( halfSize > v9 )
{
memcpy(&v14[v7], &v2[v9], halfSize - v9);
v6 = size - (halfSize);
v7 = v7 + halfSize - v9;
}
if ( v8 < v6 )
memcpy(&v14[v7], &v2[v8 + halfSize], size - v8 - halfSize);
memcpy(v2, v14, size);
return 0;
}
int main(int argc, char *argv[]) {
char buf[16];
char prev_buf[16];
for(int i = 0;i < 16; i++) {
buf[i] = i;
}
int cnt = 0;
do {
c = 1;
p = 0;
memcpy(prev_buf, buf, 16);
M(buf, 16);
} while (c == 0); // 不断地调整输入，直到某次 merge sort 后 c 仍为 1
for(int i=0;i<16;i++) {
printf("%02x ", prev_buf[i]);
}
printf("n");
return 0;
}
Java
由于通过 native 函数反推出的数组是并不是原始数组，所以需要利用给定的 sha256 值推断真正的合法输入，然后使用原始的输入作为密钥，通过 AES 解密函数即可获得藏有 flag 的关卡文件：
#!/usr/bin/env python
# -*- coding:utf-8 -*-
from Crypto.Cipher import AES
from itertools import product
from hashlib import sha256
a = [46, 50, 92, -111, -55, 20, 120, -77, 92, 46, 12, -74, 91, 120, 81, -58, -6, -104, -123, 90, 119, -61, -65, -45, -16, 8, 64, -68, -103, -84, -30, 107]
b = [-30, 1, 9, -29, -92,104, -52, -82, 42, -116, 1, -58, 92, -56, -25, 62]
c = [-113, -47, -15, 105, -18, 14, -118, 122, 103, 93, 120, 70, -36, -82, 109, 113, 36, -127, 19, -35, -68, 21, -20, -69, 7, 94, -115, 58, -105, -10, -77, -62, 106, 86, -44, -24, -46, 112, 37, 3, -34, -51, -35, 90, -93, -59, 12, -35, 125, -33, -6, -109, -100, 25, 127, 126, -81, -73, -50, -61, 84, 32, 127, -126, -81, -20, -116, -82, 38, 119, 27, 7, 122, -2, -30, 58, 98, -17, 66, -103, 116, -83, -36, 106, 121, -23, -40, 125, -27, -37, -95, -59, -70, 61, 71, 43, -55, -22, -8, -72, 50, -19, -77, 37, 78, -37, 126, 119, 31, -37, 70, 41, 64, -97, -28, 68, -14, -41, -17, -94, 3, 2, 31, -85, -86, 84, -34, -58, 115, -14, 87, 62, 52, 103, -28, -89, 3, 104, 19, 61, -7, -53, -15, 28, -108, -85, -106, 3, -77, -11, 37, -65, -107, -61, 53, -3, -68, 105, -101, -118, -44, 69, -63, -81, -57, 74, -86, 76, 27, -58, 91, 64, 60, -86, 3, 5, -108, -44, 77, -80, 50, 119, 109, 107, -43, -93, -87, -42, 32, 66, 27, -64, 38, -44, 50, -108, -21, -70, -102, -63, -120, 118, 7, 89, -106, 66, -3, -10, 93, -9, 3, 13, 35, 37, -19, 116, 47, 29, 91, -30, 69, -49, 109, 72, 6, 36, 58, -63, 107, 48, 70, 127, -127, 51, -110, 48, -73, -62, -118, 59, -27, 30, -109, -42, -109, -54, -22, 95, 123, -89, -62, -99, -62, 66, 60, 126, -52, -117, -98, -95, 2, -93, -93, -30, 85, -113, -77, -60, -83, -4, -50, 52, 113, 62, -104, -124, 56, 89, -62, 108, 35, -10, 90, -42, -26, 114, 11, -49, -18, 56, -60, -87, -118, -106, -76, -103, -53, -7, -54, -70, -120, -92, -29, -17, -106, 80, -3, -18, -44, 115, -31, 57, -57, 60, 94, -6, 18, -56, -27, -17]
a = [i&0xff for i in a]
b = [i&0xff for i in b]
c = [i&0xff for i in c]
digest = ''.join(map(chr,a))
final_input = [9, 8, 7, 2, 11, 15, 13, 10, 6, 5, 14, 4, 3, 0, 12, 1]
posses = product(*[set([(0,i),(i,0)]) for i in final_input])
actual_input = None
# crack
for poss in list(posses):
poss_input = ''.join([chr(i)+chr(j) for i,j in poss])
if sha256(poss_input).digest() == digest:
actual_input = poss_input
break
assert(actual_input != None)
# AES
key = actual_input
iv = ''.join(map(chr,b))
encrypt_data = ''.join(map(chr, c))
data = AES.new(key, AES.MODE_CBC, IV=iv).decrypt(encrypt_data)
with open('./flag.bin', 'w') as f:
f.write(data[:-ord(data[-1]):]) # mov padding bytes
此时生成的 flag.bin 文件即我们的输入验证通过后会加载的地图文件，通过手动改包的方式，将其替换为 level1.bin ，即可直接进入 flag 关卡获得 flag：CTF{Up_d0WN_TAp_TAp_TAp_tHe_b1rd_g0Es_flaG_flaG_flaG}
