SECCON CTF 2022にチームTSGとして参加し、以下の4問を解きました。チーム全体では2951点で9位でした。

目次

pqpq (crypto)
witches_symmetric_exam (crypto)
insufficient (crypto)
easylfi (web)

Crypto

pqpq

overview

Warm your hands first. It's not obvious, right?

とある3つの素数p, q, rの合成数Nと、e = 2*65537 に対して以下の数をNで割ったあまりが与えられる。

$$
C_1 = p^e - q^e, C_2 = (p-q)^e, C_m = m^e
$$

平文の$m$を復元できれば勝ち。

solution

$ C_1 - C_2 $ は$q$の倍数、 $C_1 + C_2$は$p$の倍数であることを用いて、以下のように素数を復元できる。

P = math.gcd(c1 + c2, n)
Q = math.gcd(c1 - c2, n)
assert n % (P * Q) == 0
R = n // (P * Q)

よってオイラー関数$\phi$は$(p-1)(q-1)(r-1)$ だが、$e$が偶数なので $gcd(\phi, e)=2$となるように互いに素にならず$d=e^{-1} \mod \phi$が求まらない。そこでとりあえず$m^2$を求める。

from Crypto.Util.number import *
# cm = (m^2)^(e//2) mod n

d = inverse(e//2, phi)
m2 = pow(cm, d, n)

素数を法としたときの二乗根はTonelli-Shanks Algorithmで求めることができる。今$N=pqr$と因数分解できているので、平文$m$をそれぞれの素数で割ったあまりを求めることができる。

"""https://tex2e.github.io/blog/crypto/tonelli-shanks-algorithm"""

mp = tonelli_shanks(m2 % P, P)
mq = tonelli_shanks(m2 % Q, Q)
mr = tonelli_shanks(m2 % R, R)

あとは中国剰余定理で平文を特定する。それぞれのあまりの自由度が2個あることに注意する。

from itertools import product
"""https://tjkendev.github.io/procon-library/python/math/chinese-remainder.html"""

for _mp, _mq, _mr in product([mp, P-mp], [mq, Q-mq], [mr, R-mr]):
    m,d = remainder([(_mp, P), (_mq, Q), (_mr, R)])
    assert d == n
    print(long_to_bytes(m))

SECCON{being_able_to_s0lve_this_1s_great!}

witches_symmetric_exam

overview

crypto witch made a exam. The exam has to communicate with witch and saying secret spell correctly. Have fun ;)

key = get_random_bytes(16)
nonce = get_random_bytes(16)


def encrypt():
    data = secret_spell
    gcm_cipher = AES.new(key, AES.MODE_GCM, nonce=nonce)
    gcm_ciphertext, gcm_tag = gcm_cipher.encrypt_and_digest(data)

    ofb_input = pad(gcm_tag + gcm_cipher.nonce + gcm_ciphertext, 16)

    ofb_iv = get_random_bytes(16)
    ofb_cipher = AES.new(key, AES.MODE_OFB, iv=ofb_iv)
    ciphertext = ofb_cipher.encrypt(ofb_input)
    return ofb_iv + ciphertext

...

print(f"ciphertext: {encrypt().hex()}")
while True:
    c = input("ciphertext: ")
    print(decrypt(bytes.fromhex(c)))

secret_spellをAES-GCMで暗号化したのち、タグと合わせて同じ鍵でAES-OFBにかける。この結果が与えられ、好きな回数サーバーに暗号文を投げ復号させることができる。ただしAES-OFBの復号結果のパディングがおかしいときはb"ofb error"が、AES-GCMの検証がおかしいときはb"gcm error"が返される。復号結果がb"give me key"となる暗号文を生成でき、さらに元のsecret_spellを求めることができればフラグがもらえる。

solution

Padding Oracle AttackによってAES encryption blockの任意のivに対する出力を手に入れることができる。
そしてAES-OFBの性質から、ofb_ivからの状態遷移列がわかればciphertextに対するOFBの平文(つまりAES-GCMの暗号文)を手に入れることができるうえ、任意の平文をAES-OFBで暗号化することができる。

