2019-googlectf-writeup-part1

7月某天兴起玩了一下googlectf,发现很有意思。不过最后一个也没做出来,都是赛后重新学的。这里把wp放出来和大家分享一哈。
_PS:整个wp太长了,所以就分成两部分了

2019 GoogleCTF part1

Rev

Malvertising

这个题目本意是模拟了恶意广告(那种覆盖页面,点击后会跳转的广告),然后顺着混淆的js脚本找到源头,所以和Reverse相关,但是全部都是发生在Web段。。。

Stage1

题目是一个urlhttps://malvertising.web.ctfcompetition.com

随便点击之后就会跳转到google.com上。对当前界面的代码进行审计,可以看到如下关键代码:

1
2
3
4
5
6
7
<script>
function click() {
window.top.location.href = "http://www.google.com";
}
document.addEventListener("click", click)
</script>
<script id="adjs" src="./src/metrics.js" type="text/javascript"></script>

这个地方尝试加载了一个js脚本,于是去资源中找到这个脚本,不过基本上是看不懂的。。。用Chrome自带的格式化工具处理一下后,找到关键代码:

1
2
3
4
5
6
7
8
9
10
11
12
// 省略前面一大段
var s = b('0x16', '%RuL');
var t = document[b('0x17', 'jAUm')](b('0x18', '3hyK'));
t[b('0x19', 'F#*Z')] = function() {
try {
var u = steg[b('0x1a', 'OfTH')](t);
} catch (v) {}
if (Number(/\x61\x6e\x64\x72\x6f\x69\x64/i[b('0x1b', 'JQ&l')](navigator[b('0x1c', 'IfD@')]))) {
s[s][s](u)();
}
}
;

结合之前的逻辑分析,会发现函数b被反复的调用。并且动态调试后注意到,这个函数会对一些加密的内容进行解密,于是动态跟踪程序,在如下的位置下断点:

可以发现,这个地方解开了一段加载js的代码。然后在如下的位置:

1
2
3
if (Number(/\x61\x6e\x64\x72\x6f\x69\x64/i[b('0x1b', 'JQ&l')](navigator[b('0x1c', 'IfD@')]))) {
s[s][s](u)();
}

对加载的逻辑进行了判断。这个地方利用了js的各种特性,编码的部分扔到console里面可以得到如下结果:

1
2
'/\x61\x6e\x64\x72\x6f\x69\x64/i'
"/android/i"

直译过来就是

1
if (Number(/android/i["test"](navigator["userAgent"])))

正则后面跟着["test"],就是利用js的特性,其实本质上是调用了/android/i.test的正则匹配。这里的意思相当于说:读出当前浏览器的userAgent,并且检测其中是否包含Android字样。为了解决这个问题,可以利用Chrome的Toggle Device Bar模拟切换浏览设备,如下:

这样就会进入第二个js文件

Stage2

