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してくれました。実質私の得点じゃないじゃん。私のマシンだと全然フラグでてこなかった。