Go 的 crypto/dsa 漏洞（CVE-2016-3959）摘要

Alex Mullins

2016年4月9日

引言

最近，Go 编程语言的数字签名算法（DSA）加密库中发现了一个 bug。在本文中，我们将详细介绍该 bug 的细节，以及攻击者如何利用它来对使用底层 DSA 库进行客户端认证的标准 Go SSH 服务器发起拒绝服务攻击。

该漏洞首次被提及是在 Open Source Security（oss-sec）邮件列表的一篇帖子中：http://seclists.org/oss-sec/2016/q2/11。

Go 在几个大整数例程中存在无限循环，这使得 Go 程序容易受到远程拒绝服务攻击。使用 HTTPS 客户端认证或 Go ssh 服务器库的程序都暴露在此漏洞之下。此问题正在以下 CL 中解决：https://golang.org/cl/21533

-- Jason Buberel

总而言之，如果该漏洞被利用，可能会导致底层 BigNum 库代码陷入无限循环。这将消耗 CPU 和内存等系统资源，并最终可能导致程序或系统本身无响应。

上述声明称 SSH 以及 HTTPS 客户端认证均受影响，但在查看了 Go 的 crypto/tls 和 net/http 包之后，这似乎并不正确。HTTPS 客户端认证可以使用 RSA 或 ECDSA 签名方案，但不能使用 DSA。请参见下文。如果我在这方面有误，请告知我。

https://golang.org/pkg/crypto/tls/#Certificate

type Certificate struct {
        Certificate [][]byte
        // PrivateKey contains the private key corresponding to the public key
        // in Leaf. For a server, this must implement crypto.Signer and/or
        // crypto.Decrypter, with an RSA or ECDSA PublicKey. For a client
        // (performing client authentication), this must be a crypto.Signer
        // with an RSA or ECDSA PublicKey.
        PrivateKey crypto.PrivateKey

        ... other fields
}

在该帖子出现在 oss-sec 邮件列表后不久，CVE 编号被发布：CVE-2016-3959。Go 维护者已准备好修复方案，该修复将出现在计划于 2016年4月13日（星期三）发布的 1.5.4 和 1.6.1 版本中；https://groups.google.com/forum/#!topic/golang-nuts/MmSbFHLPo8g。

要跟随本文中的代码示例进行操作，你需要安装 Go 1.6 版本。请按照 https://golang.org/doc/install 上的说明进行操作。如果你想下载本文档和代码示例，你还需要安装 Git。请按照 https://git-scm.com/book/en/v2/Getting-Started-Installing-Git 上的说明进行操作。要在终端中克隆仓库，请执行以下命令：

$ go get github.com/alexmullins/dsa

这会将仓库克隆到你的 Go 工作区中。

下一节将介绍该漏洞的详细信息。

缺陷

那么到底哪里出了问题？要回答这个问题，我们必须回到 oss-sec 邮件列表上的最初公告。除了对问题的一般性解释和指向 https://golang.org/cl/21533 的代码修复链接之外，那里没有太多信息。该变更的提交信息包含以下内容：

crypto/dsa: 尽早排除无效的 PublicKey

当 PublicKey.P == 0 时，Verify 将会失败。根本无需尝试。

--- Robert Griesemer

以及修复后的代码：

https://github.com/golang/go/blob/master/src/crypto/dsa/dsa.go#L247

// Verify verifies the signature in r, s of hash using the public key, pub. It
// reports whether the signature is valid.
//
// Note that FIPS 186-3 section 4.6 specifies that the hash should be truncated
// to the byte-length of the subgroup. This function does not perform that
// truncation itself.
func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
    // FIPS 186-3, section 4.7

    // Code fix added to check if the key parameters are sensible.
    if pub.P.Sign() == 0 {
        return false
    }

    if r.Sign() < 1 || r.Cmp(pub.Q) >= 0 {
        return false
    }
    if s.Sign() < 1 || s.Cmp(pub.Q) >= 0 {
        return false
    }

    w := new(big.Int).ModInverse(s, pub.Q)

    n := pub.Q.BitLen()
    if n&7 != 0 {
        return false
    }
    z := new(big.Int).SetBytes(hash)

    u1 := new(big.Int).Mul(z, w)
    u1.Mod(u1, pub.Q)
    u2 := w.Mul(r, w)
    u2.Mod(u2, pub.Q)
    v := u1.Exp(pub.G, u1, pub.P)
    u2.Exp(pub.Y, u2, pub.P)
    v.Mul(v, u2)
    v.Mod(v, pub.P)
    v.Mod(v, pub.Q)

    return v.Cmp(r) == 0
}

