Google CTF 2019 quals - Flaggy Bird 详解

阅读量    152720 |   稿费 200

分享到: QQ空间 新浪微博 微信 QQ facebook twitter

 

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

Game

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

Game

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

 

分析

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

APK

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

  • assets 目录下的 level1.bin level2.bin level3.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

函数 a

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

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

又一个函数 a

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

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

  1. 数组需要通过 nativeCheck 函数检验,如果不通过直接返回 null
  2. 数组在 sha256 后的哈希值要与预设值 a 匹配,否则同样返回 null
  3. 如果通过以上两个要求,该数组会作为 AES 的密钥对数组 c 进行解密,返回解密后的字节数组

Checker

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

level3

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

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 层面的分析完毕,根据以上分析,可以得出游戏的验证逻辑如下:

  1. 游戏需要玩到第三关(或者作弊进入)
  2. 在第三关以指定的序列摆放 egg,然后可以触发相应的校验函数
  3. 校验函数会将 egg 的摆放关系转换成一个数组,如果该数组通过 native 函数校验以及 sha256 后的哈希值与预计的相符,则将该数组作为 AES 的密钥解密 flag 关卡的地图文件,进入 flag 关卡,获得 flag。

native 分析

第一步先定位到 library.soJava_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 的数组。然后,该函数会将这个新的数组传入函数 MM 函数执行完成后,该函数会检查数组的最后一个元素是否小于 16,以及变量 c 是否在函数 M 执行过程中被修改为 0。

继续跟进函数 M,通过分析可以发现该函数实质上是一个由小到大排序的 merge sort,但和一般 merge sort 不同的是,该函数要求数组中的元素互不相等,而且每次元素比较的时候,元素的状态要和数组 d 中定义的一致。即 v11 >= v10 时,需要 d[p] == 0;相应的,当 v11 < v10 时,需要有 d[p] == 1

M

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

思路总结

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

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

  1. 形如 [(1,0),(2,0),(0,3),(4,0),...,(0,15)] 的形式,两两相加后得到的新数组是 0-15 的特定组合序列。
  2. 新数组能通过魔改后的 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}

flag

 

参考链接

分享到: QQ空间 新浪微博 微信 QQ facebook twitter
|推荐阅读
|发表评论
|评论列表
加载更多