第二个js文件的内容如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
// 省略一些不必要的内容
var T = {};
T.d0 = function(a, b) {
var c, d;
return a = String(a),
b = String(b),
0 == a.length ? '' : (c = T.f0(a.b1()),
d = T.f0(b.u0().slice(0, 16)),
c.length,
c = T.d1(c, d),
a = T.longsToStr(c),
a = a.replace(/\0+$/, ''),
a.u1())
}
,
T.d1 = function(a, b) {
for (var c, d, e, f = a.length, g = a[f - 1], h = a[0], i = 2654435769, j = Math.floor(6 + 52 / f), k = j * i; 0 != k; ) {
for (d = 3 & k >>> 2,
e = f - 1; e >= 0; e--)
g = a[e > 0 ? e - 1 : f - 1],
c = (g >>> 5 ^ h << 2) + (h >>> 3 ^ g << 4) ^ (k ^ h) + (b[3 & e ^ d] ^ g),
h = a[e] -= c;
k -= i
}
return a
}
,
T.f0 = function(a) {
var b, c = new Array(Math.ceil(a.length / 4));
for (b = 0; b < c.length; b++)
c[b] = a.charCodeAt(4 * b) + (a.charCodeAt(4 * b + 1) << 8) + (a.charCodeAt(4 * b + 2) << 16) + (a.charCodeAt(4 * b + 3) << 24);
return c
}
,
T.longsToStr = function(a) {
var b, c = new Array(a.length);
for (b = 0; b < a.length; b++)
c[b] = String.fromCharCode(255 & a[b], 255 & a[b] >>> 8, 255 & a[b] >>> 16, 255 & a[b] >>> 24);
return c.join('')
}
,
'undefined' == typeof String.prototype.u0 && (String.prototype.u0 = function() {
return unescape(encodeURIComponent(this))
}
),
'undefined' == typeof String.prototype.u1 && (String.prototype.u1 = function() {
try {
return decodeURIComponent(escape(this))
} catch (a) {
return this
}
}
),
'undefined' == typeof String.prototype.b0 && (String.prototype.b0 = function() {
if ('undefined' != typeof btoa)
return btoa(this);
if ('undefined' != typeof Buffer)
return new Buffer(this,'utf8').toString('base64');
throw new Error('err')
}
),
'undefined' == typeof String.prototype.b1 && (String.prototype.b1 = function() {
if ('undefined' != typeof atob)
return atob(this);
if ('undefined' != typeof Buffer)
return new Buffer(this,'base64').toString('utf8');
throw new Error('err')
}
),
'undefined' != typeof module && module.exports && (module.exports = T),
'function' == typeof define && define.amd && define([''], function() {
return T
});
function dJw() {
try {
return navigator.platform.toUpperCase().substr(0, 5) + //WIN32
Number(/android/i.test(navigator.userAgent)) + //1(sure, because we use this enter)
Number(/AdsBot/i.test(navigator.userAgent)) + //0,1
Number(/Google/i.test(navigator.userAgent)) + //0,1
Number(/geoedge/i.test(navigator.userAgent)) + //0,1
Number(/tmt/i.test(navigator.userAgent)) + //0,1
navigator.language.toUpperCase().substr(0, 2) + //many....(ZH,EN,FR,EN,DE,JP)
Number(/tpc.googlesyndication.com/i.test(document.referrer) || /doubleclick.net/i.test(document.referrer)) + //0,1
Number(/geoedge/i.test(document.referrer)) + //0,1
Number(/tmt/i.test(document.referrer)) + //0,1(以上三者互斥)
performance.navigation.type + // (0,1,2,255)
performance.navigation.redirectCount + // 0,1
Number(navigator.cookieEnabled) + // true
Number(navigator.onLine) + // true
navigator.appCodeName.toUpperCase().substr(0, 7) + // MOZILLA
Number(navigator.maxTouchPoints > 0) + // 0,1
Number((undefined == window.chrome) ? true : (undefined == window.chrome.app)) + //0,1
navigator.plugins.length //0,1,2,3
} catch (e) {
return 'err'
}
}
;a = "A2xcVTrDuF+EqdD8VibVZIWY2k334hwWPsIzgPgmHSapj+zeDlPqH/RHlpVCitdlxQQfzOjO01xCW/6TNqkciPRbOZsizdYNf5eEOgghG0YhmIplCBLhGdxmnvsIT/69I08I/ZvIxkWyufhLayTDzFeGZlPQfjqtY8Wr59Lkw/JggztpJYPWng=="
// "WIN3210000ZH0000011MOZILLA100"
eval(T.d0(a, dJw()));

这个地方会检测一大堆的属性,并且检测我们当前的浏览器是否符合这些属性,然后用这个属性组合的密钥对一段密文进行解密。这个地方比较头疼,需要一个爆破逻辑。。。不过有几个地方可以限制一下爆破的范围:

  • 前文我们是通过修改成Android的操作系统,那么这个时候platform就是Linux
  • 测试发现,有几位数是不生效的

