Case Study: Trivial Attack and Nontrivial Attacks against DSS

Introduction

最近遇到了好几道关于DSS(DSA + ECDSA)的题目:

也去认真地看了几篇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

关于DSSDSA的关系,实际上就跟AESRijndael的关系一样

这边主要关注DSA(ECDSA基本上都是同样的原理)。

DSA具体流程如下:

Screen Shot 2020-03-15 at 9.34.07 PM

上图中的$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 ):

Screen Shot 2020-03-15 at 9.41.30 PM

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.sage for 2020 gyctf LCG

     1
     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

Screen Shot 2020-03-15 at 11.21.55 PM

Id0-rsa.pub DSA with LCG nonce 这一题中,

1
2
q = 1221368137336824742280343964279058901472991770439
M = 983310466739698185049446758331422281214830590642

我们现在有2组签名,那么

1
2
3
n = 2
# M * q**(1-2) = M / q
M / q = 0.805089339307469

非正确解的个数比0.805...小,也就是说不存在非正常解。即如果我们能解出那个同余方程组,那么我们解出来的一定是正确解。

关于这个Uniqueness Lemma的证明,看了一眼就不想看了,感兴趣的话可以仔细研究研究:

Screen Shot 2020-03-15 at 11.27.48 PM


然后就是如何解这个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 中的这道题:

 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
# sagemath 8.9

from hashlib import sha1

def s2n(s):
    return int(sha1(s).hexdigest(), 16)

# Parameters
r1 = 202861689990073510420857440842954393147681706677
s1 = 316598684468735233298185340984928938581112602589
m1 = s2n("message1")
# m1 = 1044406300802172270572686707632639134303359350586

r2 = 43602034738807436825901197549075276008737747591
s2 = 642028161610139974743754581527505118749777770326
m2 = s2n("message2")
# m2 = 294463748341256225761057611418150472857673467481

q = 1221368137336824742280343964279058901472991770439

a = 545094182407654161786276305190438612396347946877
b = 106527113109554186270186272440947601748633355206
m = 983310466739698185049446758331422281214830590642


# Construct Lattice
L = matrix(
          [
              [-r1, s1,  0,  q,  0,  0],
              [-r2,  0, s2,  0,  q,  0],
              [  0, -a,  1,  0,  0,  m],
              [2/q,  0,  0,  0,  0,  0],
              [ 0, 2/m,  0,  0,  0,  0],
              [ 0,   0,2/m,  0,  0,  0]
          ])


# LLL Lattice Reduction
L_lll = L.transpose().LLL() # Must transpose!


# 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([m1, m2, b, 1, 1, 1]) # target vector

X = BabaisClosestPlaneAlgorithm(L_lll, Y)
print(X)


# Check
x = X[3] / (2/q)
k1 = X[4] / (2/m)
k2 = X[5] / (2/m)

assert (s1 * k1) % q == (m1 + r1*x) % q
assert (s2 * k2) % q == (m2 + r2*x) % q
assert k2 == (a*k1 + b) % m

print(x)
# 239521411488137610804169934941353577587127205711

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 中,有这样一种构造方法:

Screen Shot 2020-03-16 at 1.30.06 AM

利用CVPEmbedded Strategy来求解的。

方法上虽然有所不同,但本质上其实是大同小异的。

此外,这篇paper 实际上读起来算是很舒服的那种,十分推荐。

虽然有好几处小错误。。

Summary

所以,想要在实际中实现一个安全的密码系统(cryptosystem),还是挺困难的。。