BSides Noida CTF Writeup

この大会は2021/8/7 19:30(JST)～2021/8/8 19:30(JST)に開催されました。
今回もチームで参戦。結果は3197点で411チーム中28位でした。
自分で解けた問題をWriteupとして書いておきます。

Welcome (Misc)

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

BSNoida{W3lc0me_To_BSidesNoida_CTF}

Psst (Misc)

tar.gzの中のフォルダが階層になっていて、各階層のテキストにフラグになる1文字が書いてある。フォルダ名が長く、深い階層を見るのが難しいため、7-zipでパスなしで解凍する。あとはスクリプトで順に読み取る。

import os

DIR = 'psst/'

flag = ''
for i in range(70):
    fname = 'readme_%d.txt' % i
    with open(DIR + fname, 'r') as f:
        flag += f.read().rstrip()

print flag

BSNoida{d1d_y0u_u53_b45h_5cr1pt1ng_6f7220737461636b6f766572666c6f773f}

Xoro (Crypto)

サーバの処理概要は以下の通り。

・key: ランダム32バイト
・pt: 平文(hex)入力
・ct: pt(hexデコード) + FLAGをkeyで暗号化→表示
　・keystream: keyの繰り返し
　・keystreamとのXOR

keyは32バイトなので、32バイト以上の平文を指定し、暗号文とのXORをとれば、keyがわかる。あとはFLAGをそのkeyで復号すればよい。

#!/usr/bin/env python3
import socket
from Crypto.Util.number import *

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

def xor(a, b):
    return bytes([i^j for i,j in zip(a,b)])

def pad(text, size):
    return text*(size//len(text)) + text[:size%len(text)]

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('104.199.9.13', 1338))

pt = (b'a' * 32).hex()

data = recvuntil(s, b'>  ')
print(data + pt)
s.sendall(pt.encode() + b'\n')
data = recvuntil(s, b'\n').rstrip()
print(data)
ct = bytes.fromhex(data.split(' ')[-1])

key = xor(ct[:32], bytes.fromhex(pt))
keystream = pad(key, len(ct))
flag = xor(ct, keystream)[32:].decode()
print(flag)

実行結果は以下の通り。

===== WELCOME TO OUR ENCRYPTION SERVICE =====

[plaintext (hex)]>  6161616161616161616161616161616161616161616161616161616161616161
[ciphertext (hex)]> 886741ecd5cbb1dc272df43b71b2936e2d140c6be1f8fa8f74d687ba4615a43cab556ee2ddceb1c62e23e20573b29c50351a1855e2ebfe8f7ee8b293622b9d12bb591fac8b8bad
BSNoida{how_can_you_break_THE_XOR_?!?!}

BSNoida{how_can_you_break_THE_XOR_?!?!}

MACAW (Crypto)

$ nc 104.199.9.13 1337
Welcome to BSidesNoida!! Follow us on Twitter...

/===== MENU =====\
|                |
|  [M] MAC Gen   |
|  [A] AUTH      |
|                |
\================/

[?] Choice: M
[+] Enter plaintext(hex): 0123456789abcdef0123456789abcdef
[-] Generated tag: d098eb6d4f76a3d61396c44248447b07
[-] iv: 4aa8d73c2f644a6cecf9cf1af82ebbe9

/===== MENU =====\
|                |
|  [M] MAC Gen   |
|  [A] AUTH      |
|                |
\================/

[?] Choice: A
[+] Enter your tag to verify: d098eb6d4f76a3d61396c44248447b07
[-] Verification Flaied !!!

サーバの処理概要は以下の通り。

・iv: ivのhexデコード
・secret_msg表示
・以下3回繰り返し
　・メニュー表示
　・M選択の場合
　　・data: 平文(hex)入力(hex長:32の倍数)
　　・tag = MAC(入力データ)
　　　・AES-CBCでデータの最後16バイトを暗号化
　　　　→tag
　　・iv表示
　・A選択の場合
　　・tag: 入力
　　・AUTH(tag)
　　　・secret_msgのタグと一致していたら、フラグが表示される。
　　　　※secret_msg = 'Welcome to BSidesNoida!! Follow us on Twitter...'

