# printf 圖靈完備如何可能
> 資安讀書會 3/30
最近頗忙，這裡簡單寫個東西，然後中間有一些東西我沒有 bottom up 的去理解原理，只是觀察他的行為找規律而已。
為什麼會有這篇分享呢？因為有次 jserv 上課說 printf 可以做到圖靈完備，所以就開始亂玩，~~順便水一次讀書會~~。
完整程式碼在這：[printf-turing](https://gist.github.com/rota1001/3476c555878e9b678c2fc28611e883ed)
## 概述
能在以下程式碼中的 `...` 地方插入除了 C 語言函數呼叫以外的東西，達成圖靈完備：
```cpp
#include <stdio.h>
int main()
{
printf(...);
}
```
雖然標題下的那麼聳動，這裡只算是提供一種方向，至少它和 `libc` 中的 gadget 一樣強大，~~看有沒有人要來寫個 C to printf 編譯器看看~~
## libc 版本
```
GNU C Library (Ubuntu GLIBC 2.39-0ubuntu8.4) stable release version 2.39.
```
## format string
首先，講一下 `printf` 的 format string 拿來寫的的利用方式。
通常要任意寫會使用 `%n`，我們翻閱一下 C99 規格書對於 `%n` 的敘述（在 `fprintf` 的敘述裡，[7.19.6.1](https://rgambord.github.io/c99-doc/sections/7/19/6/1/index.html)）：
> The argument shall be a ==pointer to signed integer== into which is written the ==number of characters== written to the output stream so far by this call to fprintf. No argument is converted, but one is consumed. If the conversion specification includes any flags, a field width, or a precision, the behavior is undefined.
可以發現，它會把現在輸出的字元數往一個指向 `signed integer` 的參數指向的位置寫入。
但有時候因為寫入一個 `signed int` 不太實際，所以會用到 `%hn` 和 `%hhn`，再看一下規格書：
> The length modifiers and their meanings are:
>- hh
> Specifies that a following d, i, o, u, x, or X conversion specifier applies to a signed char or unsigned char argument (the argument will have been promoted according to the integer promotions, but its value shall be converted to signed char or unsigned char before printing); or ==that a following n conversion specifier applies to a pointer to a signed char argument==.
>- h
> Specifies that a following d, i, o, u, x, or X conversion specifier applies to a short int or unsigned short int argument (the argument will have been promoted according to the integer promotions, but its value shall be converted to short int or unsigned short int before printing); or ==that a following n conversion specifier applies to a pointer to a short int argument==.
可以發現，他們分別是把目標變成 `pointer to short int` 和 `pointer to signed char` 的 length modifiers，以下應用會使用 `%hhn`，在我的電腦上會寫入一個位元組（bytes）。
另外一點是，在底層的觀點來看，`signed` 和 `unsigned` 是一樣的，所以讓它自然 overflow 就好。
## helloworld
寫每個程式語言第一件事情就是學習 Helloworld，所以我們來寫 Helloworld 吧!（話是這麼說，其實這裡也只會示範 Helloworld）
### 如何任意寫
首先，如果有打 pwn 的人就會知道，`pwntools` 提供了 `fmt_payload` 去幫我們把寫某些地址為特定的值的 format string 寫出來，這裡我們要去實現它，並在沒有分支的情況下寫出來。
首先是怎麼輸出特定長度的字串，可以使用以下巨集：
```cpp
#define str(n) ("aaaaa...aaa\0" + (0xff - (n)))
```
`%hhn` 會寫目前輸出字元數，而輸出字元數一定是遞增的，所以我們寫入的位元組一定要是遞增的。所以我們必須在沒有分支的情況下寫一個排序演算法，我這裡用暴力的方式去接邏輯扎。
- `byte(x, i)`
得到 `x` 中第 `i` 個字元
- `bigger(x, i, j)`
`x` 中第 `i` 個字元比 `j` 大的布林值（相等比較 index 確保一一對應）
- `rank128(x, i)`
`x` 中第 `i` 個字元的排名
- `number128(x, r)`
`x` 中排名為 `r` 的字元
- `idx128(x, r)`
`x` 中排名為 `r` 的 index
```cpp
#define byte(x, i) ((x >> (i << 3)) & 0xff)
#define bigger(x, i, j) ((byte((x), (i)) > byte((x), (j))) || ((byte((x), (i)) == byte((x), (j))) && ((i) < (j)))) // i > j
#define rank128(x, i) (bigger((x), (i), 0) \
+ bigger((x), (i), 1) \
+ bigger((x), (i), 2) \
+ bigger((x), (i), 3) \
+ bigger((x), (i), 4) \
+ bigger((x), (i), 5) \
+ bigger((x), (i), 6) \
+ bigger((x), (i), 7) \
+ bigger((x), (i), 8) \
+ bigger((x), (i), 9) \
+ bigger((x), (i), 10) \
+ bigger((x), (i), 11) \
+ bigger((x), (i), 12) \
+ bigger((x), (i), 13) \
+ bigger((x), (i), 14) \
+ bigger((x), (i), 15) \
)
#define number128(x, r) ((byte((x), 0) & (-(rank128((x), 0) == (r)))) \
| (byte((x), 1) & (-(rank128((x), 1) == (r)))) \
| (byte((x), 2) & (-(rank128((x), 2) == (r)))) \
| (byte((x), 3) & (-(rank128((x), 3) == (r)))) \
| (byte((x), 4) & (-(rank128((x), 4) == (r)))) \
| (byte((x), 5) & (-(rank128((x), 5) == (r)))) \
| (byte((x), 6) & (-(rank128((x), 6) == (r)))) \
| (byte((x), 7) & (-(rank128((x), 7) == (r)))) \
| (byte((x), 8) & (-(rank128((x), 8) == (r)))) \
| (byte((x), 9) & (-(rank128((x), 9) == (r)))) \
| (byte((x), 10) & (-(rank128((x), 10) == (r)))) \
| (byte((x), 11) & (-(rank128((x), 11) == (r)))) \
| (byte((x), 12) & (-(rank128((x), 12) == (r)))) \
| (byte((x), 13) & (-(rank128((x), 13) == (r)))) \
| (byte((x), 14) & (-(rank128((x), 14) == (r)))) \
| (byte((x), 15) & (-(rank128((x), 15) == (r)))) \
)
#define idx128(x, r) ((0 & (-(rank128((x), 0) == (r)))) \
| (1 & (-(rank128((x), 1) == (r)))) \
| (2 & (-(rank128((x), 2) == (r)))) \
| (3 & (-(rank128((x), 3) == (r)))) \
| (4 & (-(rank128((x), 4) == (r)))) \
| (5 & (-(rank128((x), 5) == (r)))) \
| (6 & (-(rank128((x), 6) == (r)))) \
| (7 & (-(rank128((x), 7) == (r)))) \
| (8 & (-(rank128((x), 8) == (r)))) \
| (9 & (-(rank128((x), 9) == (r)))) \
| (10 & (-(rank128((x), 10) == (r)))) \
| (11 & (-(rank128((x), 11) == (r)))) \
| (12 & (-(rank128((x), 12) == (r)))) \
| (13 & (-(rank128((x), 13) == (r)))) \
| (14 & (-(rank128((x), 14) == (r)))) \
| (15 & (-(rank128((x), 15) == (r)))) \
)
```
那如果我去進行以下操作，就可以把最大的字元寫到它應該在的位置，並且一此類堆，我們可以做到任意寫：
```cpp
printf("%s%hhn", str(number128(target, 0)), (char *)base + idx128(target, 0));
```
但是這個任意寫有個致命的限制，就是不能太長，要不然就算不討論指令數目，編譯器也會被我們操死，寫 16 個位元組已經是蠻極限了，所以接下來要進行其他操作。
### stack pivoting
我們可以去看 `printf` 的位置來得到免費的 `libc_base`，我們又可以從 `libc` 中找到 `environ` 的值來求出 `stack` 的相對位置（它和 `rbp` 相差的偏移是固定的），以防讀者不知道這裡補充一下，你可以這樣在 `pwntools` 找到他的 `offset`：
```python
from pwn import *
libc = ELF("./libc.so.6")
print(hex(libc.symbols["environ"]))
```
於是我們可以算出各種 base：
```cpp
#define PRINTF_OFF 0x60100
#define ENVIRON_OFF (-0x20ad58)
#define RBP_OFF 0x138
#define LIBC_BASE ((unsigned long long)printf - PRINTF_OFF)
#define ENVIRON (LIBC_BASE - ENVIRON_OFF)
#define RBP ((*(unsigned long long *)ENVIRON) - RBP_OFF)
```
然後知道 `rbp` 的值又可以任意寫，所以可以控制回傳地址了，但是只能控制 16 位元組，根本不夠 ROP，這個時候就要使用 stack pivoting。
他的使用條件是有一段可控、可寫的地址，而且 `rbp` 指向的地址可控，我們就可以透過 `leave ret` 去將 `rsp` 遷移。
`leave` 所作的事情可以簡單的化為以下操作：
```asm
mov rsp, rbp
pop rbp
```
而通常結束函式呼叫時，`rbp` 指向的位置存的值是 `old rbp`，而 `rbp` 會是在 `old rsp - 8` 的位置，`rsp` 會和 `rbp` 指向同個地方。然後會執行 `pop rbp` 和 `ret`。首先會讓 `rbp` 變成 `old rbp`，然後 `rsp` 往高位一格（這裡把 8 位元組叫做一格），也就是回到了 `old rsp` 的位置。
那如果我們多執行一次 `leave` 會發生什麼事呢？這個仔細思考後會發現，在進行完這個函數的 `pop rbp` 和 `ret` 之後，`rbp` 的值已經變成了我們操控的地址了，那再 `mov rsp, rbp` 就會把 `rsp` 送到那個地址，再 `pop rbp` 就會讓 `rsp` 再往高位移動一格。於是，接下來就可以在那段可控地址寫 ROP chain。
至於要在哪裡得到這段可控地址呢？觀察可以發現，呼叫 `printf` 之後，它參數的內容會在 stack 上找得到，所以我們可以 `printf` 的參數後面寫 ROP chain，然後再用 stack pivoting 跳上去就好。
這裡簡單的建了一個 `helloworld` 的 ROP chain：
```cpp
POP_RAX_RET, // pop rax ; ret
1uLL,
POP_RDI_RET, // pop rdi ; ret
1,
POP_RSI_RET, // pop rsi ; ret
"Helloworld\n",
POP_RBX_RET, // pop rbx ; ret
11,
MOV_RDX_RBX_POP, // mov rdx, rbx ; pop rbx ; pop r12 ; pop rbp ; ret
0,
0,
STACK_PIVOT,
SYSCALL // syscall
```
### demo
結果（我也不知道為什麼前面那些東西沒有輸出，之後再研究看看）：
```
$ ./print_bk
Helloworld
[1] 78887 segmentation fault (core dumped) ./print_bk
```
然後我們可以去動態分析看看：
```bash
pwndbg> b printf
pwndbg> c
pwndbg> fin
```
執行完這個之後， main 就準備要退出了：
```asm
► 0x5555558542c4 <main+3142027> add rsp, 0x140 RSP => 0x7fffffffc980 (0x7fffffffc840 + 0x140)
0x5555558542cb <main+3142034> mov eax, 0 EAX => 0
0x5555558542d0 <main+3142039> lea rsp, [rbp - 0x28] RSP => 0x7fffffffca88 —▸ 0x7fffffffcbd8 —▸ 0x7fffffffd0b3 ◂— ...
0x5555558542d4 <main+3142043> pop rbx RBX => 0x7fffffffcbd8
0x5555558542d5 <main+3142044> pop r12 R12 => 1
0x5555558542d7 <main+3142046> pop r13 R13 => 0
0x5555558542d9 <main+3142048> pop r14 R14 => 0x555555856df0 (__do_global_dtors_aux_fini_array_entry)
0x5555558542db <main+3142050> pop r15 R15 => 0x7ffff7ffd000 (_rtld_global)
0x5555558542dd <main+3142052> pop rbp RBP => 0x7fffffffc910
0x5555558542de <main+3142053> ret <warn+184>
```
然後繼續往下，發現開始執行預期中的指令了：
```asm
0x7ffff7c299d2 <warn+184> leave
► 0x7ffff7c299d3 <warn+185> ret <__wcscmp_sse2+3159>
↓
0x7ffff7cdd237 <__wcscmp_sse2+3159> pop rax RAX => 1
0x7ffff7cdd238 <__wcscmp_sse2+3160> ret <__spawnix+875>
↓
0x7ffff7d0f75b <__spawnix+875> pop rdi RDI => 1
0x7ffff7d0f75c <__spawnix+876> ret <eval_expr_multdiv+157>
↓
0x7ffff7d10a4d <eval_expr_multdiv+157> pop rsi
```
再看一下在系統呼叫時的暫存器狀況：
```asm
RAX 1
RBX 0
RCX 0
RDX 0xb
RDI 1
RSI 0x555555855171 ◂— 'Helloworld\n'
```
看來我們成功呼叫 `SYS_write` 了
Sign in with Wallet
Connect another wallet