浅尝 Lattice 之 HNP

 

前言

格密码是一类备受关注的抗量子计算攻击的公钥密码体制。而格理论也使许多现代公钥密码RSA、DSA等体系受到影响。这篇文章主要从两道CTF题目来学习格密码中的HNP(Hidden number problem）。

 

Lattice

首先谈谈个人对Lattice的理解叭。个人觉得，Latiice就是由若干线性无关的向量组成的一个向量空间，在这个空间中，向量彼此之间可以进行相应的加、减运算。向量也可以乘以某个系数，但这个系数仅限于整数，因而形成了布满整个空间的格点。在格中的计算问题主要包括两种，即SVP(the Shortest Vector Problem of lattice)和CVP(the Closest Vector Problem)，然后个人认为，CVP可以给Latiice加上一个维度后变成SVP，继而可以用LLL算法来进行规约从而找到最短向量。

 

XCTF2020-高校战役-NHP

题目附件

题目信息

题目用的是DSA公钥密码签名系统。

题目提供签名函数：用户以用户名注册，服务端返回签名，并提供所用临时密钥的bit长度

我们需要以admin的身份登陆来获取flag，但是服务端不会给admin签名

解题流程

根据题目流程，显然，我们要利用临时密钥的bit长度来获取私钥，从而获得admin的签名

其中，我们知道的信息全局公钥p, q, g，服务端公钥y , 每轮签名使用的r, s, 以及我们可控的H(x)，x即为用户名，Hash函数这里用的是sha256

step1-公式转化

由DSA签名中各参数的关系

可得每轮临时密钥与签名、明文的关系

其中ki就是每次使用的临时密钥

化简后的式子中的Ai,Bi均可由已知信息计算

step2-构造Lattice

对于上式中的ki，我们仅仅知道它的bit_ength，bit_ength泄露了什么信息呢？

当我们知道一个数的bit_ength时，我们能确定这个数的大小范围，

比如一个数的bit_ength是500时，我们能确定这个数大小落在(2^499)-1与(2^500)-1 之间

所以我们知道这个数的MSB位为2^499

这等价于，我们知道了临时密钥的一个大概的值，我们设其为K

然后我们构造Lattice

然后这里就会存在一个向量

使得

其中向量v中的x即为我们的私钥，

step3-LLL

解决格密码的问题LLL算法的运用总是必不可少的，可是这里我们该如何利用LLL算法去找到向量vk呢？

如果我们的vk的长度在格中很小，我们利用LLL就很可能将其找出。所以，我们需要与服务端交互，然后收集当ki的bit_length比较小的情况时的相关数据。比如：我们知道q的bit_length为128，那我们可以找bit_legnth为122的ki，然后我们还需要一定的数据量，这样能提高利用LLL算法找到这个短向量的概率，并且，上述格中K/q, K的构造也是为了让vk中的每一项的长度都差不多，这样也有利于找到vk，参考这一篇文章中的

参考祥哥博客的这篇出题文章，另外感谢祥哥的解惑。

 

NPUCTF2020-babyLCG

题目附件可以在BUUOJ下载

题目流程

1. 初始化一个LCG加密类，用到随机参数a, b, m, seed，其中a, b, m，均在附件给出
2. 生成20个128位的随机数，但是只给出每个数的高64位
3. 再生成三个随机数，用AES加密加密flag，key由前两个随机数组成，分别取第一个随机数和第二个随机数的高64位拼起来，iv由第三个随机数组成

解题思路

从题目流程来看，我们目的只有一个，恢复seed。

step1-公式转化

LCG生成随机数的公式为：

但是这一题，我们只知道s1 到s20的高64位，所以我们将si分为h、l高低位两部分，其中hi已知。所以有

这里，我们通过公式的变形，可以将原来式子

中s{i+1}和s{i}的关系转变为l{i+1}和l{i}的关系。当然，原系数a、b的意义也发生了对应转变。

这里给出生成新A 和B 的脚本

b=153582801876235638173762045261195852087
a=107763262682494809191803026213015101802
m=226649634126248141841388712969771891297

h = [0,7800489346663478448,11267068470666042741,5820429484185778982,6151953690371151688,548598048162918265,1586400863715808041,7464677042285115264,4702115170280353188,5123967912274624410,8517471683845309964,2106353633794059980,11042210261466318284,4280340333946566776,6859855443227901284,3149000387344084971,7055653494757088867,5378774397517873605,8265548624197463024,2898083382910841577,4927088585601943730]
for i in range(len(h)):
    h[i] <<= 64
A = [1]
B = [0]
for i in range(1, len(h)-1):
    A.append(a*A[i-1] % m)
    B.append((a*B[i-1]+a*h[i]+b-h[i+1]) % m)
print(A[1:])
print(B[1:])

step2-构造Lattice

现在我们二十条与 l 相关的方程组了。即

且对于 l 我们真的一无所知么？我们其实知道 l 是小于2^64的，即 l 最大为64bit。这样与前面一道题就很类似了。

其中l1即为s1的低位，拼上其高位，在利用a, b, m就能会恢复seed了

step3-LLL

这里我们的vl向量每一位都只有约64bit，显然，它是整个格中比较短的向量了，且我们一共有19组数据，那么直接对这个Lattice M运用LLL算法就可以找到vl了。（格中参数2^{64}的选取道理与上面一致）

完整exp：

'''
#sage
b=153582801876235638173762045261195852087
a=107763262682494809191803026213015101802
m=226649634126248141841388712969771891297

h = [0,7800489346663478448,11267068470666042741,5820429484185778982,6151953690371151688,548598048162918265,1586400863715808041,7464677042285115264,4702115170280353188,5123967912274624410,8517471683845309964,2106353633794059980,11042210261466318284,4280340333946566776,6859855443227901284,3149000387344084971,7055653494757088867,5378774397517873605,8265548624197463024,2898083382910841577,4927088585601943730]
for i in range(len(h)):
    h[i] <<= 64
A = [1]
B = [0]
for i in range(1, len(h)-1):
    A.append(a*A[i-1] % m)
    B.append((a*B[i-1]+a*h[i]+b-h[i+1]) % m)
A = A[1:]
B = B[1:]


M = matrix(ZZ, 21, 21)

for i in range(19):
    M[i, i] = m
    M[19, i] = A[i]
    M[20, i] = B[i]
    M[i, 19] = M[i, 20] = 0
M[19, 19] =  1
M[20, 20] = 2^64
M[19, 20]= 0


#print(B)
vl = M.LLL()[0]
l1 = vl[-2]
h1 = h[1]
s1 = l1+h1
#s1 = a*seed+b %m
seed = ((s1 - b)*inverse_mod(a,m))%m
print(seed)

'''
#python
from Crypto.Util.number import *
from Crypto.Cipher import AES

class LCG:
    def __init__(self, bit_length):
        b = 153582801876235638173762045261195852087
        a = 107763262682494809191803026213015101802
        m = 226649634126248141841388712969771891297
        seed = 73991202721494681711496408225724067994
        self._key = {'a':a, 'b':b, 'm':m}
        self._state = seed

    def next(self):
        self._state = (self._key['a'] * self._state + self._key['b']) % self._key['m']
        return self._state

    def export_key(self):
        return self._key


def gen_lcg():
    rand_iter = LCG(128)
    key = rand_iter.export_key()
    f = open("key", "w")
    f.write(str(key))
    return rand_iter


def leak_data(rand_iter):
    f = open("old", "w")
    for i in range(20):
        f.write(str(rand_iter.next() >> 64) + "n")
    return rand_iter


def encrypt(rand_iter):
    f = open("ct", "wb")
    key = rand_iter.next() >> 64
    key = (key << 64) + (rand_iter.next() >> 64)
    key = long_to_bytes(key).ljust(16, b'x00')
    iv = long_to_bytes(rand_iter.next()).ljust(16, b'x00')
    cipher = AES.new(key, AES.MODE_CBC, iv)
    pt = flag + (16 - len(flag) % 16) * chr(16 - len(flag) % 16)
    ct = cipher.encrypt(pt.encode())
    f.write(ct)

def decrypt(rand_iter):
    with open("ct", "rb") as f:
        flag = f.read()

    key = rand_iter.next() >> 64
    key = (key << 64) + (rand_iter.next() >> 64)
    key = long_to_bytes(key).ljust(16, b'x00')
    iv = long_to_bytes(rand_iter.next()).ljust(16, b'x00')
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ct = cipher.decrypt(flag)
    print(ct)


def main():
    rand_iter = gen_lcg()
    rand_iter = leak_data(rand_iter)
    decrypt(rand_iter)


if __name__ == "__main__":
    main()

 

总结

从这两题我们可以发现，解决HNP问题，一般我们需要多组数据，然后每一组就像方程组中的每一条方程，我们根据这些方程组构造一个Lattice，也可以认为是一个矩阵，就好像在用矩阵解决线代中的 XA=B 的问题，这个B中的每一项是我们获得的MSB这样子的比较模糊的信息（上面两题我们拿到的都是未知量的bit_length，也相当于MSB）。然后这个B向量的长度（范式）需要相对与格中其他向量要短，然后我们就可以利用LLL算法找到这个B，进而根据我们的构造，确定X向量中我们需要的一个特定的值。也就是方程组的解。

需要再次说明的是，这个矩阵所代表的方程组并非像真正的线代中的XA=B问题中的方程组——是多元的。我们这里的方程组是一元的。如果正常解方程的话，之所以这么多条方程都算不出解，就是因为我们得到信息是模糊的，并非是准确的。故我们需要用到格理论，和一个超好用的LLL算法。