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

HITCON CTF 2016 Quals の Writeup

TSGの面々(cookies,dai,hakatashi,moratorium,satos,yamaguchi)で参加してました。(土曜は各々の自宅で、日曜は集まって1徹夜で)
1550点で38位でした。

自分が関わった問題について

Handcrafted pyc

pythonバイトコードが与えられるので、デコンパイルして読め、という問題。
dis というライブラリがあるとのことで、それでデコンパイルする。

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import marshal, zlib, base64

bbx = base64.b64decode('eJyNVktv00AQXm/eL0igiaFA01IO4cIVCUGFBBJwqRAckLhEIQmtRfPwI0QIeio/hRO/hJ/CiStH2M/prj07diGRP43Hs9+MZ2fWMxbnP6mux+oK9xVMHPFViLdCTB0xkeKDFEFfTIU4E8KZq8dCvB4UlN3hGEsdddXU9QTLv1eFiGKGM4cKUgsFCNLFH7dFrS9poayFYmIZm1b0gyqxMOwJaU3r6xs9sW1ooakXuRv+un7Q0sIlLVzOCZq/XtsK2oTSYaZlStogXi1HV0iazoN2CV2HZeXqRQ54TlJRb7FUlKyUatISsdzo+P7UU1Gb1POdMruckepGwk9tIXQTftz2yBaT5JQovWvpSa6poJPuqgao+b9l5Aj/R+mLQIP4f6Q8Vb3g/5TB/TJxWGdZr9EQrmn99fwKtTvAZGU7wzS7GNpZpDm2JgCrr8wrmPoo54UqGampFIeS9ojXjc4E2yI06bq/4DRoUAc0nVnng4k6p7Ks0+j/S8z9V+NZ5dhmrJUM/y7JTJeRtnJ2TSYJvsFq3CQt/vnfqmQXt5KlpuRcIvDAmhnn2E0t9BJ3SvB/SfLWhuOWNiNVZ+h28g4wlwUp00w95si43rZ3r6+fUIEdgOZbQAsyFRRvBR6dla8KCzRdslar7WS+a5HFb39peIAmG7uZTHVm17Czxju4m6bayz8e7J40DzqM0jr0bmv9PmPvk6y5z57HU8wdTDHeiUJvBMAM4+0CpoAZ4BPgJeAYEAHmgAUgAHiAj4AVAGORtwd4AVgC3gEmgBBwCPgMWANOAQ8AbwBHgHuAp4D3gLuARwoGmNUizF/j4yDC5BWM1kNvvlxFA8xikRrBxHIUhutFMBlgQoshhPphGAXe/OggKqqb2cibxwuEXjUcQjccxi5eFRL1fDSbKrUhy2CMb2aLyepkegDWsBwPlrVC0/kLHmeCBQ==')
bx = zlib.decompress(bbx)
x = marshal.loads(bx)

print 'valname .. ' ,x.co_varnames
print 'const .. ' ,x.co_consts
print 'const .. ' ,x.co_consts[1].co_varnames
print 'const .. ' ,x.co_consts[1].co_consts

import dis
print dis.disassemble(x)
print dis.dis(x.co_consts[1])

と、中にmainという関数があり、その中で、

  1           0 LOAD_GLOBAL              0 (chr)
              3 LOAD_CONST               1 (108)
              6 CALL_FUNCTION            1
              9 LOAD_GLOBAL              0 (chr)
 
...中略...

            722 LOAD_CONST              18 (33)
            725 CALL_FUNCTION            1
            728 ROT_TWO             
            729 BINARY_ADD          
            730 ROT_TWO             
            731 BINARY_ADD          
            732 BINARY_ADD          
            733 BINARY_ADD          
            734 BINARY_ADD          
            735 BINARY_ADD          
            736 BINARY_ADD          
            737 LOAD_CONST               0 (None)
            740 NOP                 
            741 JUMP_ABSOLUTE          759
        >>  744 LOAD_GLOBAL              1 (raw_input)
            747 JUMP_ABSOLUTE         1480
        >>  750 LOAD_FAST                0 (password)
            753 COMPARE_OP               2 (==)
            756 JUMP_ABSOLUTE          767
        >>  759 ROT_TWO             
            760 STORE_FAST               0 (password)
            763 POP_TOP             
            764 JUMP_ABSOLUTE          744
        >>  767 POP_JUMP_IF_FALSE     1591
            770 LOAD_GLOBAL              0 (chr)
            773 LOAD_CONST              17 (99)
            776 CALL_FUNCTION            1
            779 LOAD_GLOBAL              0 (chr)
            782 LOAD_CONST              10 (116)

みたいになっている。
スタックに物を積んだり連結したりしてるようなので、適当にエミュレータもどきを書いてやる。

with open('da.txt','r') as fp:
	s = fp.readlines()

sta = []

for d in s:
	if 'CONST' in d:
		x = d.split()[3][1:-1]
		if x == 'None':
			break
		sta.append(chr(int(x)))
	elif 'ROT' in d:
		x = sta.pop()
		y = sta.pop()
		sta.append(x)
		sta.append(y)
	elif 'ADD' in d:
		x = sta.pop()
		y = sta.pop()
		sta.append(x+y)

print sta
print sta[0][::-1]

#Call me a Python virtual machine! I can interpret Python bytecodes!!!

"""
password: Call me a Python virtual machine! I can interpret Python bytecodes!!!
hitcon{Now you can compile and run Python bytecode in your brain!}
"""

(どうやら、767のPOP_JUMP_IF_FALSEをnopにして実行するという手もあったらしい)

Hackpad

でかい.pcapファイルが渡される。中を見るとhttp500の中にちょこっとhttp200が紛れている、という感じ。

