NeSE升级赛

2022-03-09

字数统计: 1.9k字 | 阅读时长≈ 9分

上周六（3.5）参加了NeSE乙升甲的升级赛，很幸运解出题通过了升级赛，正式成为NeSE主队队员。接触CTF一年多，从萌新到会一点点密码学，这算是参加CTF竞赛的又一个重要的节点。之后我参加国际赛的次数可能也就多了起来，博客看情况更，复盘解题过程有时候虽然收获很多，但太费时间了。虽然毕设还是云里雾里，但今天还是在忙着摸鱼之际（bushi）抽空细写了这道和线性代数相关的密码学题解。

源码

#!/usr/bin/env sage

from hashlib import sha256
from secret import FLAG

P, n, t = 41, 64, 100

F.<x> = PolynomialRing(GF(P))
Q.<x> = F.quotient(x^(n // 2) - 1)

G = GeneralDiscreteDistribution([0.5] + [0.25] * 2)
password = random_vector(GF(P), n // 2).list()

def func_1():
    r, m, s = Q.random_element(), random_matrix(GF(P), n // 2, n), vector(GF(P), password + random_vector(GF(P), n // 2).list())
    b = [(r * F((m * s).list()) + F([choice([-1, 1]) * G.get_random_element() for _ in range(n // 2)])).list() for _ in range(t)]
    print(str(r.list()) + '\n' + str(m.list()) + '\n' + str(b))

def func_2():
    if int(input("> ")) == int(sha256(str(password).encode()).hexdigest(), 16):
        print(FLAG)
    else:
        print("[!] WRONG INPUT")

def menu():
    print("[1] GET SAMPLES\n[2] GET FLAG\n[3] EXIT")
    for _ in range(2048):
        op = int(input("> "))
        if op == 1:
            func_1()
        elif op == 2:
            func_2()
            break
        elif op == 3:
            break

if __name__ == '__main__':
    menu()

分析

最初分析会发现这是一道容错学习的问题（Learning With Errors），进而会发现这是定义在多项式环上的Module-LWE问题，去找相关论文和攻击，发现这方面的研究和现实里具体的攻击很少，之后干脆源码分析：

$s= password+random\_vector(GF(P), n // 2).list()$

其中password每一轮都是固定的。

常量定义如下

1
2
3

P, n, t = 41, 64, 100
F.<x> = PolynomialRing(GF(P))
Q.<x> = F.quotient(x^(n // 2) - 1)

最主要的加密部分，已知r，m，b并且有如下关系：

$b_i=r*F(m*s)+ error_i\\ where \ r \in Q \quad and \quad i \in [1,2,...,t] \\ Denote \quad \bar b= b_i-error=r*F(m*s)$

注意到向量每个维度的error=[-1,-2,0,1,2]的概率分布是[1/8,1/8,1/2,1/8,1/8]，我们得到的加密结果向量b里面有一百次不同随机error的加密，故统计数组b内对应位置的数字的出现次数，出现次数最多的就是原来不带误差的值（这个占比高达50%）。因此可以通过统计特征恢复出 $\bar b$ 。虽然这一步是最简单的，但最终卡在这个地方很久，因为不注意到概率分布的话，单纯用LWE的格去归约是算不出来的：模数p和误差error的上限相差有点小。

恢复之后我们得到了一个多项式混合矩阵的乘法方程。当然我们可以先对b在Q上求逆得到 $F(m*s)=\bar b^{-1}*r$ ,再转换一下系数，就变成了 $m*s=vector(GF(p),\bar (b^{-1}*r).list())$ 一个矩阵表示的线性方程。只是我们线性方程的个数只有32个，而未知数有64个（password不变，其他32位每次会变）。虽然模 $x^{32}-1$ （非本原多项式）多项式环上的逆不一定存在，但这应该也是一种可行的思路。接下来介绍另一种思路：针对模多项式 $x^{32}-1$ 上的等价矩阵。

考虑题中 $GF（41）上模 x^{32}-1 的多项式环Q.<x>$ 上的运算，如果我们先不考虑模多项式 $x^{32}-1$ ，只在 $F.<x>$ 上运算，我们发现 $x^{32} \equiv 1 \mod x^{32}-1,\ ...\ ,x^n \equiv x^{n \mod 32} \mod x^{32}-1$ 。也就是说如果我们在Q上计算 $r*q$ ，也就等价于下面矩阵相乘

$let \quad r = [r_1,r_2,r_{32}] \\ Then \quad define \quad M_r= \left[ \begin{matrix} r_{1} & r_{2} & ... & r_{32} \\ r_{32} & r_{1} & ... & r_{31} \\ ... & ... & ... & ... \\ r_{2}& r_3 & ... & r_1 \end{matrix} \right] \in GF(p)^{32 \times 32} \\ \\ r*q \iff vectror(GF(p),q.list())*M_r \\ where \quad r \quad and\quad q \quad defined \quad in \quad Q.<x>$

注意到 $m*s$ 只有32维， $F(m*s)$ 也等价于是定义在Q(x)上的，从而利用在Q(x)上的乘法 $r*q$ 的矩阵形式转换到GF(p)上的矩阵运算，也就是：

$M_r^T*m*s=\bar b \iff M*s=\bar b \\ where\quad M=M_r^T*m \in GF(p)^{32*64}$

到这里就又回到了线性代数里线性方程的求解，已知 $M，\bar b$ ，和方程 $M*s=\bar b$ ，其中M是32×64的矩阵，s是64维的向量：前面32维固定为password，后面32维为随机向量。由于前面32位password是固定的，我们将M拆开看： $M=A||B$ ，其中A,B都是32×32的矩阵，原方程就拆分为下面问题：

$M*s=A*password+B*random\_vector=\bar b$

其中我们每进行一次sample请求，可以得到一组 $(A_i,B_i,\bar b_i)$ ，最多可以得到2048组：

如果B满秩，我们得不到任何有用信息。
如果B非满秩，也就是说存在非零向量 $y \in GF(p)^{32}$ ，使得 $y*B=0$ （B的左核空间，维数是32-rank（B））：
$y * \bar b=(y*A)*password+(y*B)*random\_vector=(y*A)*password$

也就是如果B不满秩（非奇异），我们能得完全到password的 $(32-rank(B))$ 个线性组合，一个线性组合就是一组方程！！！

不断收集这样的 $(y_i*A_i,y_i*\bar b_i)$ ，直到所有 $y_i*A_i$ 向量构成的矩阵的秩达到32，也就可以通过解方程完全得到password。由此，整个问题得到解决。

解题脚本

# sage 9.2
from hashlib import sha256
import socket
def recvline(st):
    x = st.recv(1)
    data = b''
    while x != b'\n':
        data += x
        x = st.recv(1)
    return data


def sendline(st, data):
    st.send(data+b'\n')

P, n, t = 41, 64, 100

F.<x> = PolynomialRing(GF(P))
Q.<x> = F.quotient(x^(n // 2) - 1)
p=41
st = socket.socket()
# nc xxx.xxx.xxx.xxx xxx
st.connect(('xxx.xxx.xxx.xxx',xxx))
recvline(st)
recvline(st)
recvline(st)

def get_data():
    sendline(st,b"1")
    rl=Q(eval(recvline(st).decode().strip(">")))
    # m=eval(recvline(st).decode().strip(">"))
    m=matrix(GF(p),32,64 ,eval(recvline(st).decode().strip(">")))
    b=eval(recvline(st).decode().strip(">"))
    st.recv(2) # "> "
    return rl,m,b

r,m,b=get_data()
G = GeneralDiscreteDistribution([0.5] + [0.25] * 2)
password = random_vector(GF(P), n // 2).list()

def func_1():
    r, m, s = Q.random_element(), random_matrix(GF(P), n // 2, n), vector(GF(P), password + random_vector(GF(P), n // 2).list())
    b = [(r * F((m * s).list()) + F([choice([-1, 1]) * G.get_random_element() for _ in range(n // 2)])).list() for _ in range(t)]
    # print(str(r.list()) + '\n' + str(m.list()) + '\n' + str(b))
    return r,m,s,b

# 统计特征恢复b
def recover_b(b):
    b_dict=[dict() for _ in range(32)]
    for i in range(100):
        for j in range(32):
            if b[i][j] in b_dict[j]:
                b_dict[j][b[i][j]]+=1
            else:
                b_dict[j].setdefault(b[i][j],1)
    real_b=[]
    for b_counts in b_dict:
        clist= b_counts.items()
        real_b.append(max(clist,key=lambda x: x[1])[0])
    return vector(GF(p),real_b)
    
# 得到Q上r的等价矩阵
def get_equal_mat(r):
    rl=r.list()
    res=[]
    nl=len(rl)
    for i in range(nl):
        v=rl[(nl-i):]+rl[:(nl-i)]
        res.append(v)
    return matrix(GF(p),res)

known = []
target = []
for i in range(2048):
    # r,m,s,b=func_1()
    if i%200==0:
        print("rounds ",i)
    r,m,b=get_data()
    nl=32
    p=41
    MP=get_equal_mat(r).transpose()*m
    A = MP[:nl,:nl]
    B = MP[:nl,nl:n]
    c = recover_b(b)
    # assert A*vector(GF(p),s[:32])+B*vector(GF(p),s[32:])==c

    if B.rank() != 32:
        for ker in B.left_kernel().matrix():
            known.append(ker * A)
            target.append(ker * c)
            print("rank is ",matrix(GF(p),known).rank())
            if matrix(known).rank() >= 32:
                sol = matrix(GF(p), known).solve_right(vector(GF(p), target))
                print("got pwd")
                print(sol)
                sol=vector(GF(p),sol).list()
                sendline(st,b"2")
                sendline(st,str(int(sha256(str(sol).encode()).hexdigest(), 16)).encode())
                print(recvline(st))
                print(recvline(st))