この大会は2017/8/26 6:00(JST)~2017/8/27 6:00(JST)に開催されました。
今回もチームで参戦。結果は981点で345チーム中4位でした。
自分で解けた問題をWriteupとして書いておきます。
Rotate it (Bacche 2)
シーザー暗号。ROT13で復号できた。
d4rk{wh0_give$_ca3sar_in_CTF???}c0de
High Bass (Bacche 3)
Base64デコードする。
$ echo VGhpcyB3YXMgaW4gYmFzZS02NDogZDRya3t0aGF0XyRpbXBsXzNuMHVnaDRfVX1jMGRl | base64 -d This was in base-64: d4rk{that_$impl_3n0ugh4_U}c0de
d4rk{that_$impl_3n0ugh4_U}c0de
Needle (Bacche 3)
テキストファイルをd4rkで検索
d4rk{n33dle_in_a_h4ystck}c0de
ALL CAPS (Bacche 5)
換字式暗号。quipqiupで復号する。
IN CRYPTOGRAPHY, A S??STIT?TION CIPHER IS A METHOD OF ENCODING ?Y WHICH ?NITS OF PLAINTEXT ARE REPLACED WITH CIPHERTEXT, ACCORDING TO A FIXED SYSTEM; THE "?NITS" MAY ?E SINGLE LETTERS (THE MOST COMMON), PAIRS OF LETTERS, TRIPLETS OF LETTERS, MIXT?RES OF THE A?O?E, AND SO FORTH. THE RECEI?ER DECIPHERS THE TEXT ?Y PERFORMING THE IN?ERSE S??STIT?TION. THAN?S FOR READING THAT, HERE'S YO?R FLAG: D4R?{TRY_FACCH3_IFTHIS_TOO_SIMPEL}C0DE
D4RK{TRY_FACCH3_IFTHIS_TOO_SIMPEL}C0DE
RSA - 1 (Bacche 10)
p, q がわかっているので、そのまま復号する。
p = 152571978722786084351886931023496370376798999987339944199021200531651275691099103449347349897964635706112525455731825020638894818859922778593149300143162720366876072994268633705232631614015865065113917174134807989294330527442191261958994565247945255072784239755770729665527959042883079517088277506164871850439 q = 147521976719041268733467288485176351894757998182920217874425681969830447338980333917821370916051260709883910633752027981630326988193070984505456700948150616796672915601007075205372397177359025857236701866904448906965019938049507857761886750656621746762474747080300831166523844026738913325930146507823506104359 c = 8511718779884002348933302329129034304748857434273552143349006561412761982574325566387289878631104742338583716487885551483795770878333568637517519439482152832740954108568568151340772337201643636336669393323584931481091714361927928549187423697803637825181374486997812604036706926194198296656150267412049091252088273904913718189248082391969963422192111264078757219427099935562601838047817410081362261577538573299114227343694888309834727224639741066786960337752762092049561527128427933146887521537659100047835461395832978920369260824158334744269055059394177455075510916989043073375102773439498560915413630238758363023648 e = 65537 n = p * q a = (p - 1) * (q - 1) x = 0 while True: if (a * x + 1) % e == 0: d = (a * x + 1) / e break x = x + 1 m = pow(c, d, n) flag = ('%x' % m).decode('hex') print flag
d4rk{s1mpl3_rsa_n0t_th1s_34sy_next_time}c0de
RSA - 2 (Crypto 50)
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]) n = 109676931776753394141394564514720734236796584022842820507613945978304098920529412415619708851314423671483225500317195833435789174491417871864260375066278885574232653256425434296113773973874542733322600365156233965235292281146938652303374751525426102732530711430473466903656428846184387282528950095967567885381 e = 49446678600051379228760906286031155509742239832659705731559249988210578539211813543612425990507831160407165259046991194935262200565953842567148786053040450198919753834397378188932524599840027093290217612285214105791999673535556558448523448336314401414644879827127064929878383237432895170442176211946286617205 c = 103280644092615059984518332609100925251130437801342718478803923990158474621180283788652329522078935869010936203566024336697568861166241737937884153980866061431062015970439320809653170936674539901900312536610219900459284854811622720209705994060764318380465515920139663572083312965314519159261624303103692125635 p, q = wiener(n, e) flag = decrypt(p, q, e, c) print flag
d4rk{1_70ld_y0u_th15_would_8e_more_difficult}c0de
VizHash (Crypto 100)
暗号化の概要は以下の通り。
・flagをBase64エンコードする。 ・flagのBase64文字列分、以下の処理を行い、結合する。 ・先頭1文字をencode(逆にしてASCIIコードで4つプラス) ・先頭2文字をencode : ・全文字をencode ・結合したものを1文字ずつmd5を取る。 ・md5の文字について以下のような処理で色にして画像にする。 R (128 + ord('0')) ^ ord('x') G 128 + ord('x') ^ ord(2番目) B 128 + ord(2番目) ^ ord(3番目) R (128 + ord(3番目)) ^ ord(4番目) G 128 + ord(4番目) ^ ord(5番目) B 128 + ord(5番目) ^ ord(6番目) : R (128 + ord(30番目)) ^ ord(31番目) G 128 + ord(31番目) ^ ord(32番目) B 128 + ord(32番目) ^ ord(33番目)
一つ一つ逆算していけば元に戻せそう。
import hashlib from PIL import Image BODY_DATA_NUM = 12936 def decode(s): return (''.join([ chr(ord(c)-4) for c in s[::-1] ])) hash_dict = {} for i in range(32, 127): h = hashlib.md5(chr(i)).hexdigest() hash_dict[h] = chr(i) img = Image.open('digest.png').convert('RGB') pixel_list = img.getdata() md5_list = [] for i in range(BODY_DATA_NUM / 11): h = [] for j in range(11): if j != 0: h.append(pixel_list[i*11+j][0] ^ (h[-1] + 128)) h.append((pixel_list[i*11+j][1] - 128) ^ h[-1]) else: h.append((pixel_list[i*11+j][1] - 128) ^ ord('x')) h.append((pixel_list[i*11+j][2] - 128) ^ h[-1]) md5str = '' for i in range(32): md5str += chr(h[i]) if md5str[-1:] == 'L': md5str = '0' + md5str[:-1] md5_list.append(md5str) encrypted_flag = '' for md5_val in md5_list: encrypted_flag += hash_dict[md5_val] len_b64 = 0 while True: if len_b64 * (len_b64 + 1) == len(encrypted_flag) * 2: break len_b64 += 1 b64_flag = decode(encrypted_flag[-len_b64:]) flag = b64_flag.decode('base64') print flag
d4rk{no00000oo_not0x_myfaUltXXX}c0de
White (Steg 50)
PNGファイルが添付されているが、PNGフォーマットの後にBase64の文字列が入っている。Base64の文字列をデコードすると、またPNGフォーマットとその後にBase64文字列のデータが入っている。繰り返し処理してPNGファイルを取り出す。
def div_png_and_b64dec(data): PNG_TAIL = '\x49\x45\x4e\x44\xae\x42\x60\x82' index = data.find(PNG_TAIL) enc = data[index+8:] if enc == '': return True, data, '' else: final = False dec = enc.decode('base64') return final, data[:index+8], dec with open('final.png', 'rb') as f: data = f.read() i = 1 while True: print 'Round %d' % i final, png, data = div_png_and_b64dec(data) file = 'png\\%02d.png' % i if final: with open(file, 'wb') as f: f.write(png) break else: with open(file, 'wb') as f: f.write(png) i += 1
取り出した画像の中にフラグの断片が入っているので、結合する。
$ convert +append 01.png 02.png 03.png 04.png 05.png 06.png flag01.png $ convert +append 07.png 08.png 09.png 10.png 11.png 12.png flag02.png $ convert +append 13.png 14.png 15.png 16.png 17.png 18.png flag03.png $ convert +append 19.png 20.png 21.png 22.png 23.png 24.png flag04.png $ convert +append 25.png 26.png 27.png 28.png 29.png 30.png flag05.png $ convert -append flag*.png flag.png
d4rk{1mag3_m4n1pul4t10n_F7W}c0d3