A Summary of Go's crypto/dsa Vulnerability (CVE-2016-3959)

Alex Mullins

April 9, 2016

---

Introduction

Recently, there was a bug discovered in the Digital Signature Algorithm (DSA) crypto library for the Go programming language. In this article we'll go over the details of the bug and how an attacker could leverage it to initiate a denial of service attack against a standard Go SSH server that uses the underlying DSA library to authenticate clients.

The first mention of this vulnerability appeared in a post on the Open Source Security (oss-sec) Mailing List at http://seclists.org/oss-sec/2016/q2/11.

Go has an infinite loop in several big integer routines that makes Go programs vulnerable to remote denial of service attacks. Programs using HTTPS client authentication or the Go ssh server libraries are both exposed to this vulnerability. This is being addressed in the following CL: https://golang.org/cl/21533

-- Jason Buberel

In summary, if this vulnerability were exploited, it could lead to an infinite loop in the underlying BigNum library code. This will eat up system resources in terms of CPU and memory and could eventually cause the program or the system itself to become unresponsive.

The above statement says that SSH along with HTTPS client authentication are affected, but after looking at Go's crypto/tls and net/http packages that appears to be incorrect. HTTPS client authentication can use either RSA or ECDSA signature schemes, but not DSA. See below. If I am wrong about this please let me know.

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
}

Not long after that post appeared on the oss-sec mailing list, a CVE number was issued: CVE-2016-3959. The Go maintainers have a fix ready for this and will appear in versions 1.5.4 and 1.6.1 that are to be released on Wednesday, April 13, 2016; https://groups.google.com/forum/#!topic/golang-nuts/MmSbFHLPo8g.

To follow along with the code samples in this article you'll need Go version 1.6 installed. Follow the instruction at https://golang.org/doc/install. If you want to download this document and the code samples you'll need Git installed too. Follow the instructions at https://git-scm.com/book/en/v2/Getting-Started-Installing-Git. To clone the repository issue the following command in a terminal:

$ go get github.com/alexmullins/dsa

This will clone the repository into your Go workspace.

The next section will cover the details of the vulnerability.

The Flaw

So what exactly is wrong? To answer that, one must go back to the original announcement on the oss-sec mailing list. There isn't much information there other than a general explanation of the problem and a link to the code fix at https://golang.org/cl/21533. The commit message for that change contains the following:

crypto/dsa: eliminate invalid PublicKey early

For PublicKey.P == 0, Verify will fail. Don't even try.

--- Robert Griesemer

and the fixed code:

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
}

To sum up the commit message and the code fix above: in Go 1.6 and previous versions there is a bug in the Verify function of the crypto/dsa package. If someone calls Verify with the public key parameter P set to 0 then it will cause an infinite loop in one of the statements further down in the Verify function.

A brief detour to explain DSA. DSA is a digital signature algorithm that uses asymmetric cryptography to sign a message which can later be used to guarantee that the message was in fact sent by the sender/private key holder. A simple example, Alice sends a message to Bob telling him where and when they should both meet for lunch. Bob though, wants to be sure that Alice is really the one that sent him the message and not someone else. For this to work Alice will sign the message with her private key and Bob can verify Alice's signature with her public key that Bob knows. No one other than the private key holder can sign a message that can then be verified by the corresponding public key (that's the idea at least).

To work, DSA needs 5 large numbers. The first 3 numbers are known as the DSA parameters P, Q, and G. These define the underlying group and the group generator. These numbers can be properly created with a call to dsa.GenerateParameters().

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

The last two numbers needed for DSA are the private key X and the corresponding public key Y. These numbers can also be created with a call to dsa.GenerateKey().

type PrivateKey struct {
        PublicKey
        X *big.Int
}

type PublicKey struct {
        Parameters
        Y *big.Int
}

That is all that you need to know about DSA to follow along. For more information see the NIST standard: http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf or the wikipedia page: https://en.wikipedia.org/wiki/Digital_Signature_Algorithm.

Back on topic; where is the infinite loop at in the Verify function? With a little more digging you will find that the code hangs on:

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

This is the comment for the Exp() method:

// 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 {

From the above, you can see the comment specifies that when m == 0 that it will exponentiate without modular reduction. When you take a large number and exponentiate it with another large number then the result will also be a REALLY BIG number. I'm not too familiar with how math/big works, but I think that is what is going on here. Exp() is crunching away at this exponentiation that will take a very, very long time to complete (might as well be infinity).

Here are some sample numbers being used in a dsa.Verify() call to Exp() gathered from the testing code below:

x = 87134495734400160760614045850064869082246125869475484226357302998590334523718907040547736115253396811403341841812955872027275698952059512800196447089300992352859585665865224989740
07948775031938554271780506269767106717359222697821209685947889925442133804051298762702245652821695254167558015585995918548052076 (307 digits)