この大会は2019/3/8 21:30(JST)～2018/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)
10人分のQRコードがあるので、QRコードを読み取る。
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が含まれているだけという条件しかわからないので、上記の条件をもとに、ブルートフォースで復号し、英文として意味の通るものを探す。
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?}
