2026年第二届湾区杯网络安全大赛 WriteUp

Reverse

Pixel Oracle

题目信息

题目提供 pixel_oracle.apk。程序界面包含一个 5×5 棋盘、上下左右移动按钮和 Flag 输入框。

校验器不会直接比较明文 Flag，而是依次检查移动路线长度、棋盘边界、路线的 FNV-1a 哈希、棋盘分数回放、JNI native gate，并使用 native gate 派生的 xorshift32 密钥流解密字节数组。

附件外层 ZIP 的 SHA-256 为：

1	a96931bdba1bc56fc43bac8b1d35baf4ea77319f90f6b3ed69f48a7a60bcc422

解压得到的 APK SHA-256 为：

1	b80c5d7247b22ccda5bb1790a87b8e7a252256ab9e08af44758400a79718ea1b

APK 中包含 classes.dex，以及 x86 和 x86_64 两种架构的 libpixgate.so。整个过程只进行静态解包、反编译和脚本模拟，没有在宿主机安装或执行 APK 和 native 库。

解题思路

先使用 JADX 反编译 classes.dex。MainActivity.verify() 显示路线必须恰好包含 11 个 U、D、L、R 字符，起点为 (0,4)，每步必须位于 5×5 棋盘内。

路线还需要同时满足两个约束：

1 2	FNV-1a(path) = 0xb97de93a score(path) = 0x33191d74

每次移动后的分数更新规则为：

1	score = ((score * 131) ^ (BOARD[y][x] + move * (index + 7))) & 0x7fffffff;

初始分数是 20823。由于合法路线只有 11 步，直接深度优先枚举棋盘内路线，并在枚举过程中同步维护 FNV-1a 和 score，即可恢复正确路径。

随后分析 x86_64 的 libpixgate.so。ELF 没有加壳，保留了以下符号：

1
2
3

Java_com_ddl4_easy_MainActivity_ng  0x1330
rotl32                               0x1380
xs32                                 0x13b0

JNI 函数的等价逻辑为：

uint32_t native_gate(uint32_t path_hash, uint32_t score) {
    uint32_t state = path_hash ^ rotl32(score, 5) ^ 0x6f726163;
    return xs32(state) ^ 0x42b0c0de;
}

最后使用 native gate、score 和路径哈希生成 xorshift32 初始状态。每个密文字节都先更新一次 xorshift32，再取状态低字节参与异或，因此更新顺序不能颠倒。

技术实施

FNV-1a 使用标准 32 位初值和质数：

1 2	初值：0x811c9dc5 步进：hash = ((hash ^ byte) * 0x01000193) mod 2^32

恢复出的路线为：

1	UURRDRURDDL

逐步回放结果如下：

step=01 move=U pos=(0,3) cell= 68 score=0x00299d12
step=02 move=U pos=(0,2) cell= 88 score=0x154b6336
step=03 move=R pos=(1,2) cell= 13 score=0x6593c64d
step=04 move=R pos=(2,2) cell= 57 score=0x7a9e7a0a
step=05 move=D pos=(2,3) cell= 18 score=0x3f1871e0
step=06 move=R pos=(3,3) cell= 85 score=0x4982418d
step=07 move=U pos=(3,2) cell=124 score=0x1da78fea
step=08 move=R pos=(4,2) cell= 32 score=0x2cbea022
step=09 move=D pos=(4,3) cell= 42 score=0x658bf540
step=10 move=D pos=(4,4) cell= 77 score=0x769e7b4d
step=11 move=L pos=(3,4) cell=  7 score=0x33191d74

该路线的 FNV-1a 为 0xb97de93a，最终 score 为 0x33191d74。代入 JNI 逻辑得到 native gate 0x4dbcda7a，与 Java 层的预期常量完全一致。

xorshift32 的 seed 为：

1	seed = native_gate ^ score ^ path_hash ^ 0x9e3779b9

每轮更新和字节解密规则为：

state ^= state << 13
state ^= state >>> 17
state ^= state << 5
plain[i] = ENC[i] ^ (state & 0xff) ^ ((i * 17 + 61) & 0xff)

完整解题脚本

#!/usr/bin/env python3

BOARD = [
    [35, 65, 23, 91, 45],
    [9, 114, 78, 49, 102],
    [88, 13, 57, 124, 32],
    [68, 111, 18, 85, 42],
    [51, 24, 106, 7, 77],
]
ENC = [
    25, 129, 65, 214, 197, 155, 129, 91, 120,
    192, 253, 116, 19, 90, 28, 56, 17, 211,
    122, 151, 167, 47, 107, 204, 184, 212, 114,
]
EXPECTED_PATH_HASH = (-1182930630) & 0xffffffff
EXPECTED_SCORE = 857283956
EXPECTED_NATIVE_GATE = 1304222330
EXPECTED_FLAG_HASH = 665128300
MOVES = {
    "U": (0, -1),
    "D": (0, 1),
    "L": (-1, 0),
    "R": (1, 0),
}


def u32(value):
    return value & 0xffffffff