これ(【CODEGATE2011 - Quals】 Crypto400 - 人素(とーしろー)の物思い)の存在を思い出す。どうやら同じくpadding oracle attackのキャプチャが与えられるので、元の文字列を復号する問題。こないだやったなー、(csaw ctf 2016 quals のwriteup - 忖度のNeo)と思いつつやる。

当初scapyでやろうかとおもっていたのだが、データが膨大で無限に時間がかかっていたので適当に抽出もどきを書く。C++pythonよりずっとはやい。

#include<cstdio>
#include<cstring>

using namespace std;
#define rep(i,n) for(int i=0;i<((int)(n));i++)

FILE* fp;
void uget(char* s){
	int ls = strlen(s);
	int i=0;
	for(;i<ls;){
		char c;
		fread(&c, sizeof(char),1,fp);
		if(s[i]==c)i++;
		else{
			if(c==s[0])i=1;
			else i=0;
		}
	}
}

int main(void){
	fp = fopen("hackpad.pcap","rb");
	rep(i,100000){
		uget("msg");
		char s[100];
		int de = 65;
		if(!fread(s, sizeof(char),de,fp)){
			break;
		}
		s[de]='\0';
		printf("%s\n",s);
	}
	return 0;
}

padding oracle attackなので、

...前略...
=67acd06f7f7b28762310ce1213fccb11997d9369c74c82abba4cc3b1bfc65f02
=000000000000000000000000000000ff6c957ff0feef61b161cfe3373c2d9b90
...後略...

こんな感じで、先頭文字が一気に000000になってるとこを探して、その直前のみを抽出する。

with open('extattack.txt','rb') as fp:
	s = fp.read()

ms = '=ff'
s = s.split('\n')
for d in s:
	d = d[d.find('='):]
	if len(d)<2 or d[1]==' ':
		continue
	if d[1:3]=='00':
		continue
	
	if int(ms[1:3],16) <= int(d[1:3],16):
		print ms
	ms = d

これによって、

=67acd06f7f7b28762310ce1213fccb11997d9369c74c82abba4cc3b1bfc65f02
=a90ca309b638f6d2c43bf3ceddb72c7e6c957ff0feef61b161cfe3373c2d9b90
=19a50e949a9e12ca51b680074d53abe15639aa3688659566d9acc93bb72080f7
=325ddb45f355f21ea0dfb10bce43b097e5ebd643808a0e50e1fc3d16246afcf6
=9089a03ce2f77b24d1995e6f5a1dcc9288dfedf02ad4ae84fd92c5c53bbd98f0
=f0aadd905ba0dafd83e5f5ba4d8de9c08b21d838a3261874c4ee3ce8fbcb9662
=f843b158c7596f16b58e449188fbeb178d5706499dd985ec0c13573eeee03766
=ee34773ee8e79f9475772441908b6f42f7010a867edfed92c33233b17a9730eb
=847a7ff24ead84a2b20247c45bee43924a82a6db51fa6124bfc48ef99d669e21
=6ae7c5eb319f1550c6baf9c9aa45a94c740d12656f597e691bbcbaa67abe1a09
=6e546c551c3b17097fc3cdc40bde6260f02afc37140b167533c7536ab2ecd4ed
=cc1a9a46767267074fb26e16c792a38937572fc9154d23aa7d8c92b84b774702
=4f674fb564345dce08e4f68836022461632ed2737a569e4dfbe01338fcbb2a77
=1259a7104a29e8298e9e23408ddd5f47ddd6990ce169bb4f48e1ca96d30eced2
=b9a9a97e9459db3e3c95bfe2e336bbba3b6fe5b875ca6481056848be0fbc26bc
=5b1e9bcc00be5db1611778cc7a8c55c3bffdfe966da4221103408f459ec1ef12
=c29d8ff214d65e643327f621e6f18b6ac72068bc1b96df045d3fa12cc2a9dcd1
=b2100dc26fe3bd783446df5bf2dabeb862ffdf876b3bc3a3ed2373559bcbe3f4
=029ba0f0094aa3db94504335f9b29e8d70a8c695bf54796bfe471cd34b463e98
=14d1a0e0814e6371e45d06c9515c248276212df912deef882b657954d7dada47

という、正式にdecodeできる(であろう)長さ2ブロック分の文字列が20個見つかる。

あと、ほかにパケットの先頭を漁ると、

3ed2e01c1d1248125c67ac637384a22d997d9369c74c82abba4cc3b1bfc65f026c957ff0feef61b161cfe3373c2d9b905639aa3688659566d9acc93bb72080f7e5ebd643808a0e50e1fc3d16246afcf688dfedf02ad4ae84fd92c5c53bbd98f08b21d838a3261874c4ee3ce8fbcb96628d5706499dd985ec0c13573eeee03766f7010a867edfed92c33233b17a9730eb4a82a6db51fa6124bfc48ef99d669e21740d12656f597e691bbcbaa67abe1a09f02afc37140b167533c7536ab2ecd4ed37572fc9154d23aa7d8c92b84b774702632ed2737a569e4dfbe01338fcbb2a77ddd6990ce169bb4f48e1ca96d30eced23b6fe5b875ca6481056848be0fbc26bcbffdfe966da4221103408f459ec1ef12c72068bc1b96df045d3fa12cc2a9dcd162ffdf876b3bc3a3ed2373559bcbe3f470a8c695bf54796bfe471cd34b463e9876212df912deef882b657954d7dada47

という、21ブロック(336byte)の文字列が見つかる。
これが攻撃対象の文字列と考えられるので、これを復号してやる。
やり方はNEOのときと同様に。

