VNCTF2022 Crypto WriteUp

2022-02-12

字数统计: 2.6k字 | 阅读时长≈ 13分

寒假无聊摸鱼，月赛题没有crypto，就随便写了misc来看看VN的题，下午写完两道crypto就没看了，后面发现VN的题质量还挺不错。

ezmath

模15意义下2的阶为4，从而返回4*n即可。

远程exp如下：

from pwn import *
import string
from hashlib import sha256
from itertools import product

# context.log_level="debug"

def set_connect_proof():
    io=remote("node4.buuoj.cn",27867)
    io.recvuntil(b"sha256(XXXX+")
    alphabet = string.ascii_letters + string.digits
    lattar_part=io.recv(16).decode('utf8')
    io.recvuntil(b'== ')
    h=io.recvline().strip().decode('utf8')
    # print(h)
    io.recvuntil(b'[+] Plz Tell Me XXXX :')
    bruteforce=[ ''.join(prefix)+lattar_part  for prefix in product(alphabet,repeat=4)]
    for proof in bruteforce:
        if sha256(proof.encode()).hexdigest()==h:
            io.sendline(proof.encode()[:4])
            break
    print("proof done")
    return io

io=set_connect_proof()
for _ in range(777):
    line=io.recvline().decode("utf8").split(" ")
    t=int(line[4][:-2])
    n=t*4
    io.sendline(str(n).encode())
    io.recvline()

print(io.recvline())
print(io.recvline())

AreYouAdmin

DSA的题，k是由类似LCG的伪随机数生成器产生的，所以用于签名的k之间是相关的，在本题中，对于连续的三个签名之间的k有如下关系：

$k_2=(k_0*a+k_1*b+c)\mod M \mod q$

参考用一般的LCG： $next=a*prev+b \mod M$ 来产生DSA中的k的相关攻击：DSA-LCG（理论的推导看这篇paper），我们对该攻击进行扩展。

如果M小于q，那么后面一个模q可以忽略，但是本题中M大于q，而 $k_i$ 在模q的意义一致即可，因此，M与q的大小没有关系。我们梳理一下已知的信息：

$a,b,c已知\\ M=2^{512}\\ secretkey位数为169位\\ p,q,g已知\\ 三组连续签名(hm_i,r_i,s_i),i=0,1,2$

那么我们可以联立得到以下方程：

