hxp CTF 2021 Writeup

この大会は2021/12/18 0:00(JST)～2021/12/20 0:00(JST)に開催されました。
今回もチームで参戦。結果は85点で150チーム中127位でした。
自分で解けた問題をWriteupとして書いておきます。

gipfel (CRY)

$ nc 65.108.176.66 1088
please give S such that sha256(unhex("8f35e21761b7c327" + S)) ends with 30 zero bits (see pow-solver.cpp).
01000000157e6a3e
pubA = 0x1c0cbb33dc0f5ead27915ff41cc2b744d312a86fb19f573c50a58ff0a35dfd988e5a101f6db9c24d7f4c207126d41f8b7aaed1ded4a1f6a7e6e2bc6deef653aa81e3f0bccb574e865aaa5a5ca3a87e908925a8865d88840722243871758845e

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

・q: 固定値
・password: 10**6未満整数
・go()
　・g = int(H(password).hex(), 16)
　・privA: 40*[2**999未満整数値]
　・pubA = pow(g, privA, q)→表示
　・pubB: 2以上q未満整数入力
　・shared = pow(pubB, privA, q)
　・verA = pow(g, shared**3, q)→表示
　・verB: 整数値入力
　・verBとpow(g, shared**5, q)が一致している場合
　　・key = H(password, shared)
　　・flag: flag.txtから読み込み
　　・flagのAES-CTR(nonce=b'')暗号化したものを16進表記で表示
　・verBとpow(g, shared**5, q)が一致していない場合
　　・sharedを16進数で表示
・go()
・go()

最初のPoWはソルバーをコンパイルしたものをそのまま使う。
1回目のgo()で適当な値を入力し、sharedを入手する。verAの値からRSA暗号の復号の方法でgを計算できる。
2回目のgo()でBの秘密鍵(=privB)を適当に指定して、sharedを求める。sharedがわかったら、verBを算出できるので、フラグの暗号化データを入手できる。
鍵はpasswordとsharedから生成されるので、passwordがわかったらフラグを復号できることになる。passwordはブルートフォースでgが一致するものを探し、割り出すことができる。

#!/usr/bin/env python3
import socket
import re
import subprocess
from Crypto.Hash import SHA256
from Crypto.Cipher import AES
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 enc(a):
    f = {str: str.encode, int: int.__str__}.get(type(a))
    return enc(f(a)) if f else a

def H(*args):
    data = b'\0'.join(map(enc, args))
    return SHA256.new(data).digest()

q = 0x3a05ce0b044dade60c9a52fb6a3035fc9117b307ca21ae1b6577fef7acd651c1f1c9c06a644fd82955694af6cd4e88f540010f2e8fdf037c769135dbe29bf16a154b62e614bb441f318a82ccd1e493ffa565e5ffd5a708251a50d145f3159a5

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('65.108.176.66', 1088))

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

pattern = 'unhex\(\"(.+)\" \+ S\)\) ends with (\d+) zero'
m = re.search(pattern, data)
pre = m.group(1)
bits = m.group(2)
cmd = './pow-solver %s %s' % (bits, pre)
S = subprocess.check_output(cmd.split(' ')).rstrip()
print(S.decode())
s.sendall(S + b'\n')

#### 1st (& 2nd) go() ####
data = recvuntil(s, b'\n').rstrip()
print(data)
pubA = int(data.split(' ')[-1], 16)
pubB = 3
print(pubB)
s.sendall(str(pubB).encode() + b'\n')
data = recvuntil(s, b'\n').rstrip()
print(data)
verA = int(data.split(' ')[-1], 16)
verB = 2
print(verB)
s.sendall(str(verB).encode() + b'\n')
data = recvuntil(s, b'\n').rstrip()
print(data)
shared = int(data.split(' ')[-1], 16)
phi = q - 1

if GCD(shared, phi) == 1:
    d = inverse(shared**3, phi)
    g = pow(verA, d, q)
    assert pow(g, shared**3, q) == verA
    print('[+] g =', g)
