---
title: Hack.lu CTF 2019 - Futuretran
description: Rev
tags: CTF
lang: zh_tw
---

# `Hack.lu` CTF 2019 - Futuretran
[TOC]

## Description
### Readme
Complex, unsafe languages are the past. We've built a new programming language for the future that uses only a fraction of the instructions of RISC. This should be easy, right?

### Analysis
題目給了 [flag.ftb](https://github.com/LJP-TW/CTF/blob/master/hackluCTF-2019/rev/Futuretran/temp/public/flag.ftb) 跟 [interpreter.py](https://github.com/LJP-TW/CTF/blob/master/hackluCTF-2019/rev/Futuretran/temp/public/interpreter.py)
看了一下 [interpreter.py](https://github.com/LJP-TW/CTF/blob/master/hackluCTF-2019/rev/Futuretran/temp/public/interpreter.py) 後，發現重點是 run 這個 function

簡單講一些用到的資料:
- code 為一個分數的 list，被當作是指令 cur_ins
分子為 cur_ins\[0\]，分母為 cur_ins\[1\]
- idx 為現在執行到哪個指令

主要行為如下:
- state *= 分子
- 若 state 能被分母整除，則 state 為除分母後的商數，並且指令重頭開始跑
- 整個指令都跑完才 return state

main call 完 run 後，若能被 out 整除，就是錯誤。

### Prime
這題用到一個質數的特性，就是質數基本定義
`質數為只有自己本身跟1能整除自己本身的數字`

比如說 2 * 3 * 5，只能被 2^n * 3^n * 5^n, n <= 1 這些數字整除。

且任何數都能換成 `質數A`^`次方` * `質數B`^`次方` ... 的形式
e.g. 30 = 2 ^ 1 * 3 ^ 1 * 5 ^ 1
以下先稱之為`展開形式`

那 120 能被 7 整除嗎? 不行。Why?
可以這樣想
120 的展開形式為 2 ^ 3 * 3 ^ 1 * 5 ^ 1
可以想成，120 有**3個2，1個3，1個5**
而 7 的展開形式為 7 ^ 1，也就是**1個7**
120 交不出**1個7**，所以不能整除。

那 120 能被 12 整除嗎? 可以。Why?
可以這樣想
12 的展開形式為**2個2，1個3**
120 交得出**2個2，1個3**
所以能整除，整除後的數字就是**交出2個2、1個3後剩下的數**
也就是**1個2，1個5**，也就是10

為啥要講廢話，因為這題就是在用這個概念。

### Reversing - phase 1
看看[interpreter.py](https://github.com/LJP-TW/CTF/blob/master/hackluCTF-2019/rev/Futuretran/temp/public/interpreter.py)的部分 code

def run(state, code):
    size = len(code)
    idx = 0
    while idx < size:
        cur_ins = code[idx]
        idx += 1
        tmp = state * cur_ins[0]
        if tmp % cur_ins[1] == 0:
            state = tmp // cur_ins[1]
            idx = 0

    return state

想像一下，state 為 120，分子(cur_ins[0])為7，分母為(cur_ins[1])為12
tmp 先讓 state 乘上分子
- tmp 有**3個2，1個3，1個5，1個7**
- 若 tmp 能交出分母，也就是**2個2，1個3**
- state 等於 tmp // 分母，也就是tmp交出分母後剩下的數，也就是**1個2，1個5，1個7**
- 若 tmp 交不出分母，則 state 不會變化

就好像每一個指令、每一個分數、都像是交易過程，state 交出分母的數，來取得分子的數
以上的狀況就是 state 交得出 12，就交出 12 換 7，state = (120 // 12) * 7
那如果 state 交不出分母的數，就不會進行這次交易

再進一步想，每個質數就像是一種貨品，state 就好像你現在有的各種貨品總數
每個指令都是一個分數，就像是一個交易選項，若你現在剛好有符合分母的貨，就會交出這些貨，並換回分子的貨，一個以物易物的概念。

理解好概念後，來看看我做了什麼事情。

首先我寫了一個 [dump.py](https://github.com/LJP-TW/CTF/blob/master/hackluCTF-2019/rev/Futuretran/temp/public/dump.py)，改編自 [interpreter.py](https://github.com/LJP-TW/CTF/blob/master/hackluCTF-2019/rev/Futuretran/temp/public/interpreter.py)
做的事情是
- 檢查所有 primes (flag.ftb 的第一行所有數字)是否真的是 prime
- 將所有分數的分子分母化為展開形式

就是把每個指令、每個交易內容顯示出來

而剛剛提到的概念，就能用來實作 if 邏輯、xor 邏輯之類的

怎麼說呢?
現在來看看執行 [dump.py](https://github.com/LJP-TW/CTF/blob/master/hackluCTF-2019/rev/Futuretran/temp/public/dump.py) 的部分輸出

17: [{337: 1, 347: 1}, {331: 1}]
18: [{1}, {167: 1, 211: 1, 337: 1}]
19: [{167: 1}, {211: 1, 337: 1}]
20: [{1}, {337: 1}]
21: [{349: 1, 353: 1}, {347: 1}]
22: [{1}, {173: 1, 223: 1, 349: 1}]
23: [{173: 1}, {223: 1, 349: 1}]
24: [{1}, {349: 1}]

- line 17 若 state 交得出 331 就交出 331 換回 337、347
- line 18 若 state 交得出 167、221、337，就交出並換回 nothing
- line 19 若 state 交得出 211、337，就交出並換回 167

這邊可以小小做一個統整，若 state 原本只有**1個331**
那麼經過 line 17，state 會變成**1個337，1個347**(331被換掉了)

這裡再更改原本假設，state 現在多了**1個211**
則到了 line 18、19，將兩行交易合併一起解釋則為
有 167 就換掉 **1個167，1個211，1個337** 換回 **1個1**
不然就換掉 **1個211，1個337** 換回 **1個167**

注意，每次若成功交易了，則會回到第一筆交易開始檢查能否交易

**331**就好像flag，若 state 中有 331，就會換到 337，有 337，就有機會執行 line 18、19 的交易
若 state 根本沒有 **331** 則 line 18、19 的交易根本不可行

所以我說他像 flag，這 flag 為 true 則就會嘗試執行 line 18、19
為 false 則根本不會進 line 18、19

而 **211** 也像一個flag，為 true 則要嘗試執行 line 18、19
為 false 也根本不會進 line 18、19

就好像

if(v331)
{
    if(v211)
    {
        if(v167)
        {
            v167 -= 1
        }
        else
        {
            v167 += 1
        }
    }
}

這樣不就能完成 if 了嗎 ?

### Reversing - phase 2
現在可以大概知道說能用以上提到的 trick 實作一些簡單的邏輯。
那來完整的 reverse 這題目的邏輯吧

首先 main 做的事情是將 sys.argv\[2\]，也就是 flag 的部分
一一變成各個「貨品」的數量
比如說 flag 為 flag{........}
會將 state 設定為 **ord('f')個2，ord('l')個3，ord('a')個5，ord('g')個7 ...**

再來，寫一個觀察 state 的動態的腳本 [approach.py](https://github.com/LJP-TW/CTF/blob/master/hackluCTF-2019/rev/Futuretran/temp/public/approach.py)
他會在交易成功時，將以下資訊輸出
- 是第幾行的交易
- tmp，也就是 state 乘上分子
- 交易完畢的 state

然後可以發現第92行的交易一直被執行
來看一下
`92: [{257: 1, 571: 1}, {2: 1, 587: 1}]`
原來是 2 一直被換掉，
並且發現 257 數量會一直往上疊加，但 571 不會
表示 571 後續還有被換掉

來到 2 被換完後
還會執行第93、94、89的交易
分別為

93: [{593: 1}, {587: 1}]
94: [{223: 1, 227: 1, 239: 1, 241: 1, 569: 1, 599: 1}, {593: 1}]
89: [{277: 1, 331: 1, 433: 1, 503: 1}, {569: 1}]

第 92 行一直有在被執行，所以大膽假設，每次 loop 時，總會有 587
當 2 換到沒了，無法執行第 92 行的交易
才會來到第 93 行交易，將 587 換為 593
有 593 才能再換第 94 行交易
有了從第 94 行交易換來的 569
才能再從 89 行換來 277、331、433、503
所以統整一下現在 state 會多有哪些東西
- 從第 94 行交易換到的 223、227、239、241、599
- 從第 89 行交易換到的 277、331、433、503

再來看看繼續執行了什麼交易
發現後續執行第2、3、5、8、10 ... 這些交易
這邊把整段 dump 拉出來看

1: [{199: 1, 281: 1}, {257: 128, 277: 1}]
2: [{281: 1}, {277: 1}]
3: [{197: 1, 283: 1}, {257: 64, 281: 1}]
4: [{283: 1}, {281: 1}]
5: [{193: 1, 293: 1}, {257: 32, 283: 1}]
6: [{293: 1}, {283: 1}]
7: [{191: 1, 307: 1}, {257: 16, 293: 1}]
8: [{307: 1}, {293: 1}]
9: [{181: 1, 311: 1}, {257: 8, 307: 1}]
10: [{311: 1}, {307: 1}]
11: [{179: 1, 313: 1}, {257: 4, 311: 1}]
12: [{313: 1}, {311: 1}]
13: [{173: 1, 317: 1}, {257: 2, 313: 1}]
14: [{317: 1}, {313: 1}]
15: [{167: 1}, {257: 1, 317: 1}]
16: [{1}, {317: 1}]

這邊可以看到，進來執行的條件為要有 277
對吧，沒有 277 不會有 281，沒 281 就沒 283 就沒 293 ... ，就不會有後續連鎖的執行了
而從 89 行有拿到 277，有機會進來執行
那 257 就是剛剛 2 被拿去 1 比 1 換的貨物
這邊講結論，這裡是一個 decimal to 8-bits binary 的 function
這 8 bits 由高到低為
199,197,193,191,181,179,173,167

比如說我輸入的 flag 第一個字是 f，最後這8個貨物的貨品數為
| 199| 197|193|191|181|179|173|167
|----|----|---|---|---|---|---|-----
| 0 | 1 | 1| 0| 0| 1| 1| 0
就是 `bin(ord('f'))`

執行完第 16 交易後，會繼續執行第 17、20、21、22、25... 這些交易
一樣把一大段拿出來

17: [{337: 1, 347: 1}, {331: 1}]
18: [{1}, {167: 1, 211: 1, 337: 1}]
19: [{167: 1}, {211: 1, 337: 1}]
20: [{1}, {337: 1}]
21: [{349: 1, 353: 1}, {347: 1}]
22: [{1}, {173: 1, 223: 1, 349: 1}]
23: [{173: 1}, {223: 1, 349: 1}]
24: [{1}, {349: 1}]
25: [{359: 1, 367: 1}, {353: 1}]
26: [{1}, {179: 1, 227: 1, 359: 1}]
27: [{179: 1}, {227: 1, 359: 1}]
28: [{1}, {359: 1}]
29: [{373: 1, 379: 1}, {367: 1}]
30: [{1}, {181: 1, 229: 1, 373: 1}]
31: [{181: 1}, {229: 1, 373: 1}]
32: [{1}, {373: 1}]
33: [{383: 1, 389: 1}, {379: 1}]
34: [{1}, {191: 1, 233: 1, 383: 1}]
35: [{191: 1}, {233: 1, 383: 1}]
36: [{1}, {383: 1}]
37: [{397: 1, 401: 1}, {389: 1}]
38: [{1}, {193: 1, 239: 1, 397: 1}]
39: [{193: 1}, {239: 1, 397: 1}]
40: [{1}, {397: 1}]
41: [{409: 1, 419: 1}, {401: 1}]
42: [{1}, {197: 1, 241: 1, 409: 1}]
43: [{197: 1}, {241: 1, 409: 1}]
44: [{1}, {409: 1}]
45: [{421: 1, 431: 1}, {419: 1}]
46: [{1}, {199: 1, 251: 1, 421: 1}]
47: [{199: 1}, {251: 1, 421: 1}]
48: [{1}, {421: 1}]

331 就像是這一大段邏輯的入口
可以看到每四行就一個類似的結構，
331 換
- 337 -> 用來進入後續的兩行交易，用完就丟
- 347 -> 用來進入下一個結構

line 21 也是類似這樣，就不贅述了

這邊在幹嘛?直接說就是
將以下兩列的值做 xor
| 199| 197|193|191|181|179|173|167
|----|----|---|---|---|---|---|-----
| 0 | 1 | 1| 0| 0| 1| 1| 0

| 251| 241|239|233|229|227|223|211
|----|----|---|---|---|---|---|-----
| 0 | 1 | 1| 0| 0| 1| 1| 0

第一個序列為 `bin(ord('f'))`
第二個序列是從第 94 行交易換到的 223、227、239、241

這邊突然意識到，2 換完後，會在換一行 key，這 key 要等於 `bin(ord(第0個字元))`

大膽假設，3 換完後也會換一行 key，這 key 就是 `bin(ord(flag 的第二個字元))`
找到就表示，這題可能就這樣了

來到 2 換完的邏輯附近

92: [{257: 1, 571: 1}, {2: 1, 587: 1}]
93: [{593: 1}, {587: 1}]
94: [{223: 1, 227: 1, 239: 1, 241: 1, 569: 1, 599: 1}, {593: 1}]
95: [{601: 1}, {599: 1}]
96: [{257: 1, 599: 1}, {3: 1, 601: 1}]
97: [{607: 1}, {601: 1}]
98: [{227: 1, 229: 1, 239: 1, 241: 1, 569: 1, 613: 1}, {607: 1}]
99: [{617: 1}, {613: 1}]
100: [{257: 1, 613: 1}, {5: 1, 617: 1}]
101: [{619: 1}, {617: 1}]
102: [{211: 1, 239: 1, 241: 1, 569: 1, 631: 1}, {619: 1}]
103: [{641: 1}, {631: 1}]
104: [{257: 1, 631: 1}, {7: 1, 641: 1}]
105: [{643: 1}, {641: 1}]
106: [{211: 1, 223: 1, 227: 1, 239: 1, 241: 1, 569: 1, 647: 1}, {643: 1}]
107: [{653: 1}, {647: 1}]

3 如果換完了，會換 607，再換 227 229 239 241
| 251| 241|239|233|229|227|223|211
|----|----|---|---|---|---|---|-----
| 0 | 1 | 1| 0| 1| 1| 0| 0
=> chr(0b01101100) = 'l'

如果到這邊還看得懂，那後續的事情我也不用贅述了

[solve.py](https://github.com/LJP-TW/CTF/blob/master/hackluCTF-2019/rev/Futuretran/temp/public/solve.py)

## Reference
No reference.