总结一下上面的提交信息和代码修复：在 Go 1.6 及更早版本中，crypto/dsa 包的 Verify 函数存在一个 bug。如果有人在将公钥参数 P 设置为 0 的情况下调用 Verify，则会导致 Verify 函数中更靠后的某个语句陷入无限循环。

稍微绕道解释一下 DSA。DSA 是一种使用非对称密码学对消息进行签名的数字签名算法，该签名之后可用于保证消息确实是由发送方/私钥持有者发送的。举个简单的例子，Alice 给 Bob 发送一条消息，告诉他俩应该在何时何地共进午餐。不过 Bob 想确保消息确实是 Alice 发送的，而不是其他人。为了实现这一点，Alice 将用她的私钥对消息签名，而 Bob 可以用他所知道的 Alice 公钥来验证 Alice 的签名。除私钥持有者外，任何人都无法对消息进行签名，使其能够通过对应的公钥验证（至少理念上是这样）。

DSA 正常工作需要 5 个大数。前 3 个数被称为 DSA 参数 P、Q 和 G。它们定义了底层群和群生成元。可以通过调用 dsa.GenerateParameters() 正确创建这些数。

type Parameters struct {
        P, Q, G *big.Int
}

DSA 所需的最后两个数是私钥 X 和对应的公钥 Y。也可以通过调用 dsa.GenerateKey() 创建这些数。

type PrivateKey struct {
        PublicKey
        X *big.Int
}

type PublicKey struct {
        Parameters
        Y *big.Int
}

要跟上本文的进度，以上便是你需要了解的关于 DSA 的全部内容。更多信息请参阅 NIST 标准：http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf 或维基百科页面：https://en.wikipedia.org/wiki/Digital_Signature_Algorithm。

回到正题；Verify 函数中的无限循环在哪里？再多挖掘一点，你会发现代码卡在：

v := u1.Exp(pub.G, u1, pub.P)

这是 Exp() 方法的注释：

