2023 看雪 KCTF 98k 战队防守方精准攻击赛题设计

字数统计: 1.8k字   |   阅读时长≈ 8分

本篇博客是 2023 看雪 CTF 年度赛上精准攻击赛题的官方题解与设计思路，精准攻击赛题属于逆向题 ，但是主要的难点在于密码方向，本题基于两个后量子困难问题（SDP，SSP）设计，解出情况为 0 解，但是由于出题时间较晚，没有拿到最佳坦克奖 orz。最终 98k 战队攻击方排名第一，防守方：坦克奖排名第二，精致奖排名第二。

 

题目设置

给了 184 个 上多项式集合 ，一个编码后的多项式 ，一个编码矩阵 。需要求一个 184 比特秘密输入 secret ，使得：

  1. 用 secret 的 184 比特进行选择，使得
  2. 上述 target 转换为 上向量
  3. 将 转换为 上向量
  4. 经过矩阵编码后满足 ：
  5. 误差向量 的汉明重量小于等于 10。

即求一个多项式子集积，其经过线性编码后与已知目标多项式的汉明误差小于等于 10。

这里给出 python 的验题逻辑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
from out_public import *
from Crypto.Util.number import *
# modulo x**n - 1
n = 543

# circle shift left
def cshift(a: int, shift: int) -> int:
    """Cyclic shift left b bits of a."""
    return ((a << shift) | (a >> (n - shift))) & ((1 << n) - 1)

# polynomial multiplication in GF(2) modulo x**n - 1
def pmul(a: int, b: int) -> int:
    """Multiply two polynomials in GF(2) modulo x**n - 1."""
    c = 0
    for i in range(n):
        if a & 1:
            c ^= b
        a >>= 1
        b = cshift(b, 1)
        # print(f"i = {i}, a = {a}, b = {b}, c = {c}")
    return c

def m_mul(a: int,b: int) -> int:
    """ matrix multiplication in GF(2)"""
    return bin(a&b)[2:].count('1')%2

def m_encode(M: list, a: int) -> int:
    return int("".join([str(m_mul(a, b)) for b in M]),2)

subset = out
m = len(subset)
M = ms[:]

print("[+] known : M, subset , encoded_target")
print("[+] unknown : target, secret")

# check subset product
secret = int(input("secret: "))

result = 1
for i in range(m):
    if (secret>>i)&1:
        result = pmul(result, subset[i])
# check if target is correctly encoded
encoded_target_no_error = m_encode(M, result)
err_bits = encoded_target_no_error ^ bytes_to_long(encoded_target)
err_num = bin(err_bits).count('1')
print(f"[+] {err_num = }")
assert err_num <= 10, "too many errors"
print(f"[+] check error bits ? True")

 

Code-Based Cryptography

首先注意到后半部分是一个编码问题，给定 ，求一个向量 和汉明重量不大于 10 的误差向量 使得 :

本质上就是 543 个变量，给了 800 个方程，但是这 800 个方程中存在至多 10 个错误的方程（实际上刚刚好有 10 个方程是错误的），我们需要找出错误的方程，并且恢复出编码前的向量 。大概有两个思路：

  1. 这个形式像 LWE ，可以考虑用格来解，构造格，用 BKZ 规约，但是 上的格比较特殊 。
  2. Information Set Decode 问题， 可以使用 sage 的 Information Set Decode （ISD）类求解。

因为本题涉及到了编码纠错问题，于是这题有必要简单提一下 后量子密码（PQC） 中的一个重要分支：Code-Based Cryptography。本题中的方程纠错问题是标准的 Linear Code 纠错解码。

 

Linear Code

这里简单介绍 Linear Code 中的一些基本定义。

  1. 线性编码 Linear Code : 记 是阶为 的伽罗瓦域，一个 编码的空间 称为线性的，即它是 的线性子空间，其中 是明文空间， 是码字个数， 是最短码字距离。对于任意 和任意 使得 .

  2. 线性编码的维数 Dimension : 即线性子空间 的维数，此时我们可以记为 code ，其中， 是总（密文）空间的维数， 是明文编码空间的维数，最短距离 可以省略

  3. Linear Code 生成矩阵 ： 上述概念还比较抽象，实际上直接从生成矩阵看 Linear Code 是很直观的。线性编码 的一个生成矩阵是一个 的矩阵 ，其 个行向量构成整个线性子空间的基 ，即任意码字 可以编码为：

  4. Linear Code 校验矩阵（Parity Check Matrix）: 顾名思义，校验矩阵能够验证某个码字是否正确的。 令 是定义在 上 的线性编码，其奇偶校验矩阵 满足：

    也就是说编码的空间是校验矩阵 的 kernel space（核空间）。

 

纠错方程组转换

给定 ，求一个向量 使得 :

543 个变量，给了 800 个方程， 的汉明重量小于等于 10 （错误方程数不超过 10 个，题目给的约束是 10，实际上约束到 20 可能更好），恢复出编码前的向量 ，这就是 Linear Code 中典型的带纠错的 Decoding Problem。

  • Problem 1 (Decoding Problem). Let be positive integers. Given a generator matrix of a code over , a positive integer , and a vector , which is such that , for some and of Hamming weight , find .
  • Problem 2 (Syndrome Decoding Problem). Let be positive integers. Given an parity-check matrix of a code over , a positive integer , and a vector , which is such that , for some of Hamming weight , find .

Linear Code 相关的论文和书籍都会说 Decoding Problem 和 Syndrome Decoding Problem 是等价的，这给出一个简单的证明，其实只需要用到核空间的性质：