from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from Crypto.Util.Padding import pad, unpad
from struct import pack, unpack
import socket

class Connect:
    def __init__(self):
        socket.setdefaulttimeout(3)
        self.conn = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    def connect(self):
        self.conn.connect((HOST, PORT))
        ret = self.conn.recv(1024)
        print("[<]", ret)
        ret = ret.split(b"\n")[0]
        ret = ret[len("ciphertext: "):].decode("utf-8")
        print("[+] hex:", ret)
        return ret

    def challenge(self, data: str):
        # print("[>]", data)
        self.conn.send(data.encode() + b"\n")
        ret = self.conn.recv(1025)
        ret = ret.split(b"\n")[0]
        # print("[<]", ret)
        if ret.startswith(b"ok"):
            spell = input().encode()
            self.conn.send(spell + b"\n")
            print(self.conn.recv(1025))
        return ret[2:-1]

d = Connect()

cip = d.connect()
cip = bytes.fromhex(cip)
ofb_iv, ofb = cip[:16], cip[16:]

print("ofb iv:", ofb_iv.hex())
print("ofb cipher:", ofb.hex())

rounds = len(ofb) // len(ofb_iv)
print("you need", rounds, "rounds for OFB")

def find_next_state(state: bytes):
    known_tail = []
    def find(prefix, suffix):
        print("prefix:", bytes(prefix).hex(), "suffix:", bytes(suffix).hex())
        candidate = []
        for i in range(256):
            cipher = (state + bytes(prefix + [i] + suffix)).hex()
            # print("[+] challenge:", cipher)
            ret = d.challenge(cipher)
            if ret == b"ofb error":
                continue
            else:
                candidate.append(i)
        # print("candidate:", candidate)
        return candidate

    for index in range(16):
        prefix = [0] * (15 - index)
        suffix = [t ^ (index+1) for t in known_tail]
        candidate = find(prefix, suffix)
        assert len(candidate) > 0
        if len(candidate) > 1:
            prefix = [0] * (14 - index) + [1]
            candidate = find(prefix, suffix)
            assert len(candidate) == 1

        known_tail.insert(0, candidate[0] ^ (index+1))
    return bytes(known_tail)

def xor(xs, ys):
    return bytes([x ^ y for x, y in zip(xs, ys)])

states = [ofb_iv]
for i in range(rounds):
    v = states[-1]
    nv = find_next_state(v)
    print(v.hex(), "->", nv.hex())
    states.append(nv)

ofb_plain = xor(b"".join(states[1:]), ofb)
print("ofb_plain:", ofb_plain)
gcm_tag = ofb_plain[:16]
gcm_nonce = ofb_plain[16:32]
gcm_cipher = unpad(ofb_plain[32:], 16)

また、AES-GCMとAES-OFBで鍵を共有しており、Nonceもコントロールできるので、AES-GCMの暗号化・復号をAES-OFBでの計算で代用できる。
AES-GCMに入力される128bit NonceとCounterの合成方法は http://csrc.nist.gov/publications/nistpubs/800-38D/SP-800-38D.pdf のsection 7.1 に書かれている。実装は適当にググってきて https://github.com/n0fate/iChainbreaker/blob/master/crypto/gcm.py から拝借した。

def gcm_oneblock(H, nonce, data, with_tag=True):
    j0 = ghash(H, b"", nonce)

    e = b""
    cb = j0
    for i in range(0, len(data), 16):
        cb = inc32(cb)
        e = e + xor(find_next_state(cb), data[i:i+16])
    if with_tag:
        s = ghash(H, b"", e)
        t = find_next_state(j0)
        tag = xor(s, t)
    else:
        tag = None
    return e, tag

H = find_next_state(bytes([0] * 16))

print("H:", H.hex())
gcm_plane, _ = gcm_oneblock(H, gcm_nonce, gcm_cipher, with_tag=False)

print("magic spell is:", gcm_plane)