qs = "3ed2e01c1d1248125c67ac637384a22d997d9369c74c82abba4cc3b1bfc65f026c957ff0feef61b161cfe3373c2d9b905639aa3688659566d9acc93bb72080f7e5ebd643808a0e50e1fc3d16246afcf688dfedf02ad4ae84fd92c5c53bbd98f08b21d838a3261874c4ee3ce8fbcb96628d5706499dd985ec0c13573eeee03766f7010a867edfed92c33233b17a9730eb4a82a6db51fa6124bfc48ef99d669e21740d12656f597e691bbcbaa67abe1a09f02afc37140b167533c7536ab2ecd4ed37572fc9154d23aa7d8c92b84b774702632ed2737a569e4dfbe01338fcbb2a77ddd6990ce169bb4f48e1ca96d30eced23b6fe5b875ca6481056848be0fbc26bcbffdfe966da4221103408f459ec1ef12c72068bc1b96df045d3fa12cc2a9dcd162ffdf876b3bc3a3ed2373559bcbe3f470a8c695bf54796bfe471cd34b463e9876212df912deef882b657954d7dada47"

xs = """
=67acd06f7f7b28762310ce1213fccb11997d9369c74c82abba4cc3b1bfc65f02
=a90ca309b638f6d2c43bf3ceddb72c7e6c957ff0feef61b161cfe3373c2d9b90
=19a50e949a9e12ca51b680074d53abe15639aa3688659566d9acc93bb72080f7
=325ddb45f355f21ea0dfb10bce43b097e5ebd643808a0e50e1fc3d16246afcf6
=9089a03ce2f77b24d1995e6f5a1dcc9288dfedf02ad4ae84fd92c5c53bbd98f0
=f0aadd905ba0dafd83e5f5ba4d8de9c08b21d838a3261874c4ee3ce8fbcb9662
=f843b158c7596f16b58e449188fbeb178d5706499dd985ec0c13573eeee03766
=ee34773ee8e79f9475772441908b6f42f7010a867edfed92c33233b17a9730eb
=847a7ff24ead84a2b20247c45bee43924a82a6db51fa6124bfc48ef99d669e21
=6ae7c5eb319f1550c6baf9c9aa45a94c740d12656f597e691bbcbaa67abe1a09
=6e546c551c3b17097fc3cdc40bde6260f02afc37140b167533c7536ab2ecd4ed
=cc1a9a46767267074fb26e16c792a38937572fc9154d23aa7d8c92b84b774702
=4f674fb564345dce08e4f68836022461632ed2737a569e4dfbe01338fcbb2a77
=1259a7104a29e8298e9e23408ddd5f47ddd6990ce169bb4f48e1ca96d30eced2
=b9a9a97e9459db3e3c95bfe2e336bbba3b6fe5b875ca6481056848be0fbc26bc
=5b1e9bcc00be5db1611778cc7a8c55c3bffdfe966da4221103408f459ec1ef12
=c29d8ff214d65e643327f621e6f18b6ac72068bc1b96df045d3fa12cc2a9dcd1
=b2100dc26fe3bd783446df5bf2dabeb862ffdf876b3bc3a3ed2373559bcbe3f4
=029ba0f0094aa3db94504335f9b29e8d70a8c695bf54796bfe471cd34b463e98
=14d1a0e0814e6371e45d06c9515c248276212df912deef882b657954d7dada47
""".split()
xs = map(lambda d: d[1:],xs)

ts = ""

for s in xs:
	s = s[:32]
	ta = qs[:32]
	qs = qs[32:]
	be = ""
	for i in xrange(16):
		a = int(s[i*2:i*2+2],16)
		b = int(ta[i*2:i*2+2],16)
		be += chr(a^b^16)
	
	ts += be

print ts
"""
In cryptography, a padding oracle attack is an attack which is performed using the padding of a cryptographic message.
hitcon{H4cked by a de1ici0us pudding '3'}
In cryptography, variable-length plaintext messages often have to be padded (expanded) to be compatible with the underlying cryptographic primitive.
"""

Let's Decrypt

CBCモード理解してますか、という問題。

こっちから暗号化された値を送ると向こうでAES-CBCで復号してくれるサービスが与えられる。また、文字列 'The quick brown fox jumps over the lazy dog' を暗号化した値も返してくれる。鍵と初期化ベクトルとしてどちらもflagを使われているので、それを当ててください、という問題。

CBCについては、暗号利用モード - Wikipedia が分かりやすい。
CBCは16byteのブロックごとに処理しているので、まず、'The quick brown fox jumps over the lazy dog' にパディングを足して48byteにする。(各ブロックをC[0],C[1],C[2]とする) これを暗号化すると48byteの文字列が返ってくる。(各ブロックをD[0],D[1],D[2]とする)
ここで、初期化ベクトルをIVとすると、各ブロックに対して、

C[0] = dec(D[0]) ^ IV, C[1] = dec(D[1]) ^ D[0], C[2] = dec(D[2]) ^ D[1] 

の関係がある。
さて、たとえば復号文字列として、D[1]+D[0]+D[1]+D[2] を送ってみると、64byteの復号化された文字列が返ってくる。(A[0],A[1],A[2],A[3]とする)
このとき、

A[0] = dec(D[1]) ^ IV, A[1] = dec(D[0]) ^ D[1], A[2] = dec(D[1]) ^ D[0], A[3] = dec(D[2]) ^ D[1] = C[2]

となっている。C[2]は正しくパディングされているのでA[2]も正しくパディングされていて、向こうでdecrypt-errorになることはない。
さて、ここで式をよく見てみると、

IV = A[0] ^ dec(D[1]) = A[0] ^ C[1] ^ D[0] 

