从CTF认识格的常见构造

传统的 CTF 密码学依赖大整数分解或离散对数,然而当题目给出掺杂了微小随机噪声的线性方程组,或被高位截断的残缺密钥等特殊情况时,一般的攻击方法便彻底失灵,唯一的破局利器就是格密码学(Lattice-based Cryptography)。在CTF中,格是用 LLL/BKZ 算法在多项式时间内将“扭曲坏基”重构为“正交好基”、暴力剥离出极短向量的解题方法。这次将从CTF实战视角出发,详细解释和剖析常见的格的复杂问题。对于CVP和SVP,这篇文章就不详细说了,重点放在了进阶的部分上,但是我会总结这部分经验与大家分享。

注意:可能里面的式子不能的显示,可以放到typora里看

SVP和CVP

这部分简单写写,网上其他师傅写的很详细了,资料也很多

svp

最短向量问题
$$
在格 L
中找到一个最短非零向量
中找到一个最短非零向量 oldsymbol{v}
,满足
,满足 oldsymbol{v}in L
且
且 |oldsymbol{v}| 最小
$$
最短的向量显然可能不止一个,但解题过程中解出一个即可,但是相对于CVP问题,CVP问题不太好解答,一般情况下都是换一个格,转化成SVP问题求解

cvp

最近向量问题
$$
给定一个不在格 L
中的向量
中的向量 oldsymbol{w}in mathbb{R}^{m}
,找到一个向量
,找到一个向量 oldsymbol{v}in L
,满足
,满足 |oldsymbol{v}-oldsymbol{w}| 最小。
$$
就是一个在格里找一个向量,使得与不在格中的那个向量最接近,也就是三角形定则中第三边最短

经验分享:

CVP问题一般转化为SVP问题求解,单纯的CVP问题很难求解,除了上面换一个格的处理外,还可以使用 Babai 的最近平面算法,通过把目标点嵌入到原矩阵中,将其转化为 SVP 求解。这个用法在我前面那个ECDSA那个文章的侧信道攻击中用过,可以参考一下。

针对SVP问题,是非常普遍的,针对一个式子或几个式子的,可以直接构建二维或三维的格求解,这些是比较简单的。一般的步骤是先化简整合式子,将一个未知量(包括各种式子的形式,例如p-65537)移到一边,但要保证其一边只有一个未知量,之后根据另一边构造合适的格,一定要注意用合适的值配平,这个也是比较难的,要找到比较合适的量。

AGCD问题

简单的问题,加密方式如下:
$$
x_1=pq_1 ewline
x_2=pq_2 ewline
dots ewline
x_l=pq_l
$$
解密得到p的话,直接gcd就行

再加入一个干扰值后,进行加密,方式如下:
$$
x_1=pq_1+e_1 ewline
x_2=pq_2+e_2 ewline
dots ewline
x_l=pq_l+e_l
$$
如果e生成的比较小的话,可以直接取前两个式子爆破e1、e2,之后gcd(x1-e1,x2-e2)即可得到p

如果没办法爆破的话,就转化为格密码问题,这两种方法区别不是很大在格构造上

丢番图近似 SDA 格攻击
$$
详细一下各个参数,p的大小为eta位,e_i的大小为ho位,q_i的大小为gamma -eta位,x的大小为gamma位
$$

以第一个和第二个为例
$$
egin{align}
q_0x_1-q_1x_0&=q_0(q_1p+e_1)-q_1(q_0p+e_0)
&=q_0q_1p+q_0e_1-q_1q_0p-q_1e_0
&=q_0e_1-q_1e_0
end{align}
$$
构建格
$$
(q_0,q_1,cdots,q_l)egin{bmatrix}
2^{ho+1}&x_1&x_2&cdots&x_l
&-x_0
&&-x_0
&&&ddots
&&&&-x_0
end{bmatrix}=(q_02^{ho+1},q_0e_1-q_1e_0,cdots,q_0e_l-q_le_0)
$$
经检验,这个向量就是最短向量,

这样就可以得到q0,通过第一个式子,将x0%q0就能得到余数,即e0,之后得到p

脚本

生成

from Crypto.Util.number import getPrime, getRandomRange

def gen(k:int, gamma: int, eta: int, rho: int):
    xs = []
    qs = []
    es = []
    p = getPrime(eta)
    for _ in range(k):
        q = getPrime(gamma - eta)
        e = getRandomRange(-pow(2, rho) + 1, pow(2, rho) - 1)
        qs.append(q)
        es.append(e)
        xs.append(p * q + e)
    return p, qs, es, xs

k = 5
eta = 768
gamma = 1024 + eta
rho = 256
p, qs, es, xs = gen(k, gamma, eta, rho)
print(f'{p = }')
print(f'{qs = }')
print(f'{es = }')
print(f'{xs = }')

攻击

k = 5
rho = 256
xs = ...

