GNU: A Heuristic for Bad Cryptography

If you see the letters GNU in a systems design, and that system intersects with cryptography, I can almost guarantee that it will be badly designed to an alarming degree.

This is as true of GnuPG (and PGP in general) as it is of designs like the proposed GNU Name System (IETF draft) and cryptographic libraries like GnuTLS and libgcrypt. In fact, I cannot recall single GNU-branded cryptography project that isn’t a roaring dumpster fire.

I will elaborate.

Problems with the GNU Name System’s Cryptography

Asymmetric Cryptography

The GNS (GNU Name System) uses an unconventional construction for zones:

A zone in GNS is defined by a public/private ECDSA key pair (d,zk), where d is the private key and zk the corresponding public key. GNS employs the curve parameters of the twisted edwards representation of Curve25519 [RFC7748] (a.k.a. edwards25519) with the ECDSA scheme ([RFC6979]).

GNU Name System IETF Draft, section 2

This is beyond weird: Going out of your way to use the edwards25519 curve from RFC 7748, but not use the Ed25519 signature algorithm, but still choosing to use deterministic ECDSA (RFC 6979).

(If you’re lost, I wrote about digital signature algorithms in a previous blog post.)

The authors acknowledge the unconventional nature of their design choice in section 9.1 of the RFC draft:

GNS uses ECDSA over Curve25519. This is an unconventional choice, as ECDSA is usually used with other curves. However, traditional ECDSA curves are problematic for a range of reasons described in the Curve25519 and EdDSA papers. Using EdDSA directly is also not possible, as a hash function is used on the private key which destroys the linearity that the GNU Name System depends upon. We are not aware of anyone suggesting that using Curve25519 instead of another common curve of similar size would lower the security of ECDSA. GNS uses 256-bit curves because that way the encoded (public) keys fit into a single DNS label, which is good for usability.

GNU Name System IETF Draft, section 9.1

The bold statement (my emphasis) is nonsense: In any design that uses digital signature algorithms, your system should map a private key (some opaque byte string) to a public key (some other opaque byte string) and signatures should also be opaque byte strings. The inclusion of a hash function under the hood of the signature algorithm is a moot point, especially since RFC 6979 also uses HMAC-SHA2 to generate deterministic nonces, thereby rendering their choice of RFC 6979 a contradiction of their stated goal. Edit: see below.

Using Ed25519 with a 32-byte private key (instead of a 64-byte private key) is also trivial. To wit: Libsodium offers crypto_sign_seed_keypair() for this purpose.

But even worse: ECDSA is less secure and slower than EdDSA, even when you use the same curves, due to how the algorithms are implemented. The authors of the RFC do not defend this design choice beyond this hash function non sequitur.

(Update) “But They Need Hierarchical Keys”

After I initially posted this, Redditor Steve132 informed me that I overlooked the reason they made this design decision.

Take a look at Section 6.1 https://tools.ietf.org/id/draft-schanzen-gns-01.html#name-recursion

From here, the following steps are recursively executed, in order: Extract the right-most label from the name to look up. Calculate q using the label and zk as defined in Section 4.1.

So then if you go to section 4.1, they do h=H(<address string>), (r,R) is some root keypair, then they do C (a child public key), C=hR, then q=H(C).

the idea behind the calculation of q is to use the root public key to derive a child public key from ONLY the root public key, exploiting the linearity property that in elliptic curves, if bG=B, then (b+s)G=(sG+B)

