[Writeups] VolgaCTF Quals 2020 - F-Hash

這題給了一個 x86-64 ELF Executable,直接跑下去跑不出來,一直卡在那裡,逆向一下會發現 13B0 這個函式是一個遞迴函式,他的虛擬碼大概長下面這樣,會一直遞迴呼叫前兩層的答案,很明顯的有很多重複的子問題,這時候就是要用 Dynamic Programming 的思路來把算過的答案記下來就不會跑那麼久了,所以這題就是要優化這個函式,把程式跑完就會印出 flag。

1
2
3
4
5
def _13B0(depth, a, b):
...
r1 = _13B0(depth - 1, a, b)
r2 = _13B0(depth - 2, a, b)
...

以下提供三種解法,讀者可以跟著練習一下。

Rewrite Function with Python

最直覺的方法就是把 IDA decompile 出來的 code 搬到 python 上重寫一下,沒什麼技術,這是我在賽中用的方法,但就是要注意一下型態的問題,比如兩個 unsigned int 相乘可能 overflow 在 python 裡面要 mod (1 << 32),更多細節請看下面的程式碼。

solve-rewrite.py
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
#!/usr/bin/env python3

table = [0]
for i in range(26):
table += [i * 10 + 1 + (0xf6 << 120)] * 10

def bitcountsum(a, b):
a %= (1 << 64)
b %= (1 << 64)
return bin(a).count('1') + bin(b).count('1')

def calc(a, b, depth = 256):
ans = [0]
ans.append((bitcountsum(a, b), 0, 0))
ans.append((bitcountsum(a ^ 1, b), 0, 1))