AES暗号のイメージは以下の通り。

0123456789abcdef
Welcome to BSide
sNoida!! Follow 
us on Twitter...

平文1ブロック目 ^ IV              --(AES暗号)--> 暗号1ブロック目
平文2ブロック目 ^ 暗号1ブロック目 --(AES暗号)--> 暗号2ブロック目
平文3ブロック目 ^ 暗号2ブロック目 --(AES暗号)--> 暗号3ブロック目

以下のような流れで、secret_msgのタグを算出する。

・[M] "Welcome to BSidesNoida!! Follow "
　→ tagは 上記の暗号2ブロック目
・[M] ("us on Twitter..."とtagのXOR)とIVとのXOR
　→ tagは 上記の暗号3ブロック目、つまりsecret_msgのタグ
・[A] 算出したtagを入力

#!/usr/bin/env python3
import socket
from Crypto.Util.strxor import strxor

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

secret_msg = b'Welcome to BSidesNoida!! Follow us on Twitter...'

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('104.199.9.13', 1337))

data = recvuntil(s, b': ')
print(data + 'M')
s.sendall(b'M\n')

pt1 = secret_msg.hex()[:64]
data = recvuntil(s, b': ')
print(data + pt1)
s.sendall(pt1.encode() + b'\n')

data = recvuntil(s, b'\n').rstrip()
print(data)
tag = bytes.fromhex(data.split(' ')[-1])
data = recvuntil(s, b'\n').rstrip()
print(data)
iv = bytes.fromhex(data.split(' ')[-1])

data = recvuntil(s, b': ')
print(data + 'M')
s.sendall(b'M\n')

pt2 = strxor(strxor(secret_msg[32:], tag), iv).hex()
data = recvuntil(s, b': ')
print(data + pt2)
s.sendall(pt2.encode() + b'\n')

data = recvuntil(s, b'\n').rstrip()
print(data)
tag = data.split(' ')[-1]
data = recvuntil(s, b'\n').rstrip()
print(data)

data = recvuntil(s, b': ')
print(data + 'A')
s.sendall(b'A\n')

data = recvuntil(s, b': ')
print(data + tag)
s.sendall(tag.encode() + b'\n')
data = recvuntil(s, b'\n').rstrip()
print(data)
data = recvuntil(s, b'\n').rstrip()
print(data)

実行結果は以下の通り。

Welcome to BSidesNoida!! Follow us on Twitter...

/===== MENU =====\
|                |
|  [M] MAC Gen   |
|  [A] AUTH      |
|                |
\================/

[?] Choice: M
[+] Enter plaintext(hex): 57656c636f6d6520746f204253696465734e6f696461212120466f6c6c6f7720
[-] Generated tag: f25d4a2c1c95c62576b48019d63e4f00
[-] iv: 4aa8d73c2f644a6cecf9cf1af82ebbe9

/===== MENU =====\
|                |
|  [M] MAC Gen   |
|  [A] AUTH      |
|                |
\================/

[?] Choice: M
[+] Enter plaintext(hex): cd86bd7f5dd1d83ef3393b665c3edac7
[-] Generated tag: eae429a7fdc8b0d6161d02b9cce52ba9
[-] iv: 4aa8d73c2f644a6cecf9cf1af82ebbe9

/===== MENU =====\
|                |
|  [M] MAC Gen   |
|  [A] AUTH      |
|                |
\================/

[?] Choice: A
[+] Enter your tag to verify: eae429a7fdc8b0d6161d02b9cce52ba9
[-] Successfully Verified!
[-] Details: BSNoida{M4c4w5_4r3_4d0r4b13}

BSNoida{M4c4w5_4r3_4d0r4b13}

Kotf_returns (Crypto)

サーバの処理概要は以下の通り。

