Harekaze CTF 2019 Writeup

CTF writeup

この大会は2019/5/18 15:00(JST)～2019/5/19 15:00(JST)に開催されました。
今回もチームで参戦。結果は1960点で523チーム中5位でした。
自分で解けた問題をWriteupとして書いておきます。

Welcome (Misc 10)

問題にフラグが書いてあった。

HarekazeCTF{Thank_you_for_participating_in_Harekaze_CTF_2019}

ONCE UPON A TIME (Crypto 100)

処理概要は以下の通り。

・flagの長さが25の倍数になるよう%でパディング
・25バイトごとに5行5列の配列を配列にする。
・5行5列の配列ごとに以下のどちらかの処理
　・takenoko(m2, mat)：m2*mat
　・takenoko(mat, m2)：mat*m2

暗号データを25バイトずつに区切り、5×5の行列にしたものをCとする。

M1 * M2 = C
または
M2 * M1 = C

つまり元のデータM1は以下のどちらかで計算できる。

M1 = C * inverse(M2)
または
M1 = inverse(M2) * C

以上のことから逆算して復号する。

# solve.sage
def str2matrix(s):
    mat = []
    for j in range(5):
        row = []
        for i in range(5):
            row.append(ord(s[i+j*5]))
        mat.append(row)

    return mat

def matrix2str(mat):
    s = ''
    for j in range(5):
        for i in range(5):
            code = mat[j][i]
            s += chr(code)
    return s

def is_printable(mat):
    for j in range(5):
        for i in range(5):
            code = mat[j][i]
            if code < 32 or code > 126:
                return False
    return True

enc = 'ea5929e97ef77806bb43ec303f304673de19f7e68eddc347f3373ee4c0b662bc37764f74cbb8bb9219e7b5dbc59ca4a42018'
enc = enc.decode('hex')

M2 = matrix(Zmod(251), [[1,3,2,9,4], [0,2,7,8,4], [3,4,1,9,4], [6,5,3,-1,4], [1,4,5,3,5]])

flag = ''
for i in range(0, len(enc), 25):
    MAT = matrix(Zmod(251), str2matrix(enc[i:i+25]))
    inv_M2 = M2.inverse()
    M1 = MAT * inv_M2
    if is_printable(M1) == False:
        M1 = inv_M2 * MAT
    flag += matrix2str(M1)

flag = flag.rstrip('\x25')
flag = 'HarekazeCTF{%s}' % flag
print flag

HarekazeCTF{Op3n_y0ur_3y3s_1ook_up_t0_th3_ski3s_4nd_s33}

Twenty-five (Crypto 100)

ppencodeをテーマにした換字式暗号の問題。
crypto.txtの文字を換字式暗号としてうまく置換すると、実行結果がフラグになるということのようだ。perlの予約語を辞書としてreserved.txtが提供されているので、参考にしながら置換していく。

length
alarm
break
semop
write
until
undef
eval
exec
join
crypt

上記に注目しながら、対応表を作ると、以下のようになる。

abcdefghijklmnopqrstuvwxy
tbwiupohdnvrsyqlkmaxfjcge

"*************************" を "tbwiupohdnvrsyqlkmaxfjcge" にして実行する。

$ perl twenty-five.pl 
HarekazeCTF{en.wikipedia.org/wiki/Frequency_analysis}

HarekazeCTF{en.wikipedia.org/wiki/Frequency_analysis}

Now We Can Play!! (Crypto 200)

Elgamal暗号になっているが、復号に違いがある。

def decrypt(c1, c2, pk, sk):
    p = pk[0]
    m = pow(3, randint(2**16, 2**17), p) * c2 * inverse(pow(c1, sk, p), p) % p
    return m

サーバ処理は上記のようになっているが、本来はこうなる。

m = c2 * inverse(pow(c1, sk, p), p) % p

そこで暗号結果のc1, c2をそのまま渡し、復号する。pow(3, randint(2**16, 2**17), p)の乗算が余計なので、ブルートフォースでinverseを計算し、フラグの形式で復号できるものを探す。

import socket
from Crypto.Util.number import *

def recvuntil(s, tail):
    data = ''
    while True:
        if tail in data:
            return data
        data += s.recv(1)

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('problem.harekaze.com', 30002))

data = recvuntil(s, '\n').rstrip()
print data
pk = eval(data[17:-1])

data = recvuntil(s, '\n').rstrip()
print data
c1, c2 = eval(data[18:-1])

data = recvuntil(s, 'c1 : ')
print data + str(c1)
s.sendall(str(c1) + '\n')

data = recvuntil(s, 'c2 : ')
print data + str(c2)
s.sendall(str(c2) + '\n')

data = recvuntil(s, '\n').rstrip()
print data
data = recvuntil(s, '\n').rstrip()
print data
m = eval(data[29:-1])

p = pk[0]
for i in range(2**16, 2**17):
    flag = (m * inverse(pow(3, i, p), p)) % p
    flag = long_to_bytes(flag)
    if flag.startswith('HarekazeCTF{'):
        print flag
        break

実行結果は以下の通り。

('Public Key :', (179173323191454988591857397662357046816406002058222699078082170304942344337525772960365297716675606420378518281831622210294670272131150121828106451512482462351605274656707674269628181870458122317495560207260507411107279195253094119477943994404974997604864735179278176112212343855702414394782510683988125734957L, 2, 53000002593913678937986352418727205538196468549418622475874892482076157998246352050156067510851110275400992586567516093249617976637603565776167257902162567157633995357563567618158233405560793326022137088001144379716157892590298561723225360685249181865325251167875039876719827029888693088533710738116269041133L))
('Cipher text :', (13939058318848869969892661769790944708827274443633249255860130775103355992242218114621405714834592066931918925168617885762705383632767654046468600883492671085892643960651879330981339090382368737591290752693040506297361373997196171277757061478625002075739258607973780566868938423203415950325973810026943457883L, 109590941535359400665615600141181086480543183338115818774409180733164575367102887217210860850806360120300452283512297474847898172474905185925208813871580965935842023665869656822510432339398702011062707781447851941826936476730118432113609805691528978006074326578988475630910504994019834070776807197697847292319L))
('------------------------------', '\n')
Input your ciphertext c1 : 13939058318848869969892661769790944708827274443633249255860130775103355992242218114621405714834592066931918925168617885762705383632767654046468600883492671085892643960651879330981339090382368737591290752693040506297361373997196171277757061478625002075739258607973780566868938423203415950325973810026943457883

Input your ciphertext c2 : 109590941535359400665615600141181086480543183338115818774409180733164575367102887217210860850806360120300452283512297474847898172474905185925208813871580965935842023665869656822510432339398702011062707781447851941826936476730118432113609805691528978006074326578988475630910504994019834070776807197697847292319

('Your Decrypted Message :', 39268793095845740212401926030298979200819615217155164098539854509541032469801080785289352965052801469642156674128708697912306078630662670836855612851002988923070651137189060084842307753112310645041440364059957404423987700979196172608023790040770192830357799786699784325482972837364501493640072710378719464216L)
HarekazeCTF{im_caught_in_a_dr3am_and_m7_dr3ams_c0m3_tru3}
HarekazeCTF{im_caught_in_a_dr3am_and_m7_dr3ams_c0m3_tru3}