FLAG:
PCTF{Db2R9bfqt4oVaXIjIxX1q9INqNX8mtL4}
附件:
doxc坏了?.zip→chall.py(加密器)、broken.docx(密文容器)
1. 先看容器:它不是 DOCX
broken.docx(38880 字节)开头是 44 43 58 32 = DCX2,而不是 PK。
头部结构由 chall.py 定义:
FIXED_HEADER = struct.Struct("<4sIQ16s") # magic, version, orig_len, salt
header = FIXED_HEADER.pack(MAGIC, VERSION, len(data), salt) # 32 字节
header += pack_vector(commitments) # 4 × 16 字节
header += pack_vector(iv_plain) # 4 × 16 字节
header += pack_vector(iv_cipher) # 4 × 16 字节分组方式:每 64 字节一块 = 4 个 lane,每个 lane 是 16 字节小端整数,所有运算都在 Z/2^128 里(MOD = 1<<128)。填充是 ISO/IEC 7816-4 风格(补 n 个字节 n)。
2. 加密流程拆解
对每个 64 字节块(按 order 重排后的顺序 sequence_index = seq 处理):
mixed[l] = block[l] + key[(l+seq)%4] + rol128(prev_plain[(l+1)%4], PLAIN_ROT[l])
+ (seq+1) * INDEX_CONSTANT[l] (mod 2^128)
transformed = scramble(mixed) # 可逆混淆
cipher[l] = transformed[l] XOR rol128(prev_cipher[(l+2)%4], CIPHER_ROT[l])
prev_plain = block # 明文反馈
prev_cipher = cipher_block # 密文反馈其中
scramble(v) = outer_backward( polynomial_layer( outer_forward(v) ) )
polynomial_layer(v) = base(v) + 2·nonlinear(v) + 4·high(v)
base = stage_backward ∘ linear_layer ∘ stage_forwardkey=SHAKE-256("PCTF-DOCX-KEY\0" || salt || e_0..e_3)取 64 字节 → 4 laneorder= 用SHA256("PCTF-DOCX-ORDER\0" || key || salt || i)对i排序(防止块重排/交换)密钥种子是 4 个 126 bit 指数
e_i,公开的commitments是
c_i = pow(UNIT_BASE, e_i, MOD) # 模 2^128看上去"给了 4 个 126 bit 指数的单向承诺",安全性应该来自离散对数——这正是设计者以为安全的地方。
3. 第一步:把 commitments 的离散对数打穿
关键观察:模数 2^128 的乘法群结构极其"光滑"。
(Z/2^n)^* ≅ C2 × C_{2^(n-2)} (n ≥ 3)即它是个纯 2-群,阶为 2^127,只有因子 2。而
UNIT_BASE = 0x2FB09295078398D5DF239A6DB9760155满足 UNIT_BASE ≡ 5 (mod 8)(末字节 0x55),因此它在 1+4Z 这个循环子群里是生成元,阶恰好为 2^126(脚本里连续平方 126 次才得到 1,可验证)。
于是三件事同时成立:
群阶没有大素因子 → Pohlig–Hellman 直接崩成一个二进制阶梯,不是
2^63的 BSGS;指数采样范围是
secrets.randbits(126) < 2^126,与元素阶完全相同 → 解唯一,不存在e + k·2^126的歧义;解只需要
O(126²)次模乘。
推导(2-adic 逐位提升,本质是 Pohlig–Hellman 在 2-群上的形式):
设 h = g^E, k = 126。低位已经求出、累计为 e,记残量 r = h·g^{-e} = g^{2^i·(E>>i)}。因为 g^{2^{k-1}} ≡ -1 (mod 2^128)(阶 2 的唯一元素),所以
r^(2^(k-1-i)) = (-1)^( (E>>i) mod 2 ) ∈ {1, -1}一步就测出 E 的第 i 位,然后 r ← r·g^{-bit·2^i} 继续。实现只有十几行:
def dlog_base_unit(h, k=126):
g_inv = pow(UNIT_BASE, -1, MOD)
e, r = 0, h % MOD
for i in range(k):
if pow(r, 1 << (k - 1 - i), MOD) != 1:
e |= 1 << i
r = (r * pow(g_inv, 1 << i, MOD)) % MOD
return e结果(每个都回代 pow(UNIT_BASE, e, MOD) == c 验过):
e0 = 0x171f510e90ff0fa06f60984a06803fe5
e1 = 0x19ad49883672d5435a4485600116a1fa
e2 = 0x0b38b0fd5ae1842e2b698a62382407d9
e3 = 0x3467463a95e654b8f26a88b2385ec303这条路径也解释了题目为什么"必然坏":承诺不是放在素数阶群/椭圆曲线上,而是放在
2^128这个 2-群上。模数选错,126 bit 的指数等于明文。
4. 第二步:key 与块顺序
指数拿到后,key 和 order 都是纯确定性推导,直接照抄 chall.py:
key = SHAKE-256("PCTF-DOCX-KEY\0" || salt || e_0||e_1||e_2||e_3) → 4 lane
= c95ba8b5be49ce049dc7d7e672954960
50f3d2f0a4a37001ebc199920aa79687
df0ffee2e5d52562f6d0c9673c994ab6
a5572cb372eb1b8bc723a5836ff7dae3
order = sorted(range(604), key=i ↦ SHA-256("PCTF-DOCX-ORDER\0" || key || salt || i))5. 第三步:逆 scramble(本题真正的技术点)
outer_forward / outer_backward 互为逆(z3 先用 z0、z1 修正,逐级回退),stage_forward / stage_backward 同样是显式三角可逆。唯一麻烦的是 polynomial_layer:
P(x) = Q(x) + 2·N(x) + 4·H(x) (N 是二次、H 是五次齐次式)
Q = stage_backward(linear_layer(stage_forward(x)))它不是线性的,也不能像仿射层那样"减一下就反"。但它有一个非常好的结构:
stage_*里的非线性项都是二次的,所以Q的线性主部恰好就是linear_layer(记作L);2N、4H的系数全为偶数,模 2 直接消失。
于是
P(x) = L·x + R(x) R 为二次及以上的整系数多项式,R(0) = 0P mod 2是F2^4上的双射(脚本枚举 16 个残基,像集正好 16 个),但它是非线性的:R(x)的偶次项 mod 2 并不为 0;对 16 个残基实测
Jacobian mod 2,行列式恒为 1(每点都可逆)。注意J_P(x0) mod 2只在x0 = 0时等于L,其它残基都会被R'(x0)改写,所以必须数值求,不能直接拿linear_layer当 Jacobian。
这正是 Hensel / 逐位提升 的适用条件,也等价于说 P 在 (Z/2^128)^4 上是双射。
设已知 P(x)=y 的 x mod 2^i,写 x = x0 + 2^i·t:
P(x) - P(x0) = 2^i · J_P(x0) · t + O(2^(2i)) ≡ 2^i · J_P(x0) · t (mod 2^(i+1))于是每一位只需在 F2 上解一个 4×4 线性方程组:
(y - P(x0)) >> i ≡ J_P(x0) · t (mod 2)实现时有两个容易踩的坑:
第 0 位不能提升:
i = 0时x - x0只是 1 的倍数,R(x) - R(x0)、2N、4H的贡献全都还留在 mod 2 里,P(x) ≡ P(x0) + J·t (mod 2)并不成立(此时P mod 2非线性)。所以第 0 位只能直接枚举 16 个残基取唯一解;Jacobian 要用
(P(x0 + 2e_j) - P(x0)) / 2 mod 2数值求出,不要手推——这样即使换参数也不会写错。
def polynomial_layer_inv(y):
# bit 0: P mod 2 是 F2^4 上的置换,但非线性 -> 枚举
cands = [r for r in range(16)
if tuple(v & 1 for v in polynomial_layer(tuple((r >> j) & 1 for j in range(4))))
== tuple(v & 1 for v in y)]
assert len(cands) == 1
x = [(cands[0] >> j) & 1 for j in range(4)]
for i in range(1, 128):
f = polynomial_layer(tuple(x))
diff = tuple((y[j] - f[j]) & MASK for j in range(4))
assert all(d % (1 << i) == 0 for d in diff)
rhs = tuple((d >> i) & 1 for d in diff)
cols = jacobian_mod2(x) # J_P(x0) mod 2
sols = [t for t in range(16) if jac_mod2_mul(cols, t) == rhs]
assert len(sols) == 1 # 唯一解 <=> Jacobian 可逆
t = sols[0]
for j in range(4):
if (t >> j) & 1:
x[j] |= 1 << i
return tuple(x)unscramble(y) = outer_backward(P^{-1}(outer_forward(y)))。脚本开头跑了几组随机 roundtrip 自检(unscramble(scramble(v)) == v),确保逆变换无误后才解真实数据。
题面 DOCX 里那句提示"应关注运算模数、奇偶性以及多项式导数",指的正是上面三件事:模 2^128(模数)、逐位提升(奇偶性)、Jacobian / 导数(多项式导数)。
6. 第四步:逐块解密
有了 key、order、unscramble,剩下的就是把加密公式按 seq 顺序倒过来(反馈链必须同序解密):
for seq, orig in enumerate(order):
transformed = cipher[lane] XOR rol128(prev_cipher[(lane+2)%4], CIPHER_ROT[lane])
mixed = unscramble(transformed)
block[lane] = mixed[lane] - key[(lane+seq)%4]
- rol128(prev_plain[(lane+1)%4], PLAIN_ROT[lane])
- (seq+1) * INDEX_CONSTANT[lane] # mod 2^128
plain_blocks[orig] = block
prev_plain, prev_cipher = block, cipher_block最后按原始下标拼回 604 块,按头部 plain_len = 38630 截断,校验填充(实际解出 26 个 0x1a,正符合 pad() 的 64 - 38630 % 64 = 26)。
7. 验证
解出的正文(节选):
PCTF 文档加密审计记录
内部材料 仅供密码系统复核
记录编号 PCTF-H2AD-2026-017 ← 表格
审计对象 128 位自定义文档加密器
审计结论 核心置换存在可逆性设计缺陷
审计摘要
本记录验证了一套面向办公文档的自定义加密方案。系统能够破坏原始包结构,
使常规办公软件无法识别文件,但其核心变换在二进制整数环中保留了过强的可逆性质。
分析人员应关注运算模数、奇偶性以及多项式导数,而不是尝试搜索 128 位密钥空间。
所有恢复工作都必须直接作用于完整文件字节流。
恢复凭据
授权标识:PCTF{Db2R9bfqt4oVaXIjIxX1q9INqNX8mtL4}8. 为什么其它"暴力"思路都不成立
穷举 key:4×128 bit,且 key 由 126 bit 指数经 SHAKE 派生,
2^504/2^252,不可行;只解密不还原顺序:
order由 key 决定,块序错一位整篇乱码(而且INDEX_CONSTANT让每块的偏移都不同,不能靠"已知明文块"平移);绕开
polynomial_layer:它是2^128环上的双射,没有"部分求逆"或近似逆;唯一可行的是 Hensel 提升;CBC 式反转:XOR 反馈用的是
prev_cipher(可逆),但prev_plain反馈与seq耦合,必须先有 key 和 order。
真正"坏掉"的只有两点:承诺放在 2-群上(dlog 可解),以及核心置换在二进制整数环上是可逆的(Hensel 可逆)。
9. Exp
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Usage: python solve.py [encrypted] [output.docx]
"""
import argparse
import hashlib
import secrets
import struct
from pathlib import Path
MOD = 1 << 128
MASK = MOD - 1
LANES = 4
MAGIC = b"DCX2"
VERSION = 3
HEADER = struct.Struct("<4sIQ16s") # magic, version, plain_len, salt
HEADER_SIZE = HEADER.size + 3 * 64 # 32 + commitments + iv_plain + iv_cipher = 224
UNIT_BASE = 0x2FB09295078398D5DF239A6DB9760155
UNIT_ORDER_BITS = 126 # ord(UNIT_BASE) == 2**126
INDEX_CONSTANT = (
0x9E3779B97F4A7C15F39CC0605CEDC835,
0xD1342543DE82EF95C6BC279692B5CC83,
0xA24BAED4963EE4079FB21C651E98DF25,
0xC13FA9A902A6328F91E10DA5C79E7B1D,
)
PLAIN_ROTATIONS = (17, 31, 47, 73)
CIPHER_ROTATIONS = (23, 41, 59, 83)
AFFINE_BIAS = (
0xA3C59AC3C3D2E1F08796A5B4C3D2E1F0,
0x1B03738712FAD5C9E7F496A80C31D24B,
0xC6BC279692B5CC83D1B54A32D192ED03,
0x91E10DA5C79E7B1DA24BAED4963EE407,
)
# --------------------------------------------------------------------------- #
# helpers
# --------------------------------------------------------------------------- #
def rol128(value, shift):
shift &= 127
return ((value << shift) | (value >> ((128 - shift) & 127))) & MASK
def pack_vector(values):
return b"".join((v & MASK).to_bytes(16, "little") for v in values)
def unpack_vector(data):
assert len(data) == 64
return tuple(int.from_bytes(data[i:i + 16], "little") for i in range(0, 64, 16))
# --------------------------------------------------------------------------- #
# 1. discrete log in the 2-group of units mod 2**128
# --------------------------------------------------------------------------- #
def dlog_base_unit(h, k=UNIT_ORDER_BITS):
"""Return the unique e in [0, 2**k) with UNIT_BASE**e == h (mod 2**128)."""
g_inv = pow(UNIT_BASE, -1, MOD)
e, r = 0, h % MOD
for i in range(k):
# r == g**(bit_i * 2**i + 2**(i+1) * ...) -> r**(2**(k-1-i)) == (-1)**bit_i
if pow(r, 1 << (k - 1 - i), MOD) != 1:
e |= 1 << i
r = (r * pow(g_inv, 1 << i, MOD)) % MOD
return e
# --------------------------------------------------------------------------- #
# 2. the permutation / polynomial layers
# --------------------------------------------------------------------------- #
def stage_forward(v):
z = list(v)
z[0] = (z[0] + z[1] * z[2]) & MASK
z[1] = (z[1] + z[2] * z[3]) & MASK
z[2] = (z[2] + z[3] * z[0]) & MASK
z[3] = (z[3] + z[0] * z[1]) & MASK
return tuple(z)
def stage_backward(v):
z = list(v)
z[3] = (z[3] - z[0] * z[1]) & MASK
z[2] = (z[2] - z[3] * z[0]) & MASK
z[1] = (z[1] - z[2] * z[3]) & MASK
z[0] = (z[0] - z[1] * z[2]) & MASK
return tuple(z)
def linear_layer(v):
x0, x1, x2, x3 = v
return ((x0 + x1 + x2) & MASK, (x0 + x2 + x3) & MASK,
(x1 + x2 + x3) & MASK, (x0 + x1 + x3) & MASK)
def polynomial_layer(v):
x0, x1, x2, x3 = v
base = stage_backward(linear_layer(stage_forward(v)))
nonlinear = (
x0 * x1 + x2 ** 3 + x3 * x3,
x1 * x2 + x3 ** 3 + x0 * x0,
x2 * x3 + x0 ** 3 + x1 * x1,
x3 * x0 + x1 ** 3 + x2 * x2,
)
high = (
x0 ** 5 + x1 * x3,
x1 ** 5 + x2 * x0,
x2 ** 5 + x3 * x1,
x3 ** 5 + x0 * x2,
)
return tuple((base[i] + 2 * nonlinear[i] + 4 * high[i]) & MASK for i in range(LANES))
def jacobian_mod2(x):
"""Jacobian of polynomial_layer at x, mod 2, as columns (cols[j][i] = J[i][j])."""
f0 = polynomial_layer(tuple(x))
cols = []
for j in range(4):
xp = list(x)
xp[j] = (xp[j] + 2) & MASK
fp = polynomial_layer(tuple(xp))
cols.append(tuple((((fp[i] - f0[i]) & MASK) >> 1) & 1 for i in range(4)))
return cols
def jac_mod2_mul(cols, t):
out = [0, 0, 0, 0]
for j in range(4):
if (t >> j) & 1:
for i in range(4):
out[i] ^= cols[j][i]
return tuple(out)
def polynomial_layer_inv(y):
"""Invert polynomial_layer by lifting the solution bit by bit (Hensel)."""
# bit 0: the map mod 2 is a permutation of F2^4 but *not* linear -> brute force
cands = [r for r in range(16)
if tuple(x & 1 for x in polynomial_layer(tuple((r >> j) & 1 for j in range(4))))
== tuple(x & 1 for x in y)]
if len(cands) != 1:
raise RuntimeError(f"bit-0 not uniquely solvable: {cands}")
x = [(cands[0] >> j) & 1 for j in range(4)]
for i in range(1, 128):
f = polynomial_layer(tuple(x))
diff = tuple((y[j] - f[j]) & MASK for j in range(4))
if any(d % (1 << i) for d in diff):
raise RuntimeError(f"lifting broke at bit {i}")
rhs = tuple((d >> i) & 1 for d in diff)
cols = jacobian_mod2(x)
sols = [t for t in range(16) if jac_mod2_mul(cols, t) == rhs]
if len(sols) != 1:
raise RuntimeError(f"singular Jacobian at bit {i}")
t = sols[0]
for j in range(4):
if (t >> j) & 1:
x[j] |= 1 << i
return tuple(x)
def outer_forward(v):
z = [(v[i] + AFFINE_BIAS[i]) & MASK for i in range(LANES)]
z[0] = (z[0] + 3 * z[1]) & MASK
z[1] = (z[1] + 5 * z[2]) & MASK
z[2] = (z[2] + 7 * z[3]) & MASK
z[3] = (z[3] + 9 * z[0]) & MASK
return tuple(z)
def outer_backward(v):
z = list(v)
z[3] = (z[3] - 9 * z[0]) & MASK
z[2] = (z[2] - 7 * z[3]) & MASK
z[1] = (z[1] - 5 * z[2]) & MASK
z[0] = (z[0] - 3 * z[1]) & MASK
return tuple((z[i] - AFFINE_BIAS[i]) & MASK for i in range(LANES))
def scramble(v):
return outer_backward(polynomial_layer(outer_forward(v)))
def unscramble(y):
return outer_backward(polynomial_layer_inv(outer_forward(y)))
# --------------------------------------------------------------------------- #
# 3. key / order derivation
# --------------------------------------------------------------------------- #
def derive_key(exponents, salt):
material = b"".join(v.to_bytes(16, "little") for v in exponents)
digest = hashlib.shake_256(b"PCTF-DOCX-KEY\x00" + salt + material).digest(64)
return unpack_vector(digest)
def derive_order(key, salt, count):
key_bytes = pack_vector(key)
def score(index):
return hashlib.sha256(
b"PCTF-DOCX-ORDER\x00" + key_bytes + salt + index.to_bytes(8, "little")
).digest()
return sorted(range(count), key=score)
# --------------------------------------------------------------------------- #
# 4. main
# --------------------------------------------------------------------------- #
def self_test():
for _ in range(4):
v = tuple(secrets.randbits(128) for _ in range(4))
assert unscramble(scramble(v)) == v, "unscramble is wrong"
e = secrets.randbits(UNIT_ORDER_BITS)
assert dlog_base_unit(pow(UNIT_BASE, e, MOD), UNIT_ORDER_BITS) == e, "dlog is wrong"
print("[*] self-test passed (dlog + unscramble roundtrip)")
def main():
ap = argparse.ArgumentParser()
ap.add_argument("encrypted", nargs="?", default="broken.docx", type=Path)
ap.add_argument("output", nargs="?", default="recovered.docx", type=Path)
args = ap.parse_args()
self_test()
blob = args.encrypted.read_bytes()
magic, version, plain_len, salt = HEADER.unpack_from(blob, 0)
assert magic == MAGIC and version == VERSION, "not a DCX2 container"
print(f"[*] container: {magic.decode()} v{version}, plaintext {plain_len} bytes, salt {salt.hex()}")
off = HEADER.size
commitments = unpack_vector(blob[off:off + 64]); off += 64
iv_plain = unpack_vector(blob[off:off + 64]); off += 64
iv_cipher = unpack_vector(blob[off:off + 64]); off += 64
assert off == HEADER_SIZE
exponents = []
for c in commitments:
e = dlog_base_unit(c)
assert pow(UNIT_BASE, e, MOD) == c
exponents.append(e)
print(f"[*] commitment -> exponent 0x{e:032x}")
exponents = tuple(exponents)
key = derive_key(exponents, salt)
print("[*] key:", " ".join(f"{k:032x}" for k in key))
body = blob[off:]
assert len(body) % 64 == 0 and body, "bad body length"
nblocks = len(body) // 64
order = derive_order(key, salt, nblocks)
print(f"[*] {nblocks} cipher blocks, permutation recovered")
cipher_blocks = [unpack_vector(body[b * 64:(b + 1) * 64]) for b in range(nblocks)]
plain_blocks = [None] * nblocks
prev_plain, prev_cipher = iv_plain, iv_cipher
for seq, orig in enumerate(order):
cb = cipher_blocks[seq]
transformed = tuple(
cb[lane] ^ rol128(prev_cipher[(lane + 2) % LANES], CIPHER_ROTATIONS[lane])
for lane in range(LANES)
)
mixed = unscramble(transformed)
block = tuple(
(mixed[lane]
- key[(lane + seq) % LANES]
- rol128(prev_plain[(lane + 1) % LANES], PLAIN_ROTATIONS[lane])
- (seq + 1) * INDEX_CONSTANT[lane]) & MASK
for lane in range(LANES)
)
plain_blocks[orig] = block
prev_plain, prev_cipher = block, cb
padded = b"".join(pack_vector(b) for b in plain_blocks)
plaintext, padding = padded[:plain_len], padded[plain_len:]
amount = len(padding)
assert amount and padding == bytes([amount]) * amount, "padding mismatch"
print(f"[*] padding ok ({amount} x 0x{amount:02x})")
args.output.write_bytes(plaintext)
print(f"[+] wrote {args.output} ({len(plaintext)} bytes), head={plaintext[:4]!r}")
if __name__ == "__main__":
main()