A = ZZ(pow(2, rho + 1))
B = matrix(xs[1:])
C = matrix.diagonal([-xs[0]] * (k - 1))
M = matrix.block([[A, B], [ZZ(0), C]])
L = M.LLL()
q0 = ZZ(L[0, 0] / A).abs()
e0 = ZZ(xs[0] % q0)
p = ZZ((xs[0] - e0) / q0)
print(f'{e0 = }')
print(f'{q0 = }')
print(f'{p = }')

范围

要满足这样的条件
$$
l+1> rac{gamma-ho}{eta-ho}
$$

正交格近似 OL 格攻击

攻击代码基本差不多,范围不同

范围

要满足
$$
l> rac{gamma-ho}{eta-ho}
$$

当看见这类题时,先按照上面的格构建,调参数(配平参数,有时候参数很刁钻)

Hidden number problem(HNP)

这个看起来和AGCD问题差不多,但是式子还是有区别的,条件也不同

定义

换句话说,当我们知道了多组u、t(t满足u^i≈αt_i (modp) ),就可以得到α
$$
就是这样表示,αt
_i

≡u
_i

+e
_i
(modp)这个e就是干扰量,e
_i是未知的误差,因为u^i≈αt_i,
$$

$$
当lapprox log^{ rac{1}{2}}{p},l就是泄露的比特数,就可以构建格来求解
left[ egin{matrix} p & 0 & dots & 0 & 0 0 & p & ddots & dots & dots dots & ddots & ddots & 0 & dots 0 & 0 & dots & p & 0 t_1 & t_2 & dots & t_{n} & rac{1}{2^{l+1}} end{matrix} ight]
$$

$$
我们需要找到在格上离mathbf{u}=(u_1, u_2, dots, u_{n}, 0)最近的向量,所以在这里,我们可以采用Babai's nearest plane algorithm。最终我们可以得到一组向量mathbf{v}=(alpha cdot t_1 mod p, alpha cdot t_2 mod p, dots, rac{alpha}{2^{l+1}}),这样就得到了alpha
$$

exp

M = matrix(ZZ, n+1, n+1)
for i in range(n):
    M[i,i] = p
for j in range(n):
    M[n,j] = t[j]
M[n,n] = 1/2^(l+1)
    

LWE 问题

LWE(Learning With Errors,带容错学习),LWE能够对“带噪音的线性方程组”求解,最终找到隐藏的秘密向量。

LWE的形式是对带有噪音的线性同余方程求解,形象的表示如下

已知a和b组,求解s
$$
b = A cdot s + e pmod q
$$

$$
egin{pmatrix} b_1 b_2 dots b_m end{pmatrix}

egin{pmatrix}
a_{1,1} & a_{1,2} & cdots & a_{1,n}
a_{2,1} & a_{2,2} & cdots & a_{2,n}
dots & dots & ddots & dots
a_{m,1} & a_{m,2} & cdots & a_{m,n}
end{pmatrix}
cdot
egin{pmatrix} s_1 s_2 dots s_n end{pmatrix}
+
egin{pmatrix} e_1 e_2 dots e_m end{pmatrix} pmod q
$$

构建格求解

将给的A弄成矩阵
$$
A = egin{pmatrix} a_{1,1} & a_{1,2} & cdots & a_{1,n} a_{2,1} & a_{2,2} & cdots & a_{2,n} dots & dots & ddots & dots a_{m,1} & a_{m,2} & cdots & a_{m,n} end{pmatrix}
$$
之后变成这样的格
$$
M = egin{pmatrix}
A & 0
q cdot I_m & 0
-b^T & 1
end{pmatrix}
$$
完整的长这样
$$
M_{LWE} = egin{pmatrix}
a_{1,1} & a_{1,2} & cdots & a_{1,m} & 0
a_{2,1} & a_{2,2} & cdots & a_{2,m} & 0
dots & dots & ddots & dots & dots
a_{n,1} & a_{n,2} & cdots & a_{n,m} & 0
hline
q & 0 & cdots & 0 & 0
0 & q & cdots & 0 & 0
dots & dots & ddots & dots & dots
0 & 0 & cdots & q & 0
hline
-b_1 & -b_2 & cdots & -b_m & 1
end{pmatrix}
$$

$$
最短向量 v= egin{pmatrix} -e_1, & -e_2, & dots, & -e_m, & 1 end{pmatrix}
$$

脚本

import random
from sage.modules.free_module_integer import IntegerModRing

# 矩阵大小: (n + m + 1) * (m + 1)
M = matrix(ZZ, n + m + 1, m + 1)
M[:n, :m] = A.transpose()
M[n:n+m, :m] = q * identity_matrix(m)
M[n+m, :m] = -b
M[n+m, m] = 1
L = M.LLL()