因为大多数 Decoding Problem 都是转换成 Syndrome Decoding Problem 来做的，而最优的算法 Information Set Decoding （ISD）都是基于 Syndrome Decoding Problem 来阐述的，因此有必要说明 ISD 解纠错编码的基本转换原理。关于 Code-based Cryptography 和 ISD 算法，感兴趣的读者可以参考下面论文和链接

  1. Weger, Violetta et al. “A Survey on Code-Based Cryptography” ArXiv abs/2201.07119 (2022): n. pag.
  2. Anna-Lena Horlemann-Trautmann, Violetta Weger. “Information Set Decoding in the Lee Metric with Applications to Cryptography” (2020)
  3. Ron Roth, Introduction to Coding Theory, Cambridge University Press, 2006
  4. Code-based challenges webpage.

 

给定一个 Syndrome ： ，找到汉明重量为不大于 的向量 ，也就是说可以从 的 个列向量中选择 个出来使得其线性组合恰好为 ，其中 ，为目标支撑集， 代表 的第 i 个列向量。ISD 算法的核心思想是：我们随机选定一个 Information Set，即 , 固定该信息集（即假设支撑集向量的总集合），然后高斯消元去解补信息集 中选定的列向量，验证是否存在满足条件的解，否则重新选择信息集。在具体实现上 ISD 每轮选取信息集 的大小是 ，如果选取的 个向量恰好都在支撑集向量外，即支撑集（ 个向量）只落在信息补集 选定的 个向量内，就能够得到目标解，从概率上看，对于线性编码 ，纠错不超过 的编码，期望需要选择信息集的次数是：

最基本的 ISD 算法的单轮迭代过程参考如下：

We are given a parity-check matrix of a code , a positive integer and a syndrome , such that there exists a vector of Hamming weight less than or equal to with syndrome , i.e., . The aim of the algorithm is to find such a vector e.

  1. Find an information set of size for .
  2. Bring into the systematic form corresponding to , i.e., find an invertible matrix , such that , for some and .
  3. Go through all error vectors having the assumed weight distribution (and in particular having Hamming weight ).
  4. Check if the parity-check equations, i.e., are satisfied.
  5. If they are satisfied, output , if not start over with a new choice of .

ISD 有多种优化版本，基本都是对于单轮迭代的策略进行优化，下面是题解中使用的 Sagemath 标准库中的 ISD 算法参数：

1
Information-set decoder (Lee-Brickell) for [800, 543] linear code over GF(2) decoding up to 20 errors

 

Linear Code & ISD in Sagemath

Sagemath 中实现了一系列 ISD 算法，以及对应的纠错解码器。本题就可以通过 sagemath 的内置 ISD 解出唯一的目标解。

记 是 上 的线性编码，则我们可以通过高斯消元得到核空间，从而得到校验矩阵 。最后使用 ISD 算法解 Syndrome Decoding Problem 得到纠错后的解。转换过程和 decoding 都在 Sagemath 内部封装了，这一步代码量非常少，但是需要有 Linear Code 的基础。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# ISD decode
# number of equations n = 800
# number of variables k = 543
# number of  errors   t = 10
M = matrix(GF(2),[Int_to_Bitvector(row, n) for row in ms])
print(M.dimensions())
# 800 * 543
c = Bytes_to_Bitvector(encoded_target)
C = codes.LinearCode(M.T)
D = codes.decoders.LinearCodeInformationSetDecoder(C, 10)
print(D.algorithm().time_estimate())
%time sol = D.decode_to_message(c)
err = M * sol  - c
print(f"{list(err).count(1) = }")
target_val = Bitvector_to_Int(sol)

ISD 是一个概率性算法，期望的运行的 iteration 次数是（粗略的估计）：

实际运行大概 10 s ~ 5 min 不等。恢复出 target 多项式后，剩下的问题就转变成了一个多项式子集积问题。

 

Polynomial Subset Product Problem

多项式的子集积问题：多项式环 ， 给定集合 ，和目标多项式 ，求 （ 的二进制展开）使得 ：

这个模多项式分解形式是 ，其中 的都是 180 次的不可约多项式 。 因此这里考虑同态到伽罗瓦域上 ，就形成了三个 Polynomial Subset Product Problem (PSPP)，这三个 PSPP 所在的乘法群的阶都是 ， 这个阶很光滑，可以直接使用 Pohlig-Hellman 算法求解离散对数（其他思路：能否通过 lift 提升到 ），进而转换到整数环上经典的子集和问题，估算一下单个背包密度： ，因此一般的求解子集和的方法在这题是行不通的，不能在多项式时间规约出。

因此考虑三个 PSPP 实例，通过求解离散对数转换成 Multiple Subset Sum Problem，构造一个接近 200 维的格（可以参考论文：A Note on the Density of the Multiple Subset Sum Problems），下面的格本质上是把单个 SSP 问题的格在维度上进行了扩展，相当于增加了一些方程：

目标短向量为 。用 BKZ 不断调整 block_size 即可，大概需要跑 5 min。

 

出题源码及EXP

出题源码和 EXP ：2023kctf-98k-精准攻击.zip

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true


Hi, this is tl2cents
Currently Ph.D at IIE of UCAS
Graduated from USTC (2018-2022)

CTFer
Focus on blockchain, crypto and reversing
Team member of NeSE and Nebula

Research
Blockchain | ETH | FHE
PQC | Cryptography | Android

Contact Me
echo Y2F4dWxhc2FlbGFAb3V0bG9vay5jb20K | base64 -d

Thanks for JoeyBling and Litten