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 に繋ぐとフラグが出てきた。