for row in L.rows():
    if abs(row[-1]) == 1:
        # 如果最后一列是 -1,说明向量方向反了,全部取反
        target_e = row[:-1] if row[-1] == 1 else -row[:-1]
        
        print(f"[+] 经 LLL 成功抓取的噪声 e: {target_e}")
        
        # 拿到完美的噪声 e 后,方程退化为无噪的 A*s = b - e mod q
        # 直接用高斯消元求出 s
        perfect_b = (b - target_e) % q
        R = IntegerModRing(q)
        A_mod = matrix(R, A)
        b_mod = vector(R, perfect_b)
        
        # 解线性方程组
        recovered_s = A_mod.solve_right(b_mod)
        print(f"[+] 成功恢复的私钥 s: {list(recovered_s)}")
        break

特定问题

这些不是什么大的方向考点,而是其他问题在格上面的一个小切口,学习一下如何构造格,下面整合了其他师傅的思路

Noise CRT问题

存在这样的矩阵
$$
A=egin{bmatrix}
N_1pmod{p_0}&N_2pmod{p_0}&cdots&N_npmod{p_0}
N_1pmod{p_1}&N_2pmod{p_1}&cdots&N_npmod{p_1}
dots& dots& dots& dots
N_1pmod{p_m}&N_2pmod{p_m}&cdots&N_npmod{p_m}
end{bmatrix}
$$

求解N

m = 15 #轮数,有多少列
nbits = 3211#n多大
P = prod(p)
Ti = []
for i, pi in enumerate(p):
    Pi = P // pi
    invPi = inverse_mod(Pi, pi)
    Ti.extend(S[i][j] * Pi * invPi for j in range(m))
T = column_matrix(Ti)
B = diagonal_matrix([2^nbits] * len(Ti))
M = block_matrix([[matrix([P]), 0], [T, B]])
def flatter(M):
    from subprocess import check_output
    import re
    inputM = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    outputM = check_output(["flatter"], input=inputM.encode())
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", outputM)))

flatter(M)

求解线性HASH

生成过程

def hash(msg: bytes):
    n = 30798082519452208630254982405300548841337042015746308462162479889627080155514391987610153873334549377764946092629701
    g = 91289086035117540959154051117940771730039965839291520308840839624996039016929
    N = 2 ** 100
    for mi in msg:
        n = g * (2 * n + mi) % N
    return (n - 0xdeedbeef114514) % N

式子可以表示为
$$
egin{align}
n_{i+1}&=(2g)^{i+1}n_0+(2g)^igcdot m_0+(2g)^{i-1}gcdot
m_1+cdots+(2g)^0gcdot m_{i}pmod{N}
&=(2g)^{i+1}n_0+sum^{i}{k=0}(2g)^{i-k}gcdot m_k
end{align}
$$
要进行碰撞两个相同哈希值但不同的字节流,不妨设两个字节流分别为(s1,s2……),(t1,t2,……)
$$
egin{align}
n{i+1}&=(2g)^{i+1}n_0+sum^{i}{k=0}(2g)^{i-k}gcdot s_kpmod{N}
&=(2g)^{i+1}n_0+sum^{i}{k=0}(2g)^{i-k}gcdot t_kpmod{N}
end{align}
$$
等式左右两边相减可得
$$
sum^{i}_{k=0}(2g)^{i-k}gcdot (s_k-t_k)equiv 0pmod{N}
$$
设e_k=s_k-t_k
$$
R=egin{bmatrix}
(2g)^ig
(2g)^{i-1}g
dots
(2g)^0g
end{bmatrix}
$$

$$
M=egin{bmatrix}
1&0&cdots&0&(2g)^ig
0&1&cdots&0&(2g)^{i-1}g
dots& dots&ddots& dots& dots
0&0&0&1&(2g)^0g
0&0&0&0&N
end{bmatrix}
$$

$$
(e_0,e_1,cdots,e_i,k)egin{bmatrix}
R
N
end{bmatrix}=0
$$

所以e就可以求出

例样

n=……
g=……
N=……
msize=……
R = [(2 * g) ** (i) * g for i in range(msize)]
R = column_matrix(R[::-1]) % N
E = identity_matrix(msize)
M = block_matrix([[E, R], [0, matrix([N])]])
X = M.LLL()
sbytes = b'a' * msize
print(sbytes, hash(sbytes))
tbytes = list(b'a' * msize)
for i in range(msize):
    tbytes[i] -= X[2][i]
tbytes = bytes(tbytes)
print(tbytes, hash(tbytes))

总结

构造格去解CTF的密码题已经是一个趋势了,而且这一部分的难度会越来越大,主要是考验选手的能力和防AI上,也就是要求我们要有更严密的逻辑,去构建更精密的格,做这种的题是通常需要构建一个合适的格,当调参数时无法得到一个正确值时,可能这个格构建的不是很精密,无法获得最短向量,换种思想去做,式子再变换一下。上面虽然写了进阶的格密码处理方式,但是还是需要随机应变,上面的只是一个基本框架,可能比较标准的式子用上面的格就行,不太一样的,就要学会灵活应用,将格改一改。BKZ相当与LLL算法的plus版,要适时使用这两种算法,可以同时使用,希望这篇文章能给大家更多思路和方向,也欢迎大家积极补充。