$\left\{ \begin{array}{**lr**} s_0*k_0-r_0*x=hm_0 \mod q\\ s_1*k_1-r_1*x=hm_1 \mod q\\ s_2*k_2-r_2*x=hm_2 \mod q\\ k_2=(k_0*a+k_1*b+c)\mod M \mod q, & \end{array} \right.$

在假设M小于q的条件下，我们可以构造如下格：

$\begin{bmatrix} -r_0 & s_0 & 0 & 0 & q & 0 & 0 &0 \\ -r_1 & 0 & s_1 & 0 & 0 & q & 0 &0 \\ -r_2 & 0 & 0 & s_2 & 0 & 0 & q &0 \\ 0 & a & b & -1 & 0 & 0 & 0 & M \\ \end{bmatrix} \begin{bmatrix} x \\ k_0\\ k_1\\ k_2\\ n_1\\ n_2\\ n_3\\ n_4 \end{bmatrix} =>\begin{bmatrix} hm_0\\ hm_1\\ hm_2\\ -c \end{bmatrix}$

即向量 $m=[hm_0，hm_1，hm_2，-c]^T$ 是格 $L$ 列空间的一个格点（ $L*X=m$ ）,L和M都已知，但是我们需要X的信息，一般的方法是扩展格矩阵，用CVP把X的信息带出来。上面的格矩阵明显不对称，一般也需要扩展到方阵，于是我们将列空间同样扩展到8维，得到下面的格矩阵。

$L*X=m$ $\begin{bmatrix} -r_0 & s_0 & 0 & 0 & q & 0 & 0 &0 \\ -r_1 & 0 & s_1 & 0 & 0 & q & 0 &0 \\ -r_2 & 0 & 0 & s_2 & 0 & 0 & q &0 \\ 0 & a & b & -1 & 0 & 0 & 0 & M \\ \mu & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & \mu_0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & \mu_1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & \mu_2 & 0 & 0 & 0 & 0 \\ \end{bmatrix} \begin{bmatrix} x \\ k_0\\ k_1\\ k_2\\ n_1\\ n_2\\ n_3\\ n_4 \end{bmatrix} =>\begin{bmatrix} hm_0\\ hm_1\\ hm_2\\ -c\\ x*\mu\\ k_0*\mu_0\\ k_1*\mu_1\\ k_2*\mu_2\\ \end{bmatrix}$

其中 $\mu_i$ 我们是可以任意选择的，L已知，由于 $x,k_i$ 的大致比特范围我们已知，我们可以对列向量m的后4维做一个简单估计，当然，要使得后4维尽可能小，一般取$\mu,\mu_i$使得后面4维都约等于1，这样就变成了求解格密码的经典CVP问题，对于一般DSA的选取， $x\in[0,q]$ ， $k\in[0,M]$ ，一般均匀分布，估算大小为极值的一半，目标向量为 $target=[hm_0，hm_1,hm_2,-c,1,1,1,1]^T$ ,格为：

$L*X=m$ $\begin{bmatrix} -r_0 & s_0 & 0 & 0 & q & 0 & 0 &0 \\ -r_1 & 0 & s_1 & 0 & 0 & q & 0 &0 \\ -r_2 & 0 & 0 & s_2 & 0 & 0 & q &0 \\ 0 & a & b & -1 & 0 & 0 & 0 & M \\ 2/q & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 2/m & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 2/m & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 2/m & 0 & 0 & 0 & 0 \\ \end{bmatrix} \begin{bmatrix} x \\ k_0\\ k_1\\ k_2\\ n_1\\ n_2\\ n_3\\ n_4 \end{bmatrix} =>\begin{bmatrix} hm_0\\ hm_1\\ hm_2\\ -c\\ x*2/q\\ k_0*2/M\\ k_1*2/M\\ k_2*2/M\\ \end{bmatrix}$

此时m与我们设置的目标向量target是很接近的，利用Baiba算法就可以求出格L空间上距离target最近的向量m，从而得到私钥x。

当然到这里核心思路结束了，我们回到题目本身，上面都是假设M小于q，而此题中M大于q，因此第四列后面还需要消去额外的整数个q才能得到-c，那么类似地，我们继续扩展格到9维的方阵就可以解决上述问题。但是 $k_i$ 只要在模q的意义相等即可，所以8维的格也可以解，只是得的的k1,k2,k3是原始LCG的输出，并且注意到题目给出secretkey的比特数为169（如果不注意到这个条件是规约不出来的），因此一个更好的格如下（最后一行和最后一列可以去掉，8维也可解）

$\begin{bmatrix} -r_0 & s_0 & 0 & 0 & q & 0 & 0 &0&0 \\ -r_1 & 0 & s_1 & 0 & 0 & q & 0 &0&0 \\ -r_2 & 0 & 0 & s_2 & 0 & 0 & q &0&0 \\ 0 & a & b & -1 & 0 & 0 & 0 & M &q\\ 2/2^{169} & 0 & 0 & 0 & 0 & 0 & 0 & 0 &0\\ 0 & 2/q & 0 & 0 & 0 & 0 & 0 & 0 &0\\ 0 & 0 & 2/q & 0 & 0 & 0 & 0 & 0 &0\\ 0 & 0 & 0 & 2/q & 0 & 0 & 0 & 0 &0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ k_0\\ k_1\\ k_2\\ n_1\\ n_2\\ n_3\\ n_4\\ n_5 \end{bmatrix} =>\begin{bmatrix} hm_0\\ hm_1\\ hm_2\\ -c\\ x*2/2^{169}\\ k_0*2/M\\ k_1*2/M\\ k_2*2/M\\ n_5 \end{bmatrix}$

由于 $M//q=2$ ，最后一行最后一个数设为1，只要target向量最后一项和它数量级差不多即可。简单一点就取为： $[hm0, hm1, hm2, -c, 1, 1, 1, 1,1]$

最后只要注意到我们的格是基于列向量的，而sagemath默认的格是基于行向量的，我们把上面矩阵转置一下放sagemath写个脚本就行。

一个本地测试的脚本：

from Crypto.Util.number import *
from hashlib import *
# from secret import secretkey,flag,ezmath_flag
import socketserver
import os
import signal
import string
# assert len(bin(secretkey)) == 169
secretkey = 623214056451052576704964697381271257021209743577127
table = string.ascii_letters+string.digits


class PseudoRandomNumbersGenerators:
    def __init__(self, seed1, seed2):
        self.state_a = seed1
        self.state_b = seed2
        self.a = getRandomNBitInteger(160)
        self.b = getRandomNBitInteger(160)
        self.c = getRandomNBitInteger(160)
        self.M = int(1 << 512)

    def GetNext(self):
        ret = (self.state_a * self.a + self.state_b * self.b + self.c) % self.M
        self.state_a = self.state_b
        self.state_b = ret
        return ret

    def GetSomethingUseful(self, admin):
        if admin == True:
            return self.a, self.b, self.c
        else:
            return "You can't get anything here!Get out!"

    def choice(self, input):
        length = len(input)
        tmp = self.GetNext() % length
        return input[tmp]


class DigitalSignatureAlgorithm:
    def __init__(self, RANDOM):
        self.p = int(8945295668911819059540208265461979177678201229057426412681001447446107919117765962027889488459965388254641301806100385155760254966914075104367813869235667)
        self.q = int(4472647834455909529770104132730989588839100614528713206340500723723053959558882981013944744229982694127320650903050192577880127483457037552183906934617833)
        self.g = int(3)
        self.Random = RANDOM

    def verify(self, m, y, sig):
        r, s = sig
        if (not (1 <= r <= self.q - 1)) or (not (1 <= s <= self.q - 1)):
            return False
        z = bytes_to_long(sha256(m).digest())
        w = int(inverse(s, self.q))
        u1 = (z * w) % self.q
        u2 = (r * w) % self.q
        v = (int(pow(self.g, u1, self.p) * pow(y, u2, self.p))) % self.p % self.q
        return r == v

    def sign(self, m, x):
        z = bytes_to_long(sha256(m).digest())
        counts=0
        while 1:
            k = int(self.Random.GetNext()) % self.q
            r = int(pow(self.g, k, self.p)) % self.q
            s = (int(inverse(k, self.q)) * (z + x * r))% self.q
            counts+=1
            if (s != 0) and (r != 0):
                print("rounds: ",counts)
                return (k,r, s)


RANDOM = PseudoRandomNumbersGenerators(getPrime(120), getPrime(120))
DSA = DigitalSignatureAlgorithm(RANDOM)
x = secretkey
y = pow(DSA.g, x, DSA.p)
proof = (''.join([RANDOM.choice(table)for _ in range(20)])).encode()

m0 = b'dawn'
m1 = b'whisper'
m2 = b'want flag'
hm0 = bytes_to_long(sha256(m0).digest())
hm1 = bytes_to_long(sha256(m1).digest())
hm2 = bytes_to_long(sha256(m2).digest())
a,b,c=RANDOM.a,RANDOM.b,RANDOM.c
k0, r0, s0 = DSA.sign(m0, x)
k1, r1, s1 = DSA.sign(m1, x)
k2, r2, s2 = DSA.sign(m2, x)
print((k0,r0,s0,hm0))
# (r0,s0)=(1921414686017997074581161758552168551548721041692651218134481256920076949484332874792185699718229639244640321432591375248987630515295164466727746429853707, 2834324931042407821640639362734919932228313677885566132218238152942460232607031232710984234664825163998771949792819195253135851333421277994498191976219009)
# (r1, s1)=(2648503835801966378580401259634643218428810134880114138275328069516007014686814031403642053908378925697235562742830439865947816287604733931489887976911315, 1003947833499642194875076065224811926855379927832458518419403180057510508488016877207592305080240491365741923784760472109083082171196337541855968662965786)
# (r2, s2)=(1471715990002345012729435267244262016155285794182281873046890968233499494457118121438260644333233916184962791360227385874862970299243025333708841313520805, 3263169614831371701685969462426117983301188332512212092339102780728470212528952059528136885702890049010562706978545392119454689252475140941956688455694189)
# (a,b,c)=(1034497105992182250055811701641580760582467012783, 831680469688668757711862490722907552909204110274, 1386289918550027622917352584150264983159276657329)
q = 4472647834455909529770104132730989588839100614528713206340500723723053959558882981013944744229982694127320650903050192577880127483457037552183906934617833
p = 8945295668911819059540208265461979177678201229057426412681001447446107919117765962027889488459965388254641301806100385155760254966914075104367813869235667
g = 3
M = 1 << 512

# Construct Lattice
L = matrix(
    [
        [-r0, s0,  0,  0,  q, 0, 0, 0,0],
        [-r1,  0, s1,  0,  0, q, 0, 0,0],
        [-r2,  0,  0,  s2,  0, 0, q, 0,0],
        [0,  a,  b,  -1,  0, 0, 0, M,q],
        [2/2**169,  0,  0,   0,  0, 0, 0, 0,0],
        [0, 2/q,  0,   0,  0, 0, 0, 0,0],
        [0,  0, 2/q,   0,  0, 0, 0, 0,0],
        [0,  0,  0, 2/q,  0, 0, 0, 0,0],
        [0,  0,  0, 0,  0, 0, 0, 0,1]
    ])

L_lll = L.transpose().LLL() 


# Solve CVP
def BabaisClosestPlaneAlgorithm(L, w):
    G, _ = L.gram_schmidt()
    t = w
    i = L.nrows() - 1
    while i >= 0:
        w -= round((w*G[i]) / G[i].norm() ^ 2) * L[i]
        i -= 1
    return t - w


Y = vector([hm0, hm1, hm2, -c, 1, 1, 1, 1,1])  # target vector
X = BabaisClosestPlaneAlgorithm(L_lll, Y)
print(X)
# Check
rx = X[4] / (2/2**169)
rk0 = X[5] / (2/q)
rk1 = X[6] / (2/q)
rk2 = X[7] / (2/q)

print(rx)
print(secretkey)
assert rx==secretkey

在本题中secretkey是固定的，拿到一组数据后就可以本地得到secretkey之后再交互得到flag。

exp如下：

from pwn import *
import string
from hashlib import sha256
from itertools import product
# context.log_level="debug"
from Crypto.Util.number import *
from hashlib import *
import string

table = string.ascii_letters+string.digits

class PseudoRandomNumbersGenerators:
    def __init__(self,seed1,seed2):
        self.state_a = seed1
        self.state_b = seed2
        self.a = getRandomNBitInteger(160)
        self.b = getRandomNBitInteger(160)
        self.c = getRandomNBitInteger(160)
        self.M = 1 << 512

    def GetNext(self):
        ret = (self.state_a * self.a + self.state_b * self.b + self.c) % self.M
        self.state_a = self.state_b
        self.state_b = ret
        return ret

    def GetSomethingUseful(self,admin):
        if admin == True:
            return self.a,self.b,self.c
        else:
            return "You can't get anything here!Get out!"
    
    def choice(self,input):
        length = len(input)
        tmp = self.GetNext() % length
        return input[tmp]

class DigitalSignatureAlgorithm:
    def __init__(self,RANDOM):
        self.p = 8945295668911819059540208265461979177678201229057426412681001447446107919117765962027889488459965388254641301806100385155760254966914075104367813869235667
        self.q = 4472647834455909529770104132730989588839100614528713206340500723723053959558882981013944744229982694127320650903050192577880127483457037552183906934617833
        self.g = 3
        self.Random = RANDOM

    def verify(self, m, y, sig):
        r, s = sig
        if (not (1 <= r <= self.q - 1)) or (not (1 <= s <= self.q - 1)): 
            return False
        z = bytes_to_long(sha256(m).digest())
        w = inverse(s, self.q)
        u1 = (z * w) % self.q
        u2 = (r * w) % self.q
        v = (pow(self.g, u1, self.p) * pow(y, u2, self.p)) % self.p % self.q
        return r == v

    def sign(self, m , x):
        z = bytes_to_long(sha256(m).digest())
        while 1:
            k = self.Random.GetNext() % self.q 
            r = pow(self.g , k, self.p) % self.q
            s = (inverse(k, self.q) * (z + x * r)) % self.q
            if (s != 0) and (r != 0) :
                return (r, s)

RANDOM = PseudoRandomNumbersGenerators(getPrime(120),getPrime(120))
DSA = DigitalSignatureAlgorithm(RANDOM)
secretkey=99681635728635879538940784529297431947697608270113
x = secretkey
y = pow(DSA.g,x,DSA.p)

def set_connect_proof():
    io=remote("node4.buuoj.cn",25896)
    io.recvuntil(b"sha256(XXXX+")
    alphabet = string.ascii_letters + string.digits
    lattar_part=io.recv(16).decode('utf8')
    io.recvuntil(b'== ')
    h=io.recvline().strip().decode('utf8')
    # print(h)
    io.recvuntil(b'[+] Plz Tell Me XXXX :')
    bruteforce=[ ''.join(prefix)+lattar_part  for prefix in product(alphabet,repeat=4)]
    for proof in bruteforce:
        if sha256(proof.encode()).hexdigest()==h:
            io.sendline(proof.encode()[:4])
            break
    print("proof done")
    return io
msg = b"I'm Admin.Plz give me flag!"
r,s=DSA.sign(msg,secretkey)
io=set_connect_proof()
io.recvuntil("[IN]:")
io.sendline(b"S")
print(io.recvline())
io.recvuntil("[IN]:")
io.sendline(b'I')
io.recvuntil("flag of ezmath is :")
io.sendline(b"vnctf{m4th_5tr#c7Ur3_c4n_b3_e@s&!}")
(a,b,c)=eval(io.recvline().strip().decode())
print(a,b,c)
io.recvuntil("[IN]:")
io.sendline(b'V')
msg = b"I'm Admin.Plz give me flag!"
io.recvuntil(b'msg:')
io.sendline(msg)
io.recvuntil(b'r:')
io.sendline(str(r).encode())
io.recvuntil(b's:')
io.sendline(str(s).encode())
print(io.recvline())
print(io.recvline())
io.interactive()
io.close()

# vnctf{A1ic3_y0u_^^^^&yYd$!}