Soreat_u's Blog

Intended Solution to GGH in GYCTF 2020

 Writeup

[题目文件]：

Mega网盘： https://mega.nz/file/neJRVAZa#K3MdaqF_eqMwg6aiRB1HZQ2LeVL6EdQEXGQTrgNOufU

[题目信息]：

出题人 出题时间 题目名字 题目类型 难度等级
Soreat_u 20200206 GGH Crypto 6

[题目描述]：

Only LLL may not help. Nguyen said that there is a major flaw in the design of the scheme. Can you exploit it?

[题目考点]：

1. 格密码
2. 最近向量难题(CVP)、最短向量难题（SVP）
3. LLL算法
4. Embedded Technique
5. Nguyen's Attack

[Flag]:

flag{5cd9893d-2753-4e8a-a954-11de5b2d553b}

[题目环境]：

SageMath 8.9

[题目制作过程]：

  1. 在“源码”目录下，执行sage task.py。

[题目writeup]：

1997年，Goldreich、Goldwasser、Halevi三人受Ajtai在格难题上的研究所启发，提出了一个基于格中最近向量难题的非对称密码学算法：GGH Cryptosystem。

1999年，Nguyen发现在这个密码学算法设计中，有一个很大的缺陷，可以使攻击者从密文中获取到明文的部分信息，且可以将原来的最近向量难题转化为一个较为简单的最近向量难题。基于这个观察，Nguyen解出了设计者放在网上的5个challenge中的4个（其中有2个被设计者认为是不可能攻破的），足以证明该密码算法是broken的。

本题即基于Nguyen's Attack。

由于大部分CTF的crypto题中的非对称密码学算法都是围绕着RSA展开，对格密码涉及很少，因此想要解出本题则需要选手有较为丰富的格相关的数学基础。且有关于格密码的内容，网上几乎很少，只能通过阅读相关的paper来进行学习，因此本题也需要选手有相当优秀的自学能力。

后来在i春秋上发现了一个很不错的格相关教学视频：https://www.ichunqiu.com/course/50433

里面都是些密码学大牛的讲课，非常专业。不过可能只有数理基础及其扎实的人才能听得懂吧。:)

具体关于GGH密码算法可以参考如下内容，在此就不详细展开了：

下面简单介绍一下Nguyen's Attack：

GGH的加密过程如下： $$ \mathbf{c} = \mathbf{m}B + \mathbf{e} $$ 其中，

  • $\mathbf{m}$：由明文组成的一个1×n 向量
  • $B$：由公钥（bad basis）组成的一个n×n矩阵
  • $\mathbf{e}$：一个1×n向量，其中每一项不是3就是-3
  • $\mathbf{c}$：加密后的密文

我们现在已知的就只有$\mathbf{c}, B$，想要求的是这个$\mathcal{m}$。

Nguyen观察到，如果对上式取模3， $$ \mathbf{c_3} = \mathbf{m_3}B_3 + \mathbf{e_3} \pmod{3} $$ 那么由于$\mathbf{e}$中每一项都是±3，所以取模3后就是$\mathbf{0}$： $$ \mathbf{c_3} = \mathbf{m_3}B_3 \pmod{3} $$ 因此可以求出$\mathbf{m_3}$，即明文mod 3后的内容。

但是Nguyen又观察到取模6会是一个更好的选择。

我们先令 $$ \mathbf{s} = (3, 3, \dots, 3) \in \mathbb{Z}^n, $$ 那么，$\mathbf{s} + \mathbf{e}$中每一项不是6就是0，取模6后也是$\mathbf{0}$。

可以在$\mathbf{c} = \mathbf{m}B + \mathbf{e}$两边加上这个$\mathbf{s}$

$$ \mathbf{c} + \mathbf{s} = \mathbf{m}B + (\mathbf{e} + \mathbf{s}) $$

取模6后，就是 $$ \mathbf{c_6} = \mathbf{m_6}B_6\pmod{6} $$ 这样就可以求出$\mathbf{m_6}$，即明文mod 6后的内容。

所以说，这个密码学算法是可以让攻击者从密文中得到部分明文的信息。