gcm_giveme_nonce = H
gcm_giveme_cipher, gcm_giveme_tag = gcm_oneblock(H, H, b"give me key")
ofb_giveme = pad(gcm_giveme_tag + gcm_giveme_nonce + gcm_giveme_cipher, 16)
print(len(ofb_giveme))
print("ready to send spell")
print(d.challenge(
    (ofb_iv + xor(states[1], ofb_giveme[:16]) + xor(states[2], ofb_giveme[16:32]) + xor(states[3], ofb_giveme[32:])).hex()
))

magic spell: decrypt_all!!277260221!!
SECCON{you_solved_this!?I_g1ve_y0u_symmetr1c_cipher_mage_certificate}

insufficient

overview

SUGOI SECRET SHARING SCHEME with insufficient shares

from random import randint
from Crypto.Util.number import getPrime, bytes_to_long
from secret import FLAG


# f(x,y,z) = a1*x + a2*x^2 + a3*x^3
#          + b1*y + b2*y^2 + b3*y^3
#          + c*z + s mod p
def calc_f(coeffs, x, y, z, p):
    ret = 0
    ret += x * coeffs[0] + pow(x, 2, p) * coeffs[1] + pow(x, 3, p)*coeffs[2]
    ret += y * coeffs[3] + pow(y, 2, p) * coeffs[4] + pow(y, 3, p)*coeffs[5]
    ret += z * coeffs[6]
    ret += coeffs[7]

    return ret % p


p = getPrime(512)

# [a1, a2, a3, b1, b2, b3, c, s]
coeffs = [randint(0, 2**128) for _ in range(8)]

key = 0
for coeff in coeffs:
    key <<= 128
    key ^= coeff

cipher_text = bytes_to_long(FLAG) ^ key
print(cipher_text)

shares = []
for _ in range(4):
    x = randint(0, p)
    y = randint(0, p)
    z = randint(0, 2**128)

    w = calc_f(coeffs, x, y, z, p)
    packed_share = ((x,y), w)
    shares.append(packed_share)

print(p)
print(shares)

solution

格子問。法が512bitであるのに対し各係数が128bitと小さいので求まるのかな？変数を [a1, a2, a3, b1, b2, b3, z_i*c+s, 1] として以下の行列にLLLを適用する。

solver.sage

scale = 2^128

M = [[0 for i in range(15)] for j in range(15)]
for i in range(6):
    M[i][i] = scale # c0:6

for i in range(6, 10):
    M[i][i] = 1  # zi * c6 + c7

M[10][10] = 2^1024 # constant (w). ここの解は +1 になってほしいので極端に重くする。

for i in range(11, 15):
    M[i][i] = p  # modulo

for i in range(4):
    xy, w = shares[i]
    x, y = xy
    M[0][11+i] = x
    M[1][11+i] = x^2 % p
    M[2][11+i] = x^3 % p
    M[3][11+i] = y
    M[4][11+i] = y^2 % p
    M[5][11+i] = y^3 % p
    M[6+i][11+i] = 1
    M[10][11+i] = -w
    
ML = Matrix(M).LLL()

するとcoeffの頭6つ [a1, a2, a3, b1, b2, b3] が求まる。残りについては、
z_i * c + s mod p が i=0,1,2,3 の4つ手に入るので、これの差分をとって最小公倍数をとれば、c がその約数のうち128bitとなるどれかということになる。最後にそれを使ってcで割ったあまりを見ればsが求まる。ここでz_i * c + sは256bitであり、法のpを気にする必要はない。

solver.sage

def calc_f6(coeffs, x, y, p):
    ret = 0
    ret += x * coeffs[0] + pow(x, 2, p) * coeffs[1] + pow(x, 3, p)*coeffs[2]
    ret += y * coeffs[3] + pow(y, 2, p) * coeffs[4] + pow(y, 3, p)*coeffs[5]
    return ret

