CVE-2016-3959: Go DSA Verify DoS Fix and Early Validation

The Verify function in Go’s crypto/dsa implementation (crypto/dsa/dsa.go) contained an input‑validation flaw that could be weaponized to force an application into an infinite loop and an effective denial‑of‑service; the bug was tracked as CVE‑2016‑3959 and fixed in the emergency releases Go 1.5.4 and Go 1.6.1.

Background​

Cryptographic signature verification is a foundational building block for secure communications. The Digital Signature Algorithm (DSA) is one of the classical public‑key signature schemes used in a variety of protocols, and Go’s standard library provides a DSA implementation under the package crypto/dsa. In April 2016 the Go project published an urgent security release to address two separate issues, one of which—CVE‑2016‑3959—related to missing parameter checks in the DSA Verify routine that allowed crafted inputs to funnel into the big‑integer math routines in a way that could hang a process.
The public disclosure and code fix were coordinated by the Go team and landed as part of the Go 1.5.4 and 1.6.1 releases. The official changelog and review metadata for the change shows the maintainers explicitly added early validation to reject patently invalid DSA public keys so the heavy math paths would never be invoked with bad parameters.
I also reviewed archived community discussion and forum traces while preparingsue and its fix were discussed on several mailing lists and security advisories at the time, and those conversations helped clarify how attackers could pass malformed DSA parameters to applications that consume untrusted public keys—SSH host keys or certificate chains in TLS contexts, for example.

---

What exactly was wrong?​

At a high level, the root cause was insufficient input validation before invoking operations from the heavy‑duty big integer arithmetic library (math/big). Some big‑integer operations return nil to indicate an arithmetic impossibility or error (for example, when an inverse does not exist), and the original crypto/dsa Verify implementation did not always check these nil returns or perform conservative parameter validation early enough.
Two aspects combined to create the DoS condition:

• A DSA public key structure with nonsensical parameters (for example, a prime modulus P equal to zero) could slip past the earlier range checks and reach code paths that invoke costly modular exponentiation and other big‑integer loops.
• Under those conditions, underlying big‑integer routines could enter a very long (in practice, effectively infinite) computation, consuming CPU and causing the process to hang rather than fail quickly.

The Go project’s fix was pragmatic and surgical: validate key parameters as early as possible (reject P==0, validate r and s ranges, check ModInverse return values later in related fixes) so the verification routine returns false quickly for malformed inputs instead of invoking risky math paths. The upstream commit message describes the change as “eliminate invalid PublicKey early.”

---

Why this mattered: attack surface and realistic attack vectors​

Not all cryptographic code is exposed to untrusted inputs in a way that matters. However, there are real‑world protocols and stacks where a remote, unauthenticated peer can cause signature verification to run on attacker‑controlled values. Two common, practical attack vectors worth highlighting:

• SSH host keys / SSH client authentication — In SSH key exchange the server signs key‑exchange material with its host key and the client verifies that signature. A malicious or compromised server (or a man‑in‑the‑middle) can present malformed DSA key parameters during that exchange to trigger vulnerable verification code in clients using Go’s crypto/ssh implementation.
• TLS/HTTPS client certificates and chain parsing — Though DSA is not commonly used for modern TLS server certificates, client certificate authentication and some legacy certificate chains can contain DSA keys in certain deployments. An HTTPS client that accepts a certificate chain from a server or a TLS server that requests client certificates could end up parsing and verifying attacker‑controlled DSA public keys. The Go security advisory explicitly called out HTTPS client certificates and SSH server libraries as exposed surface.

It is worth being precise: exploitation requires the ability to make the target verify a DSA public key crafted by the attacker. That is not a universal capability for all Internet services, but where it exists the result is severe: a remote, unauthenticated actor can induce a resource‑consumption stall (CPU burn and unresponsiveness) with trivial protocol interactions.
Security researchers later produced proof‑of‑concepts showing how malformed r/s/Q/P values could lead to crashes, panics, or infinite loops depending on the Go release and the exact code path—SSH client/server, TLS client certificate verification, or other library uses. Those write‑ups are useful reading if you want to understand the math‑level triggers and concrete exploit patterns.

---

Timeline and vendor response​