下面，我们再来推算一下，如何将这个最近向量难题（CVP）变成一个更简单的CVP。

有了$\mathbf{m_6}$之后，我们可以在等式 $$ \mathbf{c} = \mathbf{m}B + \mathbf{e} $$ 的两边同时减去$\mathbf{m_6}B$： $$ \mathbf{c} - \mathbf{m_6}B = (\mathbf{m} - \mathbf{m_6})B + \mathbf{e} $$ 其中$\mathbf{m} - \mathbf{m_6}$中的每一项必定是6的倍数，可以写为$6\cdot \mathbf{m’}$，且$\mathbf{m’} \in \mathbb{Z}^n$。

我们可以在上式两边同时除去6： $$ \begin{aligned} \frac{\mathbf{c} - \mathbf{m_6}B}{6} &= \frac{(\mathbf{m} - \mathbf{m_6})B}{6} + \frac{\mathbf{e}}{6},\newline \frac{\mathbf{c} - \mathbf{m_6}B}{6} &= \mathbf{m’}B + \frac{\mathbf{e}}{6},\newline \mathbf{c’} &= \mathbf{m’}B + \mathbf{e’} \end{aligned} $$ $\mathbf{c’}$我们可以算出来，$\mathbf{e’}$中的每一项不是$\frac{1}{2}$就是$-\frac{1}{2}$，$\mathbf{m’}$未知。

这样，我们就成功构建出了一个新的CVP，且偏差向量$\mathbf{e’}$比$\mathbf{e}$小得多，即构建出了一个更加简单的CVP。

可以利用embedded technique（篇幅有限，不深入，可以参考hxp的一篇wp ）将这个CVP转化为SVP，再利用LLL算法求解最短向量，即可得到$\mathbf{e’}$，进而解出$\mathbf{m’}$，最后求得$\mathbf{m}$。

注：在式子

$$ \frac{\mathbf{c} - \mathbf{m_6}B}{6} = \mathbf{m’}B + \frac{\mathbf{e}}{6} $$

中可能会涉及到实数域上的运算，可以在两边同乘上2，转化为在整数域上的运算。

即，求

$$ \frac{\mathbf{c} - \mathbf{m_6}B}{3} = \mathbf{m’}\cdot (2B) + \frac{\mathbf{e}}{3} $$ 的CVP。

更多内容可以参考Nguyen的那篇paper：

根据这个思路，编写exp（见“解题”下的exp.sage），即可获取到flag。

 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

# sage 8.9

# Read ciphertext and public key from the 2 given files.
c = []
with open('ciphertext.txt', 'r') as f:
    data = f.read().strip(' ')
    c =  [int(num) for num in data.split(' ')]
c = vector(ZZ, c)

B = []
with open('key.pub', 'r') as f:
    for line in f.readlines():
        line = line.strip(' \n')
        B.append([int(num) for num in line.split(' ')])
B = matrix(ZZ, B)

# Nguyen's Attack.
n = 150
delta = 3
s = vector(ZZ, [delta]*n)
B6 = B.change_ring(Zmod(2*delta))
left = (c + s).change_ring(Zmod(2*delta))
m6 = (B6.solve_left(left)).change_ring(ZZ)
new_c = (c - m6*B) * 2 / (2*delta)

# embedded technique
new_B = (B*2).stack(new_c).augment(vector(ZZ, [0]*n + [1]))
new_B = new_B.change_ring(ZZ)

new_B_BKZ = new_B.BKZ()
shortest_vector = new_B_BKZ[0]
mbar = (B*2).solve_left(new_c - shortest_vector[:-1])
m = mbar * (2*delta) + m6

print ''.join(map(chr, m[:42]))

1
2

$ sage exp.sage
flag{5cd9893d-2753-4e8a-a954-11de5b2d553b}

[后记]

本以为这题应该会挺难的，但是不到1小时就被中科大的师傅秒了。。。（似乎是自己造的格子？LLL太神奇了

但是出题的时候，我测试过（正常）LLL算不出来的啊！！

又考虑到维度太高，LLL会跑很久，就没把n设置的很大。

实际上，根据后来的某篇paper，甚至$n=400$都可以解出来。

paper链接：