for i in range(3, depth + 1):
v15, v16 = ans[i - 1], ans[i - 2]
v13 = ((v15[0] + v15[1] * (1 << 64)) + (v16[0] + v16[1] * (1 << 64)) + bitcountsum((v15[2] + v16[2]) ^ a, b)) % (1 << 128)
v14 = table[i]
while True:
if (v14 >> 64) > (v13 >> 64):
break
if (v14 >> 64) == (v13 >> 64):
if v14 % (1 << 64) >= v13 % (1 << 64):
break
k = max(1, (v13 >> 64) // (v14 >> 64))
v13 = (v13 - k * v14) % (1 << 128)
ans.append((v13 % (1 << 64), (v13 >> 64), (v15[2] + v16[2]) % (1 << 64)))
return ans

al = [0x6369757120656854, 0x706d756a20786f66, 0x20797a616c206568, 0]
bl = [0x206e776f7262206b, 0x74207265766f2073, 0x80676f64, 0x2b]

for a, b in zip(al, bl):
print(list(map(hex, calc(a, b)[256])))

GDB

另一個方法是我在賽後看 別人 用的,在 gdb 寫 python 去 hook 13B0 的開頭和結尾,在開頭判斷這組參數有沒有出現過了,跑過就把參數的 depth 設成 1 也就是 base case 讓他不要再往下遞迴了,而因為同一組函式的 Start, End Hook 沒辦法共享資訊,所以需要維護一個 state 來放目前的參數,在結尾的時候一樣是看這組參數有沒有出現過,有就把答案寫上去,沒有就把答案存起來下次就不會再跑一次了。

solve-gdb.py
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
import gdb

def register(name):
return int(gdb.parse_and_eval(name))

def read(address, size):
inf = gdb.inferiors()[0]
return inf.read_memory(address, size).tobytes()

def write(address, buf):
inf = gdb.inferiors()[0]
inf.write_memory(address, buf)

memory = {}
state = []

class Start(gdb.Breakpoint):
def __init__(self, location):
super(Start, self).__init__(spec = location, type = gdb.BP_BREAKPOINT, internal = False, temporary = False)
def stop(self):
state.append((register('$rdi'), register('$rsi'), register('$rdx'), register('$rcx')))
if memory.get(state[-1][1:]) is not None:
gdb.execute('set $rsi = 1')

class End(gdb.Breakpoint):
def __init__(self, location):
super(End, self).__init__(spec = location, type = gdb.BP_BREAKPOINT, internal = False, temporary = False)
def stop(self):
global state
buf, h = state[-1][0], state[-1][1:]
if memory.get(h) is None:
memory[h] = (read(buf, 8), read(buf + 8, 8), read(buf + 16, 8))
else:
write(buf, memory[h][0])
write(buf + 8, memory[h][1])
write(buf + 16, memory[h][2])
state = state[:-1]

Start(f'*{0x0000555555554000 + 0x13b0}')
End(f'*{0x0000555555554000 + 0x1424}')

gdb f-hash 之後,在 gdb 裡面執行 source solve-gdb.py 就可以跑上面的程式碼了
或是也可以在執行 gdb 的時候就載入 gdb -x solve-gdb.py f-hash

Frida

這個方法也是我賽後看 別人 用的,frida 真的是好東西,之前剛好有研究一點 frida,第一次用在比賽中,基本上跟前一個解法一樣去 hook 函式的開頭和結尾,不過 frida 又更方便了,請看下面程式碼。

solve-frida.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var base = ptr(Process.enumerateModulesSync()[0].base)
var recursive_func_ptr = base.add(0x13b0)

var mem = {}
Interceptor.attach(recursive_func_ptr, {
onEnter: function (args) {
this.buf = args[0]
this.hash = args[1] + '-' + args[2] + '-' + args[3]
if (mem[this.hash] !== undefined) {
args[1] = ptr(1)
}
},
onLeave: function (retval) {
if (mem[this.hash] === undefined) {
mem[this.hash] = [this.buf.readU64(), this.buf.add(8).readU64(), this.buf.add(16).readU64()]
} else {
this.buf.writeU64(mem[this.hash][0])
this.buf.add(8).writeU64(mem[this.hash][1])
this.buf.add(16).writeU64(mem[this.hash][2])
}
}
})

最後執行 frida --no-pause --runtime=v8 -l solve-frida.js ./f-hash 就可以了

Flag

1
VolgaCTF{16011432ba16efc8dcf779477985b3b9}

  1. https://github.com/OAlienO/CTF/tree/master/2020/VolgaCTF/F-Hash
  2. https://pastebin.com/Dj6wteXk
  3. https://sectt.github.io/writeups/Volga20/f-hash/README

[安卓逆向] Frida Hook 動態調試

今天我們要來練習用 frida 在 Android 上做動態調試

逆之呼吸壹之型 - 一般函式

先來寫個簡單的範例 APP
有一個按扭和一個輸入欄,輸入名字之後,按下按鈕,就會顯示 Hello 加上你輸入的名字
不會寫 APP 的小朋友可以先去 youtube 上找教學,有一大堆

MainActivity.java
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
package com.example.myapplication;

import androidx.appcompat.app.AppCompatActivity;

import android.os.Bundle;
import android.view.View;
import android.widget.Button;
import android.widget.EditText;
import android.widget.TextView;

public class MainActivity extends AppCompatActivity {
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);

Button sayButton = findViewById(R.id.sayButton);
sayButton.setOnClickListener(new View.OnClickListener() {
@Override
public void onClick(View v) {
EditText somethingEditText = findViewById(R.id.somethingEditText);
TextView resultTextView = findViewById(R.id.resultTextView);
String something = somethingEditText.getText().toString();
resultTextView.setText(say(something));
}
});
}

String say (String something) {
return "Hello " + something;
}
}

python 負責呼叫 frida api 做注入,javascript 是被注入進去做事的
我們的目標是 hook 函式 say,並在原本的輸出文字後面加上 !!!

hook.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import frida

def on_message(message, payload):
print(message)

device = frida.get_usb_device()
pid = device.spawn(["com.example.myapplication"])
session = device.attach(pid)

with open("script.js") as f:
script = session.create_script(f.read())
script.on("message", on_message)
script.load()

device.resume(pid)

input()
script.js
1
2
3
4
5
6
7
Java.perform(() => {
main = Java.use("com.example.myapplication.MainActivity")
main.say.implementation = function (something) {
var ret = this.say(something)
return ret + '!!!'
}
})