・rot: 2以上2**160-1以下ランダム整数
・chop: 159ビットランダム素数
・PoWがクリアできなかったら終了
・L, N = 1024, 160
・p(DSA mpdulus), q(order)を生成
・h: 2以上p-2以下ランダム整数
・g = pow(h, (p - 1) // q, p)
・x: 1以上q-1以下ランダム整数
・y = pow(g, x, p)
・p, q, g, y表示
・pad: 1以上2**160以下ランダム整数
・signed = []
・以下2回繰り返し
　・m: 入力(hex)をhexデコード
　・mが'give flag'か'give me all your money'はNG
　・1回目と同じmはNG
　・signedにmを追加
　・k = nonce(m, pad, i, q)
　　・(pow(message_hash(m), rot, chop) + pad + i)%q
　　　・message_hash(m) = bytes_to_long(sha1(m).digest())
　・r = pow(g, k, p) % q
　・s = (pow(k, q - 2, q) * (message_hash(m) + x * r)) % q
　・r, s表示
・r1: 入力
・s1: 入力
・r1, s1で'give flag'のsignが通れば、フラグが表示される。

m1とm2のsha1を衝突させた場合、kは1だけ異なる。https://sha-mbles.github.io/から衝突するsha1データを2つ入手する。kは1だけ異なるので、2つの方程式を作成し、sageに解かせる。

#!/usr/bin/sage
import socket
from hashlib import sha1
from Crypto.Util.number import *
from sage.matrix.matrix2 import Matrix 

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

def message_hash(x):
    return bytes_to_long(sha1(x).digest())

def resultant(f1, f2, var):
    return Matrix.determinant(f1.sylvester_matrix(f2, var))

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('34.105.241.228', 1338))

#### PoW ####
data = recvuntil(s, '\n').rstrip()
print data
pow_nonce = data.split(' ')[-1].decode('hex')

i = 0
while True:
    inp = str(i)
    hash = sha1(pow_nonce + inp).hexdigest()
    if hash.endswith('000000'):
        print(inp.encode('hex'))
        s.sendall(inp.encode('hex') + '\n')
        break
    i += 1

data = recvuntil(s, '\n').rstrip()
print data

#### send sha1 collision data ####
with open('messageA', 'rb') as f:
    msgA = f.read().encode('hex')
with open('messageB', 'rb') as f:
    msgB = f.read().encode('hex')

data = recvuntil(s, '\n').rstrip()
print data
params = data[1:-1].split(', ')
p = int(params[0].split('=')[1])
q = int(params[1].split('=')[1])
g = int(params[2].split('=')[1])
y = int(params[3].split('=')[1])

data = recvuntil(s, '\n').rstrip()
print data
print msgA
s.sendall(msgA + '\n')
data = recvuntil(s, '\n').rstrip()
print data
params = data[1:-1].split(', ')
r1 = int(params[0].split('=')[1])
s1 = int(params[1].split('=')[1])

data = recvuntil(s, '\n').rstrip()
print data
print msgB
s.sendall(msgB + '\n')
data = recvuntil(s, '\n').rstrip()
print data
params = data[1:-1].split(', ')
r2 = int(params[0].split('=')[1])
s2 = int(params[1].split('=')[1])

h1 = message_hash(msgA.decode('hex'))
h2 = message_hash(msgB.decode('hex'))
assert h1 == h2

R.<k,x> = GF(q)[]
f1 = s1*k - h1 - x*r1
f2 = s2*(k+1) - h2 - x*r2

x = resultant(f1, f2, k).univariate_polynomial().roots()[0][0]

data = recvuntil(s, '\n').rstrip()
print data
data = recvuntil(s, '\n').rstrip()
print data

msg = 'give flag'
h = message_hash(msg)
k = int(1337)
r1 = pow(g, k, p) % q
s1 = (pow(k, q-2, q) * (h + x * r1)) % q
print r1
s.sendall(str(r1) + '\n')
print s1
s.sendall(str(s1) + '\n')
data = recvuntil(s, '\n').rstrip()
print data

実行結果は以下の通り。

