Sparkle: Move From DSA to More Secure Cryptographic Signatures

[paragonie-scott]

See: https://gist.github.com/atoponce/07d8d4c833873be2f68c34f9afc5a78a#asymmetric-signatures

Avoid:

1. RSA-PKCS1v15
2. RSASSA-PSS with MGF1+SHA256
3. Really, anything RSA
4. Vanilla ECDSA
5. Vanilla DSA

[kornelski]

There are newer and better algorithms, but is there a known weakness in DSA?

The document mentions newer algorithms are more resistant to misuse, but are we misusing DSA?

[paragonie-scott]

I can't say whether or not you're misusing DSA without looking deeper, but it's worth it to move towards Ed25519 (RFC 8032) or deterministic ECDSA (RFC 6979) because there's less that can go wrong if you use those.

[kornelski]

Can you be more specific what can go wrong? What kinds of uses are at risk?

[kornelski]

I'm asking for more details about it, because there could be various levels of brokenness, which require different mitigations.

In case there is a specific, fixable bug in our implementation, then we need to fix it ASAP rather than migrate to anything else. If our cryptographic construction is unsound, then replacing one part of it may not help at all.

If something is really broken, we'd have to fix it urgently and raise alarms to get everyone to migrate ASAP. OTOH if there's nothing wrong with DSA, other than its age, then we can plan gradual migration.

I know that crypto algorithms are easy to get wrong, but hopefully Sparkle is not very exposed to these problems:

• As far as I understand the advantage of misuse-resistant algorithms is that they can't be easily weakened by choosing bad parameters (such as primes or points that don't meet all criteria). But we're not doing crypto on such a low level, so I think we avoid these problems by using only high-level interfaces of openssl and Security.framework.

• Another easy-to-get-wrong class of problems is timing attacks and side-channel leaks, but I think they're not relevant to Sparkle's usage: there's absolutely nothing secret in Sparkle.framework's signature verification. Only signing is sensitive, but that happens relatively rarely, only developer's own machine, so it's not easily observable and lacks volume to collect statistics.

[menzow]

I think this issue is related: https://github.com/sparkle-project/Sparkle/issues/1042

There was a interesting talk on this subject at DEF CON this year. You can watch it here: https://www.youtube.com/watch?v=NbHL0SYlrSQ

[vslavik]

This came up in https://github.com/vslavik/winsparkle/pull/157#issuecomment-356118206 (DSA is highly problematic to support on Windows compatibly with Sparkle, but that's obviously something you couldn't care less about). I think the gist of it is that 1024bit DSA is considered insecure, larger keys have problematic compatibility in other contexts, and so everybody is generally moving away from DSA.

In other words, it's not an urgent matter, but it would be nice to have some migration path towards something better, be it RSA or ECDSA.

[kornelski]

OK, so it does seem it may be worth moving away from DSA.

Is there a well-documented, verified signature algorithm we can adopt? I don't want to risk plugging primitives wrong way and, e.g. use ECDSA the same way PS3 did (i.e. catastrophically badly).

[paragonie-scott]

RFC 8032 is the gold standard today. RFC 6979 is the silver standard. This will change when NIST's Post-Quantum Cryptography project progresses further.

[efef]

I noticed some minor DSA issues in OpenSSL which is included with Sierra, so decided to use a newer OpenSSL version to generate the 4096 DSA key. But "generate_appcast" doesn't support this. It gives an internal error. Same error as #1155.
It doesn't feel very safe, that 'somehow' the app needs a DSA-key that is generated by an outdated OpenSSL version and doesn't support a more recent versions.

[sveeke]

Hi. And maybe to add to @efef and @paragonie-scott, I was wondering what the status of this issue is? It has been almost a year and the inherit weakness in DSA is obviously still there. I support @paragonie-scott in his suggestion to move to something less notorious/infamous like RFC 8032.

[riastradh-brave]

There are a number of problems with DSA and with Sparkle's use of it:

• Specific cryptanalysis aside, by using DSA with SHA-1, Sparkle is _generically_ limited to an 80-bit security level: the work factor needed to forge signatures is 2^80.

  The Bitcoin network today performs about 30e18 ~= 2^64 SHA-256 computations every second, or about 2^90 in a year, according to https://charts.bitcoin.com/chart/hash-rate (retrieved 2018-04-23). Breaking an 80-bit security level is well within the realm of human feasibility today -- and Sparkle users are high-value targets.

• The vulnerability of DSA with SHA-1 to _specific_ cryptanalysis yielding collisions in SHA-1 is documented elsewhere.

  DSA is not limited to SHA-1, but Sparkle's use of it appears to be.

• DSA signatures require an independent uniform random per-signature secret. If there is much nonuniformity, or if it is reused between two signatures, the private key can leak.

  Historical implementations provide this with an enormous foot-pointed gun: requiring that every time you _make a signature_, you have a good entropy source. For example, if you use a VM snapshot to make a signature, you might shoot yourself in the foot -- except you won't notice until you learn that an adversary has distributed malicious updates. (Debian users learned this the hard way with OpenSSL in 2008, and Sony learned this the hard way with the PlayStation 3 firmware update signing key in 2013.)

  There is a standard technique for mitigating this foot-pointed gun, RFC 6979, but many implementations don't employ this technique, and whether the implementation that Sparkle uses employs it requires extra work to audit -- and re-review if you ever switch to another DSA implementation.