• Discovery and reporting: the problem was publicly disclosed in April 2016 via security mailing lists and internal reporting channels.
• Vendor action: the Go project shipped emergency point releases Go 1.5.4 and Go 1.6.1 that included fixes for CVE‑2016‑3959 (and other issues). The announcement explicitly recommended upgrading to Go 1.6.1 or 1.5.4 as appropriate.
• Upstream code fix: the change is visible in the Go repository with a commit that adds early checks to crypto/dsa/dsa.go and related defensive checks reviewed through the Go code review process.
• Distribution: Linux distributions and package maintainers rebased or repackaged patched Go releases after the upstream fixes; advisory databases catalogued the CVE and categorized its impact.

In short: the maintainers reacted quickly and produced a minimal, correct fix that avoided touching unrelated behavior. The fix closed the immediate DoS vector.

---

Technical deep dive (for developers and security engineers)​

This section walks through the important technical points you should know if you maintain Go code or operate services built with Go.

Where the bug lived​

The vulnerable code was in the function:

• crypto/dsa.Verify(pub PublicKey, hash []byte, r, s big.Int) bool

This function performs DSA verification steps including range checks for r and s and modular arithmetic with pub.P, pub.Q, pub.G and the signature components r and s. The problem was that certain invalid public‑key parameters (notably P==0) or signature values could reach a point where the big‑integer library behaved in unexpected ways: returning nil from operations like ModInverse or entering costly internal loops that never completed in reasonable time for the caller.

The fix​

Two immediate defensive practices were applied:

• Early parameter sanity checks — Reject obvious invalid public keys (for example, a modulus P with Sign() == 0) before any heavy math occurs. Returning false for verification on clearly invalid keys prevents invoking the expensive code paths.
• Check returned big.Int values — When calling operations like ModInverse, code must check for nil results and treat them as verification failures. Later follow‑on fixes in the DSA Verify family added those checks where they were missing.

Together these changes turn long‑running computations into constant‑time quick fails for malformed inputs.

Why modular inverse and big integer returns matter​

The math/big package in Go uses pointers to big.Int objects and some operations conventionally return nil to indicate the result cannot be computed (e.g., no modular inverse exists). If caller code assumes non‑nil returns and immediately dereferences or uses the result, a nil can propagate into a panic—or unguarded behavior can create mathematically non‑terminating loops depending on how those values are used. Defensive programming against nil returns is mandatory when using math/big in a security context.

---

Operational impact: who is at risk?​

The set of affected targets depends on two things:

• The Go runtime and standard library version used to build the binary (older releases before 1.5.4 / 1.6.1 are vulnerable).
• Whether the deployed binary accepts or verifies DSA public keys or certificate chains originating from untrusted or remote peers.

High‑priority exposures include:

• SSH servers and clients built with Go that accept DSA host keys or attempt to verify DSA signatures from untrusted sources.
• Any TLS client that performs client‑certificate verification where the certificate or chain could include DSA public keys from untrusted servers.
• Middleware and libraries that parse and validate X.509 material in contexts where attackers control (or can inject) the public key values.

Lower‑risk cases include Go programs that use only RSA/ECDSA and never parse DSA keys, or services running behind strict middleboxes that filter malicious protocol artifacts. Nonetheless, auditing and patching is recommended because DSA keys can appear in unexpected places (legacy configurations, cross‑signed chains, or edge stacks).

---

Detection, audit, and remediation checklist​

If you operate Go services, follow this checklist to assess and remediate exposure.

• Inventory Go versions used to build deployed binaries.
• If you have access to sources or build pipelines, ensure the Go toolchain used to compile production binaries was upgraded to at least Go 1.5.4 / 1.6.1 at the time of the fix—or preferably to a currently supported release.
• If you only have binaries, look for build info embedded in the binary (Go 1.12+ embed build info; older binaries may include strings referencing the Go toolchain). If you can run the binary, run it with a probe that prints runtime/debug build info or inspect the binary for module or build metadata.
• Recompile and redeploy using a patched toolchain.
• This vulnerability is in the standard library; compiled binaries include the vulnerable code. Replacing the runtime source or patching the system Go package is not sufficient—you must recompile the application with a fixed standard library.
• For containerized builds or CI pipelines, pin base images and toolchain versions to known patched releases and re‑run full builds to produce patched artifacts.
• Update OS/package vendor Go runtimes.
• If you use distribution‑provided Go packages (system package managers), install the updated golang packages provided by the distro and rebuild or redeploy binaries as necessary. Distribution advisories tracked the CVE and many released updated packages soon after the upstream fix.
• Audit protocol configurations for DSA use.
• Where possible, disable DSA keys in SSH and TLS configuration. Modern best practice is to use RSA (with safe key sizes) or ECDSA/Ed25519 for SSH host keys and certificates.
• For TLS, prefer ECDSA/RSA and require strong algorithms; disallow legacy signature types in client auth where feasible.
• Add runtime protections and monitoring.
• Use process supervision and resource limits (cgroups, ulimits, service managers) to ensure a single hung process does not disrupt critical systems.
• Monitor for anomalous CPU spikes or unexplained process hangs on services that perform signature verification; these indicators can point to attempted exploitation.
• Test with proof‑of‑concept checks.
• In controlled test environments, exercise client and server code paths with malformed DSA parameters to verify your patched builds reject invalid keys quickly. Use safe PoC code from reputable writeups only in isolated lab conditions.