def fnv1a(data):
    value = 0x811c9dc5
    for byte in data:
        value = u32((value ^ byte) * 0x01000193)
    return value


def xs32(value):
    value = u32(value ^ u32(value << 13))
    value = u32(value ^ (value >> 17))
    return u32(value ^ u32(value << 5))


def rotl32(value, count):
    return u32((u32(value) << count) | (u32(value) >> (32 - count)))


def native_gate(path_hash, score):
    state = u32(path_hash ^ rotl32(score, 5) ^ 0x6f726163)
    return u32(xs32(state) ^ 0x42b0c0de)


def djb2(text):
    value = 5381
    for char in text:
        value = u32(ord(char) ^ u32((value << 5) + value))
    return value


def replay(path):
    x, y, score = 0, 4, 20823
    rows = []
    for index, move in enumerate(path):
        dx, dy = MOVES[move]
        x += dx
        y += dy
        if not (0 <= x < 5 and 0 <= y < 5):
            return None
        cell = BOARD[y][x]
        score = ((score * 131) ^ (cell + ord(move) * (index + 7))) & 0x7fffffff
        rows.append((index + 1, move, x, y, cell, score))
    return score, rows


def find_route(prefix="", x=0, y=4, score=20823, path_hash=0x811c9dc5):
    index = len(prefix)
    if index == 11:
        if path_hash == EXPECTED_PATH_HASH and score == EXPECTED_SCORE:
            return prefix
        return None

    for move, (dx, dy) in MOVES.items():
        next_x = x + dx
        next_y = y + dy
        if not (0 <= next_x < 5 and 0 <= next_y < 5):
            continue

        byte = ord(move)
        next_score = (
            (score * 131) ^ (BOARD[next_y][next_x] + byte * (index + 7))
        ) & 0x7fffffff
        next_hash = u32((path_hash ^ byte) * 0x01000193)

        result = find_route(
            prefix + move,
            next_x,
            next_y,
            next_score,
            next_hash,
        )
        if result:
            return result
    return None


def decrypt_flag(gate, score, path_hash):
    state = u32(gate ^ score ^ path_hash ^ 0x9e3779b9)
    output = []
    for index, encrypted in enumerate(ENC):
        state = xs32(state)
        plain = encrypted ^ (state & 0xff) ^ ((index * 17 + 61) & 0xff)
        output.append(chr(plain & 0xff))
    return "".join(output)


def main():
    route = find_route()
    assert route is not None

    score, rows = replay(route)
    path_hash = fnv1a(route.encode("ascii"))
    gate = native_gate(path_hash, score)
    flag = decrypt_flag(gate, score, path_hash)

    print("route =", route)
    print("length =", len(route))
    print("fnv1a = 0x%08x" % path_hash)
    print("score = 0x%08x" % score)
    print("native_gate = 0x%08x" % gate)
    for row in rows:
        print(
            "step=%02d move=%s pos=(%d,%d) cell=%3d score=0x%08x"
            % row
        )
    print("flag =", flag)
    print("djb2 = 0x%08x" % djb2(flag))

    assert path_hash == EXPECTED_PATH_HASH
    assert score == EXPECTED_SCORE
    assert gate == EXPECTED_NATIVE_GATE
    assert len(flag) == 27
    assert djb2(flag) == EXPECTED_FLAG_HASH
    print("ALL_CHECKS_OK")


if __name__ == "__main__":
    main()

验证输出

route = UURRDRURDDL
length = 11
fnv1a = 0xb97de93a (-1182930630 signed)
score = 0x33191d74 (857283956)
native_gate = 0x4dbcda7a (1304222330)
flag = flag{pix_oracle_moves_5279}
djb2 = 0x27a50d6c (665128300)
ALL_CHECKS_OK

路径哈希、score、native gate 和最终 DJB2-XOR 均与 APK 内的目标常量一致。平台提交后确认 Flag 正确。

问题与解决

该题的 Flag 不以明文形式存在，单纯搜索字符串无法得到结果。真正的关键是先恢复移动路线，因为路径哈希和分数共同决定 native gate，而 native gate 又参与 xorshift32 seed 的构造。

Java 的 int 运算具有 32 位溢出语义，Python 实现时必须在 FNV-1a、旋转、xorshift32 和 DJB2 的每个关键阶段使用 & 0xffffffff 截断。score 还额外使用 & 0x7fffffff 清除符号位。如果忽略这些截断，后续 native gate 和解密结果都会错误。

知识点总结

本题组合了 Android DEX 反编译、JNI ELF 静态分析、棋盘状态回放、FNV-1a、32 位整数溢出、循环左移和 xorshift32。校验链存在明确的数据依赖：路线决定路径哈希与 score，二者决定 native gate，最终共同决定解密 seed。因此需要完整还原整条链，而不能只分析最后的密文字节数组。

参考资料

Fowler–Noll–Vo hash function
George Marsaglia, Xorshift RNGs
Android JNI native method naming convention

最终 Flag

1	flag{pix_oracle_moves_5279}

Crypto

TinyNTRU

题目信息