となっているが、A[0],C[1],D[1]は既知なのでこれらをXORすればフラグが得られる。

#coding: utf-8

import struct, socket, sys, telnetlib, os,time

	
def hex2s(s):
	ls = len(s)
	res = ""
	for i in xrange(ls/2):
		res += chr(int(s[i*2:i*2+2],16))
	return res


"""
The quick brown The quick brown 
fox jumps over the lazy dog

4a5b8d0034e5469c071b60000ca134d9
e04f07e4dcd6cf096b47ba48b357814e
4a89ef1cfad33e1dd28b892ba7233285

"""

a = '4a5b8d0034e5469c071b60000ca134d9'
b = 'e04f07e4dcd6cf096b47ba48b357814e'
c = '4a89ef1cfad33e1dd28b892ba7233285'


def getunt(c):
	global sock
	res = ""
	while res=='' or res[-len(c):]!=c:
		res += sock.recv(1)
	print res
	return res

def send(s):
	global sock
	sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
	sock.connect(('52.69.125.71', 4443))

	getunt('decrypt\n')
	sock.send('2\n' + s + '\n')
	s = sock.recv(1024)
	s = hex2s(s)
	print s
	return s

ta = hex2s(a)
tb = hex2s(b)
tc = hex2s(c)

tx = send(b + a + b + c)

gx = tx[:16]
ty = 'fox jumps over t'

def zxor(p,q):
	res = ""
	for c,d in zip(p,q):
		res += chr(ord(c)^ord(d))
	return res

s = zxor(zxor(ty,gx),ta)

print s
|	
#hitcon{R4nd0m IV plz XD}

Sharingan

AIが天元に打ったあとマネ碁をしてくるので、相手より石を多くとれ、という問題。
ただし、相手の石が取られそうになると、自分の石が相手の石に置換されてしまう、という仕様。
ヒカルの碁、の3巻あたりにあったマネ碁破りの方法を利用する。

+++++++++
+++○○○○++
++○●●●*○+
++●○●●○++
+●+○○○●++
++●●●●+++
+++++++++

対称に打っていくと、上の盤面のようになる。
ここで白が*に打つと、AIは取られると判断してそれを黒石に置換するが、それでも囲われているので取られる、という仕組み。

Flame

powerpcの64bitバイナリをreversingする問題。

powerpcバイナリを動かせるgdbとかのデバッガがあればあっという間に解決していた筈なのだが、それを入れるのに(僕とかyamaguchi氏とか)めちゃ苦労していて、ずっとほったらかしにされていた。yamacuchi氏からobjdump結果を貰ってそれをもとに解析した。

powerpc語になれていなかったのでわりと勘で補ったところがあるが、主要部分は

srand(7777);
unsigned int data[35] = {どうやら初期化されてるみたい};
for(int i=0;i<35;i++){
  data[i] ^= rand();
}
char s[36];
scanf("%s",s);
if(strlen(s)==35){
  for(int i=0;i<35;i++){
    if(s[i]!=data[i]){
      //たぶんWrongとか表示してexitするやつ
    }
  }
  //たぶんCongratsとかがこのへんで表示されそう
}

だいたいこんなかんじ。デバッガがあれば適当にメモリを覗くだけで済むのだがそうは問屋が卸さない。

まず、"qemu-ppc -d in_asm flame"で実行時のトレース結果が一緒に出るので、それを元にして解こうとしてみる。具体的には、先頭の一致文字数が長いほどトレース結果が増えるはずなので、まず先頭の1文字を全通り試して1文字目を確定させる->2文字目...みたいな感じでやっていこうかと思ったのだが、なぜかqemuの挙動がおかしくてうまいこと動かない(i=1のときにi<35がfalseと判定されているっぽい)。のでこの案は失敗。

さて、readelfの結果を参考にしつつ、ELF中の初期化データが置かれてそうなとこを探ってみる。と、

...前略...
0078970: 7420 796f 7572 2066 6c61 6720 3a29 0000  t your flag :)..
0078980: 596f 7572 2066 6c61 6720 6973 2069 6e63  Your flag is inc
0078990: 6f72 7265 6374 203a 2800 0000 0000 0cfe  orrect :(.......
00789a0: 0000 0859 0000 095d 0000 0871 0000 040d  ...Y...]...q....
00789b0: 0000 0006 0000 0ade 0000 0fa8 0000 0561  ...............a
00789c0: 0000 09da 0000 0878 0000 0682 0000 0fa9  .......x........
00789d0: 0000 0f5f 0000 025e 0000 0db0 0000 0fbf  ..._...^........
00789e0: 0000 0bc6 0000 0d38 0000 095d 0000 0d09  .......8...]....
00789f0: 0000 07ed 0000 0307 0000 01c0 0000 0399  ................
0078a00: 0000 0956 0000 0a45 0000 0292 0000 0c8a  ...V...E........
0078a10: 0000 092f 0000 004a 0000 0964 0000 0194  .../...J...d....
0078a20: 0000 09da 0000 011f 2e2e 2f63 7375 2f6c  ........../csu/l
0078a30: 6962 632d 7374 6172 742e 6300 5f5f 6568  ibc-start.c.__eh
0078a40: 6472 5f73 7461 7274 2e65 5f70 6865 6e74  dr_start.e_phent
0078a50: 7369 7a65 203d 3d20 7369 7a65 6f66 202a  size == sizeof *
0078a60: 474c 2864 6c5f 7068 6472 2900 4641 5441  GL(dl_phdr).FATA
0078a70: 4c3a 206b 6572 6e65 6c20 746f 6f20 6f6c  L: kernel too ol
...後略...

