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とか田中哲スペシャルとかの用語が通じるようになっていたのは面白かった。
正規表現超絶技巧プログラミング力を高めた
— じんの (@moratorium08) 2016年10月10日
「正規表現」に無限のパワーを与える"田中哲スペシャル" - 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に向けてもっと力をつける必要を感じた。
