0CTF/TCTF 2022 Writeup - よっちんのブログ

この大会は2022/9/17 11:00(JST)～2022/9/19 11:00(JST)に開催されました。
今回もチームで参戦。結果は259点で605チーム中74位でした。
自分で解けた問題をWriteupとして書いておきます。

welcome (Misc)

Discordに入り、#announcementsチャネルのメッセージを見ると、フラグが書いてあった。

flag{wish_you_have_fun_in_2022}

real magic dlog (Crypto)

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

・LEN = 17
・PoW
・magic: ランダム17バイト文字列
・magic_num: magicの数値化
・magicを16進数で表示
・P: 数値入力
・E: 数値入力
・data: 16進文字列入力
・num1: dataを10進数にした数値
・P >> (384 - LEN * 8) == magic_numで、Pが素数の場合、
　・data2: dataのsha384ダイジェスト(hex)
　・num2: data2を10進数にした数値
　・pow(num1, E, P) == num2 % Pの場合、フラグを表示

num1, num2は依存関係にあるので、独立して指定できない。また、Pは条件があるので、P - 1の素因数が小さい値になるよう調整した上で、Eを解く問題となる。
(384 - LEN * 8)ビット分は小さいビットの素数で構成し、残りのビットを条件を満たすよう割り算して算出する。P - 1の素因数がすべて51ビット未満にできるまで、サーバに接続しなおして、条件を満たすまで繰り返す。さらに離散対数問題の解が存在するnum1, num2の組を探す。離散対数問題を解くことができれば、あとはパラメータを入力していけばよい。

#!/usr/bin/env sage
import socket
import string
import re
import itertools
import sympy
from Crypto.Util.number import *
from hashlib import sha256, sha384

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

LEN = 17

while True:
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.connect(('202.120.7.219', 15555))

    data = recvuntil(s, b'\n').rstrip()
    print(data)
    pattern = '\+ (.+)\) == (.+)'
    m = re.search(pattern, data)
    tail_text = m.group(1)
    h = m.group(2)

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

    chars = string.ascii_letters + string.digits + '!#$%&*-?'
    for c in itertools.product(chars, repeat=4):
        head_text = ''.join(c)
        text = head_text + tail_text
        if sha256(text.encode()).hexdigest() == h:
            print(head_text)
            s.sendall(head_text.encode() + b'\n')
            break

    data = recvuntil(s, b'\n').rstrip()
    print(data)
    magic = bytes.fromhex(data)
    magic_num = bytes_to_long(magic)

    P_base = magic_num << (384 - LEN * 8)

    prod = 2
    for _ in range(9):
        p = getPrime(27)
        prod *= p

    found = False
    for i in range(1, 257):
        P_parts = P_base // prod + i
        P = prod * P_parts + 1
        if isPrime(P) and P >> (384 - LEN * 8) == magic_num:
            if factor(P - 1)[-1][0].nbits() < 51:
                found = True
                break

    if found:
        break
    else:
        s.close()

print('[+] P - 1 =', factor(P - 1))

F = GF(P)
g = F.multiplicative_generator()

while True:
    num1 = ZZ(g ** randint(1, p - 1))
    send_data = hex(num1)[2:]
    data2 = sha384(send_data.encode()).hexdigest()
    num2 = int(data2, 16)

    print('[+] discrete_log() start')
    try:
        E = ZZ(discrete_log(F(num2), F(num1)))
        assert pow(num1, E, P) == num2 % P
        break
    except:
        print('[+] Exception occurred')
        continue

data = recvuntil(s, b'\n').rstrip()
print(data)
print(hex(P)[2:])
s.sendall(hex(P)[2:].encode() + b'\n')
data = recvuntil(s, b'\n').rstrip()
print(data)
print(hex(E)[2:])
s.sendall(hex(E)[2:].encode() + b'\n')
data = recvuntil(s, b'\n').rstrip()
print(data)
print(send_data)
s.sendall(send_data.encode() + b'\n')
data = recvuntil(s, b'\n').rstrip()
print(data)

実行結果は以下の通り。

　　　　　　　　：
　　　　　　　　：
sha256(XXXX + ns0-1OlPpG&FWMat) == 23909a09dfb9a4efd8b264bae436f05f829bd37339d645cdea6c924abb8f0372
Give me XXXX:
z8Xy
584dfa5be19766efe6f0fa3f353214e838
sha256(XXXX + 6Q0vwpiE*5dQhe4R) == 63ba546bb91bda036778db99804144bf54927a28cd4157219d447af13942b6a2
Give me XXXX:
nHX#
099cb53f1e49f4ea3e2df88a02d11becb1
sha256(XXXX + FmcSWSPNz7Yp5pVT) == c7a799a3ee9a66f48a8caa5774f57259c764a4be132479b4afdb821bcd049247
Give me XXXX:
D&3N
ebc82af9cdb736593a0a3c397192255a0e
[+] P - 1 = 2 * 3^2 * 5 * 11 * 13 * 271 * 541 * 5903 * 40829 * 1644637 * 68905957 * 76659659 * 86409703 * 90452987 * 92508137 * 93260641 * 96174671 * 98107447 * 105566633 * 3452271289 * 39614162513
[+] discrete_log() start
P:>
ebc82af9cdb736593a0a3c397192255a0e49f1aefef7a68ed267ea2a0d2d2220b86d41e92f536519e4c75ab9ba0f8c8b
E:>
856fb0a054d4f6c2ca56e6ec8897dabdbb602c7a869a92201b14a935428ca955f1f9ff7462fdfac60db8c6bfa5ed171e
data:>
2f2488891e2ad3a456fc2d9879083bc7b9077f8105b6e744fe26cef7d93a59ed0460702886b88695a85db694e6a68078
flag{Hope_you_can_solve_by_smoothness_this_time}

flag{Hope_you_can_solve_by_smoothness_this_time}

SURVEY (Misc)

アンケートに答えたら、フラグが表示された。

flag{covid19_steals_the_finals_and_we_hope_to_meet_you_onsite_someday}