CODE BLUE CTF 2017 fs hell write-up

https://score.ctf.codeblue.jp/

某チームで参加して、revのfs hellだけ解いた。

問題を開くと、fs_hellとprogram.txtの2個のファイルが入っている。fs_hellはLinuxバイナリ、program.txtの中身はこんな感じ。

```program.txt
 :
%14$.*4$d%14$.65534d%9$hn
%14$.*5$d%14$.10d%10$hhn
%14$.*4$d%14$.65525d%9$hn
%14$.*5$d%14$.30d%10$hhn

%14$.255d%6$hn
%14$.513d%9$hn
%14$.*12$d%13$hn
%14$.1d%13$hn
%14$.4d%13$hn
%14$.*1$d%10$hhn
%14$.*4$d%14$.1d%9$hn
%14$.*1$d%14$.65535d%6$hn
%14$.65529d%13$hn
 :
```

これは、`printf`などの引数に使われる書式指定文字列。あまり知られていない仕様だが、書式指定文字列は`%n`という指定で、引数にこれまでに出力したバイト数を書き込める。

```cpp
int a;
int b;
printf("aaaa%n%d%n\n", &a, 9999, &b);
printf("a=%d, b=%d\n", a, b);
```
```
aaaa9999
a=4, b=8
```

また、GCCやClangの独自拡張で、`%x$d`とすると、`%`が出現した順番にかかわらず、`x`番目の引数を使うことができる。`h`や`hh`は引数の変数の型で、`h`ならば`short`、`hh`ならば`char`になる。

```cpp
printf("%2$d %1$d\n", 0, 100);
```
```
100 0
```

普通は（？）これを使って、サーバーで動いているプログラムのメモリを書き換えて攻撃する。この問題では書式指定文字列でプログラムを書いていた。面白い。書式指定文字列はチューリング完全だったのか。

fs_hellは読み込んだ書式指定文字列を次のような引数で実行していた。

```cpp
snprintf(tmp, 1, P[pc].c_str(),
        a,  b,  c,  d,  mem[d],
       &a, &b, &c, &d, &mem[d],
       a==0, a>>15, &pcd, 0);
pc = pc + pcd + 1;
```

例えば、

```
%14$.*5$d%14$.30d%10$hhn
```

は5番目の引数（`mem[d]`）の桁数の`0`を出力して、30桁の`0`を出力して、そのバイト数を10番目の引数（`&mem[d]`）を`char`型とみなして書き込むので、

```
memd[d] = (memd[d] + 30) % 256
```

となる。

適当にスクリプトを書いてprogram.txtを置換する。

```
d = d + 65534
mem[d] = mem[d] + 10
d = d + 65525
mem[d] = mem[d] + 30

a = 255
d = 513
pcd = a<0
pcd = 1
pcd = 4
mem[d] = a
d = d + 1
a = a + 65535
pcd = 65529
```

ここでは`% 256`や`% 65536`は省略しているけれど、`mem[d]`を`short`とみなして書き込むところもあった。

program.txtを書き換えると次のようになる。

```program.py
mem = [0]*1024
for i, c in enumerate(open("input.txt").read()):
  mem[i] = ord(c)

A = [
  11, 22, 65514, 26, 65523, 65526, 7, 65522, 10, 3, 65535, 11, 6, 65505, 13, 65534,
  65533, 65529, 18, 10, 65527, 7, 65506, 25, 65529, 3, 6, 65514, 9, 16, 65507, 23,
  2, 7, 3, 65521, 65522, 9, 65526, 65529, 4, 5, 65529, 65533, 27, 65535, 8, 65506,
  29, 65525, 65527, 18, 65520, 65531, 65530, 8, 18, 65534, 65525]
B = [
  87, 52, 109, 56, 44, 84, 179, 92, 15, 88, 114, 37, 175, 100, 3, 32,
  181, 48, 52, 129, 68, 39, 204, 30, 91, 2, 212, 43, 113, 9, 117, 45,
  13, 164, 39, 13, 218, 5, 216, 65, 125, 225, 97, 67, 18, 68, 22, 119,
  110, 36, 4, 34, 227, 5, 23, 49, 84, 10, 30]

d = 288
for i in range(len(A)):
    d = (d + A[i]) % 65536
    mem[d] += B[i]

a = 255
d = 513
while a>=0:
  mem[d] = a
  d += 1
  a -= 1

mem[256] = 0
mem[258] = 0
mem[260] = 0
mem[262] = 0
while (mem[260] != 39):
  b = mem[mem[260]]
  a = mem[262]
  while a!=0:
    b *= 2
    a -= 1
  mem[266] = b % 256
  mem[267] = b / 256
  a = mem[266]
  a += mem[267]
  a += mem[mem[258] + 512]
  b = mem[mem[260] + 288]
  mem[258] = b
  a += mem[b + 512]
  if a%256!=0:
    mem[256] = 1
  else:
    mem[256] = mem[256]
  mem[260] += 1
  mem[262] += 1
  if mem[262]==8:
    mem[262] = 0

print ["Congratz!", "Nope :("][mem[256]]
```