Solve PoW for 719ea081
3132373739323732
Correct PoW. Continue
<p=89884656743115795393151238227154430948969646136056507539839034582316858483881505448995654369138978288445899751721170167500310608452575083595018959407454977955971630184008759940298683990740305552727097216600028850177041539316695783453148479234674363044967374129321349390392072225341286688208101646869788742881, q=1368367053386220366443358620191572967271825920067, g=55637581543671523836080539537970157082937552186866620253844596323952357000248002087001559365705209957390734422091444577398359713363693415932440778549692310932978738988963617101218383140802936339258763167123822700757309432336435012779240220807320332620577033874836413512397612498764732221618042635160203502556, y=81261206256094546289973148292480245414252226304908508375083541016241945954229129730488386517769691171151627814090353050093565486308920414926322258755406895607390379633114878570004895141337787516540981679605358581947851771776054200971007254173162198594111081116373555503145317876176655336791410686035113171423>
what would you like me to sign? in hex, please
99040d047fe81780012000ff4b65792069732070617274206f66206120636f6c6c6973696f6e212049742773206120747261702179c61af0afcc054515d9274e7307624b1dc7fb23988bb8de8b575dba7b9eab31c1674b6d974378a827732ff5851c76a2e60772b5a47ce1eac40bb993c12d8c70e24a4f8d5fcdedc1b32c9cf19e31af2429759d42e4dfdb31719f587623ee552939b6dcdc459fca53553b70f87ede30a247ea3af6c759a2f20b320d760db64ff479084fd3ccb3cdd48362d96a9c430617caff6c36c637e53fde28417f626fec54ed7943a46e5f5730f2bb38fb1df6e0090010d00e24ad78bf92641993608e8d158a789f34c46fe1e6027f35a4cbfb827076c50eca0e8b7cca69bb2c2b790259f9bf9570dd8d4437a3115faff7c3cac09ad25266055c27104755178eaeff825a2caa2acfb5de64ce7641dc59a541a9fc9c756756e2e23dc713c8c24c9790aa6b0e38a7f55f14452a1ca2850ddd9562fd9a18ad42496aa97008f74672f68ef461eb88b09933d626b4f918749cc027fddd6c425fc4216835d0134d15285bab2cb784a4f7cbb4fb514d4bf0f6237cf00a9e9f132b9a066e6fd17f6c42987478586ff651af96747fb426b9872b9a88e4063f59bb334cc00650f83a80c42751b71974d300fc2819a2e8f1e32c1b51cb18e6bfc4db9baef675d4aaf5b1574a047f8f6dd2ec153a93412293974d928f88ced9363cfef97ce2e742bf34c96b8ef3875676fea5cca8e5f7dea0bab2413d4de00ee71ee01f162bdb6d1eafd925e6aebaae6a354ef17cf205a404fbdb12fc454d41fdd95cf2459664a2ad032d1da60a73264075d7f1e0d6c1403ae7a0d861df3fe5707188dd5e07d1589b9f8b6630553f8fc352b3e0c27da80bddba4c64020d
<r=684433838204310411144919252757299042194274876965, s=43742751748441175302803789578037487502044763448>
what would you like me to sign? in hex, please
99030d047fe81780011800ff50726163746963616c205348412d312063686f73656e2d70726566697820636f6c6c6973696f6e211d276c6ba661e1040e1f7d767f076249ddc7fb332c8bb8c2b7575dbec79eab2be1674b7db34378b4cb732fe1891c76a0260772a5107ce1f6e80bb9977d2d8c68524a4f9d5fcdedcd0b2c9ce19231af26e9759d5250dfdb2d4d9f58729fee553319b6dccc619fca4fb93b70ec72de30a087ea3ae67359a2ee27320d72b1b64fecc9084fc3ccb3cdd83b62d97a904306150aff6c267237e523e228417bde6fec4ecd7943b44a5f572c1ebb38ef11f6e00bc010d01e90ad78a3be641997dc8e8d0d3a789f24c46fe1eaba7f35b4c7fb8272b6c50edaba8b7cd655bb2c2fc50259e39f9570cda94437bffd5fafe3cfcac09812526615e827105b79178eaa43825a341a2acfa5de64ce7af9dc59b54da9fc9eb56756f2563dc70ff4c24c932caa6b1418a7f54f30452a004e850dc99962fd98d8ad4259dea97014db4672f232f461f338b09923d626b4f5a0749cd02bfddd6e825fc431dc35d00f7115285f172cb79e84f7cba4df514d571cf62368fc0a9e9dd32b9a16da6fd16340429870c4586feee1af96647fb426b53f2b9a98e8063f5b7b334cd0b250f826bcc427550b1974c920fc280986e8f1ffc01b51df14e6bfc61b9baee6c1d4aae99d574a00c38f6dca5c153a834122939bf5928f98c2d9363e3ef97cf25342bf28f56b8ef73b5676e485cca8f5d3dea0a65e413d59ec0ee71c201f163b6f6d1eb3f525e6aa06ae6a2dfef17ce205a404f76312fc554141fddb9cf24586d0a2ad1f111da60ecf26406ff7f1e0c6e5403afb4cd861cb33e5707348dd5e1765589b83a7663051838fc34a03e0c26da80bddb6f464021d
<r=946921572912164719633165536609394932855661674264, s=53409641567362002547258864790318961068847494565>
ok im done for now. You visit the flag keeper...
for flag, you must bring me signed message for 'give flag'
695240602578100249532386398206178501261771109936
1128783260648141532291815900755346180990121962322
BSNoida{uncle_roger_added_MSG_to_kotf_fuiyooh_8189dcd9b9}

