Understanding and Exploiting Go’s DSA Verify Vulnerability

Last week the Go project announced version 1.13.2. It contained a fix for a bug in the dsa.Verify function. The bug is considered a security vulnerability and was assigned the name CVE-2019-17596. Using CVSS to score the vulnerability, it would likely be classified as a MEDIUM, because an attack vector for the vulnerability is over the network, without authentication.

The Go language has a good track record from a security point of view. Vulnerabilities have historically been in the developer toolchain (eg, effecting go get), or logical errors. This vulnerability is different. It is a null pointer dereference causing a panic. Perhaps more importantly is that it could be exploited in many “pre-authentication” contexts. This is because public key cryptographic algorithms like the Digital Signature Algorithm (DSA) are used as an authentication mechanisms. Thankfully, due to the design of the Go language, this vulnerability is limited to crashing the process, and does not appear to be a mechanism to trigger a remote code execution or have a more serious impact.

A few years ago I was discussing network level pre-authentication exploits with Marc Rogers. I made a ridiculous statement about how they just aren’t going to happen that often — and how this is an important component for the vision of Zero Trust architectures. Marc responded with this:

Anything man makes, man can break

And today, Marc is right. DSA is math at its heart, but the implementation is still man made, and was broken. I hope these kinds of vulnerabilities aren’t common, since we need some building blocks to build systems upon, but since this is a more interesting vulnerability, I thought it would be fun to dive into how it works and see if we can build an exploit.

Background and initial research

The release announcement email said “Invalid DSA public keys can cause a panic in dsa.Verify”. Sounds simple enough, although the Go project did not provide any examples of what an invalid public key looks like. The next step is to look at the fix, as committed to git in the 1.13 release branch:

	w := new(big.Int).ModInverse(s, pub.Q)
+	if w == nil {
+		return false
+	}

The math/big package deals with very large numbers, and the big.Int type has a different design pattern than many parts of Go standard library: Many functions in the package return new copies of *big.Int for an operation, and if that operation has an error, they return nil instead. The big.Int.ModInverse function is documented as doing this. If we look further along in the the dsa.Verify function, we can see w is used without checking if ModInverse failed. The commit to fix the bug is a simple guard, checking the return value of ModInverse, and failing verification if it failed.

Breaking ModInverse

Since the release announcement mentioned invalid public keys could cause the panic, it seems clear we just need to make a pub.Q that causes the ModInverse function to return nil. The ModInverse documents its failure conditions:

// ModInverse sets z to the multiplicative inverse of g in the ring ℤ/nℤ
// and returns z. If g and n are not relatively prime, g has no multiplicative
// inverse in the ring ℤ/nℤ.  In this case, z is unchanged and the return value
// is nil.

I didn’t take time to really comprehend what the documentation was explaining, instead thinking I needed to construct a seemingly valid pub.Q, but slightly invalid somehow. I dove headfirst in with an ignorant fuzzing phase. I started with a pub.Q from a valid DSA key parameters, and thought I could increment it by one until ModInverse failed. I made a small test case, let my laptop run for a minute trying higher values, but it did not work.

I paused and took time to read the code, to understand what ModInverse is doing. The critical error condition path is this:

	d.GCD(&x, nil, g, n)

	// if and only if d==1, g and n are relatively prime
	if d.Cmp(intOne) != 0 {
		return nil
	}

src/math/big/int.go#L758-L788

We just need the Greatest Common Denominator (GCD) of the two numbers to not be the integer 1.

The other piece of information I realized at this point, was that the r parameter in the dsa.Verify function is from the DSA SIgnature. In most cases if you are an attacker, you could be in a position to provide both the public key and the signature to verify. After staring at very large numbers like 1289233352290115814210005730521570412018870172097 for awhile, I decided to use the smallest numbers possible that could cause a GCD of more than one.

When you reduce the problem down to this, you could use the number two (2) for r, and four (4) for pub.Q, since the greatest common denominator of these numbers is 2, the condition returns nil:

	r := new(big.Int).SetInt64(2)
	q := new(big.Int).SetInt64(4)

	d := new(big.Int).GCD(nil, nil, r, q)

full example

Back to DSA Verify

Now that we have numbers that cause ModInverse to return nil, we need to construct a test case that can cause dsa.Verify to crash. But when I tried our numbers out, I saw that dsa.Verify returned false instead of crashing. Going back to the unpatched function, we see this:

	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
	}

src/crypto/dsa/dsa.go#L274-L286

There are 3 conditionals we must pass before crashing, in addition ModInverse returning nil. The first two conditions are simple enough, we cannot use a negative r or s, and the pub.Q must be greater than r and s. Our choices of 2 and 4 work fine. The last conditional is a little different. It’s checking how many bits it would take to represent pub.Q in binary. With a value of 4, the BitLen() is only 3. The minimal value with a BitLen() that is greater than 7 is 128.

