Google CTF 2025 write-ups [crypto]

⚠️ 주인장이 오랜만에 CTF 감 좀 익히려고 작년에 이미 끝난 대회의 크립토 문제를 끄적여본 것입니다.

numerology - 50pt (218 solved)

First, decompile .pyc file with PyLingual. You can get the python file but be aware that this file is not completely correct.

You can find that using only one round is vulnerable to create key stream. Only 0, 4, 8, 12-th idx of state is shuffled. Also, ciphertext of flag is 48 bytes so nonce doesn’t matter with encrypting the flag. You don’t know the secret counter but using the plaintext starts with ‘CTF{‘, you can recover the secret counter number. The problem is that we don't know d0, while we know a0, b0, c0, a2 in mix_bits(). Refer to below code:

MASK = 0xffffffff

def rotl32(v, c):
    v &= MASK
    return ((v << c) & MASK) | (v >> (32 - c))

def rotr32(v, c):
    v &= MASK
    return (v >> c) | ((v << (32 - c)) & MASK)

def add32(a, b): return (a + b) & MASK
def sub32(a, b): return (a - b) & MASK

def recover_d0_from_a2(a0, b0, c0, a2):
    a1 = add32(a0, b0)
    b1 = sub32(a2, a1)
    c1 = (b0 ^ rotr32(b1, 12)) & MASK
    d1 = sub32(c1, c0)
    d0 = (rotr32(d1, 16) ^ a1) & MASK
    return d0

So, you can fully recover the plaintext by revealing the key.

CTF{w3_aRe_g0Nn@_ge7_MY_FuncKee_monkey_!!}

filtermaze - 180pt (61 solved)

First, you can get the absolute value of error by finding the hamilton path for node by node.

import json
from pwn import remote
import os
import sys
import urllib.request
import tempfile
import subprocess

POW_URL = "https://goo.gle/kctf-pow"

def solve_pow_from_token(token: str) -> str:
    token = token.strip()

    # kctf-pow 스크립트 다운로드 -> 임시 파일로 저장 -> subprocess로 실행
    with urllib.request.urlopen(POW_URL) as r:
        script_text = r.read().decode("utf-8", errors="replace")

    with tempfile.NamedTemporaryFile("w", suffix=".py", delete=False) as f:
        f.write(script_text)
        script_path = f.name

    try:
        # 사용 예: python3 kctf-pow_script solve <token>
        out = subprocess.check_output(
            [sys.executable, script_path, "solve", token],
            text=True,
        )
        return out.strip()
    finally:
        try:
            os.unlink(script_path)
        except OSError:
            pass


def main():
    p = remote("filtermaze.2025.ctfcompetition.com", 1337, level="debug")

    _ = p.recvuntil(b"with:\n")
    data = p.recvline()
    token = data.decode().strip().split("solve ")[-1]
    print("token:", token)

    ans = solve_pow_from_token(token)
    print("pow answer:", ans)

    # 서버가 요구하는 포맷이 "정답 한 줄"이면 보통 이렇게 보냅니다.
    p.sendline(ans.encode())

    # 이후 프로토콜에 따라 추가 recv/send가 필요할 수 있음
    _ = p.recvuntil("get_flag")
    _ = p.recvline()

    # Solve Hamiltonian Path
    e = None
    with open("graph.json", "r") as f:
        graph = json.load(f)
    segment = [0]
    while True:
        current_node = segment[-1]
        nodes = graph[str(current_node)]
        for node in nodes:
            if node in segment:
                continue
            payload = {"command": "check_path", "segment": segment + [node]}
            p.sendline(json.dumps(payload).encode())
            result = json.loads(p.recvline())
            if result["status"] == "valid_prefix":
                segment.append(node)
                break
            elif result["status"] == "path_complete":
                e = result["lwe_error_magnitudes"]
                break

        if e is not None:
            break
    print(e)

if __name__ == "__main__":
    main()

Now, simplify the problem by using left kernel of A. Build the lattice to apply LLL. re-weighting is important and I learned that I must convert sparse matrix to dense matrix before applying LLL.

import json

with open("lwe_pub_params.json", "r") as f:
    params = json.load(f)

n = params["lwe_n"]
m = params["lwe_m"]
q = params["lwe_q"]
F = Zmod(q)
A = Matrix(F, params["A"])
b = vector(F, params["b"])
e = vector(
    F,
    [
        265,
        622,
        38,
        716,
        722,
        308,
        996,
        799,
        742,
        337,
        927,
        698,
        626,
        969,
        330,
        126,
        321,
        20,
        271,
        839,
        175,
        399,
        752,
        989,
        666,
        629,
        271,
        400,
        311,
        840,
        821,
        821,
        17,
        978,
        488,
        781,
        74,
        818,
        849,
        903,
        776,
        142,
        505,
        951,
        582,
        638,
        222,
        872,
        427,
        165,
        307,
        209,
        475,
        970,
        748,
        814,
        69,
        213,
        27,
        742,
        744,
        566,
        262,
        852,
        740,
        309,
        997,
        502,
        995,
        434,
        405,
        193,
        257,
        953,
        924,
        678,
        232,
        226,
        560,
        414,
        584,
        579,
        767,
        810,
        51,
        894,
        446,
        281,
        761,
        908,
        715,
        787,
        722,
        270,
        94,
        169,
        474,
        431,
        292,
        346,
    ],
)

new_b = Matrix(ZZ, A.left_kernel_matrix() * b)
new_A = Matrix(ZZ, A.left_kernel_matrix() * diagonal_matrix(e))

# b = A * s + e
# new_b = new_A * sig

M = (
    Matrix(new_A)
    .augment(matrix(new_b).T)
    .change_ring(ZZ)
    .augment(diagonal_matrix([q] * 50))
)
N = Matrix(diagonal_matrix([1 / QQ(1000)] * 100).augment(zero_matrix(100, 51))) # Important!! 
M = M.stack(N).stack(vector([0] * 100 + [1] + [0] * 50))

for row in matrix(M, sparse=False).T.LLL():  # Important!!
    if row[-1] == 1:
        sign = -row[50:150] * 1000

real_e = vector(F, [ZZ(e) * ZZ(s) for e, s in zip(e, sign)])
s = A.solve_right(b - real_e)
print(s)

CTF{d4_sup3r_sh0rt_3rr0r_v3ct0r_1s_th3_k3y}