---
# System prepended metadata

title: picoctf 2018 Reverse Engineering Write Up
tags: [CTF]

---

# picoctf 2018 Reverse Engineering Write Up
###### tags: `CTF`
## 1. be-quick-or-be-dead-1
- 先跑一次
 ![](https://i.imgur.com/UNG23PS.png) 
- 用objdump去看source
    ![](https://i.imgur.com/nHYDoKh.png)
    - get_key
     ![](https://i.imgur.com/wfjfzcd.png)
        - calculate_key
            ![](https://i.imgur.com/bzs04WF.png)
            - 發現會從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可以搜尋到
![](https://i.imgur.com/ZxxIird.png)
- 輸入i來把96 cbd2 74的地方修改為2b 97a5 e9
- 輸入:%!xxd -r 來把文件變回二進位模式(不然之後會無法判別檔案格式)
- 輸入:wq
- 此時再執行就可以順利得到flag!!
![](https://i.imgur.com/yu2KN1S.png)

## 2. quackme
- 丟進ida,發現有個function叫do_magic,看起來就很可疑!!
![](https://i.imgur.com/tH0FzYN.png)
- do_magic的psuedocode
`會先接收使用者input,並將input[i]逐一與i+134514776所存的data做xor,如果與greetingMessage[i]相同就贏惹`
![](https://i.imgur.com/J5cyqvZ.png)
- 其中134514776應該是一個offset,轉成hex之後是0x8048858,該位置有個sekrutBuffer
![](https://i.imgur.com/rqMmVm4.png)
- 再來看一下greetingMessage是啥(按d可以改變用byte/word/dword/qword顯示)
![](https://i.imgur.com/vqkVb3k.png)
- 想法: 因為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惹
    ![](https://i.imgur.com/rZhVyln.png)
 
    
## 3. assembly-2
- 開shell看組語
![](https://i.imgur.com/sW3fkO8.png)
- 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
- 先執行看看
![](https://i.imgur.com/lHyf44H.png)
- 丟進IDA: get_key -> calculate_key -> fib(1015)
`Note: 費式數因為要算很久 -> 不夠快的原因`
![](https://i.imgur.com/xnqrD3f.png)

    ![](https://i.imgur.com/tAn3d4x.png)

- 寫一個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
```
![](https://i.imgur.com/Y2NMwba.png)

- 再回來看看main function,我們已經先算好fib(1015),因此不需要再經過get_key -> calculate_key的步驟 
     - 做法1:把0x40087d~0x40088c的所有byte都改成nop
     ![](https://i.imgur.com/Ypoxv5o.png)
然後用gdb開啟在print_flag的這邊設斷點
![](https://i.imgur.com/GRlvK5X.png)
之後set $rax=... 繼續執行就可以獲得flag
![](https://i.imgur.com/OqFwIM5.png)


    - 做法2:把mov eax,0x0 / call calculate_key這兩個指令替換掉
     ![](https://i.imgur.com/EDSszkI.png)
 也就是底下這10個byte
![](https://i.imgur.com/zF2BYNg.png)
換成這樣(相當於movabs rax, 17662975587330736941)
![](https://i.imgur.com/M1rWq7K.png)
就可以獲得FLAG
![](https://i.imgur.com/gvHlC4N.png)


## 5. quackme up
- 先跑一次
![](https://i.imgur.com/IAjGGeb.png)
- 是做加密,因此Now quack it: **11 80...** 這一串密文應該就是加密後的flag
- 丟進objdump: main -> encrypt
`Note: 可以看出加密過程先 1. rol4(左移4bit) 2. 跟0x16做XOR 3. ror8(右移8bit)`
![](https://i.imgur.com/OhPHSkR.png)
- 因此解密應該是 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看組語
![](https://i.imgur.com/g5aP48W.png)
- asm3(0xaee1f319, 0xe0911505, 0xfac0f685)
    - 先把stack繪出
    `Note:因為是little endian,所以順序從低位開始算`
    ![](https://i.imgur.com/v3tnALI.png)
    - 步驟1~7依序完成
    ![](https://i.imgur.com/P8mW44b.png)
![](https://i.imgur.com/gA4e150.png)

## 7. Radix's Terminal
- 跑一遍發現是需要輸入password在argv[1]
- 丟ida main -> check_password 最後檢查的時候比較了一個可疑字串
![](https://i.imgur.com/6iFjpIx.png)
- 題目提示跟base64有關,用base64 decode看看
![](https://i.imgur.com/VDDGwno.png)


## 8. keygen-me-1
- 開shell跑一遍,發現應該是一個16byte的密碼
![](https://i.imgur.com/xr1wNQO.png)
- 丟進ida main -> validate_key
![](https://i.imgur.com/ImbsHjt.png)
    - ord()
    ![](https://i.imgur.com/skDAE5w.png)
- 還原成程式碼大概長這個樣子
`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惹!!!
![](https://i.imgur.com/viHICVi.png)


## 9. be-quick-or-be-dead-3
- 又是不夠快系列,直接丟進ida看一下 main -> get_key -> calculate_key -> calc
`Note: 可以看出calc很慢的問題出在裡面總共又呼叫了5次的calc,遞迴呼叫就是問題所在` 
![](https://i.imgur.com/MrfqZXH.png)
還原程式碼大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 
    ![](https://i.imgur.com/3lqR7eY.png)
        - gdb可以針對各種SIGINAL做相應處理
    (用法: handle <SIGNAL_NAME> <keyword>)
    這邊用handle SIGALRM ignore (代表忽略這個SIGNAL繼續執行)
        - 斷點設在call <calc>,並set $eax 
        - 跳過SIGALRM後跳到call <calc>後的那條指令位置
        - 欸嘿flag get!!
    ![](https://i.imgur.com/6LDYJ0O.png)


## 10. assembly-4
- 由檔名comp.nasm可知是nasm檔
- 用nasm編譯
```asm=
$ nasm -f elf32 comp.nasm
```

## 11. keygen_me2
- 跟keygen_me類似
- 丟ida main -> validate_key
![](https://i.imgur.com/Yu8PF7W.png)
...恩對,就是這麼崩潰QQ
    - 一個key_constraint大概都長這樣,用跟keygen一樣的ord
    ![](https://i.imgur.com/RFzZUDV.png)
    - 總結一下所有的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
    ![](https://i.imgur.com/cW2G01k.png)
    
    
## 12. circuit123
- 先來跑一次
![](https://i.imgur.com/AQM6fiJ.png)
- 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對不對
![](https://i.imgur.com/9rmClRn.png)

- 可以的話就可以測試map2惹
![](https://i.imgur.com/KzaXfdB.png)




