この大会は2019/3/8 21:30(JST)~2019/3/10 21:30(JST)に開催されました。
今回もチームで参戦。結果は2525点で499チーム中26位でした。
自分で解けた問題をWriteupとして書いておきます。
Cookie Monster (Web 100)
Cookieのflagはmd5の値がセットされている。ページを更新すると、その値は変わっていく。md5逆変換すると、2文字になるようだ。これを前提にmd5の元の文字をつなげていく。
import requests import hashlib import itertools import string url = 'http://159.89.166.12:13500/' h_list = {} for c in itertools.product(string.printable, repeat=2): text = ''.join(c) h = hashlib.md5(text).hexdigest() h_list[h] = text s = requests.session() flag = '' for i in range(24): r = s.get(url) flag_val = s.cookies.get('flag') flag += h_list[flag_val] print flag
pctf{c0oki3s_@re_yUm_bUt_tHEy_@ls0_r3vEaL_@_l0t}
Welcome (Forensics 50)
jpgの後ろにzipが入っている。解凍すると、d.zipが展開される。さらに解凍すると、a.zipとsecret.bmpが展開される。a.zipはパスワード付きzip。secret.bmpはbmpではなく、末尾の方にBase64文字列がある。
$ echo dGhlIHBhc3N3b3JkIGlzOiBoMzExMF90aDNyMyE= | base64 -d the password is: h3110_th3r3!
このパスワードでa.zipを解凍すると、a.pngが展開される。これをStegsolveで開き、Blue plane 1を見ると、フラグが書いてある。
pctf{st3gs0lv3_1s_u53ful}
Magic PNGs (Forensics 100)
pngのヘッダが壊れているので、以下のような修正をする。
5バイト目:2E -> 0D 7バイト目:2E ->1A チャンク名が小文字になっているのを修正:idat→IDAT 各チャンク:CRCを修正
これでpngファイルが見れる。
上下反転すると、文字が読める。
h4CK3RM4n
またtEXtチャンクにmd5_MEf89jf4h9と書いてある。
$ echo -n h4CK3RM4n | md5sum 2c919f82ee2ed6985d5c5e275d67e4f8 -
このmd5の値でtryme.zipを解凍すると、flag.txtが展開されフラグが書いてある。
pctf{y0u_s33_m33_n0w!}
Slow Realization (Forensics 200)
jpgの後ろにmp3があるので、Audacityで開いてみると。モールス信号があるのがわかる。
.--. .- - .. . -. -.-. . .. ... - .... . -.- . -.-- .--. -.-. - ..-. -. ----- - .... ...-- .-. ...--
デコードする。
PATIENCEISTHEKEYPCTFN0TH3R3
mp3をサポートしているステガノツールをいろいろ試したがうまくいかない。mp3側を確認するのをあきらめ、もう一方のpdfを攻めることにする。パスワードがかかっていたので、クラックできないか試してみる。
>pdfcrack --wordlist=rockyou.txt flag.pdf PDF version 1.4 Security Handler: Standard V: 2 R: 3 P: -1028 Length: 128 Encrypted Metadata: True FileID: 936f22840118a542401db0b9716930c8 U: c6417694dd485620f1629c6ae47a795700000000000000000000000000000000 O: ed2fd42c99e91c38c42eff249cacb3f968f3605be0ee9dc8586d5d38ab06c7f5 found user-password: 'congratulations'
このパスワードでpdfを開くと、フラグが書いてあった。
pctf{y0u_h34rd_m3_r1ght}
Spoiler (Cryptography 50)
pdfの%%EOFの後ろにデータが入っている。これから0を削除し、デコードしたものが鍵。PDFに書かれているhexデータのデコードとXORをとる。
enc_key = '0000006a0000006f0000006e000000730000006e0000006f000000770000006900000073000000640000007200000061000000670000006f0000006e00000062000000790000006200000069000000720000007400000068' key = enc_key.replace('0', '').decode('hex') print key enc = '3a2c3a35152538272c2d213e332e3c25383030373a15'.decode('hex') flag = '' for i in range(len(enc)): code = ord(enc[i]) ^ ord(key[i]) flag += chr(code) print flag
PCTF{JON_IS_TARGARYEN}
Add them Sneaky Polynomials (Cryptography 100)
xのn乗のnがビットの位置を表していると推測して、p,q,rのxorをとる。
def poly_to_str(p): pt = p.rstrip().replace('+ x +', '+ x^1 +').replace('+ 1', '+ x^0') pt = map(int, pt.replace('x^', '').split(' + ')) bin_list_p = ['0'] * 408 for p in pt: bin_list_p[p] = '1' bin_list_p.reverse() bin_str = ''.join(bin_list_p) s = '' for i in range(0, len(bin_str), 8): s += chr(int(bin_str[i:i+8], 2)) return s def str_xor(s1, s2): return ''.join(chr(ord(a) ^ ord(b)) for a, b in zip(s1, s2)) p = 'x^406 + x^405 + x^402 + x^399 + x^397 + x^391 + x^390 + x^387 + x^386 + x^378 + x^374 + x^372 + x^371 + x^369 + x^367 + x^364 + x^360 + x^358 + x^357 + x^352 + x^350 + x^345 + x^344 + x^341 + x^336 + x^335 + x^334 + x^333 + x^331 + x^330 + x^329 + x^328 + x^327 + x^324 + x^322 + x^320 + x^314 + x^311 + x^308 + x^307 + x^303 + x^300 + x^299 + x^296 + x^295 + x^290 + x^289 + x^287 + x^279 + x^271 + x^266 + x^264 + x^262 + x^260 + x^257 + x^256 + x^252 + x^249 + x^248 + x^246 + x^243 + x^239 + x^238 + x^236 + x^233 + x^230 + x^227 + x^225 + x^223 + x^222 + x^220 + x^218 + x^216 + x^215 + x^209 + x^208 + x^207 + x^204 + x^202 + x^199 + x^190 + x^189 + x^185 + x^184 + x^180 + x^177 + x^176 + x^175 + x^172 + x^167 + x^166 + x^162 + x^160 + x^159 + x^155 + x^154 + x^149 + x^147 + x^143 + x^137 + x^135 + x^131 + x^129 + x^126 + x^124 + x^122 + x^116 + x^110 + x^108 + x^105 + x^104 + x^100 + x^99 + x^97 + x^94 + x^93 + x^90 + x^88 + x^87 + x^86 + x^85 + x^83 + x^75 + x^73 + x^69 + x^63 + x^62 + x^57 + x^54 + x^51 + x^44 + x^41 + x^38 + x^37 + x^36 + x^34 + x^29 + x^28 + x^26 + x^25 + x^21 + x^20 + x^19 + x^16 + x^15 + x^14 + x^13 + x^6 + x^5 + x^2 ' q = 'x^399 + x^398 + x^396 + x^393 + x^392 + x^391 + x^388 + x^386 + x^384 + x^381 + x^377 + x^376 + x^368 + x^364 + x^360 + x^355 + x^354 + x^353 + x^352 + x^348 + x^346 + x^345 + x^344 + x^343 + x^335 + x^334 + x^329 + x^326 + x^325 + x^321 + x^318 + x^317 + x^315 + x^314 + x^311 + x^307 + x^306 + x^304 + x^300 + x^296 + x^293 + x^291 + x^282 + x^277 + x^270 + x^263 + x^261 + x^260 + x^256 + x^254 + x^253 + x^252 + x^251 + x^248 + x^245 + x^242 + x^241 + x^239 + x^238 + x^236 + x^232 + x^226 + x^225 + x^222 + x^220 + x^219 + x^214 + x^209 + x^208 + x^207 + x^206 + x^202 + x^200 + x^196 + x^191 + x^190 + x^186 + x^181 + x^180 + x^178 + x^177 + x^169 + x^168 + x^165 + x^164 + x^163 + x^162 + x^161 + x^159 + x^157 + x^156 + x^151 + x^149 + x^148 + x^147 + x^146 + x^144 + x^141 + x^140 + x^138 + x^137 + x^136 + x^134 + x^133 + x^132 + x^130 + x^129 + x^128 + x^126 + x^123 + x^121 + x^113 + x^109 + x^103 + x^101 + x^100 + x^95 + x^93 + x^91 + x^85 + x^84 + x^81 + x^74 + x^73 + x^71 + x^68 + x^67 + x^54 + x^52 + x^51 + x^50 + x^48 + x^46 + x^45 + x^43 + x^39 + x^35 + x^32 + x^31 + x^30 + x^29 + x^21 + x^15 + x^14 + x^9 + x^8 + x^5 + x^4 + x^2 + 1 ' r = 'x^404 + x^402 + x^396 + x^389 + x^387 + x^386 + x^384 + x^382 + x^376 + x^373 + x^367 + x^366 + x^365 + x^362 + x^361 + x^358 + x^356 + x^355 + x^354 + x^353 + x^352 + x^349 + x^348 + x^347 + x^345 + x^343 + x^340 + x^334 + x^332 + x^331 + x^328 + x^327 + x^326 + x^322 + x^317 + x^316 + x^314 + x^313 + x^312 + x^310 + x^309 + x^308 + x^305 + x^304 + x^303 + x^301 + x^300 + x^299 + x^296 + x^295 + x^292 + x^291 + x^290 + x^288 + x^287 + x^286 + x^285 + x^283 + x^279 + x^278 + x^274 + x^271 + x^269 + x^268 + x^266 + x^265 + x^263 + x^261 + x^260 + x^259 + x^258 + x^256 + x^254 + x^252 + x^251 + x^250 + x^249 + x^244 + x^243 + x^242 + x^237 + x^236 + x^228 + x^225 + x^224 + x^223 + x^222 + x^221 + x^215 + x^214 + x^213 + x^212 + x^205 + x^201 + x^200 + x^199 + x^197 + x^193 + x^192 + x^191 + x^190 + x^189 + x^188 + x^187 + x^182 + x^180 + x^175 + x^174 + x^173 + x^167 + x^166 + x^163 + x^158 + x^156 + x^155 + x^153 + x^151 + x^150 + x^149 + x^143 + x^142 + x^140 + x^139 + x^136 + x^135 + x^133 + x^129 + x^126 + x^125 + x^123 + x^121 + x^118 + x^117 + x^116 + x^115 + x^113 + x^110 + x^106 + x^105 + x^104 + x^103 + x^102 + x^98 + x^95 + x^92 + x^89 + x^87 + x^85 + x^81 + x^80 + x^77 + x^76 + x^75 + x^74 + x^71 + x^70 + x^67 + x^66 + x^64 + x^63 + x^60 + x^59 + x^58 + x^56 + x^54 + x^53 + x^48 + x^44 + x^41 + x^39 + x^38 + x^35 + x^34 + x^31 + x^29 + x^28 + x^27 + x^22 + x^21 + x^20 + x^17 + x^14 + x^12 + x^11 + x^10 + x^9 + x^6 + x^4 + x^3 + x + 1 ' msg1 = poly_to_str(p) msg2 = poly_to_str(q) msg3 = poly_to_str(r) flag = str_xor(str_xor(msg1, msg2), msg3) print flag
pctf{f1n1t3_f13lds_4r3_m0r3_us3ful_th4n_y0u_th1nk}
The Order of the Phoenix (Cryptography 100)
Bill a-424b493442128adbeef5ce33f18c6c5996cdd97e4922644a4479bb4e05f8846f Charlie 8-1268bf4430c0b1a4c568a302da92421bc672aceb57fef3401f2434cfc3bf740b Fleur 9-b52781fd38b0185bd1a8a92a92dbf01c99eddbb50b86f65a882ad8a7fa313e9d George 6-7c61f3ee00ab759a6853f041e74ae2378144a96b662230888d6ba6412c646190 Ginny 7-d01f29e42de0ab1fb183a35d06a2ac6117acaad2b3017671846c7b380e83d6bb Harry 1-d301da5536a5d8b8e2be50a7584127eb3704025f048cf72335f1b301b852b30a Hermione 2-e1af01e2f7887b63c068823cbcd812f91899678656456db71dfa9ab1fbb1bd26 Luna 4-510c9c8f6aaacebf16bb5fd9e2cd8c0845ec483bd49bf57fa4151e5b672c73b0 Neville 3-dc60d55a411ccfd4a44e6a9799774dd6207dffdfcab4b442075ead165fa7ecb Ron 5-bd4f58a846bb9e47a7402e22df13002aef3bf3048011674269eaff39154c62bf
Shamir's Secret Sharingの問題のようだ。Pythonのライブラリを使って簡単に秘密情報を取得できる。
from secretsharing import PlaintextToHexSecretSharer shares = [ '1-d301da5536a5d8b8e2be50a7584127eb3704025f048cf72335f1b301b852b30a', '2-e1af01e2f7887b63c068823cbcd812f91899678656456db71dfa9ab1fbb1bd26', '3-dc60d55a411ccfd4a44e6a9799774dd6207dffdfcab4b442075ead165fa7ecb', '4-510c9c8f6aaacebf16bb5fd9e2cd8c0845ec483bd49bf57fa4151e5b672c73b0', '5-bd4f58a846bb9e47a7402e22df13002aef3bf3048011674269eaff39154c62bf', '6-7c61f3ee00ab759a6853f041e74ae2378144a96b662230888d6ba6412c646190', '7-d01f29e42de0ab1fb183a35d06a2ac6117acaad2b3017671846c7b380e83d6bb', '8-1268bf4430c0b1a4c568a302da92421bc672aceb57fef3401f2434cfc3bf740b', '9-b52781fd38b0185bd1a8a92a92dbf01c99eddbb50b86f65a882ad8a7fa313e9d', 'a-424b493442128adbeef5ce33f18c6c5996cdd97e4922644a4479bb4e05f8846f' ] flag = PlaintextToHexSecretSharer.recover_secret(shares) print flag
pctf{sh4m1r3_w4s_4_gr34t_m4n}
Help Rabin (Cryptography 150)
公開鍵を見ると、eは1だが、encrypt.pyを見ると実質e=2のRabin暗号。また、pとqは近い素数なので、Fermat法で素因数分解できる。あとはRabin暗号の復号方法で復号する。
from Crypto.PublicKey import RSA from Crypto.Util.number import * def isqrt(n): x = n y = (x + n // x) // 2 while y < x: x = y y = (x + n // x) // 2 return x def fermat(n): x = isqrt(n) + 1 y = isqrt(x * x - n) while True: w = x * x - n - y * y if w == 0: break elif w > 0: y += 1 else: x += 1 return x - y, x + y def egcd(a, b): if a == 0: return b, 0, 1 else: gcd, y, x = egcd(b % a, a) return gcd, x - (b // a) * y, y def is_printable(s): for c in s: if ord(c) != 10 and (ord(c) < 32 or ord(c) > 126): return False return True with open('publickey.pem', 'r') as f: pub_data = f.read() pubkey = RSA.importKey(pub_data) n = pubkey.n p, q = fermat(n) with open('ciphertext.txt', 'r') as f: ct = bytes_to_long(f.read().decode('hex')) r = pow(ct, long((p+1)/4), long(p)) s = pow(ct, long((q+1)/4), long(q)) gcd, c, d = egcd(p, q) x = (r * d * q + s * c * p) % n y = (r * d * q - s * c * p) % n plains = [x, n - x, y, n - y] for plain in plains: flag = long_to_bytes(plain) if is_printable(flag): print flag break
復号結果は以下の通り。
Hey Rabin, would you like to be the front end to my back end? Here is your flag: pctf{R4b1n_1s_th3_cut3st}
pctf{R4b1n_1s_th3_cut3st}
Easy RSA (Cryptography 150)
eが非常に大きいので、Wiener's Attackで復号する。
from fractions import Fraction def egcd(a, b): x,y, u,v = 0,1, 1,0 while a != 0: q, r = b//a, b%a m, n = x-u*q, y-v*q b,a, x,y, u,v = a,r, u,v, m,n gcd = b return gcd, x, y def decrypt(p, q, e, c): n = p * q phi = (p - 1) * (q - 1) gcd, a, b = egcd(e, phi) d = a pt = pow(c, d, n) return hex(pt)[2:-1].decode('hex') def continued_fractions(n,e): cf = [0] while e != 0: cf.append(int(n/e)) N = n n = e e = N%e return cf def calcKD(cf): kd = list() for i in range(1,len(cf)+1): tmp = Fraction(0) for j in cf[1:i][::-1]: tmp = 1/(tmp+j) kd.append((tmp.numerator,tmp.denominator)) return kd def int_sqrt(n): def f(prev): while True: m = (prev + n/prev)/2 if m >= prev: return prev prev = m return f(n) def calcPQ(a,b): if a*a < 4*b or a < 0: return None c = int_sqrt(a*a-4*b) p = (a + c) /2 q = (a - c) /2 if p + q == a and p * q == b: return (p,q) else: return None def wiener(n,e): kd = calcKD(continued_fractions(n,e)) for (k,d) in kd: if k == 0: continue if (e*d-1) % k != 0: continue phin = (e*d-1) / k if phin >= n: continue ans = calcPQ(n-phin+1,n) if ans is None: continue return (ans[0],ans[1]) e = 217356749319385698521929657544628507680950813122965981036139317973675569442588326220293299168756490163223201593446006249622787212268918299733683908813777695992195006830244088685311059537057855442978678020950265617092637544349098729925492477391076560770615398034890984685084288600014953201593750327846808762513 n = 413514550275673527863957027545525175432824699510881864021105557583918890022061739148026915990124447164572528944722263717357237476264481036272236727160588284145055425035045871562541038353702292714978768468806464985590036061328334595717970895975121788928626837881214128786266719801269965024179019247618967408217 c = 337907824405966440030495671003069758278111764297629248609638912154235544001123799434176915113308593275372838266739188034566867280295804636556069233774555055521212823481663542294565892061947925909547184805760988117713501561339405677394457210062631040728412334490054091265643226842490973415231820626551757008360 p, q = wiener(n, e) flag = decrypt(p, q, e, c) print flag
復号結果は以下の通り。
Here is your flag, pctf{Sup3r_st4nd4rd_W31n3r_4tt4ck}
pctf{Sup3r_st4nd4rd_W31n3r_4tt4ck}
Decode This (Cryptography 200)
行列で以下のような計算になる。
key[0][0] key[0][1] 'p' 't' c1 c3 * = key[1][0] key[1][1] 'c' 'f' c2 c4
key = c * inv(m) m = inv(key) * c
pctfが含まれているだけという条件しかわからないので、上記の条件をもとに、ブルートフォースで復号し、英文として意味の通るものを探す。
# solve.sage ct = 'vuqxyugfyzfjgoccjkxlqvguczymjhpmjkyzoilsxlwtmccclwizqbetwthkkvilkruufwuu' n = 26 for j in range(len(ct) - 4): print '**** %d ****' % j ct_parts = ct[j:j+4] cipher = matrix(Zmod(n), [[ord(ct_parts[0]) - 97, ord(ct_parts[2]) - 97], [ord(ct_parts[1]) - 97, ord(ct_parts[3]) - 97]]) plain = matrix(Zmod(n), [[ord('p') - 97, ord('t') - 97], [ord('c') - 97, ord('f') - 97]]) key = cipher * plain.inverse() flag = '' for i in range(0, len(ct), 4): c = matrix(Zmod(n), [[ord(ct[i]) - 97, ord(ct[i+2]) - 97], [ord(ct[i+1]) - 97, ord(ct[i+3]) - 97]]) try: m = key.inverse() * c flag += chr(int(m[0][0]) + 97) flag += chr(int(m[1][0]) + 97) flag += chr(int(m[0][1]) + 97) flag += chr(int(m[1][1]) + 97) except: break print flag
実行結果は以下の通り。
: **** 38 **** ramhasalittlesecretforyourighthereitispctfilikeclimbinghillswhataboutyou :
pctf{ilikeclimbinghillswhataboutyou}
EXORcism (Miscellaneous 300)
10000行あり、0か1になっている。100×100に並べると、QRコードが浮かぶ。
strong-qr-decoderで読めるよう少し整形する。
with open('encoded.txt', 'r') as f: lines = f.readlines() qr = '' i = 0 for line in lines: val = line.strip() qr += val if i % 100 == 99: qr += '\n' i += 1 qr_lines = qr.split('\n') qr_lines = qr_lines[13:-14] qr_array = [] for line in qr_lines: qr_array.append(line[13:-13]) qr = '' for y in range(37): for x in range(37): qr += qr_array[y*2][x*2] qr += '\n' qr = qr.replace('0', 'X') qr = qr.replace('1', '_') with open('qr.txt', 'w') as f: f.write(qr)
$ cat qr.txt XXXXXXX___XX_X_X_X___X__X_X___XXXXXXX X_____X__X_XXX_XXX_XX_X_X_X_X_X_____X X_XXX_X__X_____XXXX_XX_XXXX_X_X_XXX_X X_XXX_X__XXX_____X__X_X_XX__X_X_XXX_X X_XXX_X_X_X_XXXX_XXXXXX_XX_X__X_XXX_X X_____X___XX____X_XXX__X__X_X_X_____X XXXXXXX_X_X_X_X_X_X_X_X_X_X_X_XXXXXXX ________X__X_X__X_X_XX_XXXX__________ __XX__XXXX_X__XX___XX__XXXX_XXX_X____ XX_XXX_____XX__X__X__XX_X__X___X_X_X_ XX_XXXXX_X__X__X___XXX____X_X__XXXXX_ X___X__X____X_X______X___XX_X_X___XX_ _X_XX_X_XXX___XX____X__XXX_XX_XXX_X_X X_X_X____XXXX__XX_X_XXX_X__X__X_X__XX XX_XX_XXXX_XXX__X________XX_XX___XXX_ _______XX__XXXX_XXX_XXXXX_X_XXXX_X_XX _XXX_XX________XX_____X_XXX_XX_X_XXX_ ____X___X_X_X____X_X__X__XXXXXXX__XXX XX_XX_X_X_X__X____XX_X___X_XX_XX_XX_X _XXXXX_____XX_XX_X__XX__X__X__X____X_ XXXXX_X_X___X___X__XXX_X_______XXX__X X_X__X___XX_____XXXX_X__X_X__X_X_X_X_ X_XXX_XXX_____X__XX__XX_X_X_X___XXXX_ X__XXX_X____X__XX__X__X__XX__X_X__XX_ XX__XXX_XXXXX_XXXXXX_______X__XXX_X_X __XXXX___XX____XX_X_XXXX___XX_X_XX__X _X____X__XXX__XX_XXX____XX_______XX__ X__XXX__XXXXX__X_X__X_X_X_XX_XX_XX_XX __X___XXXXX____XX___X__XXX__XXXXXXX__ ________X__X__XXX_X__XXX____X___XXXXX XXXXXXX_XXX_X_XXXX__XX__X___X_X_XXX_X X_____X__XX__XXX_XXX_X__X__XX___X__X_ X_XXX_X__XXX_X_XXXXX_X______XXXXXX_X_ X_XXX_X_XXXXXX___XX___X___X___XXXX___ X_XXX_X_XXX_X_XX_X__X_X____X__X_X__X_ X_____X_____X__XXXX_XX_XXXXX___X__X__ XXXXXXX___X_XXX_XXX_XX_X_X_X_X__X_XXX $ ./sqrd.py qr.txt 160f15011d1b095339595138535f135613595e1a
問題タイトルからもXORが関係していそう。pctfが先頭につくことからXOR鍵を推測して復号する。
enc = '160f15011d1b095339595138535f135613595e1a'.decode('hex') pre_flag = 'pctf{' key = '' for i in range(len(pre_flag)): code = ord(enc[i]) ^ ord(pre_flag[i]) key += chr(code) print 'key =', key key = key[:4] flag = '' for i in range(len(enc)): code = ord(enc[i]) ^ ord(key[i%len(key)]) flag += chr(code) print flag
pctf{wh4_50_53r1u5?}