某チームで参加して、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という指定で、引数にこれまでに出力したバイト数を書き込める。

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になる。

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

100 0

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

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

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になるまでのステップ数が増えるように入力を総当たりするという手もある。コンテスト中はバグっていて動かなかったが。

fs shell、VMのメモリをchar data[1024]からunsigned char data[1024]にしたらちゃんと動いた。アセンブラみたいなものだから符号なんてどうでも良いと思っていたけど、この変数はsnprintfの引数になるのか。面白い問題だったのでWrite-upを書こう。明日。 #codeblue_ctf
— kusanoさん@がんばらない (@kusano_k) 2017年11月10日

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;
    }
}