转载

Google CTF 2019 quals - Flaggy Bird 详解

最近练习的时候做到 Google CTF 2019 quals 的一道题目，在做题的时候也学到了很多，在此记录一下解题经历。

Game

安装 APK 并运行，发现是个玩家控制移动类型的游戏：

很明显移动到旗子处就会进入下一关，初步推测通关可以获得 flag 或者在 flag 隐藏在游戏的某个细节中。本来想直接通过玩游戏来做题的但手残党玩了 20 分钟都没有过第一关2333，该想法放弃。

分析

既然上一个思路失败，那么只能继续分析提供的 apk 文件了。众所周知，apk 实际上是一个 zip 文件，直接用解压缩软件打开：

Google CTF 2019 quals - Flaggy Bird 详解

可以看到有这样几个文件比较引人注意：

assets 目录下的 level1.bin level2.bin level3.bin ，推测可能为关卡相关的地图文件。
lib 目录下的 library.so 文件，应该囊括了应用的 native 部分代码。

其余文件看上去价值不大，所以继续从 java 和 native 两个层面对代码进行分析。

java 类分析

用反编译工具（比如 jadx ）打开 flaggybird.apk 文件，浏览包结构：

Google CTF 2019 quals - Flaggy Bird 详解

可以看到其中 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 ：

Google CTF 2019 quals - Flaggy Bird 详解

这两个函数验证了我们之前的猜想，即 level?.bin 表示的是关卡的地图文件，在通过 InflaterInputStream 读取后会转为游戏的地图数组。

另一个函数 void a() （为什么都是 a 主要是由于万恶的混淆）：

Google CTF 2019 quals - Flaggy Bird 详解

该函数会调用 Checker 类中的校验函数 a ，如果校验通过的话，会将返回的字节流解析为地图文件，由函数 void a(byte[] bArr) 进行解析，游戏进入隐藏关卡（推测可能含有 flag）。

继续看 Checker 类，可以看到该类的逻辑非常简单：

nativeCheck
a
c

Google CTF 2019 quals - Flaggy Bird 详解

为了验证之前理解的代码逻辑，我们可以再玩一次游戏。通过改包，将 level1.bin 的内容替换为 level3.bin 的内容，直接进入第三关：

Google CTF 2019 quals - Flaggy Bird 详解

可以看到第三关多了摆放 egg 的功能，按右边的 X 键，我们可以将某个 egg 放到指定的框中，然后可以在最上方触发相应的校验函数：

Google CTF 2019 quals - Flaggy Bird 详解

随意摆放 egg，然后触发校验函数，得到结果如下图所示， "Close, but no cigar." 和 void a 的输出一致，说明我们理解的逻辑无误：

Google CTF 2019 quals - Flaggy Bird 详解

继续回到 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 。

Google CTF 2019 quals - Flaggy Bird 详解

因此，我们可以得出结论，native 层面的检查实际上要求的是一个长度为 16 的数组，数组是一个 0-15 的特定组合序列，该序列满足魔改后的 merge sort 的条件限制。

思路总结

综合 Java 层面和 native 层面的分析，可以得出以下结论：

我们需要找到一个特定的 egg 摆放顺序，该顺序满足以下要求：

[(1,0),(2,0),(0,3),(4,0),...,(0,15)]

如果找到了这个数组，那么就可以用该数组作为 AES 密钥解密 flag 地图，然后通过改包等方式，我们可以进入 flag 关卡，获得 flag。

solve

首先需要找到一个能够通过魔改后的 merge sort 的合法输入，下面分享两种不同的解法：

第一个思路是通过 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]

思路参考了 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;
}

由于通过 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}

Google CTF 2019 quals - Flaggy Bird 详解