出题小记 HDCTF-Rainbow sour

题目背景

这是一道基于Rainbow多元公钥签名的题目，可以先去了解一下UOV油醋签名，而本题是多层UOV——rainbow签名

分层油醋结构（Rainbow Layers）​​

这是Rainbow的核心创新。它将变量和方程分成多个层：

• 每一层都包含一定数量的“油”变量（Oil）和“醋”变量（Vinegar）。

• 在每一层的多项式中，“油”变量之间不相互乘，而“醋”变量之间以及“醋”变量与“油”变量之间可以相乘。这种设计使得当某一层的“醋”变量被赋值后，该层的方程就变成了关于“油”变量的一次线性方程组，可以通过高斯消元法快速求解。

• 层与层之间通过变量绑定形成依赖关系，后一层的“醋”变量包含了前一层的所有变量。签名时需要从最后一层开始，逐层向前求解。

题目分析

目标：伪造一个签名，使得公钥映射P(x)的输出等于目标对应的向量

已知：

目标：

map——公钥映射P的系数

$公钥映射：P:\mathbb F^{10}{31} \rightarrow \mathbb F^6{31}$

对第i个方程：$P_i(x)=c_i+\sum j l{ij}x_j+\sum_{i \leq j}q_{ijk}x_jx_k$

trace_仿射掩码

公钥与中心映射的关系：$P(x)=B \cdot C(x)+b$

题目流程：

1. 先将消息target转换为向量target_vector

2. evaluate计算公钥多项式：$f_i(x)=\sum {j \leq k} q{ijk}x_ix_{l} +\sum l_{ij}x_j+c_i$

共有6个方程：$P(x)=(f_0(x),f_1(x),…,f_5 (x))$为公钥多项式

3. 需要构造$P(x)=H(m)$

解题思路

题目直接给出了隐藏仿射层，那么可以直接恢复中心映射：$C(x)=B^{-1}(P(x)-b)$

1. 可以随机选择4个v变量

原因：未知数有10个变量x=(v,o1,o2)，方程数有6个，所以有10-6=4个自由度，也就是说，满足P(x)=y的解不止一个，而是有一整个解簇

2. 根据rainbow的设计——没有oo项也就是没有二次项

v选定后，用第一层3个方程（关于o1是线性的）解出o1

再将v，o1当成新的v，用第二层3个方程（关于o2是线性的）解出o2

注意：随机选取v后的线性方程需要系数矩阵可逆，否则重新选取v

数学说明：

根据算法规定没有oo项，每层可线性化：

$C(v,o)=C(v,0)+\sum _i A_i \cdot o_i$

$A_i=C(v,e_i)-C(v,0) \quad (e_i表示第i个o变量为1，其余为0) $

$r=target-C(v,0)$

解线性方程：$A \cdot o=r$

核心代码

题目已经给出求A和r的代码：

def linearize(central_map, point, unknowns, equations, target):
    """
    With vinegar fixed, convert one Rainbow layer into A*u = rhs.
    central_map:The recovered central Rainbow map.
    point:Current variable vector [x0, x1, ..., x9].Some variables are already fixed.
    unknowns:Indices of variables to solve in this layer.
    equations:Indices of equations used in this layer.
    target:Target vector after removing the output mask
    """
    base = point[:]
    *for* i *in* unknowns:
        base[i] = 0

    base_value = evaluate(central_map, base)
    A, rhs = [], []

    *for* equation *in* equations:
        row = []
        *for* i *in* unknowns:
            trial = base[:]
            trial[i] = 1
            row.append((evaluate(central_map, trial)[equation]
                        - base_value[equation]) % P)
        A.append(row)
        rhs.append((target[equation] - base_value[equation]) % P)

    *return* A, rhs

高斯消元解线性方程：

P = 31

def solve_linear(A, rhs):
    n = len(A)
    # 构造增广矩阵 [A | rhs]
    aug = [A[i][:] + [rhs[i]] for i in range(n)]

    for col in range(n):
        #1.选主元
        pivot = None
        for r in range(col, n):
            if aug[r][col] % P != 0:
                pivot = r
                break
        if pivot is None:
            raise ValueError("矩阵奇异")

        #2.交换到当前行
        aug[col], aug[pivot] = aug[pivot], aug[col]

        #3. 主元归一化
        inv = pow(aug[col][col], P - 2, P)
        aug[col] = [(v * inv) % P for v in aug[col]]

        # 4.消去其他行的该列
        for r in range(n):
            if r != col and aug[r][col] != 0:
                factor = aug[r][col]
                aug[r] = [
                    (aug[r][c] - factor * aug[col][c]) % P
                    for c in range(n + 1)
                ]
    return [aug[i][n] % P for i in range(n)]

分层求签名：

