Crypto Lions and Tigers and Bears … Oh My! (2024)

I recently had occasion to plumb the depths of the OpenSSH, OpenSSL, and GPG libraries in a fair amount of detail (that “stepping through the source code in gdb as it runs” kind of detail), as I endeavored to create an alternative version of the sftp utility that provides end-to-end encryption of files and secure sharing of those files with other users. Along the way, my colleague and I decided to make our key data and encrypted files compatible with GPG, as I describe here:

That necessitated a pretty deep dive into the GnuPG code, which was rough. Sure, there’s a spec out there — RFC 4880, OpenPGP Message Format. That should make it pretty simple, right? Well, not so much. The spec has some ambiguity, which is less than ideal for a spec. Try to figure out what the signature for a data packet should look like and contrast that to what a signature for a public key should look like, for example. On top of that, GPG introduces some idiosyncracies of its own. To top it off, we need a “modern” version of GPG that supports the elliptic curve algorithms. These modern versions have started using constructs that aren’t part of the OpenPGP spec for things like storing the private key files. There wasn’t any choice but to dig through the source. And, since I wanted to avoid linking any of the gpg/libgcrypt code into OpenSSH, I had to spend some time figuring out how to do the same things using the OpenSSL crypto libraries.

So there I was, libgcrypt S-expressions on one side, OpenSSL bignums on the other, me stuck in the middle. It was the coding equivalent of refereeing a face-off between a rabid saber toothed tiger hopped up on energy drinks and a hung over grizzly bear with anger management issues. OK, that’s maybe just a little hyperbolic. But it felt very daunting some days.

It was the coding equivalent of refereeing a face-off between a rabid saber toothed tiger hopped up on energy drinks and a hung over grizzly bear with anger management issues.

Here are a couple of examples from a long sequence of head-scratching puzzles. First up, one of those little GPG idiosyncracies. The OpenPGP message format starts with a tag byte, followed by the message length (which can by one or more bytes, depending on the value it stores), followed by the message body. One of the messages stored in a key file is a User Identification message, or UID. The UID is just text, usually something like “Gumby <rubber.man@nowhere.com>”, that is associated with a key as an identifier. Unless you have a really long name or email address, this is likely to fit into 256 bytes. This means that the message header would be two bytes long. And in fact, that’s the way GPG writes it when generating a new key. But … when you are hashing the public key and corresponding UID messages to generate a signature, GPG does this:

static void
hash_uid (gcry_md_hd_t md, int sigversion, const PKT_user_id *uid)
{
 byte buf[5];
 (void)sigversion;
 buf[0] = 0xb4; /* Indicates a userid packet. */
 buf[1] = uid->len >> 24; /* Always use 4 length bytes. */
 buf[2] = uid->len >> 16;
 buf[3] = uid->len >> 8;
 buf[4] = uid->len;
 gcry_md_write( md, buf, 5 );
 gcry_md_write (md, uid->name, uid->len );
}

For starters, I don’t even know what “(void)sigversion;” does. I’ve never seen that before in C code. Then, I don’t know why you would force the length of the message to be four bytes. For that matter, I am not sure why you would hash the fields that make up the message in one place and serialize the message in another. GPG does that frequently. I much prefer our implementation inside IronSSH:

 gpg_packet * pubkey_pkt = serialize_pubkey(...);
 gpg_packet * uid_pkt = serialize_uid(...);
 hash_packet(md, pubkey_pkt);
 hash_packet(md, uid_pkt);

As a side benefit, if someone is validating the hash, she doesn’t need to deserialize the data and recompute the hash one field at a time. That’s a nice thing to do.

In gpg-compatible data, large numbers are stored as “multi-precision integers” (MPIs) — the data consists of a two-byte length in bits, followed by enough bytes to hold that many bits. Well, unless the most significant bit is a 1. Then, since in crypto pretty much all the values are unsigned, and gcrypt MPIs support signed numbers as well, it is necessary to add a byte of zeroes in front. OK, no problem. Except when you are generating the “keygrip” for an elliptic curve public key. (In GPG, a keygrip is a string representing a public key. It’s similar to, but not the same as, the key fingerprint. Why have two different shorthand names for a public key? That’s something you will need to ask the GPG developers.) Then, for some reason, you do not add the zero byte, even if the high bit is set. What the …?

Similarly, gpg uses a prefix byte on elliptic curve points (like a curve25519 public key) to indicate that the value is just the point’s X coordinate, not both the X and Y coordinates. This is true most places you run across one of these point values. Unless you are still struggling to compute the keygrip for an elliptic curve public key, after you figured out that zero byte padding thing. Then, you don’t add the prefix. ARGH! Figuring out these two things was a fun little exercise with gdb, because the data that was generated was run through a hash, so it wasn’t obvious looking at the output why things didn’t match up between my calculations and gpg’s.