BSNoida{uncle_roger_added_MSG_to_kotf_fuiyooh_8189dcd9b9}

Macaw_Revenge (Crypto)

基本的にMACAWの問題と同じ解き方なので、スクリプトを流用。secret_msgがランダムで設定されるのが異なるところを中心に修正して実行する。

#!/usr/bin/env python3
import socket
from Crypto.Util.strxor import strxor

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

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('34.121.95.29', 1338))

data = recvuntil(s, b'Choice: ')
secret_msg = bytes.fromhex(data.split('\n')[0].split(' ')[-1])
print(data + 'M')
s.sendall(b'M\n')

pt1 = secret_msg.hex()[:64]
data = recvuntil(s, b': ')
print(data + pt1)
s.sendall(pt1.encode() + b'\n')

data = recvuntil(s, b'\n').rstrip()
print(data)
tag = bytes.fromhex(data.split(' ')[-1])
data = recvuntil(s, b'\n').rstrip()
print(data)
iv = bytes.fromhex(data.split(' ')[-1])

data = recvuntil(s, b': ')
print(data + 'M')
s.sendall(b'M\n')

pt2 = strxor(strxor(secret_msg[32:], tag), iv).hex()
data = recvuntil(s, b': ')
print(data + pt2)
s.sendall(pt2.encode() + b'\n')

data = recvuntil(s, b'\n').rstrip()
print(data)
tag = data.split(' ')[-1]
data = recvuntil(s, b'\n').rstrip()
print(data)

data = recvuntil(s, b': ')
print(data + 'A')
s.sendall(b'A\n')

data = recvuntil(s, b': ')
print(data + tag)
s.sendall(tag.encode() + b'\n')
data = recvuntil(s, b'\n').rstrip()
print(data)
data = recvuntil(s, b'\n').rstrip()
print(data)

実行結果は以下の通り。

[+] Forbidden msg: a7514e87ecd0a20974955448d06052a51b059122c041d85b36ae825bc4fe223c99b15a94c126988451c47a4fd17a3543

/===== MENU =====\
|                |
|  [M] MAC Gen   |
|  [A] AUTH      |
|                |
\================/

[?] Choice: M
[+] Enter plaintext(hex): a7514e87ecd0a20974955448d06052a51b059122c041d85b36ae825bc4fe223c
[-] Generated tag: b79b7f63155fb88887c389799f0781f4
[-] iv: f2bba77567746a12257b9bd439f31bf7

/===== MENU =====\
|                |
|  [M] MAC Gen   |
|  [A] AUTH      |
|                |
\================/

[?] Choice: M
[+] Enter plaintext(hex): dc918282b30d4a1ef37c68e2778eaf40
[-] Generated tag: 69872ece715767b8daf9486f39766d04
[-] iv: f2bba77567746a12257b9bd439f31bf7

/===== MENU =====\
|                |
|  [M] MAC Gen   |
|  [A] AUTH      |
|                |
\================/

[?] Choice: A
[+] Enter your tag to verify: 69872ece715767b8daf9486f39766d04
[-] Successfully Verified!
[-] Details: BSNoida{M4c4w5_4r3_pr3tty_l0ud}

BSNoida{M4c4w5_4r3_pr3tty_l0ud}