libcert: Implementing S/MIME PKI in Lua (1)

So, this is my first status update post to dev.to. This one's gonna be a bit longer than I'm aiming for for these types of posts, since I have to explain my entire project so far for any of my current progress to be understandable. But I've got plenty to talk about, so let's jump in.

Abstract

This section's a bit of an overview of my goal for this project. As part of my Phoenix operating system, I want to have some sort of code signing for applications, a lot like how macOS has code signing. Now I don't necessarily see it as being as strict - I'm not implementing a web service that checks validity, or enforcing code signing from my root on every single executable - but I'd like to at least toy around with the idea of a secure system, just to see whether/how it works.

One of my underlying principles in Phoenix's design is to reuse common protocols and formats as much as possible. That's why I'm using POSIX standards for the command line utilities, and dpkg/.deb for packaging. For cryptographic routines, I wanted to use a public key infrastructure design that was already commonplace. I could have used GPG/PGP, which is pretty common in the Linux world, but it's not as flexible - it lacks certificates and signing paths, which is pretty important for having distributed code signing in the way I imagined. (I also don't think it supports elliptic curve cryptography, which is the only type of encryption supported in CC at the moment - I really don't want to have to toil over making my own RSA implementation.) I liked the idea of X.509 certificates as used on the internet, and OpenSSL is commonly used to handle that, so I decided to pick that group of formats (which I soon learned is officially called S/MIME).

Initial research

I already knew some basics about X.509 certificates - they store a public key along with some metadata in an ASN.1 DER container, which is then signed by a certificate authority as assurance that the certificate is trusted. The certificate authority is then signed by another certificate, up to a root of trust that is stored in the operating system or security library like OpenSSL.

I had some experience with ASN.1 encoding and decoding before this - I wrote a script that extracts encryption keys from iOS update packages a long time ago, which involved parsing a DER-encoded keybag - but I hadn't actually worked with ASN.1 definitions before. At first, I started writing my own decoder for DER structures, referencing the Wikipedia article on DER, supplemented by the very thick X.680 and X.690 standards. I made it through a decent number of the tags, but eventually I got tired of working on it, so I searched to see if someone else had already done the work of making one. Fortunately, I found one. Unfortunately, it was very barebones, and lacked most of the tags I needed. To remedy this, I ported some of my code I'd written to this new one, filling in tags like object identifiers, which are extremely important in S/MIME. I also added stuff that really should have been there, like sets, optional values, and implicit tags.

One thing that was really nice about this new library is that it's structured - instead of just blasting the decoded data into a list of unnamed entries, it follows a structure that you give it, and not only names each entry as it reads them, but also can do type checking to make sure the structure it's reading in is correctly written. This ended up becoming extremely important, because I would have had quite a tough time with optional values and just general usage of these types if I had stuck with my own plan. It also meant that I could just slap a type definition on the resulting object without having to fiddle with figuring out what each entry in an array means manually.

Another benefit of this format came when I started reading the X.509 standard. The 236-page document would be ridiculous for me to read all of for this one little project, but one little section, Annex A, has a breakdown of every part of the X.509 certificate format, written in ASN.1 structure format. These were also included in a very useful blog post here, which let me know what each field meant. All I had to do was rewrite those definitions into Lua code, and the ASN.1 library would convert those definitions into an encoder and decoder for that type. I then spent many hours carefully transcribing those definitions into Lua, which, because of how the library was built, was surprisingly straightforward and elegant.

(An example of a definition ported to Lua:)

local TBSCertificate = asn1.sequence {
    {"version", asn1.default(asn1.explicit(0, asn1.integer), 1)},
    {"serialNumber", asn1.integer},
    {"signature", AlgorithmIdentifier},
    {"issuer", Name},
    {"validity", Validity},
    {"subject", Name},
    {"subjectPublicKeyInfo", SubjectPublicKeyInfo},
    {"issuerUniqueID", asn1.optional(asn1.implicit(1, asn1.bit_string))},
    {"subjectUniqueID", asn1.optional(asn1.implicit(2, asn1.bit_string))},
    {"extensions", asn1.optional(asn1.explicit(3, asn1.sequence_of(Extension)))}
}

However, one roadblock I ran into was figuring out what those darn object identifiers were. The X.509 standard makes no mention of any IDs for any purpose, including signature algorithms, public key algorithms, extensions, attributes, etc. (Rightfully so, it defines the certificate format, not what you put in them.) This meant I now had to run around finding these obscure identifiers for each purpose. I hit gold when I found some documentation for a Python crypto library, which had most of the IDs I needed. But it didn't have all of them - most notably, the OIDs for Ed25519 signature keys, which is the only signature algorithm I had access to in Lua. So, I went hunting for these OIDs online, and after an accidental detour through the unrelated RFC 5480 (which describes general-purpose EC curves, and not Ed25519), I found what I needed in RFC 8410. Once I put those all together, and after putting together a very quick and dirty PEM decoder (which is just Base64), I was able to load and print X.509 certificates, with all the keys named and everything.

I'd like to shout out asn1js, a super useful tool for reading out ASN.1 structures in the browser. I was able to use it to figure out why certain structures were getting encoded or decoded wrong, and its breakdown of structures into both a hierarchy and the hex view were very handy. I also appreciated its ability to annotate the field names using built-in structure definitions.

PKCS#8: Private Keys (and initial signatures)

Next was being able to use the private keys that go along with the certificates. You can't sign anything without a private key. From the Wikipedia page on X.509, I learned that the appropriate standard for private keys is PKCS#8 (or PKCS#1 for RSA, but I'm not using RSA, so it's irrelevant). Clicking through references brought me to the standard, RFC 5208. Luckily, it was just two structures (PKCS#8 is really simple), but I ran into a little roadblock: I had no idea how to encrypt the key. I'd eventually get back to this later, but for the time being I just left the encrypted key part as a stub.

Once I had loading certificates and keys working, I decided to take a crack at signature generation. I wrote up a quick script to read in a certificate and key file (generated by OpenSSL), and then write a signature blob (encoded in ASN.1/DER) with the Ed25519 signature over some file. Then it would read in the signed file, split off the signature blob, and then verify the signature using the certificate in the blob. (No chain validation yet.) After a good bit of debugging, I got it working:

Anyway, this is getting way longer than I was thinking at first - I've been writing this for over an hour. I'm gonna continue this more tomorrow, with my journey through PKCS#7, plus chain validation of certificates, and maybe PKCS#10 if I have time.