逆之呼吸貳之型 - 重載函式

改一下範例 APP,多加上一個接受數字做輸入的 say 函式
接收到數字後,就輸出 Hello 加上輸入的數字的平方

MainActivity.java
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
package com.example.myapplication;

import androidx.appcompat.app.AppCompatActivity;

import android.os.Bundle;
import android.view.View;
import android.widget.Button;
import android.widget.EditText;
import android.widget.TextView;

public class MainActivity extends AppCompatActivity {
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);

Button sayButton = findViewById(R.id.sayButton);
sayButton.setOnClickListener(new View.OnClickListener() {
@Override
public void onClick(View v) {
EditText somethingEditText = findViewById(R.id.somethingEditText);
TextView resultTextView = findViewById(R.id.resultTextView);
String something = somethingEditText.getText().toString();
try {
Integer number = Integer.parseInt(something);
resultTextView.setText(say(number));
} catch (NumberFormatException e) {
resultTextView.setText(say(something));
}
}
});
}

String say (String something) {
return "Hello " + something;
}

String say (Integer number) {
number = number * number;
return "Hello " + number.toString();
}
}

兩個 say 都是一樣的名字,所以 hook 的時候要用 overload 去區分,overload 參數放的是目標函式輸入參數的型態
這次我們在新的 say 函式的輸出文字後面加上 ???
hook.py 跟上一個例子一樣就不再貼一次了

script.js
1
2
3
4
5
6
7
8
9
10
11
Java.perform(() => {
main = Java.use("com.example.myapplication.MainActivity")
main.say.overload("java.lang.String").implementation = function (something) {
var ret = this.say(something)
return ret + '!!!'
}
main.say.overload("java.lang.Integer").implementation = function (number) {
var ret = this.say(number)
return ret + '???'
}
})

逆之呼吸參之型 - 隱藏函式

再改一下範例 APP,多加上一個變數 secret 和一個函式 getSecret,在 onCreate 裡面會給 secret 一個隨機值,我們的目標就是找出這個值

MainActivity.java
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
package com.example.myapplication;

import androidx.appcompat.app.AppCompatActivity;

import android.os.Bundle;
import android.view.View;
import android.widget.Button;
import android.widget.EditText;
import android.widget.TextView;

public class MainActivity extends AppCompatActivity {

private int secret;

@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);

secret = (int) (Math.random() * 100);

Button sayButton = findViewById(R.id.sayButton);
sayButton.setOnClickListener(new View.OnClickListener() {
@Override
public void onClick(View v) {
EditText somethingEditText = findViewById(R.id.somethingEditText);
TextView resultTextView = findViewById(R.id.resultTextView);
String something = somethingEditText.getText().toString();
try {
Integer number = Integer.parseInt(something);
resultTextView.setText(say(number));
} catch (NumberFormatException e) {
resultTextView.setText(say(something));
}
}
});
}

String say (String something) {
return "Hello " + something;
}


String say (Integer number) {
number = number * number;
return "Hello " + number.toString();
}

int getSecret () {
return secret;
}
}

因為我們的目標不是自己 new 一個物件出來抓 secret,這樣就只是一個我們自己就可以生成的隨機值而已
我們是要找出目前已經存在的那個 instance 的 secret,在實際例子中可能就會是一組隨機生成的密碼之類的
所以我們要用到 Java.choose 去抓 instance,抓到 instance 後,可以

  1. instance.getSecret() 呼叫函式搞定
  2. instance.secret.value 存取變數搞定

然後用 send 可以把資料傳到 python 端的 on_message 做處理

script.js
1
2
3
4
5
6
7
8
9
Java.perform(function () {
Java.choose("com.example.myapplication.MainActivity", {
onMatch: function (instance) {
send(instance.getSecret()) // call function
send(instance.secret.value) // access vairable
},
onComplete: function () {}
})
})

疑難雜症

Q : 有函式 a 跟變數 a 同名怎麼辦 ?
A : a 存取函式,_a 存取變數


  1. https://github.com/hookmaster/frida-all-in-one
  2. How to access class member variable if there’s a member function called the same name?
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×