As far as I can tell, if an adversary is able to forge signatures under an application's DSA key, it _does not help_ for the application to also use Apple code signing, according to https://sparkle-project.org/documentation/#apple-code-signing (retrieved 2018-04-23):

If you both code-sign your application and include a public DSA key for signing your update archive, Sparkle allows issuing a new update that changes either your code signing certificate or your DSA keys. Note however this is a last resort and should only be done if you lose access to one of them.

The use of DSA is a red flag and makes auditing more complicated. In contrast, Ed25519 avoids all of these problems by (a) advertising a 128-bit security level, (b) using a safer hash function (SHA-512) _and_ obviating the need for collision resistance in the first place, and (c) deterministically deriving the per-signature secret as a secret pseudorandom function of the message so that _no_ implementations are even tempted to rely on the historical foot-pointed gun of DSA. This would raise the security level for everyone, and make everyone's auditing tasks easier.

Would you please consider prioritizing the implementation of Ed25519?

[kornelski]

It looks like Apple's Security.framework has partially dropped/broken support for DSA, in a weird fashion: some keys from old versions of openssl still work, but it doesn't accept keys from current openssl/libressl, and can't generate new DSA keys itself. This destroys my "if it works, don't break it" reason for keeping DSA.

I've looked at other algorithms in Apple's Security.framework, but it is severely lacking in this area:

• As far as I can tell, Ed25519 is not supported by any public API at all.

• kSecAttrKeyTypeECDSA is deprecated, replaced by a type available only in 10.12+. There are some other EC-based functions, but all are 10.12+ only. Unfortunately, this is too new for Sparkle (we need 10.8 support, maaaybe we could get away with 10.9+, but not newer).

• SecKeyCreateRandomKey with kSecAttrKeyTypeECDSA and kSecAttrKeyTypeECSECPrimeRandom segfaults. The same code works fine with RSA key type, and gracefully fails with DSA key type, so it looks like a bug in the Security.framework.

So my conclusion is that cryptographic support built into macOS is useless for us. We'll have to bundle our own.

Is there a small, safe RFC 8032 implementation that you could recommend?

[vslavik]

Is there a small, safe RFC 8032 implementation that you could recommend?

libsodium would be my recommendation; it has good reputation and adoption -- you don't want some obscure rarely used library, but something battle-tested and developed competently and libsodium fits that bill.

[dimitribouniol]

I don’t think it would be a good idea to embed cryptographic libraries, if only because it would probably trigger the need for developers to also register their app with United States Export Compliance, which is not something that everyone is willing to do.

From a backwards compatibility point of view, could we not do the following:

• Include both a DSA and a EC signature in the feed.
• Alsways require both signatures to be present, unless the app has only ever deployed to 10.12 and newer, where DSA keys can be omitted.
• For apps built with the newer build of Sparkle, on 10.12 or newer, always check EC keys.
• Older systems could still work because the EC code is guarded behind runtime checks.
• Use Apple’s new-ish EC implementation from Security.framework.

This would ignore DSA on all new systems, but keep it around for compatibility with older systems.

[kornelski]

The DSA compatibility problem is with developer machines, not user machines. Currently no new app can adopt Sparkle, because fresh DSA key generation/signing with new keys doesn't work since macOS High Sierra.

Security.framework, on all versions of macOS, can still verify DSA signatures fine.

So we can't even use both DSA and EC, because using DSA means a developer has to find an old copy of macOS to generate the DSA private key. I guess we can dig out an old copy of openssl that was in old macOS and ship that for key generation :)

[vslavik]

I don’t think it would be a good idea to embed cryptographic libraries, if only because it would probably trigger the need for developers to also register their app with United States Export Compliance

FWIW, use for authentication only, including verifying digital signatures, is explicitly not covered by that regulation.

[dimitribouniol]

@kornelski Understood - for some reason, I though the concern was having Sparkle run pre 10.12 on user machines :P

@vslavik That might be the case if only the signature checking code was included, but shipping a binary with code that can do everything else as well is technically the same as embedding complete cryptographic functionality in the app. I would assume Apple's libraries are already limited from being distributed or used to the capacity where they would be illegal, which cannot necessarily be said of libsodium as well (Which is silly, because the code is all available online, and does not "belong" to the US, and is not being treasonous by being shared globally, but alas...). There is also a mindset that developers may not want to include more dependancies into their shipping binary than are absolutely necessary - the more that is added to Sparkle, the less some people will be comfortable using it.

[kornelski]

How about this one?

https://github.com/orlp/ed25519

it seems tiny enough, and I could even remove a few more bits from it.

[kornelski]

Getting there: 623b7b6bda8043e28bd8c5f793c2c8f228f0f993

[kornelski]

It's on master! (1.21.0a1). Please help test it!

[pedroosorio]

@vslavik is win sparkle also supporting EC?

[paragonie-scott]

It wouldn't make much sense to migrate in one place, and then not migrate elsewhere.

[Eitot]

Just for reference: Apple CryptoKit (10.15+) supports Ed25519. It may be an alternative to the portable Ed25519 library above at some point.

At first glance I noticed that the Ed25519 signing keys generated by CryptoKit are 32 bytes long (both private and public), whereas the portable library generates private signing keys that are 64 bytes long.