def sign(central_map, target, v):
    x = [0] * N
    for i in range(V1):
        x[i] = v[i] % P
    #第一层
    unknowns1  = list(range(V1, V1 + O1))
    equations1 = list(range(0, O1))

    A1, r1 = linearize(central_map, x, unknowns1, equations1, target)
    o = solve_linear(A1, r1)
    for idx, val in zip(unknowns1, o):
        x[idx] = val
    #第二层
    unknowns2  = list(range(V1 + O1, N))
    equations2 = list(range(O1, M))

    A2, r2 = linearize(central_map, x, unknowns2, equations2, target)
    u = solve_linear(A2, r2)
    for idx, val in zip(unknowns2, u):
        x[idx] = val

    return x

完整解答：

*#!/usr/bin/env python3*
*import* json
*import* secrets
*import* socket
*import* sys

*from* PLAYER_ALGORITHM_ATTACHMENT *import* (
    M, N, O1, P, V1,
    evaluate, linearize, mat_inv, mat_vec, remove_output_mask,
)

def solve_linear(A, rhs):
    n = len(A)
    aug = [A[i][:] + [rhs[i]] *for* i *in* range(n)]

    *for* col *in* range(n):
        pivot = None
        *for* r *in* range(col, n):
            *if* aug[r][col] % P != 0:
                pivot = r
                *break*
        *if* pivot is None:
            *raise* ValueError("矩阵奇异")

        aug[col], aug[pivot] = aug[pivot], aug[col]
        inv = pow(aug[col][col], P - 2, P)
        aug[col] = [(v * inv) % P *for* v *in* aug[col]]

        *for* r *in* range(n):
            *if* r != col and aug[r][col] != 0:
                factor = aug[r][col]
                aug[r] = [
                    (aug[r][c] - factor * aug[col][c]) % P
                    *for* c *in* range(n + 1)
                ]

    *return* [aug[i][n] % P *for* i *in* range(n)]

def sign(central_map, target, v):
    x = [0] * N
    *for* i *in* range(V1):
        x[i] = v[i] % P

    unknowns1 = list(range(V1, V1 + O1))
    equations1 = list(range(0, O1))
    A1, r1 = linearize(central_map, x, unknowns1, equations1, target)
    o = solve_linear(A1, r1)
    *for* idx, val *in* zip(unknowns1, o):
        x[idx] = val

    unknowns2 = list(range(V1 + O1, N))
    equations2 = list(range(O1, M))
    A2, r2 = linearize(central_map, x, unknowns2, equations2, target)
    u = solve_linear(A2, r2)
    *for* idx, val *in* zip(unknowns2, u):
        x[idx] = val

    *return* x

def forge(central_map, target):
    *for* _ *in* range(2000):
        v = [secrets.randbelow(P) *for* _ *in* range(V1)]
        *try*:
            x = sign(central_map, target, v)
            *if* evaluate(central_map, x) == [value % P *for* value *in* target]:
                *return* x
        *except* ValueError:
            *pass*
    *raise* RuntimeError("could not forge signature")

def read_key(sock):
    data = b""
    *while* True:
        data += sock.recv(65536)
        *while* b"\n" in data:
            line, data = data.split(b"\n", 1)
            *if* line.startswith(b"KEY "):
                *return* json.loads(line[4:])

def main():
    host = sys.argv[1] *if* len(sys.argv) > 1 *else* "127.0.0.1"
    port = int(sys.argv[2]) *if* len(sys.argv) > 2 *else* 31337

    *with* socket.create_connection((host, port), timeout=10) *as* sock:
        key = read_key(sock)

    trace = key["trace"]
    B, b = trace["codomain_basis"], trace["codomain_shift"]
    central = remove_output_mask(key["map"], B, b)
    target = mat_vec(mat_inv(B), [
        (x - y) % P
        *for* x, y *in* zip(key["target_vector"], b)
    ])

    signature = forge(central, target)
    print("message_hex=" + key["target_message"].encode().hex())
    print("signature_hex=" + bytes(signature).hex())

*if* __name__ == "__main__":
    main()

动态靶机搭建学习

基本概念

容器(Container)：轻量化的运行实例，包含应用代码、运行时环境和依赖库。基于镜像创建，与其他容器隔离，共享主机操作系统内核

镜像(Image)：只读模版，定义了容器的运行环境（操作系统、软件配置等）。通过分层存储(Layer)优化空间和构建速度。

Dockerfile：文本文件，描述如何自动构建镜像

仓库(Registry)：存储和分发镜像的平台

文件目录：

server.py：TCP 服务和 Rainbow 公钥逻辑

flag.py：动态 flag 生成

flag_checker.py：出题人侧 checker 辅助脚本

solve.py：连接实例并生成目标签名，不自动提交

Dockerfile：运行镜像

docker-compose.yml：本地启动

dynamic-uuid-hdctf.rx：平台动态 UUID 评测脚本