のようなものがある。0x789cから0x78a24に謎データが載っていて、これの長さがint配列で35なので、これで試しにデコードしてみる。と、フラッグが復元された。

x = """
00789a0: 0000 0cfe  orrect :(.......
00789a0: 0000 0859 0000 095d 0000 0871 0000 040d  ...Y...]...q....
00789b0: 0000 0006 0000 0ade 0000 0fa8 0000 0561  ...............a
00789c0: 0000 09da 0000 0878 0000 0682 0000 0fa9  .......x........
00789d0: 0000 0f5f 0000 025e 0000 0db0 0000 0fbf  ..._...^........
00789e0: 0000 0bc6 0000 0d38 0000 095d 0000 0d09  .......8...]....
00789f0: 0000 07ed 0000 0307 0000 01c0 0000 0399  ................
0078a00: 0000 0956 0000 0a45 0000 0292 0000 0c8a  ...V...E........
0078a10: 0000 092f 0000 004a 0000 0964 0000 0194  .../...J...d....
0078a20: 0000 09da 0000 011f
"""

y = """
205757590
998377520
1430092073
2047191058
1959523426
1763442792
1345239717
793358328
658433361
1016199565
1294268491
1322964720
2137247737
1405325116
642114049
1392987601
988381069
740379636
1285459211
1904974096
943865137
605738913
1559909246
926847391
1442292648
425531748
1307965978
1673880289
860617914
1317232
831869049
1066375504
999694753
114477475
966082914
"""

x = x.split('\n')
x = x[1:-1]
tx = []

td = []
for i,d in enumerate(x):
	d = d.split(' ')
	d = d[1:]
	p = 4
	if i==0:
		p = 1
	elif i == 9:
		p = 2
	for j in xrange(0,p):
		td.append(d[j*2+1])

y = y[1:-1]
y = y.split('\n')


s = ""
for p,q in zip(td,y):
	q = hex(int(q))
	p = int(p,16)
	q = int(q[2:],16)
	
	s += chr( (p ^ q) & 0xff)

print s

#hitcon{P0W3rPc_a223M8Ly_12_s0_345y}

I'm here

yamaguchiプロとcookiesプロのペアがやってた。解説は彼らに任せる。
僕も手元でいじったりしていて、pythonでサーバとの通信部を書いてそれを渡したりしていたのだが、自分が出力部を適当に書いていたせいで、なぜかコアダンプが途切れてしまってflagが得られない、みたいなバグを生み出してしまっていた。申し訳ねえ。(自戒の意味をこめてメモしておく)

angry boy

申し訳ねえシリーズ第二弾。自分の書いたスクリプトをhakatashi氏に並列化とかいじってもらったりしていたのだが、書き方がひどかった(自分の書くコードはたいてい目が腐るといわれてしまう)ためにいろいろと面倒くさいことになってしまった模様。

RegExpert

moRE

今回のesolang部門。与えられた要件を満たす正規表現を作って送りつける問題。人々の間でonigurumaとか田中哲スペシャルとかの用語が通じるようになっていたのは面白かった。

「正規表現」に無限のパワーを与える"田中哲スペシャル" - Atzy->getLog() とか、回文や XML にマッチする鬼車の正規表現 - まめめも とかを参考にした。Rubular: a Ruby regular expression editor and tester ここがテストとしてよいそう。

自分の関わった部分についてだけ。

^(?<p>(a\g<p>b|ab))$

a^nb^nにマッチする正規表現。(反復補題とはなんだったのか...)
\gを使えば再帰ができるので実質文脈自由文法と同じ能力になる。
あと、これを12文字以下にする必要があったが、そのへんはmoratorium氏にまかせた。

^(0|[1-9]\d*0000|(4|8|(([1-9]\d*|)([13579][26]|[2468][048])|[1-9]\d*0[48]))(00|))$

うるう年のみにマッチする正規表現。つまり x%4==0 && (x%100!=0 || x%400==0) ですね。
x%4==0 || x%400==0をまとめることができるので縮まる。

^(?!(xx+)\1+$)xx+$

xが素数個ならんだ文字列(xx|xxx|xxxxx|.....) に対応する正規表現
文脈自由でさえないので、どないすればええねんという感じだったが、ぐぐるとこれ (java - How to determine if a number is a prime with regex? - Stack Overflow)
が出てくる。?!内の(xx+)\1+が合成数にマッチするので、これを用いれば動く。

^(?=[01]*,[01]*$)(?=((?<u>(.,.|.\g<u>.)))$)(?<w>(|(?<s>(0|1))\g<w>)),(?<t>(|(?!\k<s+0>).\g<t>))$

001,110とか、010100,101011とか、前半と後半がビット反転の関係にあるもののみにだけマッチするやつ。
本質は

^(?<w>(|(?<s>(0|1))\g<w>)),(?<t>(|(?!\k<s+0>).\g<t>))$

の部分で、左側にある?<s>でキャプチャされた部分と同じ再帰の深さにあるとこで、右で\k<s+0>がキャプチャされる、みたいな?(自分でも原理はよく分かっていなくて、適当に動かしていたらうまく動いた、という感じ)これだけだとコンマの左右での文字列長が違っていてもマッチしてしまっていたので、前半をとりあえず書いてみたが、これでは長いと言われてしまい、あとはmoratorium氏のショートコーディング力におねがいした。

moREは、4問解いて終いかと思ったら、flagがregexp形式で出力されてきて焦る。残り20分強くらあったが似非solverを書ききれなかった...(終了30分後くらいにフラグが得られた)

