Cryptography Dispatches: DSA Is Past Its Prime

I want to start by acknowledging that tech is not the most important thing happening around me at the moment. It’s critical to understand our role in fixing the issues in the system we are part of. I found that Russ Cox captured that message very well in a recent email to golang-nuts, you should read the whole thing.

As the Rust team said well, tech is and will always be political, not in the sense of political parties but in the sense of affecting societal decisions about how opportunities and resources are allocated. […]

To people who think technology can be apolitical or neutral: let me say that when I started working on Go over a decade ago I thought the same thing. If you’re not the one being discriminated against – if the playing field is tilted in your favor – it is very easy not to notice that fact.

This is the time to listen to our Black colleagues and neighbors, but as a personal note I want to mention that when I came to the US from Italy I didn’t really understand the dynamics of racism here. I initially resisted the concepts of privilege and affirmative action, and I only learned thanks to a number of kind people who took the time to discuss with me.

That’s ok. Not understanding or agreeing with all the arguments one hears is not something to feel bad about, and doesn’t make someone a bad person. It’s just a sign that there’s more to learn about.

Here are a couple links that I promise will be a more important read than the rest of this newsletter.

• Can white people experience racism?
• Market, discrimination, and “lowering the bar”
• How NYPD Impunity Works
• How the Supreme Court Lets Cops Get Away With Murder

Now, to stay on brand, here’s some dunking on a broken cryptographic algorithm.

DSA

The Digital Signature Algorithm, as regrettably implemented by the Go standard library package crypto/dsa, is an old asymmetric signature scheme. It’s pretty bad in theory. It’s even worse in practice.

DSA was defined in the early 90s by NIST in the Digital Signature Standard.¹ (This is why SSH refers to it as ssh-dss.) Like the Diffie-Hellman key exchange, it works over the finite field of numbers modulo a prime, and is based on the discrete logarithm problem: the public key is g^x mod p, where x is the private key and p is a large prime.

A lot of the drawbacks and complexity of DSA carried over to its elliptic curve variant, ECDSA.³ However, a major issue specific to DSA is parameter generation. Operating DSA requires a set of parameters, like the p prime. They can be reused across different keys, but there is no standard set, and you are for some reason expected to generate a new set yourself and to send it along with the key.

This has been widely regarded as a bad move. It’s as if every time you wanted to use ECDSA you had to define a new elliptic curve. Generating parameters is slow (quoting the Go docs, it “can take many seconds, even on fast machines”), they make keys unnecessarily large, and worse of all if you can’t trust them they are extremely hard to verify.

Case in point: CVE-2019-17596 was a crash in the Go standard library due to a non-prime DSA parameter that the attacker could control through an SSH key or an X.509 certificate.²

This is really one of the major lessons cryptography engineering learned in the last 25 years: parameters need to be standardized, fixed, and hardcoded. Ideally, there should be only one set. We used to think the ability to change parameters was a security advantage should they turn out to be weak, but today we know the weak spot is the parameter selection itself.

DSA is not only broken from an engineering point of view, though, it’s also cryptographically weak as deployed. The strength of an N-bit DSA key is approximately the same as that of an N-bit RSA key⁴, and modern cryptography has painstakingly moved away from 1024-bit RSA keys years ago considering them too weak. Academics computed a discrete logarithm modulo a 795-bit prime last year. NIST 800-57 recommends lengths of 2048 for keys with security lifetimes extending beyond 2010. The LogJam attack authors estimated the cost of breaking a 1024-bit DLP to be within reach of nation-states in 2015.⁵ And yet, DSA with keys larger than 1024 bits is not really a thing!

What happened is that FIPS 186 required the key size to be between 512 and 1024 bits until the FIPS 186-3 revision in 2001. By then there was already little reason to implement DSA in a new system, and using larger keys would not interoperate with older ones, so no one really implemented the larger key sizes.

OpenSSH’s ssh-keygen only generates 1024-bit keys. Of the 8M SSH keys in the whoami.filippo.io dataset, 14285 are DSA keys, of which 13380 are 1024 bits long. The Go golang.org/x/crypto/ssh package literally rejects DSA keys larger than 1024 bits!

If you see DSA, you should really parse that as “1024-bit RSA, but more complex”. You see my point.

Thankfully, DSA support is dwindling. OpenSSH disabled DSA support by default in OpenSSH 7.0. The CA/Browser Forum Baseline Requirements banned DSA certificates from the WebPKI. FIPS 186-5 indicates DSA will no longer be approved for digital signature generation, but only for verification of legacy signatures. If you can read between the lines, you know what’s going to happen to DSA in Go.

Of course, DSA is still well-regarded in the PGP ecosystem.

Things happen

• Age now has a public Go package!
• A combined security and compliance incident offers lots of insight into the complex CA ecosystem, in case you have weird hobbies.
• Alex Gaynor did some science on the harms of memory unsafety.
• Ryan Sleevi wrote a monumental post about certificate chain building.

The picture

This is the little lake town where I attended the Italian math team training for 10 years in a row (although these days I mostly play board games) until COVID-19 broke my streak. 😢