else:
    data = recvuntil(s, b'\n').rstrip()
    print(data)
    pubA = int(data.split(' ')[-1], 16)
    pubB = 5
    print(pubB)
    s.sendall(str(pubB).encode() + b'\n')
    data = recvuntil(s, b'\n').rstrip()
    print(data)
    verA = int(data.split(' ')[-1], 16)
    verB = 2
    print(verB)
    s.sendall(str(verB).encode() + b'\n')
    data = recvuntil(s, b'\n').rstrip()
    print(data)
    shared = int(data.split(' ')[-1], 16)
    phi = q - 1
    d = inverse(shared**3, phi)
    g = pow(verA, d, q)
    assert pow(g, shared**3, q) == verA
    print('[+] g =', g)

#### last go() ####
data = recvuntil(s, b'\n').rstrip()
print(data)
pubA = int(data.split(' ')[-1], 16)
privB = 1
pubB = pow(g, privB, q)
print(pubB)
s.sendall(str(pubB).encode() + b'\n')
data = recvuntil(s, b'\n').rstrip()
print(data)
verA = int(data.split(' ')[-1], 16)
shared = pow(pubA, privB, q)
verB = pow(g, shared**5, q)
print(verB)
s.sendall(str(verB).encode() + b'\n')
data = recvuntil(s, b'\n').rstrip()
print(data)
enc_flag = data.split(' ')[-1]

for password in range(10**6):
    try_g = int(H(password).hex(), 16)
    if try_g == g:
        break

print('[+] password =', password)

key = H(password, shared)
aes = AES.new(key, AES.MODE_CTR, nonce=b'')
flag = aes.decrypt(bytes.fromhex(enc_flag)).decode()
print('[*] flag:', flag)

実行結果は以下の通り。

please give S such that sha256(unhex("a6da72cadcab0304" + S)) ends with 30 zero bits (see pow-solver.cpp).
0100000005e3ea41
pubA = 0x257cae78f3f23cba016200abdc09d2e5007392ff4b0c63aec1dbbf92cb4e3db8e50d9faeb418643828fa5a6050b7e00db0fbc7a770a5bcd1d53b39674d9b2a2d1007f642ce54b811a4d16eee711f3d3984a6dab5be1dce36bc28b78a8b30387
3
verA = 0xffce09f70b1ed7e3d24ba7651d6059d4e5c50938a391710ef3ef963ffad2b08db9898ecb1bfb45abee869fd854ae2f48eb92b0ca85a9fb5c3f7b1a4572539b3cc07b58448548b8e21cf20ab0d6402e6df90b123fac84ffd9fa6175bf44f62d
2
nope! 0xf965ff0d6b22e6dd9a47cc6d392913062654de223a67b5ee878afe3dbcd726b5e31450f4b6212fcac76a00e8bacc0e232430c1b17078a4a17de7d70c2bd3fcd3715e65c4feba983b4673a1fe2c3b7269f91bcbf9529fb04b8df86dba5289b
[+] g = 13493793633820603780901075325722880484676950487827758055252724828867100710213
pubA = 0x2eb0dfeaf601ef3993db9b3a8b5f872608073b3efa794b600893bbe43162aa14b0025c2d382afeca8c8816f5aeab978b09c45df30a6c16d35ff661b08c0be54295d5865ca6151d96231f35be623ceddaed334f8e979cd52e52a85bdbc275cc
13493793633820603780901075325722880484676950487827758055252724828867100710213
verA = 0x1182826b9fbd0d4add2b52fc64f392b2701b9c61d7479886ea9caa8d58db4d27c654760a5c46ccccf488bd20469210de8aa2887fba4d4cbd654de3510985f86be8c12ac8af032b84b5b80f4e360e2cd61497b9d8d4034462d44db707f623a87
10222498644341506938343598224304245593466464162217677047877898700877722581416404301594557632764667021937154267283258709061638868653792738409785033440829078565783119877648318555176791890932495702335158882959608977932523567241840462
flag: 91be4c89e2b9f610d072f04b3efabeb1a598b89421b4a478509dfe4a42fc015783f93f65d0640acc
[+] password = 346041
[*] flag: hxp{ju5T_k1ddIn9_w3_aLl_kn0w_iT's_12345}

hxp{ju5T_k1ddIn9_w3_aLl_kn0w_iT's_12345}