# picoctf 2018 Reverse Engineering Write Up
###### tags: `CTF`
## 1. be-quick-or-be-dead-1
- 先跑一次
- 用objdump去看source
- get_key
- calculate_key
- 發現會從0x74d2cb96開始一直做+0x1直到0xe9a5972c
類似於 for(i=0x74d2cb96; i<0xe9a5972c; i++)
這就是不夠快的原因!!!
- 因此目標就是把0x74d2cb96改成0xe9a5972b,讓這個for loop只需要執行一次
- 用二進位模式編輯檔案 (vim -b be-quick-or-be-dead)
- 輸入:%!xxd變成16進位模式
- 由objdump知道mov DWORD PTR [rbp-0x4],0x7fd2cb96的Machine Code為 c7 45 fc 96 cb d2 74,因此輸入/c745可以搜尋到
- 輸入i來把96 cbd2 74的地方修改為2b 97a5 e9
- 輸入:%!xxd -r 來把文件變回二進位模式(不然之後會無法判別檔案格式)
- 輸入:wq
- 此時再執行就可以順利得到flag!!
## 2. quackme
- 丟進ida,發現有個function叫do_magic,看起來就很可疑!!
- do_magic的psuedocode
`會先接收使用者input,並將input[i]逐一與i+134514776所存的data做xor,如果與greetingMessage[i]相同就贏惹`
- 其中134514776應該是一個offset,轉成hex之後是0x8048858,該位置有個sekrutBuffer
- 再來看一下greetingMessage是啥(按d可以改變用byte/word/dword/qword顯示)
- 想法: 因為greetingMessage = sekrutBuffer ^ Input
而xor有個特殊性質: A ^ B ^ A == B
因此如果將gM ^ sek就會等於Input
- 來寫個C code
```c=
int main(){
char greeting_message[25] = {0x59,0x6F,0x75,0x20,0x68,0x61,0x76,0x65,0x20,0x6e,0x6f,0x77,0x20,0x65,0x6e,0x74,0x65,0x72,0x65,0x64,0x20,0x74,0x68,0x65,0x20};
char sekrutBuffer[25] = {0x29,0x06,0x16,0x4f,0x2b,0x35,0x30,0x1e,0x51,0x1b,0x5b,0x14,0x4b,0x08,0x5d,0x2b,0x50,0x14,0x5d,0x00,0x19,0x17,0x59,0x52,0x5d};
for(int i=0;i<25;i++)
printf("%c", greeting_message[i]^sekrutBuffer[i]);
printf("\n");
}
- 編譯並執行就得到flag惹
## 3. assembly-2
- 開shell看組語
- asm2(0x7,0x28)
- 其中0x7 = ebp + 0x8 = counter , 0x28 = ebp - 0x4 = answer
- cmp + jle 是一個loop,如果counter <= 0xa1de,就執行part_a的內容: counter + 0x76 及 answer + 0x1
- 因此answer為 (0xa1de - 0x7)/0x76 + answer + 1 = 0x188
## 4. be-quick-or-be-dead-2
- 先執行看看
- 丟進IDA: get_key -> calculate_key -> fib(1015)
`Note: 費式數因為要算很久 -> 不夠快的原因`
- 寫一個python code來計算fib(1015)
```python=
n = 1015
def fib(n):
i = 0
nextterm = 1
present = 1
previous = 0
while i < n:
nextterm = present + previous
present = previous
previous = nextterm
i = i + 1
return nextterm
result = fib(n)
print(f'fib({n})={result}')
print('====================')
print(f'32bit = {result & (2 ** 32- 1)}') #因為結果是放進eax,所以要轉成32bit=3611214637
```
- 再回來看看main function,我們已經先算好fib(1015),因此不需要再經過get_key -> calculate_key的步驟
- 做法1:把0x40087d~0x40088c的所有byte都改成nop
然後用gdb開啟在print_flag的這邊設斷點
之後set $rax=... 繼續執行就可以獲得flag
- 做法2:把mov eax,0x0 / call calculate_key這兩個指令替換掉
也就是底下這10個byte
換成這樣(相當於movabs rax, 17662975587330736941)
就可以獲得FLAG
## 5. quackme up
- 先跑一次
- 是做加密,因此Now quack it: **11 80...** 這一串密文應該就是加密後的flag
- 丟進objdump: main -> encrypt
`Note: 可以看出加密過程先 1. rol4(左移4bit) 2. 跟0x16做XOR 3. ror8(右移8bit)`
- 因此解密應該是 1.左移8bit 2.跟0x16做XOR 3.右移4bit
```python=
from pwn import *
def decrypt(s):
de_text = ''
for i in s:
i = ord(unhex(i)) #in pwnlib ex: unhex('11') -> \x11
i = rol(i, 8, 8) #in pwnlib usage: rol(n, k-round, word_size)
i^= 0x16
i = ror(i, 4, 8) #or rol(i, -4, 8))
de_text += chr(i)
return de_text
input_text = '11 80 20 E0 22 53 72 A1 01 41 55 20 A0 C0 25 E3 20 30 00 45 05 35 40 65 C1'.split()
print(decrypt(input_text))
```
## 6.assembly3
- 開shell看組語
- asm3(0xaee1f319, 0xe0911505, 0xfac0f685)
- 先把stack繪出
`Note:因為是little endian,所以順序從低位開始算`
- 步驟1~7依序完成
## 7. Radix's Terminal
- 跑一遍發現是需要輸入password在argv[1]
- 丟ida main -> check_password 最後檢查的時候比較了一個可疑字串
- 題目提示跟base64有關,用base64 decode看看
## 8. keygen-me-1
- 開shell跑一遍,發現應該是一個16byte的密碼
- 丟進ida main -> validate_key
- ord()
- 還原成程式碼大概長這個樣子
`Note: 16byte的密碼中前15個byte會做一些運算並累加得到sum,最後會check sum%36跟最後一個byte做ord的結果是否相等`
```c=
int ord(char c){
if (c <= '0' || c >= '9')
if(c >= 'A' && c <= 'Z' )
return c-55;
else
return c-48;
}
int validate_key(char *key){
int sum = 0;
for (int i=0; i<15; i++){
sum += (ord(key[i])+1) * (i+1);
}
return sum%36 == ord(key[15]);
}
```
- 因此再寫一個code來算如果前15byte都是0,那16byte應該會是什麼
(算出來為000000000000000C)
```c=
int gen_key(){
char key = '0';
int sum = 0;
for (int i=0; i<15; i++){
sum += (ord(key)+1) * (i+1);
}
return sum%36 + 55; #還原第16byte
int main(){
printf("password can be %s%c\n", "000000000000000", gen_key());
}
```
- 得到flag惹!!!
## 9. be-quick-or-be-dead-3
- 又是不夠快系列,直接丟進ida看一下 main -> get_key -> calculate_key -> calc
`Note: 可以看出calc很慢的問題出在裡面總共又呼叫了5次的calc,遞迴呼叫就是問題所在`
還原程式碼大guy4醬
```c=
#include<stdio.h>
unsigned int calc(unsigned int n){
unsigned int answer, a, b, c, d, e;
if (n<=4)
answer = n * n + 0x2345;
else{
a = calc(n-1);
b = calc(n-2);
c = calc(n-3);
d = calc(n-4);
e = calc(n-5);
answer = a - b + c - d + e * 0x1234;
}
return answer;
}
int main(){
printf("%u\n", calc(0x186b5));
}
```
- 解決遞迴呼叫很慢最好的方式就是把算過的存下來!! 因此重寫的程式碼長醬
`Note: 算出來結果為572362474`
```c=
#include<stdio.h>
#define SIZE 0x186b5
unsigned int result[SIZE]; //use to store calculated result
int check[SIZE]; //if calc(n) has been calculated, then check[n] will set to 1
unsigned int calc(unsigned int n){
unsigned int answer, a, b, c, d, e;
if (check[n]) //stop recursive
return result[n];
if (n<=4)
answer = n * n + 0x2345;
else{
a = calc(n-1);
b = calc(n-2);
c = calc(n-3);
d = calc(n-4);
e = calc(n-5);
answer = a - b + c - d + e * 0x1234;
}
check[n]=1;
result[n]=answer;
return answer;
}
int main(){
printf("%u\n", calc(SIZE));
}
```
- be-quick2的兩種做法一樣行得通,這邊來嘗試gdb的進階用法!!
- 跑一遍發現是跳出SIGALRM
- gdb可以針對各種SIGINAL做相應處理
(用法: handle <SIGNAL_NAME> <keyword>)
這邊用handle SIGALRM ignore (代表忽略這個SIGNAL繼續執行)
- 斷點設在call <calc>,並set $eax
- 跳過SIGALRM後跳到call <calc>後的那條指令位置
- 欸嘿flag get!!
## 10. assembly-4
- 由檔名comp.nasm可知是nasm檔
- 用nasm編譯
```asm=
$ nasm -f elf32 comp.nasm
```
## 11. keygen_me2
- 跟keygen_me類似
- 丟ida main -> validate_key
...恩對,就是這麼崩潰QQ
- 一個key_constraint大概都長這樣,用跟keygen一樣的ord
- 總結一下所有的key_constraint
```
1: (ord(input[0]) + ord(input[1])) % 36 == 0xE
2: (ord(input[2]) + ord(input[3])) % 36 == 0x18
3: (ord(input[2]) - ord(input[0])) % 36 == 0x6
4: (ord(input[1]) + ord(input[3]) + ord(input[3])) % 36 == 0x4
5: (ord(input[2]) + ord(input[4]) + ord(input[6])) % 36 == 0xd
6: (ord(input[3]) + ord(input[4]) + ord(input[5])) % 36 == 0x16
7: (ord(input[6]) + ord(input[8]) + ord(input[10])) % 36 == 0x1f
8: (ord(input[1]) + ord(input[4]) + ord(input[7])) % 36 == 0x7
9: (ord(input[9]) + ord(input[12]) + ord(input[15])) % 36 == 0x14
10: (ord(input[13]) + ord(input[14]) + ord(input[15])) % 36 == 0xc
11: (ord(input[8]) + ord(input[9]) + ord(input[10])) % 36 == 0x1b
12: (ord(input[7]) + ord(input[12]) + ord(input[13])) % 36 == 0x17
```
- hint提示為z3, 可以用python的z3來解
```python=
from z3 import *
key = [Int('x{}'.format(i)) for i in range(16)]
# key = [x0, x1, x2, ... , x15]
s = Solver() #create solver
for i in range(16):
s.add(key[i] >= 0, key[i] <= 35) # ord: 0(48)~9(57) -> -48
# A(65)~Z(90) -> -55
# add key_constraints
s.add((key[0] + key[1]) % 0x24 == 0xe)
s.add((key[2] + key[3]) % 0x24 == 0x18)
s.add((key[2] - key[0]) % 0x24 == 6)
s.add((key[1] + key[3] + key[5]) % 0x24 == 4)
s.add((key[2] + key[4] + key[6]) % 0x24 == 0xd)
s.add((key[3] + key[4] + key[5]) % 0x24 == 0x16)
s.add((key[6] + key[8] + key[10]) % 0x24 == 0x1f)
s.add((key[1] + key[4] + key[7]) % 0x24 == 7)
s.add((key[9] + key[12] + key[15]) % 0x24 == 0x14)
s.add((key[13] + key[14] + key[15]) % 0x24 == 0xc)
s.add((key[8] + key[9] + key[10]) % 0x24 == 0x1b)
s.add((key[7] + key[12] + key[13]) % 0x24 == 0x17)
correct_key = []
if s.check() == sat: # .check() return sat if there exists a solution
m = s.model()
for i in range(16):
# usage of as_long() : m[a].as_long() -> return solved value of a
if m[key[i]].as_long() >= 10 : # 10 = ord('A') - 55 -> is alphabets
correct_key.append(chr(m[key[i]].as_long() + 55))
else: # is numbers
correct_key.append(chr(m[key[i]].as_long() + 48))
print('KEY: ' + ''.join(correct_key))
```
- 執行出來的key就可以用惹XD
## 12. circuit123
- 先來跑一次
- decrypt.py
```python=
#!/usr/bin/python2
from hashlib import sha512
import sys
from z3 import *
def verify(x, chalbox):
length, gates, check = chalbox
# check = (570, True) in map1
# length = 64 = length of key
b = [(x >> i) & 1 for i in range(length)]
# b = [1L, 1L, 0L, 1L, 1L, 1L, 1L, 0L, 1L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 1L, 1L, 1L, 0L, 0L, 0L, 0L, 1L, 1L, 1L, 1L, 1L, 0L, 0L, 1L, 1L, 0L, 1L, 1L, 1L, 1L, 0L, 0L, 1L]
for name, args in gates:
# gates[0] = ('true', []) in map1
# gates[1] = ('xor', [(0, False), (64, False)]) in map1
if name == 'true':
b.append(1)
else:
u1 = b[args[0][0]] ^ args[0][1]
u2 = b[args[1][0]] ^ args[1][1]
if name == 'or':
b.append(u1 | u2)
elif name == 'xor':
b.append(u1 ^ u2)
return b[check[0]] ^ check[1]
def dec(x, w):
z = int(sha512(str(int(x))).hexdigest(), 16)
return '{:x}'.format(w ^ z).decode('hex')
if __name__ == '__main__':
if len(sys.argv) < 3:
print 'Usage: ' + sys.argv[0] + ' <key> <map.txt>'
print 'Example: Try Running ' + sys.argv[0] + ' 11443513758266689915 map1.txt'
exit(1)
with open(sys.argv[2], 'r') as f:
cipher, chalbox = eval(f.read())
key = int(sys.argv[1]) % (1 << chalbox[0])
print 'Attempting to decrypt ' + sys.argv[2] + '...'
if verify(key, chalbox):
print 'Congrats the flag for ' + sys.argv[2] + ' is:', dec(key, cipher)
else:
print 'Wrong key for ' + sys.argv[2] + '.'
```
- map1.txt
```
(1091562780682878452932647567206562803258945860781462102555439111325671293639822353361220777655154004326830877696329866178864341430343894025596404608627826L,
(64, [('true', []), ('xor', [(0, False), (64, False)]), ('xor', [(65, False), (64, True)]), ..., ('or', [(538, False), (569, False)])], (570, True)))
```
- Summary:
1. 第37行: cipher = 109156...這段
chalbox = 後面剩餘的部分
2. verify()把chalbox再拆成三部分
length = 64
gates = [(...), (...), ..., (...)]
check = (1140, True)
3. 第39行: key = argv[1] 長度不可以超過64bit(length)
-> chalbox[0]是key的長度
4. 第12行: b是一個0/1 array
5. 第41行: verify()要return True才可獲得flag
-> b[check[0]] 必須 = 0
-> check[0]代表最後b的size,所以代表b的最後一位一定要是0
- 上z3,在decrypt.py最後直接加上:
```python=46
########################### new added ###################################
s = Solver()
solvers_key = BitVec('solvers_key', int(chalbox[0])) # usage BitVec('name', size)
s.add(verify(solvers_key, chalbox) == True) # add constraint
if s.check() == sat:
print s.model()
#########################################################################
```
- 先用map1測試看看key對不對
- 可以的話就可以測試map2惹
Sign in with Wallet
Connect another wallet