bef = r"""
^([[dKSbqJWjnuhQ}iyfspkUPY HBFxtRE{GCLOXwoNcv]&&[^dqEpDvkz\-}BPoIrXFW ]&&[^Oo zE}PvdBl\-:DkcUXifjnLMueryg]&&[^EmlpD}TYbiaNonudjHAwzCUcQkxf{vSWFrXgIOBV]&&[f:VLxUeGFYMEoaWyPchBbvA]&&[^XsZjFxQ:wAgqiE{er\-fODTd]&&[^EtZlYUze\-G{JgyVcfknDSXCRo:jx]])([[srkgOMniDpXEujfdVwBYUKJmWAQ{Sqh\-oRa b]&&[IVyWRAJBxiGkDoefLQt]&&[^Y:PsuMK br{mjZkgG]&&[^KVcqnRYdojLQXsrBlzeyDI gbStGZ]&&[ ZEMnjAbkH{iQKmzgDtTsFpxXI:uCvfUVdqSlBwYP]&&[^qsbGCEn:NFDhyU{]&&[^}\-zWEAOTJSMrIaPHChvN{Y]&&[tvYkLJrTiAxeVnHmjQ I{FpRqESyzONlKCWg\-cX]])([[^Ssk}\-mqKUOARXIuZLgDpHeM]&&[OFxcVeqJHbtYvmuza]&&[jKHYwgPpsntbkCdl\-UxBTZFaVGzSOrvem]&&[^gKyqRLDMcA kWmlHEJGPXSdxeZ\-F:sobz}rC]&&[pRwAFqeKc{jnzU ClmNOhiYWPxytVbufX:GTg]&&[^zmUMVNk}SWCiDGLFTP:Xsea\-]&&[\-QVjC:woRJtFAvkIbEKGYi{DLaxf]&&[PVcx wFZNuklmqbzshpedGf}tWSaTXo\-OiL]])([[^xNFB:TzpysbwA ]&&[^wyNXgCKLTMIbAtRU]&&[^eGIdM SroOjLpDVNatWA\-JKqCwU]&&[xUEnXRGLmCHkdTMuBZeSqc}yh:IpwlQA]&&[TC\-pUB{xIlH:sPaKvkoDQeAXiMWnJNGVrLy hFR}cS]&&[BFVabZicAu sEqmLxdTP]])([[td\-{kaP iEFWqCZlOomnSVeG}]&&[mAzYtkBZjEH oWligRncIhNs}]&&[vYeb\-VAg:oQSRwjMkd]&&[IPgS}kr DiazyxudVHneNsEcmoQRBtbMGKhWq]&&[QNkdSTWKF vBoqPXJrItayA]&&[aPL{AQ:RJ\-fFrETKel}unxpYBmVq vwoSOdUIbCjtH]])([[^Xm fQlHLDeGJtwqgCTxAB]&&[^Odhsi{lPbyotmRFkzHcAf XEIuGVKYaeUWJwgjZpM]&&[^FgG}sPyXEdTwWxvcrCUjN:\-M]&&[^abJd\-IFyWeEixGM{V:ATrOqLposcvNU ]&&[ukRGnoW VBK}yq]])([[nzK{aRQwqYIsZvuMxyO:GUFWb\-lrSc]&&[DULOQ{IxBgRAhymMJe]&&[^tuEybwanKZhJOVlUQ\-ioRM XfvqP:NrdcIDzAxeH]])([[PujVDm:fOxEygG{sIbJkRnrC\-}HSaUlXdMBZLYio]&&[^MiWlhQtrfDodTHGS]&&[RzwgjWbda}SDUcXHfBAos{mI\-lQOtYJ]&&[^vZQBsXYo{VxjCpFyD]&&[\-emjNSv:LPkVta}IoTzdYGKCDq{fQnJhRybUZAOF]&&[iHPGNJkaScdY:BtIRVmXOw}M]&&[Z RkohALFygUut}NYdmGQprEeIWwxqs]&&[nDUCkRQLlqTPHstyhxoA\-Guap]])([[^T\-DkmjSx{zGO CLB:FZEiIVKUfqH]&&[JbR qf:ey{jQOrVBM]&&[BHQcfZr:iyovVLPJRptgM}FGX{neSulwT]&&[^Pag}fD:vu LHdRoYshziXTQFmpZCtlwG]&&[vL fI{iYMHbj:NVDck\-ZeRUQ}PqBTpAuhFCGKJsO]&&[^SpOVGYWwKZHsravMnIkDci:uogPjAXxBCUfbqRQEy]&&[^VIEGU:jvyhQw{xsioSgWTdPDcZrJRB\-HLKOA}lmzM]])([[YOepxMTni{sFR UdlkhtJrKo:ZDHXEzASgGVf]&&[zXJlpWqfhswme{vUVd\-ZL}KQoItyYSbaR:OGE]&&[^EpAWqdDONwLTtCkm ZMsy]&&[^kpd\-nASNDaLvWhmMyEeYJoHjGOTziX{IF l]&&[^bse{rtKxY\-kyOd]&&[^QKMdVsRvaq}AyCHneglrXDTcSo{UIbZFNOj]&&[ivfpnNSbIROhCj\-MDuwygazmqxoPL:KGAc]&&[GnCOM}DsfxoBSUzHItXFQiPEpVbdkq:hRcTJLeg]&&[^hDtfnY\-KZgRLSFz]])([[JYOmFnZCMyLoQGNXz}kUgDdW A{wscevhbIRqSE]&&[^aJdQXmlVHroTfw]&&[^vzeKuJiFGST\-cDm jVqCdNy:]&&[^kDLtoJsfixvMXpVE SBRd\-AU:lQuqP}cYn]&&[^jeAMXfFpBlYO dWgShJRqv}TUNCbkzP]&&[qwGYZmefjtJNbL:gyuiKPsMn}BprTDIkRFocvx]&&[^tMI:U}uzkK\-Ogad]])\9([[^tAjm\-WcNe{STqiwlEfPhQ}:nXoCkxFu]&&[gmvMKIUSAFXxaEd{\-N bwo:RGCkeyVQrPOqlcD}u]&&[gJx u:YONUlbM{CKrocsk]&&[gJHCARb\-Z WnfTGzjp:MhYaFseVwSrli]&&[^}GUxR{yKl\-AfMXiFOYNHkw]&&[^xAUOIVozPv\-gQJsjLSe]&&[^U}QipGex{quvHDZ JA]&&[^YRFsayHbzjQ:CL\-tDxlpN]])\5([[S\-kYJaogmdW{cVK}AFCsnf Irqile:X]&&[fBQFUpGkInrVHS{JCujcwM ZiL}\-RWvdy]&&[u\-PnYjdrtB colfQHOIDKSbZUiJ{]&&[^E}uHVzplmiIvaFCZksy:AnWMeo]&&[^gmu}\-eJXlTqIZL]&&[zKVJgdFDEvcLksjYBHmGRWTiPlwMOSXC :bt}Z]&&[URKEWj\-qx{ekAglQ:DozcaMtHsB hPFCYZu]&&[^ARlmN}TuUZ{fFhsX:iJ]&&[^LVdTwsPjaRQGpJYcXeMHuxEBZ{q\-kKlFWmtg]])([[^TeW{vc}rJCqVgyHOPZpwM]&&[^xnevtzrilpJXHISOTdGCumAwqEsU]&&[hTFAEIaNMuyXHe:QiSr\-fLm}vbYUD{RkJBgKq x]&&[XCLNRxtPivVnhBKu\-olwpYsEWzkUMqaeGT{]&&[kCVXKEPwQWDh{qYmBOgZUlIaRHN:jJv\-bTxMncs ]&&[^dQqWLhNBmjCtoOYyGTSMFzVRli}rvHgkA ]&&[^{dUaK}t:gLFlfVEeTvmCNIxqZYijnJokspWcAHbSX]])([[^wEaDvpNlILVQAXGu]&&[^rDnApNtPmeVUuLoJQ}FRBKwqy O]&&[^\-eE:YlaJk}yRoLWugzdVZPT MDvrqHUGn]&&[^n}zejcgb{Gsfk\-J NaiolwEYWDHdLTM:VmyXAvpQq]&&[nckSa}mzWJU:BxPwltY{TVMsvXpoGeiOI]&&[akS\-Iy}mvL{lWU:GNDHQKYATCsErdgpzOM wX]])\3([[^}KWdlCNqGHBjJhsDIMrAEp]&&[^mFnOYG iXrjVdT]&&[^E B\-AzxKQX{SyvJb:gIRqkdUhtNG]&&[u{noSO}Kg\-WDYp:javyV]&&[^eHBZVpkxUFCw:f]&&[ WPRGxOuBimLkYc:wsadqf}lyJzvDUnNAQKbVIj\-e]&&[JNwKD{aUoie qEyWrpPkZBFTh]])\12\3\2\6([[aHcCmUkIfQtVgEGl hxYXFiuKeSLZ]&&[xefFIqAgSaYMuGs]&&[^uGLnsoDclFqhIQbfvOWix{ezHJV aZ:ytUpmYTw]&&[ITtQmBnJSUgNDV}hAWXGMsureERFL]&&[^ldLBEXwC{tP H:zyIKODU]&&[^OEVYTbFq hHed\-KcXw]&&[^SxtJGvPc\-XDFKRsYZanur]])\13([[wLPkKCduRy\-aMOlmbiFEZWXvIGJjoDct]&&[EDrC}I{xBT\-hcabNusAPFneqJOX:ki j]&&[xiFIYQMDLGHlmV{a\-XyZP]&&[^uG s}XCzqnTKBvH]&&[nzLdajUB{CmwySsAROk\-QKFPMxftv}olDi]&&[^DjqEMzyRhuSZJxbWQsLvONUCG Vfk:KmdYaw\-TnitH]&&[Qd{PUywXOpxzurml]])\12\5\17\12\16([[PBr{mqMZFhUazHpOxKSfondtV}TkICRbLGg:yD]&&[joDyrlszYQNUcSfhmVnPuEHb]&&[A:DBcWzNsnmX JCLTaxOVSH}fYZqro]&&[x:nR{DMCNGKlAqSvemziYufHFw dc}ZsLkQbWryh]&&[WrHQ\-EezlgLwNPT}pUCFicMoa:jtDfmXbyRB]&&[rsIwzLy{HVCKtkAndxOlRF TXmNZQafjBUPGJ:pMc}]&&[^CUtQDsIjhNF \-nlpiAVHuBRYEoKXdwS{yLaGf]&&[kYphKuSL}emn{wxOVTrCNJHoIfUavXAD]&&[{oIxVNXZHiM\-AwcjsdCOtmFzB]])\19\2\6\17\13\2\6\13([[LC Awgo:OBe\-hNTtuKaSbqzlcG]&&[^FxTbDHLga}UWjyOtXh\-RqeMzdflPVJnImBYkCiN]&&[mkOlsoBhb:{TiuNPeHqLnY}MgZ\-UfAvQz]&&[^r\-dOsbDVPcyiSwUXRh FoCLWIvQuza]&&[^bVJUOwlNjPdzBCeZa{GkHEgWchr]&&[REg{W oUv:VnmwAXa]&&[^rnqgfEcmetLih}JKUbTZW ON]&&[^NxDRsYGZyjatCoqXPWr]&&[^WkXcKVYSjTf{ydnupPUbwqtMGJhONQRv}DHg:ei L]])\6\5\3\1\9\12\13([[Ay MDBhsCnWTGfrcoqF}N\-ZUQixmRkzbpYud]&&[^GENTDZQe\-PnVxIdJAMBjOcCz:Xp FyHbgRraf]&&[znksUoR:JjEDBpSNChQWZ f}OYiwugXA\-y]&&[^YQZPzcVluyn}qe:SDBbtIUNd iO{r]&&[^UEGPoLdriVzNglYmyObTnv :]&&[^UYdtg{PbaZHOjlFi:rQycEIvVBx\-sADCLS}R]&&[^hON{U\-lbyEJASYLoGD]&&[osuJSiHrN{htdUDGaZWPImM:FBQ bYOA]])\5\12([[^EVFSeGNrbDCaM{KmLh\- YHdopOsInfXW}]&&[^XGSh}Ha:eADCPpcEZrjidzOMBUImwQWon sL]&&[v{dOApXUfG}haeqS\-DJyW:KHNoTzElkgYiImVFBucC]&&[^MmPebn:Q KhsDz]&&[^Kuog {OPQXivtTWzhDC}GSfcM\-k:wLAY]&&[FQiLqbSJwesUhf DuARlZdaIGg]&&[^FOLsfqRUIcCV{jJYmodivN}xAHPpy]])([[^CX:OBWnHboDhzi}F]&&[nrpgbcqI lTCQAowdZfmEGKyij:tPHhDU]&&[^sgLvMFGSR{quCTpBQKcProyA]&&[^mF:ZAoskhfgKwH]&&[MqiJYyR:SWDQpd v}rKwsmEcXHTzZtgakf{Gju]&&[^Ko\-psGakrVg:nYAiuFSxEXwbmehOM qNHURT]&&[cRydhm{iQDKaTvFeIAnBqWlwLt:GOs]&&[^lpgFNLIDZJKuzXT:Pf]&&[TzUePJX{\-ausnEicyWwdA}rIVRgMHNLQ:kKbDxSh]])\14([[^eSwrLVByhniCQvDsAcIlxfmNUWuMzToHKpGd]&&[}vNOcwzmipquLHtJah:rTfyZXl KBGCMSbUYe]&&[^kWsTvGqrV\-mfMac]&&[^ZLmIfqdnjCzRXrQYsbBWv\-UJ:plu]&&[jOV}CaWBkMKuFvcESLhsilz{YNydmfQRUXDxJ:ZtP]&&[jLzqHRo{:kabdrK}ZUsQCGiuA\-mecExvgShwMFJOyt]&&[EtRYlumkyHDUTz:Ve}i\-nBJdcOqKZpWXNFbxShfs]&&[^IxRqKplz:fYoerTn uCMDiJVyNUAQE]&&[^z{AqXkswgMfaJdOIN:PjytRebU]])$
"""