题目提供 TinyNTRU-like 公钥加密方案的源码、公钥和密文，目标是恢复私钥多项式并解密 Flag。附件 ZIP 的 SHA-256 需以题目目录中的原始证据为准；解题过程未向外部站点上传附件或明文。

解题思路

方案工作在环 R = Z[x]/(x^127 - 1) 上，参数为 q = 12289、p = 3。私钥满足 f = 1 + 3F，其中 F 只有 7 个 ±1 系数；g 也只有 7 个非零系数，公钥关系为：

1	h = f^(-1) · g mod q

因此可以利用：

1	f · h = g mod q

恢复私钥。由于 f 和 g 极度稀疏，且系数集合被限制在 {−3, 0, 1, 3}，采用三坐标约束的 meet-in-the-middle 枚举比通用格攻击更直接且确定性更强。枚举 f 中 4 个 +3 位置和 3 个 −3 位置，在 g 的零坐标上匹配卷积约束，命中后完整卷积验证 f · h ≡ g (mod q)。

技术实施

恢复出的私钥位置为：

f[0] = 1
f 的 +3 位：15, 28, 49, 66
f 的 −3 位：55, 61, 106

g 的 +3 位：60, 62, 121, 123
g 的 −3 位：18, 55, 87

对应系数形状为：

1 2	f ∈ {−3, 0, 1, 3}，除 f[0] 外有 7 个非零系数 g ∈ {−3, 0, 3}，共有 7 个非零系数，其中 4 个为 +3、3 个为 −3

源码、公钥和密文位于：

1	D:\CaptureTheFlag\Analysis\Writeup\CTF\湾区杯\Crypto\TinyNTRU\source\

离线恢复和解密命令：

1
2
3

& 'C:\Program Files (x86)\Dev-Cpp\MinGW64\bin\g++.exe' -O3 -std=c++11 recover_sparse.cpp -o recover_sparse.exe
.\recover_sparse.exe source\public_key.txt > recovered_key.txt 2> recover_stderr.txt
& 'C:\Users\glj07\AppData\Local\Programs\Python\Python310\python.exe' decrypt_recovered.py > decrypt_output.txt

解密脚本的核心校验如下，脚本同时验证公钥关系、系数形状、Flag 格式和重新编码往返一致性：

params = NTRUParams(127, 3, 12289, 7, 7, 6, 24)
h = assignment(SRC / 'public_key.txt', 'h')
ciphertexts = assignment(SRC / 'output.txt', 'ciphertexts')
f = listline(ROOT / 'recovered_key.txt', 'f')
g = listline(ROOT / 'recovered_key.txt', 'g')

assert poly_mul(f, h, params.N, params.q) == [x % params.q for x in g]
assert f[0] == 1
assert sum(x != 0 for x in f[1:]) == params.df
assert set(f) <= {-3, 0, 1, 3}
assert sum(x != 0 for x in g) == params.dg
assert set(g) <= {-3, 0, 3}

blocks = [decrypt(c, PrivateKey(f, g), params) for c in ciphertexts]
plaintext = poly_blocks_to_bytes(blocks, params.chunk_bytes)
recoded = bytes_to_poly_blocks(plaintext, params.N, params.chunk_bytes)
assert recoded == blocks

恢复程序第一次和第二次运行均确定性命中 coords=0,1,2，退出码为 0，输出一致。解密得到 2 个密文块，共 42 字节明文。明文 SHA-256 为：

1	02ae75274d129533f14db58a5de9db6cf7e243e9974b9ab7bafa51e138b9ead4

验证输出摘要：

verify_f_times_h_eq_g=true
blocks=2 plaintext_len=42
flag_format=True
reencode_blocks_match=True

问题与解决

直接把公钥当作普通整数或只做字符串搜索无法恢复明文。关键在于识别出 NTRU 公钥关系以及私钥的极端稀疏约束，再利用卷积零坐标构造确定性匹配。Python 解密时必须遵守源码的多项式环模运算、三进制块编码和字节序，否则即使私钥恢复正确，也会得到错误明文。

知识点总结

本题涉及 NTRU 公钥关系、环上多项式卷积、稀疏短向量恢复、meet-in-the-middle 枚举、模逆、三进制多项式编码和可逆性验证。恢复私钥后，应同时进行代数校验、系数形状校验、明文格式校验和重新编码往返校验，不能只依赖 flag{...} 格式判断。

参考资料

NTRU 公钥加密基本构造
多项式环 Z[x]/(x^N - 1) 上的卷积运算
Meet-in-the-middle 搜索
模运算与多项式可逆性

最终 Flag

1	flag{27dec48f-f9c7-4bad-9a1b-f7aa77badc5f}

2026年第二届湾区杯网络安全大赛 WriteUp

Reverse

Pixel Oracle

题目信息

解题思路

技术实施

完整解题脚本

验证输出

问题与解决

知识点总结

参考资料

最终 Flag

Crypto

TinyNTRU

题目信息

解题思路

技术实施

问题与解决

知识点总结

参考资料

最终 Flag

Steam好友代码