`mem[512]`からのデータは符号を逆転にするために使っているとか、`b *= 2`のあたりは`b <<= a`とかで整理すると、

```program2.py
input = map(ord, open("input.txt").read())

T = [
  67, 65, 204, 214, 142, 225, 48, 135, 216, 218, 230, 196, 49, 185, 84, 227,
  145, 45, 8, 114, 179, 179, 36, 15, 96, 68, 113, 48, 23, 212, 121, 34,
  48, 162, 151, 164, 175, 56, 39]

f = 0
p = 0
for i in range(39):
  t = input[i]<<(i%8)
  if (t%256 + t/256 - p - T[i])%256 != 0:
    f = 1
  p = T[i]

print ["Congratz!", "Nope :("][f]
```

後は`f`が0にならないような入力を逆算するだけ。

```solve.py
T = [
  67, 65, 204, 214, 142, 225, 48, 135, 216, 218, 230, 196, 49, 185, 84, 227,
  145, 45, 8, 114, 179, 179, 36, 15, 96, 68, 113, 48, 23, 212, 121, 34,
  48, 162, 151, 164, 175, 56, 39]

flag = ""
for i in range(39):
  t = (T[i] + (0 if i==0 else T[i-1]))&0xff
  flag += chr(t>>(i%8) | t<<(8-i%8)&0xff)
print flag
```

```
CBCTF{Do_Y0U_W4nt_MOR3_foRm4t_57RiNg5?}
```

ある程度解析して`mem[256]`が`1`になったらダメと分かれば、実際にプログラムを動かして、`1`になるまでのステップ数が増えるように入力を総当たりするという手もある。コンテスト中はバグっていて動かなかったが。

<blockquote class="twitter-tweet" data-conversation="none" data-lang="ja"><p lang="ja" dir="ltr">fs shell、VMのメモリをchar data[1024]からunsigned char data[1024]にしたらちゃんと動いた。アセンブラみたいなものだから符号なんてどうでも良いと思っていたけど、この変数はsnprintfの引数になるのか。面白い問題だったのでWrite-upを書こう。明日。 <a href="https://twitter.com/hashtag/codeblue_ctf?src=hash&amp;ref_src=twsrc%5Etfw">#codeblue_ctf</a></p>&mdash; kusanoさん@がんばらない (@kusano_k) <a href="https://twitter.com/kusano_k/status/929033295400091648?ref_src=twsrc%5Etfw">2017年11月10日</a></blockquote>

```solve.cpp
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cstdio>

using namespace std;

int execute(vector<string> P, string init)
{
    unsigned char mem[1024] = {};
    for (int i=0; i<init.size(); i++)
        mem[i] = init[i];

    unsigned short a = 0, b = 0, c = 0, d = 0;
    unsigned short pc = 0;
    int count = 0;
    while (pc<P.size())
    {
        unsigned short pcd = 0;
        char tmp[16];
        snprintf(tmp, 1, P[pc].c_str(),
             a,  b,  c,  d,  mem[d],
            &a, &b, &c, &d, &mem[d],
            a==0, a>>15, &pcd, 0);
        pc = pc + pcd + 1;
        count++;
        if (mem[256]==1)
            return count;
    }
    return count;
}

int main()
{
    vector<string> P;
    fstream f("program.txt");
    string p;
    while (getline(f, p))
        P.push_back(p);

    string flag = "";
    for (int i=0; i<39; i++)
    {
        int c = execute(P, flag);
        for (char a=0x20; a<0x7f; a++)
            if (execute(P, flag+a) > c)
            {
                flag += a;
                break;
            }
        cout<<flag<<endl;
    }
}
```