inde = 0

def ins(s):
	global inde
	return inde * ' ' + s 

def spka(s):
	s = s[1:]
	d = 1
	r = ""
	res = []
	for c in s:
		r += c
		if c=='[':
			d += 1
		elif c==']':
			d -= 1
			if d==0:
				res.append(r)
				r = 0
	return res


def toa(ss):
	res = ""
	for s in ss:
		s = s[:-1]
		a = [1] * 256
		p = s.split('&&')
		#print p
		for d in p:
			d = d[1:-1]
			#print d
			if d[0]=='^':
				d = d[1:]
				for c in d:
					q = ord(c)
					a[q] = 0
			else:
				ta = [0] * 256
				for c in d:
					q = ord(c)
					ta[q] = 1
				for c in xrange(256):
					a[c] *= ta[c]
		
		for d in xrange(256):
			if a[d]==1:
				res += chr(d)
				break
	#print res
	return res

rs = [""]
i = 0
ps = []

ans = []

for c in bef:
	if c=='(':
		print ins('(')
		inde += 3
		if len(rs)>0:
			po = rs.pop()
			print 'naka ..',po
			ans.append(po)

		rs.append("")
	elif c==')':
		g = rs.pop()
		#print 'g .. ',g
		#print ins(g)
		g = spka(g)
		g = toa(g)
		ps.append(g)
		ans.append(g)
		print ins(g)
		print g
		inde -= 3
		print ins(')')
	else:
		if len(rs)>0:
			rs = rs[:-1] + [rs[-1] + c]
		else:
			rs += [c]
	i += 1
print ps
ans = ans[1:]
print ans

ta = ""
for d in ans:
	if d[0]=='\\':
		d = d.split('\\')
		d = d[1:]
		for x in d:
			p = int(x)
			ta += ps[p-1]
	else:
		ta += d
print ta

#hitcon{Re:Zero -Starting Programming in Another World-}

時間内に通したい人生だった。

感想

集まってやると、知見がその場で共有できるし問題を解くやる気が大いに向上する(個人比)のでとてもよかった(ただし徹夜は判断能力を奪う)。
終わってみるとチームでいろいろ解いたように思えるが、実際は日曜の晩とか、6時間ほどだれも得点しない、みたいな状況が生えていたりしたのでもうちょっとすぱすぱ進められるようになりたい。あと、結局最後、angry boy も moREも1時間ほど間に合わなくて得点できていない(650点が得られなかった)みたいな感じだったのでずいぶん心残りである。
自分はpwn力をわりとつけたと思っていたのに全く解けなかったのでなんだかなあ、と。64bitELFを読む根性をつけるか、読みやすくするツールを導入するべき。あとヒープがてんでだめなのでどうにかしたい。
SECCONに向けてもっと力をつける必要を感じた。