Square CTF Writeup
2018/11/9 - 2018/11/15 の期間、insecure(ptr-yudai, yoshiking, theoldmoon0602, hikopiyo) として SquareCTF に挑戦していました。中盤、ptr-yudai が実力を遺憾なく発揮して 2-4位をうろつく展開だったのですが、最終問題を解くことができずに84291点で8位という結果でした。 First Blood からの時間経過で配点が下がることを知らずに(つまり早く解くほど点数が高い)最初の問題に出遅れたこと、最後の問題が解けなかったことが悔やまれますが、8位はなかなか高順位で、Top 10 teams にも入れたことは嬉しいです。
解いた問題の内訳としては、 hikopiyoが1問、私が1問、残りの7問を ptr-yudai が解きました。私が解いた問題についてWriteupを書きます。
[Rev 86Solves] gofuscated
名前からは Go の難読化したバイナリが渡されるのかなという感じですが、実際には以下のソースコードが渡されただけでした。
package main import ( "encoding/hex" "fmt" "math/rand" "os" "regexp" "strings" "time" ) /** * important computation, part 1 of 2 */ func compute1(done chan bool) { fmt.Printf("\n\n\n\n\n\n") frames := []string{ "\033[6A\r X \n \n O \n Y/|\\Z\n |\n / \\\n", "\033[6A\r \n X \n Y_O \n |\\Z\n |\n / \\\n", "\033[6A\r \n XY \n (O \n |\\Z\n |\n / \\\n", "\033[6A\r Y \n \n X_O \n |\\Z\n |\n / \\\n", "\033[6A\r Y \n \n O \n X/|\\Z\n |\n / \\\n", "\033[6A\r \n Y\n O_Z\n X/| \n |\n / \\\n", "\033[6A\r \n ZY\n O) \n X/| \n |\n / \\\n", "\033[6A\r Z\n \n O_Y\n X/| \n |\n / \\\n", } ctr := 0 for { select { case <-done: return case <-time.Tick(time.Duration(250) * time.Millisecond): ctr++ s := frames[ctr%len(frames)] x := []byte("\033[32mo\033[39m") y := []byte("\033[34mo\033[39m") z := []byte("\033[35mo\033[39m") for t := 0; t < ctr/len(frames)%3; t++ { x = xor_slice(xor_slice(x, y), z) y = xor_slice(xor_slice(x, y), z) z = xor_slice(xor_slice(x, y), z) x = xor_slice(xor_slice(x, y), z) } s = strings.Replace(s, "X", string(x), 1) s = strings.Replace(s, "Y", string(y), 1) s = strings.Replace(s, "Z", string(z), 1) fmt.Print(s) } } } const Output = 16 const Space = 100000 const Rounds = 100000 /** * important computation, part 2 of 2 * * pro-tip: you should always roll your own crypto. This prevents the NSA or other attackers from using * off-the-shelf tools to defeat your system. */ func compute2(data []byte, done chan bool) chan string { r := make(chan string) go func() { state := make([]int, Space) j := 0 i := 0 for i = range state { state[i] = i } for t := 0; t < Space*Rounds; t++ { i = (i + 1) % Space j = (j + state[i] + int(data[i%len(data)])) % Space state[i], state[j] = state[j], state[i] } o := make([]byte, Output) for t := 0; t < Output; t++ { i = (i + 1) % Space j = state[(state[i]+state[j])%Space] o[t] = byte(j & 0xff) } done <- true r <- hex.EncodeToString(o) }() return r } /** * Some other computation. */ func compute3(r chan byte) chan byte { s := make(chan byte) go func() { var prev byte = 0 for v := range r { if v != prev { s <- v prev = v } } close(s) }() return s } /** * These aren't helpful, right? */ func compute4(input string) string { rand.Seed(42) m := make(map[int]int) for len(m) < 26 { c := rand.Int()%26 + 'a' if _, ok := m[c]; !ok { m[c] = len(m) + 'a' } } r := "" for _, c := range input { r = fmt.Sprintf("%s%c", r, m[int(c)]) } return r } /** * A boring helper function */ func xor_slice(a []byte, b []byte) []byte { r := make([]byte, len(a)) for i, v := range a { r[i] = v ^ b[i] } return r } /** * Another boring function */ func panicIfInvalid(s string) { if !regexp.MustCompile("^[a-zA-Z0-9]{26}$").MatchString(s) { panic("invalid input!") } } /** * Last one */ func another_helper(input string) (r bool) { r = true for i, v := range input { for j, w := range input { r = r && (i > j || v <= w) } } return } /** * Pro-tip: start here. */ func main() { input := os.Args[1] panicIfInvalid(input) done := make(chan bool) go compute1(done) h := compute2([]byte(input), done) s := make(chan byte, len(input)) r := compute3(s) for _, c := range input { s <- byte(c) } close(s) input = "" for c := range r { input = fmt.Sprintf("%s%c", input, c) } panicIfInvalid(input) input = compute4(input) flag := <-h if !another_helper(input) { panic("invalid input!") } panicIfInvalid(input) fmt.Printf("Congrats! 🚩 = flag-%s\n", flag) } // author: Alok
みるとわかりやすいコメントが書かれています。読み進めていくと以下のことがわかりました。
- panicIfInvalid は入力が
^[a-zA-Z0-9]{26}$
であることを期待している - compute1 はお手玉を表示するだけで特に読まなくて良い
- compute2 は入力を受け取ってswapなどをしてあと、計算結果が
flag := <-h
と用いられており、本体っぽい。 - compute3 は入力を受け取ってuniq をして return している。そのあと
panicIfInvalid
に渡されていることから、入力に同じ文字の連続がないことがわかる - compute4 は compute3 された入力を受け取って独自のマッピングで置換している。
- another_helper は 入力文字C_i について
i < j
ならC_i < C_j
であることを保証してくれている(演算子は<=
だけど compute3 の制約で=
になることはない)。文字数が26文字であることから考えて、compute4
の出力はabcdefghijklmnopqrstuvwxyz
になる。
compute3, 4と another_helper のおかげで入力が一意に定まりそうです。 compute4
内で作成していた置換テーブルを逆にしたものを abcdef...xyz
に適用してやると、nxelvzqaifsyhojudrbcwgptmk
と出てきたので、これを入力してやれば compute2
ががんばってFlagを出力してくれそうです。
……というところまで解析してSlackに投げて走らせたら、ptr-yudaiのほうが先にflagが出力されてSubmitしてくれました。実質私の得点じゃないじゃん。私のマシンだと全然フラグでてこなかった。
そのほか感想など
- 解析そんなに難しくないしもっと早く解けるべきだった。結構compute1, compute2を読む方を頑張ってしまっている時間が長くて失敗。
- すわ1位か!? というところまで頑張ったのに最後の問題解けなくてがっかり。惜しいところまで解析できていたのですが、惜しいだけじゃあ点数にはならないんだよな。
- ptr-yudaiが各問題を爆速で解いていたのですごかった。ptr-yudaiがGo読めたら僕の出番がなくなるところでした。
おわり。SquareCTFは早くも来年の予定を公開しているので、またinsecureでチャレンジして、今度は勝利を掴みたいところです。