for row in ML:
    if row[10] != 2^1024:
        continue
    key = 0
    coeffs = []
    for i, coeff in enumerate(row[:6]):
        key <<= 128
        key ^^= coeff // scale
        coeffs.append(coeff // scale)
        assert coeff // scale < 2 ^128
    key <<= 128*2
    
    zccs = [(w - calc_f6(coeffs, x, y, p)) % p for (x,y),w in params]
    for zcc in zccs:
        assert zcc > 0 and zcc < 2^256
    c6x = gcd([abs(zccs[0] - zccs[1]), abs(zccs[1] - zccs[2]), abs(zccs[2] - zccs[3])])
    print(c6x)
    assert c6x < 2^128
    
    c6_valid = []
    for c6 in divisors(c6x):
        if c6 >= 2^128:
            break
        _key = key ^^ (c6 << 128)
        _m = long_to_bytes(_key ^^ cipher)
        if all([0x20 <= char <= 0x7e for char in _m[-32:-16]]): # 現れるflagがvalidならそのc6 (c)を採用
            c6_valid.append(c6)
    print(c6_valid)
    assert len(c6_valid) == 1
    
    c6 = c6_valid[0]
    c7 = zccs[0] % c6 # c7 (s) を求める
    
    key ^^= (c6 << 128) ^^ c7
    print(long_to_bytes(key ^^ cipher))

SECCON{Unfortunately_I_could_not_come_up_with_a_more_difficult_problem_than_last_year_sorry...-6fc18307d3ed2e7673a249abc2e0e22c}

Web

easylfi

overview

Can you read my secret?

web/app.py

from flask import Flask, request, Response
import subprocess
import os

app = Flask(__name__)


def validate(key: str) -> bool:
    # E.g. key == "{name}" -> True
    #      key == "name"   -> False
    if len(key) == 0:
        return False
    is_valid = True
    for i, c in enumerate(key):
        if i == 0:
            is_valid &= c == "{"
        elif i == len(key) - 1:
            is_valid &= c == "}"
        else:
            is_valid &= c != "{" and c != "}"
    return is_valid


def template(text: str, params: dict[str, str]) -> str:
    # A very simple template engine
    for key, value in params.items():
        if not validate(key):
            return f"Invalid key: {key}"
        text = text.replace(key, value)
    return text


@app.after_request
def waf(response: Response):
    return Response(str(b"".join(response.response)))
    if b"SECCON" in b"".join(response.response):
        return Response("Try harder")
    return response


@app.route("/")
@app.route("/<path:filename>")
def index(filename: str = "index.html"):
    if ".." in filename or "%" in filename:
        return "Do not try path traversal :("

    try:
        proc = subprocess.run(
            ["curl", f"file://{os.getcwd()}/public/{filename}"],
            capture_output=True,
            timeout=1,
        )
    except subprocess.TimeoutExpired:
        return "Timeout"

    if proc.returncode != 0:
        return "Something wrong..."
    return template(proc.stdout.decode(), request.args)

ファイル名を指定してGETパラメータに沿ったテンプレートを適用できる。
一つ上のディレクトリにflag.txtがあるが、..の使用を妨害されるためそのままではトラバーサルできない。また、これを回避してもwaf()によってSECCONを含むレスポンスは拒絶される。

solution

curlは/path/to/{one,two,three}.txtのようにすることで複数ファイルを指定することができる。実は単数でも問題なくて、{.}{.}/は../と等価になる。これを使ってフィルタを回避する。

またcurlは複数ファイル指定すると改行を挟んで各ファイルをconcatする。つまり手前のファイルに{があれば、その次に指定したflag.txtのSECCON{...という文字をテンプレートで消せるかもしれない。validate()をみると実は{のみでもテンプレートのキーとして受理されることがわかり、{ -> }{と置き換えることで

...something... }{ ...
SECCON}{flag_is_here}

というレスポンスを作ることができるので、あとは { ...\nSECCON} を置き換えればwafを回避できる。
前半の{を含むファイルとして /proc/self/cmdlineを利用した。

query.txt

/%7B.%7D%7B.%7D/%7B.%7D%7B.%7D/%7Bproc/self/cmdline,flag.txt%7D?{proc/self/cmdline,flag.txt}={hoge}&{hoge}={&{=}{&{%00--_curl_--file:///app/public/../../flag.txt%0ASECCON}=fuga

SECCON{i_lik3_fe4ture_of_copy_aS_cur1_in_br0wser}