然而因为编码问题,以为是上述思维有错,最后写了一个完全爆破脚本。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
function main_func(){
s15 = ""
for(i = 0;i <3; i ++){
var platform = ["ANDRO", 'LINUX','WIN32']
s1 = platform[i]
for(j = 1; j < 2; j++){//Number(/android/i.test(navigator.userAgent))
s2 = s1 + j
for(k=0; k < 2; k++){//Number(/AdsBot/i.test(navigator.userAgent))
s3 = s2 + k
console.log("Now s15 is " + s15)
for(l = 0; l < 2; l++){//Number(/Google/i.test(navigator.userAgent))
s4 = s3 + l;
for(m = 0; m < 2; m++){//Number(/geoedge/i.test(navigator.userAgent))
s5 = s4 + m
for(n = 0; n < 2; n++){//Number(/tmt/i.test(navigator.userAgent))
s6 = s5 + n
for(o = 0; o < 6; o++){//navigator.language.toUpperCase().substr(0, 2)
var lan = ["ZH","EN","FR","EN","DE","JP"]
s7 = s6 + lan[o]
for(p = 0; p < 2; p++){//Number(/tpc.googlesyndication.com/i.test(document.referrer) || /doubleclick.net/i.test(document.referrer))
s8 = s7 + p
for(q = 0; q < 2; q++){//Number(/geoedge/i.test(document.referrer)){
s9 = s8 +q
for(r = 0; r < 2; r++){//Number(/tmt/i.test(document.referrer))
s10 = s9 + r
for(s = 0; s < 4; s++){//performance.navigation.type
var types=[0,1,2,255]
s11 = s10 + types[s]
for(t = 0; t < 2; t++){//performance.navigation.redirectCount
s12 = s11 + t
s12 = s12 + 0 + 0 + "MOZILLA"
for(u = 0; u < 2; u++){//Number(navigator.maxTouchPoints > 0)
s13 = s12 +u
for(v = 0; v < 2; v++){//Number((undefined == window.chrome) ? true : (undefined == window.chrome.app))
s14 = s13 + v
for(w = 0; w < 4; w++){//navigator.plugins.length
s15 = s14 + w
try {
// console.log(s15)
// if(s15 == "LINUX10000FR1000000MOZILLA000"){
console.log(T.d0(a, s15).toString("utf8"));
console.log("\nand now the answer is :\n")
// console.log(T.d0(a, "LINUX11000FR1000000MOZILLA000"))
console.log(eval(T.d0(a, s15)).toString())
// }
// console.log("success")
// return
} catch (error) {
console.log(error)
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}

但是最后还是爆不出答案…..结果知道比赛结束都没能做出来。之后仔细检查了逻辑,发现其实是比赛给的btoa实现有问题!https://github.com/EmpireCTF/empirectf/tree/master/writeups/2019-06-22-Google-CTF-Quals#140-reversing–malvertising。我重新用npm下载了一个数据包,然后再次爆破,终于能够找到可见字符:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
and now the answer is :

ReferenceError: document is not defined
at eval (eval at main_func (D:\Daily\Competition\Google\2019\Reverse\Youtube_files\burce.js:157:85), <anonymous>:1:11)
at main_func (D:\Daily\Competition\Google\2019\Reverse\Youtube_files\burce.js:157:85)
at Object.<anonymous> (D:\Daily\Competition\Google\2019\Reverse\Youtube_files\burce.js:188:1)
at Module._compile (internal/modules/cjs/loader.js:776:30)
at Object.Module._extensions..js (internal/modules/cjs/loader.js:787:10)
at Module.load (internal/modules/cjs/loader.js:653:32)
at tryModuleLoad (internal/modules/cjs/loader.js:593:12)
at Function.Module._load (internal/modules/cjs/loader.js:585:3)
at Function.Module.runMain (internal/modules/cjs/loader.js:829:12)
at startup (internal/bootstrap/node.js:283:19)

var dJs = document.createElement('script'); dJs.setAttribute('src','./src/npoTHyBXnpZWgLorNrYc.js'); document.head.appendChild(dJs);

于是赶紧去找到了这个文件

Stage3

这个文件里面也使用了和Stage1中类似的算法,并且这一次上了反调试,如果使用调试器的话,会陷入一个死循环中出不来,而直接运行脚本,又会有如下的错误(我看网上的wp似乎没遇到这个问题。。)

考虑到隐藏的内容可能包含了答案,于是简单逆向,找到了加密算法_0x5877,并且写了一个小jio本把里面所有调用的函数都捞了出来:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
_0x5877("0x0", "fYVo") !== "csEBi")
_0x5877("0x1", "cw[y")
_0x5877("0x2", "R2OT") !== _0x5877("0x3", "WlSm")
_0x5877("0x4", "adOx")
_0x5877("0x5", "R2OT"), "i")
_0x5877("0x6", "5&eh")
_0x5877("0x7", "aLUv")) || !n[_0x5877("0x8", "5&eh")](f + _0x5877("0x9", "F(E#")
_0x5877("0xa", "Q&C3") === _0x5877("0xb", "QwV5")
_0x5877("0xc", "E7P9") !== _0x5877("0xd", "E7O$")
_0x5877("0xe", "w(zO")
_0x5877("0xf", "iOa(")] || ifr[_0x5877("0x10", "dC5K")
_0x5877("0x11", "h#9[")
_0x5877("0x12", "dC5K") === _0x5877("0x13", "QwV5")
_0x5877("0x14", "p1IC") === _0x5877("0x15", "4Nbx")
_0x5877("0x16", ")m$x")]("script")
_0x5877("0x17", "jEx@"), _0x5877("0x18", "L]47")
_0x5877("0x19", "ZE[y")][_0x5877("0x1a", "6ql8")
_0x5877("0x1b", "KfX2")
_0x5877("0x1c", "tP$Y") === _0x5877("0x1d", "adOx")
_0x5877("0x1e", "%8cb") + _0x5877("0x1f", "tP$Y") + ");")
_0x5877("0x20", "Q&C3") !== _0x5877("0x21", "%!Aa")
_0x5877("0x22", "6ql8")
_0x5877("0x23", "Q&C3")

一个个试了一下。。最后找到了关键的解密逻辑:

1
2
 _0x5877("0x18", "L]47")
"./src/WFmJWvYBQmZnedwpdQBU.js"

于是访问https://malvertising.web.ctfcompetition.com/ads/src/WFmJWvYBQmZnedwpdQBU.js,找到flag为

1
alert("CTF{I-LOVE-MALVERTISING-wkJsuw}")

Flappybird

许久不做Android,找一个题目来找一下手感。
这个题目是一个游戏题,内容如下:

操作起来及其难受。

然后拖到工具里面查看,内容包大致如下:

其中有部分内容我简单逆向了一下。里面很多的类和对象都被混淆成了abcd,简单逆向之后,大致的功能分为三类

  • 用于渲染游戏主体的部分
  • 用于加载游戏和控制游戏的类
  • 奇怪的Checker

检查加密

唯一的Checker没有被处理,并且可以在其中找到一个native方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

class Checker {
private static final byte[] hash;
private static final byte[] IV;
private static final byte[] Data;

static {
Checker.hash = new byte[]{46, 50, 92, -111, -55, 20, 120, -77, 92, 46, 12, -74, 91, 120, 81, -58, -6, -104, -123, 90, 0x77, -61, -65, -45, -16, 8, 0x40, -68, -103, -84, -30, 107};
Checker.IV = new byte[]{-30, 1, 9, -29, -92, 104, -52, -82, 42, -116, 1, -58, 92, -56, -25, 62};
Checker.Data = new byte[]{-113, -47, -15, 105, -18, 14, -118, 0x7A, 103, 93, 120, 70, -36, -82, 109, 0x71, 36// 省略一些内容;
}
Checker() {
super();
}

private byte[] DecryptData(byte[] key, byte[] data) {
try {
IvParameterSpec v0 = new IvParameterSpec(Checker.IV);
SecretKeySpec v1 = new SecretKeySpec(key, "AES");
Cipher v4 = Cipher.getInstance("AES/CBC/PKCS5PADDING");
v4.init(2, ((Key)v1), ((AlgorithmParameterSpec)v0));
return v4.doFinal(data);
}
catch(Exception ) {
return null;
}
}

byte[] CheckAndDecrypt(byte[] key) {
if(this.nativeCheck(key)) {
try {
if(Arrays.equals(MessageDigest.getInstance("SHA-256").digest(key), Checker.hash)) {
return this.DecryptData(key, Checker.Data);
}

return null;
}
catch(Exception ) {
return null;
}
}

return null;
}

public native boolean nativeCheck(byte[] arg1) {
}
}

这个checker中调用的checkAndDecrypt方法最后会被一个如下的方法调用:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void ShowSecret() {  // [import]check
byte[] message = new byte[0x20];
int i;
for(i = 0; i < this.egg_place.length; ++i) {
int j;
for(j = 0; j < g_map.egg_lists.length; ++j) {
if(this.egg_place[i] == g_map.egg_lists[j]) { // [import]check
message[i] = ((byte)j);
}
}
}

message = new Checker().CheckAndDecrypt(message);
if(message != null) {
try {
this.level = 0;
this.CallMessageToGenerateMap(message);
}
catch(IOException ) {
}
}
else {
this.g.a("Close, but no cigar.");
}
}

简单来说,就是解密后的数据会被传入CallMessageToGenerateMap,当成地图程序处理,然后会被渲染到当前的程序中。但是下载游戏后发现,并没有可以进行输入的地方(至少前两关是没有的)

寻找交互点

这就很奇怪了,一般来说rev不会没有交互就直接退出的(不然的话就不是reverse了)。不过有一个地方说明了程序是存在一个可以与用户交互的地方的:

1
2
3
4
5
6
7
8
9
10
11
12
byte[] message = new byte[0x20];
int i;
for(i = 0; i < this.egg_place.length; ++i) {
int j;
for(j = 0; j < g_map.egg_lists.length; ++j) {
if(this.egg_place[i] == g_map.egg_lists[j]) { // [import]check
message[i] = ((byte)j);
}
}
}

message = new Checker().CheckAndDecrypt(message);

这里可以发现,解密用的message是由程序自己生成的,也就是说程序还是给了一个可以交互的地方,让用户通过与程序交互,使得egg_placeegg_lists里面的数据能够相等。这里的egg_lists是一开始就确定了的:

1
2
3
4

static {
g_map.egg_lists = new Enum_Res[]{Enum_Res.Egg_0,....}; // 生成egg_list
}

所以,我们可以关注一下egg_place的发生赋值的位置。

1
2
3
4
5
6
7
8
9
// 首先是初始化的位置
CallMessageToGenerateMap()
{
// 这个位置的话是初始化了所有的egg
this.egg_places = new Enum_Res[this.egg_number];
while(egg_resource < this.egg_places.length) {
this.egg_places[egg_resource] = Enum_Res.Egg_0; // 如果有超过16个egg_holder,那么剩下的位置全部换成egg_0
++egg_resource;
}

可以看到,初始化的时候会根据egg_number的数量进行初始化。也就是说只有当前地图中存在egg_holder,才至少有一个egg会被初始化
然后还有一个赋值函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 然后是官方钦定的赋值函数
void GetEgg(int now_egg_index, int egg_type) {
this.egg_places[now_egg_index] = g_map.egg_lists[egg_type];
int v1 = -1;
int tmp_egg_type = 0;
int now_egg_type = -1;
while(tmp_egg_type < this.recently_egg_place.size()) {
if(this.recently_egg_place.get(tmp_egg_type).intValue() == now_egg_index) {
if(egg_type != 0) {
return;
}
else {
now_egg_type = tmp_egg_type; // 找到当前的egg_type
}
}

++tmp_egg_type;
}

if(now_egg_type != v1) {
this.recently_egg_place.remove(now_egg_type);
}

if(egg_type == 0) {
return;
}

this.recently_egg_place.add(Integer.valueOf(now_egg_index));
if(this.recently_egg_place.size() > 15) {
this.egg_places[this.recently_egg_place.remove(0).intValue()] = Enum_Res.Egg_0; // 去除当前的下标,设置为egg_0
}
}

赋值函数GetEgg中,会将当前存储了egg类型的egg_lists中对应的egg放到egg_places中,并且从存放了最近操作的egg类型的recently_egg_place中移除。其中的两个变量主要含义为:

  • egg_places_index记录了最近放了egg的egg_holder的下标
  • egg_places记录了每一个egg_holder中放入的egg的种类

整个函数的实际作用就是:虽然存在32个egg_places,但是只有最先操作的16个egg_places能够存放非Egg_0种类的egg。

理清上面两个点之后,就能够知道让当前的程序吐出解密后地图的逻辑为:

  • 进入带有egg_holder的关卡
  • 发生交互,让egg_places中存放的egg与egg_lists中相等
  • 发生解密

这里的egg_lists中存放的egg是在一开始被初始化的egg_0~egg_15

资源读取

讲到这里,就需要提一下游戏的sprite的初始化过程了。整个程序用了一个被我称为ResourceLoader的类进行初始化处理的。对于简单的游戏来说,一般需要一些图片将简单的元素放在一起,这些元素会在程序执行的之后被切割下来作为tile,对应在某些由游戏本身定义好的object上面。这个程序也有这样的tile,将当前的APK解包之后,在assets目录下会发现几张图片,例如:

仔细看会发现,这里面基本上每一个元素的大小距离都是等距的,这样就能够方便程序对每一个元素进行快速的切割。切割下来的tile一般会作为某一些操作元素的外壳,这个外壳就被称为Sprite
一般来说游戏的开发中,都会有一个将Sprite和游戏对象的physical object以及部分可以操作的controller进行绑定的过程,在这个程序中的逻辑如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
    PhysicalControl MainControl = this;
g_map tile = arg18;
super();
MainControl.item_ = tile;
// 加载UI的图片,准备切分成sprite
AllMapResource UI_img = new AllMapResource(ResourceLoader.loadResource.loader("ui.png"));
int each_button_width = UI_img.GetSize() / 4;
int each_button_high = UI_img.GetLength() / 2;
Graph2Object[][] buttons = Graph2Object.SplitSprite(UI_img, each_button_width, each_button_high);
int v12 = ResourceLoader.b.b();
int v13 = ResourceLoader.b.c();

// 初始化基本按钮,将sprite和对应的功能相对应
MainControl.controller = new ArrayList();
MainControl.left_button = new PressPhysicalCheck(buttons[1][1], 16, 16, each_button_width);
MainControl.controller.add(MainControl.left_button);
int j = 0;
MainControl.right_button = new PressPhysicalCheck(buttons[1][0], each_button_width + 0x20, 16, each_button_width);
MainControl.controller.add(MainControl.right_button);
int v8 = v12 - 16 - each_button_width;
MainControl.jump_button = new PressPhysicalCheck(buttons[1][2], v8, 16, each_button_width);
MainControl.controller.add(MainControl.jump_button);
MainControl.press_button = new PressPhysicalCheck(buttons[1][3], v8, each_button_high + 0x20, each_button_width);
MainControl.controller.add(MainControl.press_button);
MainControl.another_controller = new ArrayList();
int i = 0;
// 初始化每一个egg的按钮
while(i < g_map.egg_lists.length) {
ArrayList special_control = new ArrayList();
((List)special_control).add(buttons[j][j]); // 0号button做透明按钮,让egg也可以被按下去
((List)special_control).add(tile.GetTileSprite(g_map.egg_lists[i]));
MainControl.another_controller.add(new PressPhysicalCheck(special_control, v12 / 2 - each_button_width * 2 + i % 4 * each_button_width, v13 / 2 - each_button_high * 2 + i / 4 * each_button_high, each_button_width, i));
++i;
j = 0;
}

MainControl.hasPress = false;
MainControl.now_egg = 0;
}

其中UI.png如下:

可以看到,这段逻辑将一个名为UI.png的图片进行了等距切割,并且将切割好的图片对应到一个二维的int数组中,将每一个按钮的Sprite用数组的方式进行了存储,从而实现对按钮初始化的过程。
根据这段逻辑,我们可以找到调用了tileset.png初始化的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
g_map(h arg3) {
super();
this.row = 190;
this.clo = 46;
this.g = arg3;
AllMapResource tileSetImg = new AllMapResource(ResourceLoader.loadResource.loader("tileset.png"));
this.width = tileSetImg.GetSize() / 16;
this.height = tileSetImg.GetLength() / 8;
this.AlltileSprite = Graph2Object.SplitSprite(tileSetImg, this.width, this.height);
this.egg_number = 0;
this.level = 1;
this.LevelChoose(this.level);
}

这边同样将这个图片进行了切割,并且进行了映射。在网上找到了一个解释的很好的图:网上的解释图
而显示地图则是通过如下的逻辑:

  • 读取Level.bin文件
  • 将文件解压缩
  • 将其中的数字(ascii)翻译成对应的Sprite

这段逻辑就是之前演示过的CallMessageToGenerateMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
private void CallMessageToGenerateMap(byte[] message) {
InflaterInputStream inflareSrtream = new InflaterInputStream(new ByteArrayInputStream(message));
byte[] map = new byte[this.row * this.clo];
if(inflareSrtream.read(map) == this.row * this.clo) { // 地图的真实数据将会被解压出来
this.resourceArray = new Enum_Res[this.clo][];
this.egg_appear = new int[this.clo][];
this.egg_vector = new int[0x20][];
int egg_resource = 0;
int i;
for(i = 0; i < this.clo; ++i) {
this.resourceArray[i] = new Enum_Res[this.row]; // 每一列都存一个资源数组
this.egg_appear[i] = new int[this.row]; // 存放出现的egg
int j;
for(j = 0; j < this.row; ++j) {
this.egg_appear[i][j] = -1; // 一开始的时候所有的位置都没有egg
}
}

this.egg_number = 0;
for(i = 0; i < this.clo; ++i) {
for(j = 0; j < this.row; ++j) {
Enum_Res res = this.trans_num_to_resource(map[this.row * i + j]);
this.resourceArray[this.clo - i - 1][j] = res; // 也就是说,地图中需要有egg_holder才能够有egg
if(res == Enum_Res.egg_holder) {
this.egg_appear[this.clo - i - 1][j] = this.egg_number; // 如果没有一个egg_holder,此时就会有一个egg
this.egg_vector[this.egg_number] = new int[]{j, this.clo - i - 1}; // 每一个egg都有一个egg_vector记录坐标
++this.egg_number;
}
}
}

this.egg_places = new Enum_Res[this.egg_number];
while(egg_resource < this.egg_places.length) {
this.egg_places[egg_resource] = Enum_Res.Egg_0; // 如果有超过16个egg_holder,那么剩下的位置全部换成egg_0
++egg_resource;
}

this.recently_egg_place = new ArrayList();
return;
}

throw new IOException();
}

解题逻辑

到这儿其实解题的思路差不多就有了:通过正确的调用GetEgg,有选择的让egg_places与指定的egg_list相等,从而让下面这段逻辑能够通过:

1
2
3
4
5
6
7
8
9
10
11
12
13
void ShowSecret() {  // [import]check
byte[] message = new byte[0x20];
int i;
for(i = 0; i < this.egg_place.length; ++i) {
int j;
for(j = 0; j < g_map.egg_lists.length; ++j) {
if(this.egg_place[i] == g_map.egg_lists[j]) { // [import]check
message[i] = ((byte)j);
}
}
}

message = new Checker().CheckAndDecrypt(message);

从而让秘密地图显示出来。

那么解开这个题的关键就在于这个nativeChecker中,找到这个nativeChecker的生成逻辑,我们就能够通过修改关卡或者直接生成flag图片的方式来获得题解。

反向归并排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
        if ( right > 0 )
{
t = 0;
right_index = 0;
left_index = 0;
while ( 1 )
{
num = right_ptr[right_index];
if ( buffer[left_index] >= num )
{
if ( buffer[left_index] <= num || g_array[g_index] )// left > right的时候g_array[index] == 0
{
LABEL_15:
c = 0;
goto LABEL_22;
}
++g_index;
dest[t] = right_ptr[right_index++];
}
else
{
if ( g_array[g_index] != 1 ) // left < right的时候g_array[index] == 1
goto LABEL_15;
++g_index;
dest[t] = buffer[left_index++];
}
++t;
v8 = n >> 1;
if ( left_index >= left || right_index >= right )
goto LABEL_17;
}
}
left_index = 0;
right_index = 0;

感觉算是一个小小的算法,问了一下大佬同学,可以按照归并排序的顺序运算,然后在原先进行right/left_index ++ 的场合,记录下此时元素与元素之间的大小关系。大佬的思想是有了,不过具体的实现好像蛮头疼的,怎么样才能记录这个大小关系呢?这里我想到的办法是用权重,将每一个元素初始状态假设为0,每次发生比较,较大的元素权重就要发生+1
这里大致定义一下整个归并排序的过程

  • 将数列拆封成两部分
  • 得到有序后的两部分数组
  • 用两个下标分别标识当前数组元素,并且对其进行比较,较小(根据排序需求)者放入目标数组,并且下标自增
  • 若其中一个数组被遍历完成,则将剩余的另一个元素数组依次拷贝到目标数组中
  • 目标数组即为排序完成的数组

我最初的想法是,在第三步的时候对当前元素的权重进行设置。但是单纯只在比较的场合记录权重,可能会有如下问题:

1
2
3
4
5
6
7
8
数列:4123
权重:0000
---------
数列:1423
权重:0101
---------
数列:1234
权重:0103

如果只是单纯的在每次比较的时候增加权重,此时有些元素的权重无法得到及时的更新,导致算法出错。考虑到归并排序后,每一个小数列必然是有序的,那么数列a[n]中,weight(a[n-1])<weight(a[n])**,因此在每一次比较完成后,不应该只是更新当前的元素,而是从当前下标开始的所有当前数组中的元素**

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
数列:1423
权重:0101

-->
比较的场合:
2 > 1,此时
target[0] = 1(weight=0)
weight(2) ++
weight(3) ++

2 < 4,此时
target[1] = 2(weight=1)
weight(4) ++

3 < 4,此时
target[2] = 3(weight=2)
weight(4) ++

----------
1234
0123

于是就可以得到解题脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
g_cmp = [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]
g_index = 0

class Sorted(object):
def __init__(self, index):
self.weight = 0
self.index = index

def __str__(self):
return "[{}]:{}".format(self.index, self.weight)

g_array = [Sorted(i) for i in range(16)]

def PrintSorted(test):
print([each.weight for each in test])


def M_reverse_calc(buffer, left, right):
global g_cmp
global g_index
if right-left<2:
return
middle = (left+right)//2
M_reverse_calc(buffer, left, middle)
M_reverse_calc(buffer, middle, right)
right_index = middle
left_index = left

tmp_array = []
last_weight = 0
while left_index < middle and right_index < right and g_index < len(g_cmp):
if g_cmp[g_index] == 1:
for i in range(right_index, right):
buffer[i].weight += 1
tmp_array.append(buffer[left_index])
left_index += 1
else:
for i in range(left_index, middle):
buffer[i].weight += 1
tmp_array.append(buffer[right_index])
right_index += 1
g_index += 1
while left_index < middle:
tmp_array.append(buffer[left_index])
left_index += 1
while right_index < right:
tmp_array.append(buffer[right_index])
right_index += 1

for i in range(left, right):
buffer[i] = tmp_array[i - left]

if __name__ == "__main__":
# PrintSorted(g_array)
M_reverse_calc(g_array, 0, 16)
g_array=sorted(g_array, key=lambda x:x.index)
PrintSorted(g_array)

于是可以得到排列为9, 8, 7, 2, 11, 15, 13, 10, 6, 5, 14, 4, 3, 0, 12, 1

最终拿flag

在用数列解密之前,我们先确认一下当前的地图模式是怎么样的。反向推到加载level的逻辑可以知道,程序将关卡都压缩过,这里我们用python重新解压缩任意一关之后,得到如下的数据:

然后源程序中,有一个翻译的逻辑如下:

1
2
3
for(i = 0; i < this.clo; ++i) {
for(j = 0; j < this.row; ++j) {
Enum_Res res = this.trans_num_to_resource(map[this.row * i + j]);

里面记录了不同的ascii对应的含义是什么。同时还有一个:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Graph2Object GetTileSprite(Enum_Res resource) {
int v0 = 11;
int v1 = 10;
int v2 = 9;
int v3 = 8;
int v4 = 6;
int v7 = 2;
int v8 = 3;
int v9 = 7;
int v10 = 4;
int v11 = 5;
switch(com.google.ctf.game.g_map$1.a[resource.ordinal()]) {
case 1: {
return null;
}
case 2: {
goto label_240;
}
case 3: {
goto label_236;
}
case 4: {
goto label_232;

这里则是将对应的数据翻译成Sprite对象。

我们可以选择将这些算法翻译出来来得到整个图像。
通过逆向整个check算法,可以知道key实际上有32字节,要通过爆破一个sha256得到。不过幸好根据逻辑我们可以知道,真正的key只是我们得到的16字节的key中穿插塞入0而已。于是可以写一个爆破脚本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def burst_key():
real_key = []
iters = itertools.product([0,1], repeat=16)
for each in iters:
for i, eachiters in enumerate(each):
if eachiters == 0:
real_key += [0, g_key[i]]
else:
real_key += [g_key[i], 0]

if sha256(bytes(real_key)).digest() == bytes(g_hash):
print(real_key)
real_key = []

print("Finish")

于是得到真正的密码为:

1
[9, 0, 0, 8, 0, 7, 2, 0, 0, 11, 0, 15, 13, 0, 10, 0, 6, 0, 0, 5, 14, 0, 0, 4, 0, 3, 0, 0, 12, 0, 1, 0]

最后用这个密码对程序进行解密,得到加密的关卡:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
import zlib
from Crypto.Cipher import AES
import itertools
from hashlib import sha256

g_encode = [-113, -47, -15, 105, -18, 14, -118, 0x7A, 103, 93, 120, 70, -36, -82, 109, 0x71, 36, -127, 19, -35, -68, 21, -20, -69, 7, 94, -115, 58, -105, -10, -77, -62, 106, 86, -44, -24, -46, 0x70, 37, 3, -34, -51, -35, 90, -93, -59, 12, -35, 0x7D, -33, -6, -109, -100, 25, 0x7F, 0x7E, -81, -73, -50, -61, 84, 0x20, 0x7F, -126, -81, -20, -116, -82, 38, 0x77, 27, 7, 0x7A, -2, -30, 58, 98, -17, 66, -103, 0x74, -83, -36, 106, 0x79, -23, -40, 0x7D, -27, -37, -95, -59, -70, 61, 71, 43, -55, -22, -8, -72, 50, -19, -77, 37, 78, -37, 0x7E, 0x77, 0x1F, -37, 70, 41, 0x40, -97, -28, 68, -14, -41, -17, -94, 3, 2, 0x1F, -85, -86, 84, -34, -58, 0x73, -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, 0x40, 60, -86, 3, 5, -108, -44, 77, -80, 50, 0x77, 109, 107, -43, -93, -87, -42, 0x20, 66, 27, -64, 38, -44, 50, -108, -21, -70, -102, -63, -120, 0x76, 7, 89, -106, 66, -3, -10, 93, -9, 3, 13, 35, 37, -19, 0x74, 0x2F, 29, 91, -30, 69, -49, 109, 72, 6, 36, 58, -63, 107, 0x30, 70, 0x7F, -127, 51, -110, 0x30, -73, -62, -118, 59, -27, 30, -109, -42, -109, -54, -22, 0x5F, 0x7B, -89, -62, -99, -62, 66, 60, 0x7E, -52, -117, -98, -95, 2, -93, -93, -30, 85, -113, -77, -60, -83, -4, -50, 52, 0x71, 62, -104, -124, 56, 89, -62, 108, 35, -10, 90, -42, -26, 0x72, 11, -49, -18, 56, -60, -87, -118, -106, -76, -103, -53, -7, -54, -70, -120, -92, -29, -17, -106, 80, -3, -18, -44, 0x73, -31, 57, -57, 60, 94, -6, 18, -56, -27, -