Setting s=2, r=2, pub.Q=128 we are able to crash dsa.Verify:

    r.SetInt64(2)
    s.SetInt64(2)
    priv.PublicKey.Q.SetInt64(128)

    dsa.Verify(&priv.PublicKey, hashed, r, s))

complete dsa_test.go

Exploiting dsa.Verify over SSH

Making a local test case that crashes is trivial even if there isn’t a security vulnerability, what makes this crash interesting is if we can trigger it over a network protocol. Many protocols can use DSA to verify the identity of the other peer. I wanted to demonstrate the vulnerability in a protocol that many people used, but in a proof of concept that is not directly weaponizable. Breaking SSH Clients seemed like a good target, since it would require a man in the middle connection for most attackers, and is just a client crash worst case. I’m going to leave exploiting this vulnerability TLS Client Certificates as an exercise for the reader…

In the SSH-2 protocol, there is a Key Exchange phase. One of the messages from the Server to the Client signed with its “host key”, and as part of the protocol, the client must run the dsa.Verify function on this signed data. For this exploit, all we need to do is inject our bad values for r, s, and pub.Q into the SSH Key exchange.

The gliderlabs/ssh package makes it easy to construct a mock SSH server, so then we can try to crash an SSH client. On the server, the first step is to construct a crypto.Signer which returns our evil values:

	priv.PublicKey.Q.SetInt64(128)
	fs := &fakeSigner{
		R:      new(big.Int).SetInt64(2),
		S:      new(big.Int).SetInt64(2),
		public: priv.PublicKey,
	}

ssh_test.go#L19-L24

The crypto/ssh package uses a different interface for its Signers, but there is a helper function to convert a crypto.Signer into the interface the ssh package needs: ssh.NewSignerFromSigner. To the mock SSH server, we add the evil signer as a host key.

On the client, we just call ssh.Dial with a default configuration:

	conn, err := gossh.Dial("tcp", addr, clientConfig)
	require.NoError(t, err)
	defer conn.Close()

ssh_test.go#L47-L51

Running this with Go 1.13.1, we get a crash:

panic: runtime error: invalid memory address or nil pointer dereference
[signal SIGSEGV: segmentation violation code=0x1 addr=0x18 pc=0x536c9c]

goroutine 6 [running]:
math/big.(*Int).Mul(0xc000043bb8, 0xc000043bd8, 0x0, 0xc000016460)
	math/big/int.go:168 +0xdc
crypto/dsa.Verify(0xc00000e460, 0xc000016460, 0x14, 0x20, 0xc000043cc0, 0xc000043ca0, 0xc000120280)
	crypto/dsa/dsa.go:289 +0x214
golang.org/x/crypto/ssh.(*dsaPublicKey).Verify(0xc00000e460, 0xc000016440, 0x20, 0x20, 0xc00011a2a0, 0x0, 0x0)
	golang.org/x/crypto@v0.0.0-20191011191535-87dc89f01550/ssh/keys.go:474 +0x367
golang.org/x/crypto/ssh.verifyHostKeySignature(0x807f00, 0xc00000e460, 0xc00011e580, 0x807f00, 0xc00000e460)
	golang.org/x/crypto@v0.0.0-20191011191535-87dc89f01550/ssh/client.go:124 +0xd9

Another interesting part of this crash, is because of how the SSH Client library is using goroutines for processing, it is not possible to use the recover() function to return from the crash. The ssh.Dial creates a goroutine for the connection, and when this verify fails, its in a new goroutine without a recover function, meaning the Go runtime has no choice but to exit the process. This design and use of goroutines in the ssh.Client is not a good pattern, since callers to Dial are unable to recover from errors. In issue #34960, it describes that the effect on net/http.Server is limited because it internally recover() the panic in its connection handling goroutine.

Test cases using a Docker container that has an old and vulnerable version of Go are on github at pquerna/poc-dsa-verify-CVE-2019-17596

Conclusion

This type of vulnerability is a good example of one that could be identified using static analysis or fuzzing. Daniel Mandragona and regilero were credited with discovering and reporting the issue, but I have not seen any mention of how they found the bug. Even with static analysis, it would take some work to fully understand if the error conditions could actually be exploited, which leads to many static analysis issues being ignored.

Finally, as a general statement, DSA itself should not be used anymore. The only reason to enable it is to support a legacy system. OpenSSH for example removed support for DSA in recent releases. This class of vulnerability isn’t isolated to DSA, but every code path has potential vulnerabilities — so if you can disable DSA completely in your systems, you should.