// Exp sets z = x**y mod |m| (i.e. the sign of m is ignored), and returns z.
// If y <= 0, the result is 1 mod |m|; if m == nil or m == 0, z = x**y.
// See Knuth, volume 2, section 4.6.3.
func (z *Int) Exp(x, y, m *Int) *Int {

从上面可以看出，注释说明当 m == 0 时，它将在没有模约减的情况下进行幂运算。当你拿一个大数去和另一个大数做幂运算时，结果也将是一个非常大的数。我对 math/big 的工作原理不太熟悉，但我认为这里发生的就是这种情况。Exp() 正在拼命计算这个幂运算，这将花费非常非常长的时间才能完成（跟无穷大也差不多了）。

以下是从下面的测试代码中收集到的、在 dsa.Verify() 调用 Exp() 时使用的一些示例数字：

x = 87134495734400160760614045850064869082246125869475484226357302998590334523718907040547736115253396811403341841812955872027275698952059512800196447089300992352859585665865224989740
07948775031938554271780506269767106717359222697821209685947889925442133804051298762702245652821695254167558015585995918548052076 (307 digits)

y = 751336012463178371212581620103057049388105279629 (48 digits)

z = x ^ y

使用 Wolfram Alpha，可以大致了解这个数字 z 有多大。结果数字 z 中有“113406800566837208055789635448879116719378036793444 或 1.13407x10^50 位十进制数字”。（注意：在 Wolfram Alpha 的网页输入框中只能输入 x 的前 150 位数字再求 y 次幂，所以实际的位数还要更多！）为了让你对规模有个概念：科学家估计宇宙中的原子数量接近 10^78 到 10^82 http://www.universetoday.com/36302/atoms-in-the-universe/。

DSA 签名/验证的测试示例：

func generatePrivKey(t *testing.T) *dsa.PrivateKey {
    // Create the DSA parameters
    params := dsa.Parameters{}
    err := dsa.GenerateParameters(&params, rand.Reader, dsa.L1024N160)
    if err != nil {
        t.Fatalf("failed to generate dsa parameters: %v", err)
    }

    // Create the DSA private/public keys
    priv := new(dsa.PrivateKey)
    priv.Parameters = params
    err = dsa.GenerateKey(priv, rand.Reader)
    if err != nil {
        t.Fatalf("failed to generate dsa keys: %v", err)
    }
    return priv
}

func TestDSASignature(t *testing.T) {
    var message = "Hello brave new world!"
    var hash = sha1.Sum([]byte(message))
    var err error

    priv := generatePrivKey(t)

    // Sign a message
    r, s, err := dsa.Sign(rand.Reader, priv, hash[:])
    if err != nil {
        t.Fatalf("failed to sign message: %v", err)
    }

    if !dsa.Verify(&priv.PublicKey, hash[:], r, s) {
        t.Fatalf("failed to verify message: %v", err)
    }
}

$ go test
PASS
ok      github.com/alexmullins/dsa    0.224s

将 P 设置为 0 的测试示例：

func TestDSAPanic(t *testing.T) {
    flag.Parse()
    if !*fail {
        t.Skip()
    }

    var message = "Hello brave new world!"
    var hash = sha1.Sum([]byte(message))
    var err error

    priv := generatePrivKey(t)

    // Sign a message
    r, s, err := dsa.Sign(rand.Reader, priv, hash[:])
    if err != nil {
        t.Fatalf("failed to sign message: %v", err)
    }

    // Set P = 0
    priv.P = new(big.Int).SetInt64(0)

    if !dsa.Verify(&priv.PublicKey, hash[:], r, s) {
        t.Fatalf("failed to verify message: %v", err)
    }
}

$ go test -fail

注意，这最后一个测试调用将会挂起。

漏洞利用

有人会如何利用这一点呢？如果攻击者能以某种方式让服务器接受并使用格式错误的 DSA 密钥来验证签名，他/她就可以使服务器陷入对一个大幂运算问题的拼命计算中，从而造成拒绝服务（DOS）。由于 SSH 在其客户端认证协议中使用 DSA 作为签名方案，这似乎是尝试该漏洞利用的完美服务器候选。让我们设想一个可能发生这种情况的场景。

一家小型 Git 托管服务商允许其用户使用 SSH 密钥对其服务进行认证，而他们的 SSH 服务器是用 Go 编写的。为了搞垮该服务，攻击者可以创建大量虚假账户，并上传格式错误的 DSA 密钥用于 SSH 认证。所有这些密钥的参数 P 都将被设置为 0。然后，攻击者可以向服务器发起数百个这样的 SSH 客户端连接，导致系统资源被锁死，从而造成有效的 DOS。

让我们测试一下该场景。

服务器

该服务器是一个简单的 SSH 服务器，接受会话请求并向连接打印当前时间。感谢 github.com/jpillora 在 https://gist.github.com/jpillora/b480fde82bff51a06238 提供了这个示例服务器代码。对代码做了一些调整，以便使用公钥认证而不是密码回调。

config := &ssh.ServerConfig{
    // Accept all authentication requests
    PublicKeyCallback: func(c ssh.ConnMetadata, key ssh.PublicKey) (*ssh.Permissions, error) {
        return nil, nil
    },
}

这将接受所有公钥认证请求。想象一个真实的服务会查询数据库，以确定某个用户是否在其账户下注册了该公钥。这个服务器看起来就像一个非常普通的 Go 服务器，开始监听端口并接受传入的连接。

dsa

最受欢迎

Go 的 crypto/dsa 漏洞（CVE-2016-3959）摘要

引言

缺陷

漏洞利用

服务器