This allows a third party to derive child public keys without any knowledge of the private keys for the root. This technique is also used in bitcoin’s bip32 (https://en.bitcoin.it/wiki/BIP_0032) for ‘unhardened’ derivation scheme.

Part of Steve132’s correction

I fully admit, I didn’t absorb this detail in my first pass of the RFC draft. It wasn’t clearly spelled out in Section 9 (which aims to justify their cryptography decisions), and I didn’t read the other sections as carefully. This was my mistake.

However, even with this explanation in mind, my original point that this design choice is both unconventional and unnecessary still stands, because BIP32-Ed25519 already exists (albeit, it still needs a carefully designed implementation to be secure against active attackers).

Therefore, the GNU Name System developers didn’t need to roll their own design, they could have used one that’s already seen real-world deployment instead. Why take on unnecessary risk?

Furthermore, trying to push through an implementation of ECDSA over edwards25519 isn’t just unnecessary and weird, it’s also probably dangerous, as Thai Duong noted:

While I don't agree that ECDSA is worse than Ed25519 – both have pros and cons — it takes courage to implement ECDSA over Edward25519. Do you know if they published any code? This unfortunate marriage may introduce fun and unique bugs

— Thái "thaidn" Dương (@XorNinja) July 9, 2020

Of course, all cryptography development can be said to be dangerous, but there are other problems fundamental to the GNU Name System design that makes any departure from a well-tread path very suspect.

Symmetric Cryptography

The GNU Name System project doesn’t stop there. It further throws IND-CCA2 security out the window and specifies encrypting with AES and TwoFish in a cipher cascade, using Cipher Feedback (CFB) mode.

The authors do not even attempt to defend this decision. Typically this happens when the authors do not understand the risks involved. I sincerely doubt they’ve heard the words “adaptive chosen-ciphertext attack” in the course of their self-study.

(Because, y’know, attackers will surely never be able to replay UDP traffic if a runtime exception occurs because of corrupted data.)

“Why Is This Bad?”

Cipher cascades are usually the result of “we want to defend against a backdoored or broken cipher”. Bear in mind, the cipher itself is rarely the first part of a cryptosystem to be broken.

On that note, TwoFish isn’t the worst choice of a cascade partner for AES, but I’d prefer a design that employed a different paradigm (since AES is a SPN permutation block cipher, an ARX-based stream cipher like Salsa20 or ChaCha seems reasonable).

AES is a boring choice, because it’s the industry standard. I’m not particularly fond of AES (due to it not being fast and constant-time in pure software implementations), but if you use it in an authenticated mode (AES-GCM, AES-CCM, AES-EAX, AES-OCB3, … I dunno, Poly1305-AES? Just use an AEAD mode!), it’s fine.

Cipher Feedback (CFB) mode is not an authenticated mode.

If you’re publishing a cryptography design in 2020 that fails the Cryptographic Doom Principle, you need to go back to the drawing board.

“But They Use Digital Signatures”

Cough.

Other GNU Projects

If you want to learn about why GnuPG (and the PGP ecosystem in general) is terrible, I recommend Latacora’s takedown.

GnuTLS is an SSL/TLS library created by the same people who created (and then abandoned) libmcrypt, which was the scourge of bad cryptography in the PHP ecosystem for many years (until it was finally excised in PHP 7.2). Consequently, the project’s CVE history should be no surprise.

Quick story: Many years ago, a few timing attacks were discovered in libgcrypt by regular chatters in Freenode’s ##crypto channel. This led a lot of us to look at libgcrypt for more bugs.

The general consensus of the ensuing IRC discussion was, roughly, “We probably shouldn’t try to fix them all, because a) that’s way too much effort because there’s too much badness and b) this library will be a ripe target for upcoming cryptanalysis researchers to get their first papers published for many years”. And, indeed, the attack papers that have come out over the years that affect libgcrypt haven’t disappointed.

To be clear, at the time this happened, I was garbage at writing C (and somehow even less confident than capable) and barely making ends meet, so “drop everything and volunteer to fix all the libgcrypt badness” wasn’t a tenable option for me. And since the world is largely moving away from GnuPG and libgcrypt, it honestly isn’t worth the effort trying to fix all the bad when an easier fix is “use something good instead”.

Takeaway

If you see the letters GNU anywhere in a project that intersects with cryptography–except for its public license–it’s almost certainly an error-prone cryptographic design.

Or, as my friend Kye calls it:

https://twitter.com/KyeFox/status/1280928890375024642

What To Use Instead?

To replace GPG, you want age and minisign.

To replace GnuTLS or libgcrypt, depending on what you’re using it for, you want one of the following: s2n, OpenSSL/LibreSSL, or Libsodium.

For embedded systems, BearSSL is a good options today and libhydrogen v2 will be an attractive choice when it’s released.

---

Header image, like the GnuNet logo found here, is available under the Creative Commons Attribution-Share Alike 4.0 International license.