---

Longer‑term lessons and risk analysis​

CVE‑2016‑3959 is a classic case study in why cryptographic code needs defensive parameter validation even when it sits inside a mature standard library. A few takeaways:

• Library correctness is necessary but not sufficient. Even well‑reviewed implementations can miss edge cases where mathematically invalid inputs produce pathologies in lower‑level arithmetic code.
• Compiled‑in vulnerabilities require rebuilds. Because Go statically links its standard library into binaries, fixes to the standard library only protect new builds. Operations teams must coordinate rebuilds and re‑deployments; patching an OS package alone is not enough if production artifacts were built with the vulnerable toolchain.
• Attack surface is protocol/context dependent. The availability of a remote attacker to supply malicious DSA parameters depends on how your application uses keys. SSH and certain TLS contexts are highest risk, while pure‑RPC or internal‑only uses may be less exposed.
• Defense‑in‑depth reduces blast radius. Having network filtering, protocol hardening, and strict algorithm policy in addition to patched libraries makes exploitation much harder.

On severity: because the vulnerability leads to process hangs and CPU exhaustion rather than arbitrary code execution, the technical severity is denial of service, but the operational impact can be high—crashing a critical service is a severe availability event. Historical CVE scoring and distribution advisories reflect that nuance.

---

Practical recommendations for Windows‑focused administrators and developers​

Windows admins and developers often host Go binaries on Windows servers or develop cross‑platform services compiled with Go on Windows build agents. Here’s a focused checklist:

• If you build on Windows, update the Go toolchain on your build machines to a patched release (minimum: 1.5.4 / 1.6.1 historically; today prefer a current, supported Go release) and recompile all binaries that include crypto functionality or network protocol code.
• If you deploy third‑party Go binaries (for example, native Windows services shipped by vendors compiled with Go), ask the vendor for proof of rebuild with a fixed toolchain or for an updated executable. Treat it as untrusted until confirmed.
• For SSH services or tools on Windows that embed Go’s crypto/ssh implementation, ensure the service will not accept or validate DSA keys from remote peers, or update the binary.
• Apply standard Windows service hardening: run sensitive services under constrained accounts, set CPU and memory limits where possible, and ensure service restarts are controlled to avoid crash/restart loops.
• Audit your environment for services that accept TLS client certificates; if those services were built with vulnerable toolchains, prioritize updating and rebuilding them.

---

Post‑mortem and follow‑on issues​

The Go project continued to harden DSA verification and related code in subsequent years; new CVEs addressing similar classes of defects (invalid DSA keys causing panics or edge‑case failures) have been discovered and fixed as the ecosystem matured. This underlines the importance of continuous maintenance and proactive dependency updates in crypto code. Security write‑ups and post‑fix analyses provide useful guidance on the precise conditions that trigger failures and how later changes guarded against them.

---

Conclusion​

CVE‑2016‑3959 exposed a simple but consequential fact: unchecked inputs into cryptographic math can freeze a process. The Go team’s rapid response—introducing early parameter validation and releasing patched point versions—closed the immediate attack vector, but the operational consequence remains an important reminder. Because Go binaries statically link the standard library, defenders must not only update the toolchain but also recompile and redeploy affected software to be truly safe.
If you run Go services, prioritize a short inventory, rebuild strategy, and protocol hardening today: check which builds used older Go releases, recompile with a maintained toolchain, and consider disabling legacy DSA usage where feasible. These steps will neutralize the DSA‑Verify DoS vector and reduce the chance that attacker‑supplied malformed keys can take your systems offline.

---

Source: MSRC Security Update Guide - Microsoft Security Response Center