Introduction
最近遇到了好几道关于DSS（DSA + ECDSA)的题目：
-
2020 gxzyCTF NHP （这题是自己出的，嘿嘿嘿）
也去认真地看了几篇paper：
- Bellare, Mihir, Shafi Goldwasser, and Daniele Micciancio. “Pseudo-random” number generation within cryptographic algorithms: The DDS case." Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 1997.
- Wong, David. “Timing and Lattice Attacks on a Remote ECDSA OpenSSL Server: How Practical Are They Really?.” IACR Cryptology ePrint Archive 2015 (2015): 839.
- Moghimi, Daniel, et al. “Tpm-fail: TPM meets timing and lattice attacks.” arXiv preprint arXiv:1911.05673 (2019).
就想写篇文章，总结一下学到的东西。
DSS
DSS的话可以看这篇Specification： FIPS 186-4 。
关于
DSS和DSA的关系，实际上就跟AES和Rijndael的关系一样
这边主要关注DSA（ECDSA基本上都是同样的原理）。
DSA具体流程如下：
上图中的$a$即下文中的私钥$x$，$S_1, S_2$即下文中的$r, s$，$D$即下文中的$m$。
具体流程也可以看wiki 。
在DSA中，要对一个信息$m$进行签名，就先得生成一个随机数$k$。
这个$k$（nonce）要随机生成，而且只能使用一次，下一次签名的时候就必须得再重新生成一个新的$k$。
DSA出问题的话，主要就会出在这个$k$上面：
- Reused k
- LCG-generated k
- Short k
Reused k
如果有两次签名，共用了同一个$k$，那么直接GG。
由于$r = (g^k \bmod{p}) \bmod{q}$，所以如果共用同一个$k$的话，可以从两次签名都有相同的$r$来看出。
我们知道$s = k^{-1}(m + xr) \bmod{q}$，如果两次的$r$都相同，即$r_1 = r_2$且$k_1 = k_2$，那么， $$ \begin{aligned} s_1 &= k_1^{-1}(m_1 + x r_1) \bmod{q} \newline s_2 &= k_2^{-1}(m_2 + x r_2) \bmod{q} \end{aligned} $$ 可以直接将这两个式子相减，消去带$x$的项， $$ s_1 - s_2 = k^{-1} (m_1 - m_2) \bmod{q} $$ 其中$s_1, s_2, m_1, m_2$都是已知的，我们可以直接算出$k$： $$ k = (s_1 - s_2)^{-1} (m_1 - m_2) \bmod{q} $$ 而只要我们能够知道某一次签名所用到的这个$k$，我们就可以算出私钥$x$： $$ x = r_i^{-1}(s_i k_i - m_i) \bmod{q} $$ 关于这个问题，ctfwiki 上也有很好的讲解。
几道相关的CTF题：
一个很有意思的现实案例就是Sony的PS3被人给日了（iPhone hacker publishes secret Sony PlayStation 3 key ）：
LCG-generated k
$k$必须是要随机生成的，而且每次都不能一样。
那么如果这个生成$k$的随机数生成器（PNG）并不是那么的安全，会怎么样呢？
这里主要研究由LCG （Linear Congruence Generator）生成的$k$。
那么，我们就可以知道前一个$k$和后一个$k$在数学上的一个关系： $$ k_2 = a\cdot k_1 + b \pmod{M} $$ 加上了这样一层关系，破解DSA就变得简单多了。
事实上，DSA中$k$是很关键的，只要暴露出了某个$k$，就可以直接根据$x = r_i^{-1}(s_i k_i - m_i) \bmod{q}$得到私钥$x$。
所以DSA中$r = (g^k \bmod{p}) \bmod{q}$的这一步，就是要通过DLP把$k$给隐藏（mask）起来。
我们能够知道的就只有$r, s, m$以及公钥，想要从$r, g, q$得到$k$，我们就必须得解出DLP。
但是当这个生成$k$的随机数生成器是LCG或者LCG的变种的话，我们就可以绕过这个DLP的限制，从其他方向得到私钥$x$。
当我们得到了2组连续的签名（$k$由LCG生成）后，
我们可以忽略掉$r = (g^k \bmod{p}) \bmod{q}$这一步，直接从$s = k^{-1}(m + xr) \bmod{q}$这一步上手，列出如下3个同余方程： $$ \begin{cases} \begin{aligned} s_1 k_1 - r_1 x & = m_1 \pmod{q} \newline s_2 k_2 - r_2 x & = m_2 \pmod{q} \newline -a k_1 + k_2 &= b \pmod{M} \end{aligned} \end{cases} $$ 其中，未知量仅3个：$k_1, k_2, x$。
我们可以试着把这三个同余方程给解出来。
但这就会引起两个问题：
-
如何解这个同余方程组？
如果说LCG的模数$M$恰好就是$q$的话，那么问题就变得十分简单了，直接在
Zmod(q)上用线代知识（gaussian elimination）解方程就完事了。（2020 gyctf LCG 就是这样的一道题）solver.sagefor 2020 gyctf LCG1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19# sagemath 8.9 from sys import argv assert len(argv[1:]) == 9 [r1, s1, r2, s2, m1, m2, a, b, q] = [int(x) for x in argv[1:]] B = Matrix(Zmod(q), [ [s1, 0, -r1], # k1 [0, s2, -r2], # k2 [a, -1, 0 ] # x ]) Y = vector(Zmod(q), [m1, m2, -b]) sol = B.solve_right(Y) x = sol[2] print(x)但是，绝大多数情况下，LCG的模数$M$是不可能和$q$相等的。那么这个时候，这个方程组就是不同模数的同余方程组，这很棘手，没有什么现成的板子能直接去解决这个问题。
-
可能会有多解的情况？
由于我们忽略掉了$r = (g^k \bmod{p}) \bmod{q}$这一层关系，实际上这个同余方程组是有可能会有多解的，当我们解出来某一组解时，这组解可能并不是满足$r = (g^k \bmod{p}) \bmod{q}$这一个条件的解。
当我们解出某一组解时，我们可以根据$g^x \bmod{p}$是否等于$y$或者$g^k \bmod{p}$是否等于$r$来判断我们的这一组解是否是我们想要的那一组解。
我们首先解决多解的情况。
会不会多解，实际上是一个概率问题。
这个概率与$p, M$以及获取到的签名个数相关。
paper
中给出了一个Uniqueness Lemma：
在Id0-rsa.pub DSA with LCG nonce 这一题中，
|
|
我们现在有2组签名，那么
|
|
非正确解的个数比0.805...小，也就是说不存在非正常解。即如果我们能解出那个同余方程组，那么我们解出来的一定是正确解。
关于这个Uniqueness Lemma的证明，看了一眼就不想看了，感兴趣的话可以仔细研究研究：
然后就是如何解这个systems of linear equations in different moduli的问题了。
实际上我们直接硬解（Solving via Integer Programming）的话，即通过把同余式转化为等式（这样会又引入3个位置量），是很慢的、infeasible。
这个时候，就得用上我们的lattice了。
事实上，同余问题是可以很容易用lattice来表示的。
那么既然要用lattice，就得先造好格子。
$$
\begin{cases}
\begin{aligned}
s_1 k_1 - r_1 x & = m_1 \pmod{q} \newline
s_2 k_2 - r_2 x & = m_2 \pmod{q} \newline
-a k_1 + k_2 &= b \pmod{M}
\end{aligned}
\end{cases}
$$
未知量是$k_1, k_2, x$。
稍微把上面那个方程组对齐一下：
$$
\begin{cases}
\begin{aligned}
-r_1 x & + s_1 k_1 & & = m_1 \pmod{q} \newline
-r_2 x & & + s_2 k_2 & = m_2 \pmod{q} \newline
& - a k_1 & + k_2 & = b \pmod{M} \newline
\end{aligned}
\end{cases}
$$
可以造好一个3✕6的格子：
$$
\begin{bmatrix}
-r_1 & s_1 & 0 & q & 0 & 0 \newline
-r_2 & 0 & s_2 & 0 & q & 0 \newline
0 & -a & 1 & 0 & 0 & M \newline
\end{bmatrix}
$$
第一列乘上$x$，第二列乘上$k_1$，第三列乘上$k_2$，再加减第四、五、六列的某几个倍数，即可得到$[m_1, m_2, b]^T$。
也就是说$[m_1, m_2, b]^T$是这个
lattice上的一个格点。
但就这样显然不太行，没什么办法去求$x, k_1, k_2$。
这个时候，就得再往下造点东西。
实际上，我们这边可以利用CVP把我们想要求的$k_1, k_2, x$给带出来。
$$
\begin{bmatrix}
-r_1 & s_1 & 0 & q & 0 & 0 \newline
-r_2 & 0 & s_2 & 0 & q & 0 \newline
0 & -a & 1 & 0 & 0 & M \newline
\gamma_1 & 0 & 0 & 0 & 0 & 0 \newline
0 & \gamma_2 & 0 & 0 & 0 & 0 \newline
0 & 0 & \gamma_3 & 0 & 0 & 0
\end{bmatrix}
$$
这样加入底下3行后，这个lattice变成了一个6✕6的格子。
LLL算法其实也可以在非方阵上运行，但是总感觉造格子基本上都是弄成方阵，这样看起来更舒服一点？？
此时，$X := [m_1, m_2, b, x \cdot \gamma_1, k_1 \cdot \gamma_2, k_2 \cdot \gamma_3]^T$就是这个lattice上的一个格点：
$$ \begin{bmatrix} -r_1 & s_1 & 0 & q & 0 & 0 \newline -r_2 & 0 & s_2 & 0 & q & 0 \newline 0 & -a & 1 & 0 & 0 & M \newline \gamma_1 & 0 & 0 & 0 & 0 & 0 \newline 0 & \gamma_2 & 0 & 0 & 0 & 0 \newline 0 & 0 & \gamma_3 & 0 & 0 & 0 \newline \end{bmatrix} \times \begin{bmatrix} x \newline k_1 \newline k_2 \newline l_1 \newline l_2 \newline l_3 \end{bmatrix} = \begin{bmatrix} m_1\newline m_2\newline b\newline x \cdot \gamma_1\newline k_1 \cdot \gamma_2\newline k_2 \cdot \gamma_3 \end{bmatrix} $$
可能这样竖着看
lattice怪怪的。。
但是这三个$\gamma_1, \gamma_2, \gamma_3$应该如何取值呢？
现在并没有很多很小的量，挺难利用SVP的。
我们可以往CVP的方向考虑：
CVP即给定一个非格点，找到一个离这个点最近的格点。
-
格点
我们现在知道$X$这个格点是绝对会在
lattice上的，但是我们无法算出这个格点，因为这个格点的后三项中有我们未知的量$x, k_1, k_2$。 -
非格点
我们应该要试着造一个离$X$十分接近的非格点。
事实上，$v$这个格点的后三项是未知的给了我们造非格点的思路，其中$\gamma_1, \gamma_2, \gamma_3$是可以任我们选取的。
既然要离得很近，干脆直接让$X$的后三项变得很小（接近于1），即我们选取非格点为$Y := [m_1, m_2, b, 1, 1, 1]^T$，然后再选取$\gamma_1, \gamma_2, \gamma_3$来使得$X$的后3项尽量接近于1。
讲道理，也可以直接让$X$的后三项无限接近于0，即选取$Y := [m_1, m_2, b, 0, 0, 0]^T$，但我试了下，貌似不太行。。
这样我们就能利用，寻找离目标非格点$Y$的最近格点$X$，这样一个求解CVP的问题，来找到携带着$x, k_1, k_2$信息的$X$。
我们知道 $$ \begin{aligned} 0 &< x < q\newline 0 &< k_1 < M\newline 0 &< k_2 < M \end{aligned} $$ 用概率论里面的数学期望来说，就是 $$ \begin{aligned} \overline{x} &= q/2\newline \overline{k_1} &= M/2\newline \overline{k_2} &= M/2\newline \end{aligned} $$
所以为了让$x \cdot \gamma_1, k_1 \cdot \gamma_2, k_2 \cdot \gamma_3$尽量地接近1，我们可以选取 $$ \begin{aligned} \gamma_1 &= 2/q\newline \gamma_2 &= 2/M\newline \gamma_3 &= 2/M\newline \end{aligned} $$
实际上选取$1/q, 1/M, 1/M$也可以求解出来
这样的话 $$ \begin{aligned} \overline{x \cdot \gamma_1} &= 1\newline \overline{k_1 \cdot \gamma_1} &= 1\newline \overline{k_2 \cdot \gamma_1} &= 1\newline \end{aligned} $$ 因此$X = [m_1, m_2, b, x \cdot \gamma_1, k_1 \cdot \gamma_2, k_2 \cdot \gamma_3]^T$就是一个离目标向量$Y = [m_1, m_2, b, 1, 1, 1]^T$相当近的一个格点。
只要我们对
$$
\begin{bmatrix}
-r_1 & s_1 & 0 & q & 0 & 0\newline
-r_2 & 0 & s_2 & 0 & q & 0\newline
0 & -a & 1 & 0 & 0 & M\newline
2/q & 0 & 0 & 0 & 0 & 0\newline
0 & 2/M & 0 & 0 & 0 & 0\newline
0 & 0 & 2/M & 0 & 0 & 0
\end{bmatrix}
$$
先LLL lattice reduction一下，然后再用Babai's algorithm来寻找最近格点，即可找到我们想要的$X$。
而此时在$X = [m_1, m_2, b, x \cdot \gamma_1, k_1 \cdot \gamma_2, k_2 \cdot \gamma_3]^T$中，第四项$ x \cdot \gamma_1$中携带者我们想要的私钥$x$，而$\gamma_1$又是我们已知的，所以可以轻松地求出私钥$x$。
paper 中对更加细微的地方进行了严谨的研究，感兴趣的可以去看看。。。
我看的时候，是真的感觉到自己智商快不够用了。。
paper
中还对此进行了延伸，即如何求解更加广泛的systems of linear equations in different moduli。
我已经看不下去了。。
但是感觉这个可能是个出难题的思路？？
利用这个方法，我们可以写出代码实现，解出Id0-rsa.pub DSA with LCG nonce 中的这道题：
|
|
Short k
从上面我们可以看到，$k$的随机性非常重要。
那既然如此，我们干脆就直接用CSPRNG（Cryptgraphically Secure Pseudorandom Number Generator），比如说os.urandom。
但，如果这也没处理好的话，也会出问题。。
即，我们生成的$k$，在$r = (g^k \bmod{p}) \bmod{q}$这一步的时候，一定要严格按照FIPS 186-4中的要求，用constant time的算法来执行。
否则，就会有可能会泄露出$k$的一个大小关系，而仅仅凭借这个大小关系，攻击者就可以直接从中获取到私钥$x$。
观察到这样一个有趣的东西，我在高校战“疫”网络安全分享赛 中就出了一道相关的密码题。
链接：http://www.soreatu.com/ctf/writeups/Writeup%20for%20NHP%20in%202020%20gxzyCTF.html
想要深入了解的可以去看看，在此就不再详细展开了。
事实上，对于short k的造格子方法，不光有我预期解里的那种。
在这篇paper 中，有这样一种构造方法：
利用CVP和Embedded Strategy来求解的。
方法上虽然有所不同，但本质上其实是大同小异的。
此外，这篇paper 实际上读起来算是很舒服的那种，十分推荐。
虽然有好几处小错误。。
Summary
所以，想要在实际中实现一个安全的密码系统(cryptosystem)，还是挺困难的。。