Throwing libsodium into the mix complicated things even further. I didn’t dig through the libsodium source too much, but I did look at some of it. It’s newer and has less historical entanglements, but there are still some oddities. For instance, elliptic curve key pairs consist of a public key that is a point on the curve and a secret key that is a multiplier for that point. In curve25519, the variant of ECC that libsodium implements, the private key is “clamped” — its highest bit and lowest three bits are set to zero, and the next to highest bit is set to one. I had read about this, but after looking for it in the key generation code and not finding it, I had to surrender, join a mailing list, and plead for a hint. It was revealed that the private key doesn’t get clamped when it is generated — instead, the clamping operation is wired into the function that multiplies a point by a scalar. Huh?

Figuring out the interop between libsodium and gpg / libgcrypt was interesting. For instance, after generating a curve25519 key pair, I store it in a GPG-compatible key file. In the process, I discovered (the hard way) that libsodium generates the private key in a little endian format, so the first byte in the array holds the least significant bits of the value. libgcrypt expects the bytes in the opposite order. OK — after some more code scrutiny to figure this out, reverse the key before writing the file. And of course, you would reverse the public key (the X coordinate of a point on the curve), right? Nope! To this day, I don’t understand why libsodium manipulates the two values differently. I am sure it has something to do with efficiency when computing the product on a little-endian processor or something, but that’s just a guess.

Lest you think that OpenSSL is just the plucky sidekick in this horror story, contemplate for a second this function:

int RSA_memory_lock(RSA *r)
{
 int i, j, k, off;
 char *p;
 BIGNUM *bn, **t[6], *b;
 BN_ULONG *ul; if (r->d == NULL)
 return (1);
 t[0] = &r->d;
 t[1] = &r->p;
 t[2] = &r->q;
 t[3] = &r->dmp1;
 t[4] = &r->dmq1;
 t[5] = &r->iqmp;
 k = sizeof(BIGNUM) * 6;
 off = k / sizeof(BN_ULONG) + 1;
 j = 1;
 for (i = 0; i < 6; i++)
 j += (*t[i])->top;
 if ((p = OPENSSL_malloc_locked((off + j) * sizeof(BN_ULONG))) == NULL) {
 RSAerr(RSA_F_RSA_MEMORY_LOCK, ERR_R_MALLOC_FAILURE);
 return (0);
 }
 bn = (BIGNUM *)p;
 ul = (BN_ULONG *)&(p[off]);
 for (i = 0; i < 6; i++) {
 b = *(t[i]);
 *(t[i]) = &(bn[i]);
 memcpy((char *)&(bn[i]), (char *)b, sizeof(BIGNUM));
 bn[i].flags = BN_FLG_STATIC_DATA;
 bn[i].d = ul;
 memcpy((char *)ul, b->d, sizeof(BN_ULONG) * b->top);
 ul += b->top;
 BN_clear_free(b);
 } /* I should fix this so it can still be done */
 r->flags &= ~(RSA_FLAG_CACHE_PRIVATE | RSA_FLAG_CACHE_PUBLIC); r->bignum_data = p;
 return (1);
}

Yes, the only comment in the whole thing is some cryptic TODO note that may no longer have meaning to even the original author!

I am an unapologetic C jockey, so I like my pointer arithmetic as well as the next nerd. But seriously?!? Even armed with the following knowledge:

• those fields d, p, q, dmp1, dmq1, and iqmp are the parameters for an RSA private key
• each of them is a pointer to a BIGNUM
• the d field in a BIGNUM is a pointer to an array of BN_ULONGs that hold the data
• the top field in a BIGNUM holds the number of unsigned longs that have been used in d

it’s a bit of a stretch to figure out what’s happening here. Seems like there would be a more understandable way to copy the contents of a set of parameters into some locked memory. How confident would you be that this code correctly “locked” the memory storing that RSA key? Maybe you are a proponent of test-driven development, and you prefer to let your tests do the explaining. Lots of luck finding a test for this code anywhere.

These are just a few things I ran across while combing through the GPG and OpenSSL code, and trying to match them up with LibSodium. I didn’t need to dig too deeply into the bowels of the crypto code. Given the things I did find, I think it would be appropriate to post

Here there be dragons.

across the source and try to avoid as much as possible! If you find that you can’t avoid the code, here are some observations:

GPG/libgcrypt: Less comment-free than the others. A lot of code is supporting old algorithms and formats. The message formats are from a time when people worried about every bit of every byte (which might be great for 14kbps modems, but is not great for people trying to decipher the data). Some of the data structures are annoyingly obtuse (for example, there are at least three different representations for their ubiquitous S-expressions). Code organization could be quite a bit better. Grade: D+.

OpenSSL: Comments are rare and exotic. Code is organized in a fairly understandable way. There is plenty of code supporting old algorithms, and there are cryptic acronyms galore. Grade: C-.

OpenSSH: Comments are few and far between. Most of the crypto code is deferred to OpenSSL; there is a small core of code that will allow you to build a crippled version without OpenSSL, and that code is very cryptic. The project is saddled with a little backward compatibility with the SSHv1 protocol. Grade: C+.

LibSodium: Pretty simple API. There are a lot of layers to the implementation onion, though. Code is fairly well organized and benefits from being pretty new. Grade: B.

There is a lot of room for improvement in all of the older projects, particularly if they could be freed of the requirement to support every version they released since the dawn of time.