Aleer
Aleer
发布于 2026-11-14 / 2 阅读
0
0

CRYPTO - Broken_docx

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 字节

偏移

长度

内容

本题取值

0

4

magic

DCX2

4

4

version

3

8

8

明文长度(小端)

38630

16

16

salt

667e0b31dc060aa357cf7afe984860bb

32

64

commitments(4 lane)

见下

96

64

iv_plain

—

160

64

iv_cipher

—

224

38656

密文块

604 × 64 字节

分组方式:每 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_forward
  • key = SHAKE-256("PCTF-DOCX-KEY\0" || salt || e_0..e_3) 取 64 字节 → 4 lane

  • order = 用 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,可验证)。

于是三件事同时成立:

  1. 群阶没有大素因子 → Pohlig–Hellman 直接崩成一个二进制阶梯,不是 2^63 的 BSGS;

  2. 指数采样范围是 secrets.randbits(126) < 2^126,与元素阶完全相同 → 解唯一,不存在 e + k·2^126 的歧义;

  3. 解只需要 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) = 0
  • P 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)

实现时有两个容易踩的坑:

  1. 第 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 个残基取唯一解;

  2. 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. 验证

检查项

结果

填充

26 × 0x1a,与 pad() 一致

ZIP 完整性

zipfile.testzip() == None,18 个 part

DOCX 可解析

python-docx 正常打开:14 个段落 + 1 张表格

结构保留

styles/theme/numbering/footer/thumbnail 等 part 齐全,Title/Heading 1/List Bullet 样式都在

明文长度

38630 字节,与头部声明一致

一致性

重跑脚本输出哈希稳定:58DECA5E…4B1AE7

解出的正文(节选):

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()


评论