libcert: Implementing S/MIME PKI in Lua (2)
Tags: cryptography, lua, certificates
Published: 2024-04-17 07:22:42

This is a continuation of my [post from yesterday](https://dev.to/jackmacwindows/libcert-implementing-smime-pki-in-lua-1-4jn8) about [libcert](https://github.com/Phoenix-ComputerCraft/libcert). Read it if you haven't - this jumps right in after the end of that post.

---------

## PKCS#7/CMS: Container for signatures (and other data types)
After getting the initial signature generation and validation working, I wanted to expand it to use a standard container format, instead of making my own blob thing. A bit of searching brought me the PKCS#7 standard; however, I soon found out that the original PKCS#7 was obsoleted by the Cryptographic Message Standard (CMS), which extends PKCS#7 for... something - I haven't dug deep enough to see exactly what's different. CMS is described in [RFC 5652](https://datatracker.ietf.org/doc/html/rfc5652), which describes the format, and has the ASN.1 reference I needed, plus all the object IDs that are relevant for implementing the format.

The PKCS#7/CMS container doesn't just store signatures, however - it's also meant for storing hashes (or digests), encrypted data, *enveloped* data (which is encrypted data, plus the key encrypted one or more times, so multiple receivers can decrypt the same data using their own keys), authenticated data (e.g. HMAC, Poly1305), and authenticated enveloped data (which I would implement later on). To allow for future expansion, I decided to implement all of the data types, which meant copying the seven-page reference into Lua. And while I was working on copying the structures, I realized that I wanted to add type annotations as well - which meant copying *all* of the types *again*, to create virtual class definitions next to each structure. The library soon blew up to 700+ lines, but I eventually got it all written out.

Once I had the definitions written, and after some fiddling with the ASN.1 library, I had functions that could load and save PKCS#7 containers. I replaced the old signature object in the test script with a PKCS#7 `SignedInfo` structure, and tried signing and verifying, and it appeared to work. However, I wanted to try verifying my signature with OpenSSL, to make sure my file was in the right format. I ran `openssl cms -verify` on the file I was testing with, plus the signature extracted to a new file and the certificate I used in Lua; but I got an obscure error instead (not surprising coming from OpenSSL).

Some searching on the matter brought me to a [pull request which implements Ed25519 signatures for `openssl cms`](https://github.com/openssl/openssl/pull/22391) - apparently the signature format I need to use isn't quite supported yet in the main release. At least there was a fork with support, so I cloned the fork and built it. Once it was built, and after discovering that it would only load the new libraries with `LD_LIBRARY_PATH`, I got a different error - it was reporting that it had an unsupported algorithm, despite having the Ed25519 fork.

My first diagnostic was to generate a signature with OpenSSL itself, and then see what the differences were. Comparing the files in [asn1js](https://lapo.it/asn1js/) showed a different signature scheme - whereas I was generating the signature directly from the file contents with no signed attributes, OpenSSL stored a hash of the message as a signed attribute, and then signed the signed attributes object. I didn't want to have to do this method because it seemed like more work, but after perusing the OpenSSL source a bit, I found that it has two different code paths for these types of signature generation, and the Ed25519 PR only implemented the one with the signed attributes (for technical reasons related to OpenSSL internals). I then changed up my code to use signed attributes, which made OpenSSL accept the file, but it still failed verification. Not only that, but my test signature from OpenSSL was *also* failing. This had me really confused, so I spent some time debugging OpenSSL itself to figure out exactly where it was failing.

Through a lot of debugging, I eventually found that the encoded attributes OpenSSL was verifying were different from the one I signed. I then read in the X.690 standard that in DER encoding, the ASN.1 `SET OF` type, which is used to store the list of attributes, has an explicit encoding order - it sorts each entry by byte ordering for the encoding of each entry. Because I didn't do this sorting, but OpenSSL did, the DER encoding that I was signing didn't match the encoding that OpenSSL was verifying. I implemented some sorting in the ASN.1 library, and finally the file verified. (I also managed to fix verifying the test file after realizing that I was signing in text mode, but verifying in binary mode.)

![CMS Verification successful](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/xd1ywr5zelldb1fuunc0.png)

## Quick-and-dirty certificate trust chain
Now that I had a standardized signature format working, the first thing I needed to do to make the signatures actually secure was to implement a chain of trust. Just checking the signature with the provided certificate isn't enough - an adversary could easily swap out the signature and certificate with their own certificate. The signature of the certificate itself needs to be verified with its issuer, up until a trusted root is found.

My original plan was to have a daemon process that handled the certificate database, including the list of root certificates. A program would hand over the signature blob through IPC, and the daemon would check the signature using its root certificate list as the root of trust. However, it's really easy to make a program that spoofs system calls (including IPC) in Phoenix. After discussing it with others, I came to the conclusion that I should just leave it in a library, as OpenSSL does.

After some reorganization of my library, I started working on the chain verifier. It turned out to be a lot simpler than I expected. The verification process is a simple recursive algorithm that does the following steps:

1. Look for the issuing certificate in the list of all known certificates, which includes root certificates, plus other certificates from a container that may be needed to verify (including intermediate CA certs).
2. If the issuer couldn't be found, fail.
3. Encode the inner `toBeSigned` certificate object to DER, and check its signature using the public key of the issuer. If the signature is invalid, fail.
4. If the issuer certificate is in the list of root certificates, verification succeeded.
5. Otherwise, if the issuer is the same as the current certificate (i.e. the cert is self-signed), fail to avoid an infinite loop. (I later replaced this with checking a list of visited certificates, to avoid looping in cross-signature scenarios.)
6. Repeat from step 1 using the issuer certificate.

I then generated a couple more certificates and keys to test certification paths, and placed the original self-signed root into `/etc/certs`, which stores the root certificates. I also adjusted my PKCS#7 signature function to allow adding extra certificates, which is needed to carry required intermediate CA certificates with the leaf certificate. Surprisingly, my code worked first-try, with it successfully validating signatures signed by the root, an intermediate CA (issued by the root), and a leaf certificate (issued by the CA).

## Implementing symmetric encryption
My next task was to tackle implementing encrypted PKCS#8 private keys. I originally wasn't planning on implementing encryption in the library, but after the reorganization, I decided to add in not only PKCS#8 decryption, but also PKCS#7 authenticated enveloped data.

My original intention was to only use ChaCha20+Poly1305 for encryption, which is fast, and is also the most prominent symmetric cipher available in Lua. However, I soon found out that there's no standard provisions for using it in anything except PKCS#7 as an authenticated encryption cipher - neither PKCS#8 key encryption, nor the key encryption used in PKCS#7 enveloped data, support it; they only accept AES, or the incredibly discouraged DES. Luckily, a ComputerCraft coder had recently written an AES library in Lua, which I was able to slightly modify to work in normal Lua. To be frank, I'm not sure how secure this library is (it did use a lot of global variables...), but it's the best I had, and I didn't want to spend another two days writing an AES library myself.

Unfortunately, PKCS#7 and #8 don't describe how the algorithms should actually be implemented. I first found [RFC 3565](https://www.rfc-editor.org/rfc/rfc3565), which describes how AES can be used as an encryption algorithm, including its OIDs. I then checked a password-encrypted PKCS#8 key generated with OpenSSL in an ASN.1 viewer, which said that it used an algorithm called PBES2. A search brought me to PKCS#5, standardized in [RFC 8018](https://www.rfc-editor.org/rfc/rfc8018), which describes the Password-Based Encryption Standard 2 (PBES2), plus the Password-Based Key Derivation Function 2 (PBKDF2), which I was already familiar with. The idea is that the encryption key is generated by running a pseudorandom function over the input password and a random salt thousands of times, and then encrypting with some cipher using that key. The PRF is usually HMAC from a SHA family hash function, and the cipher is usually AES in CBC mode. (Both are explicitly documented in PKCS#5.)

I then went to work implementing PBES2/PBKDF2. PBKDF2 was easy to implement - it's pretty common in ComputerCraft, and I was able to extract the implementation from a popular SHA-256 library. I needed to do a bit of finagling to get the PBKDF2 function, the SHA library I was using, and the AES library to all play nice together - some functions used lists of bytes, while other ones used strings. I sketched up a quick PKCS#8 key generation function, but didn't end up testing it out until later.

## PKCS#7 2: Encrypted Boogaloo
Since I was already working on encryption, I went to work on implementing PKCS#7 auth-enveloped data after PKCS#8. [RFC 5083](https://www.rfc-editor.org/rfc/rfc5083.html) describes the data format, since it's an extension of the original CMS format, but it's basically a mix of the `AuthenticatedData` and `EnvelopedData` formats, so I mostly read the CMS standard. Enveloped data uses a unique scheme where, instead of relying on the receiver to have the encryption key for the data, it generates a unique key for the data, and then stores that key encrypted for the receiver. This allows the same encrypted data to be sent to multiple receivers, who all have different keys to decrypt the data and its key. This did mean that I had to use AES again, since again, ChaCha20 isn't supported for encrypting keys.

PKCS#7 defines four key wrapping methods:
- key transit, which uses normal public-private key asymmetric encryption;
- key agreement, which uses a key exchange algorithm between two key-certificate pairs to create a shared symmetric key;
- key-encryption key, which uses a pre-shared key to symmetrically encrypt the key; and
- password-based key, which uses a password to symmetrically encrypt the key.

I wanted to implement all of these, in case I or someone else eventually needs them. However, because I am using elliptic-curve asymmetric ciphers, which don't support encryption directly, I couldn't implement key transit; but I still implemented the other three. To support all of these different methods in the same encryption function, I had a function for each method, which returned an object to encrypt and decrypt keys into an abstract `RecipientInfo` ASN.1 object. The main encryption functions can transparently call the object to convert each `RecipientInfo` in the envelope to and from the key.

The first one I implemented was key agreement. This uses the X25519 key exchange algorithm, which takes the private key of one side and the public key of the other side, and returns a key which is guaranteed to be equivalent on each side. The constructor for the key encryptor takes a private key for the current side, plus the certificate for both sides. When encrypting a key for sending, it exchanges the private key with the receiver's certificate's public key, encrypts the key with the exchange key, and returns a new `RecipientInfo` object that stores references to the sender and receiver's certificates with the encrypted key. Decryption checks that the sender and receiver in the `RecipientInfo` match the given certificates, then exchanges the private key with the sender's certificate's public key to create the same exchange key, and finally decrypts the key with that exchange key.

Next was the key-exchange key method, which is fairly simple: it just runs AES on the encryption key using the given key. It also adds in an identifier for the key, which allows the receiver to identify the proper KEK info to check. The last one was the password method, which functions a lot like PKCS#8 PBES2. The encryptor generates a salt, and then runs PBKDF2 on the password and salt to generate a key, which is then used to encrypt the encryption key. The decryptor runs PBKDF2 on the password with the salt given in the `RecipientInfo` object, and then decrypts the encryption key using the PBKDF2 key.

Then I wrote the main encryption routines. The encryption function takes data with a list of key encryptors, and returns a PKCS#7 authenticated enveloped data structure. It works by generating a random key and nonce value, and then encrypts the data using ChaCha20. It also generates an authentication tag using Poly1305, which is important to verify the origin of the data. Afterward, it uses each encryptor object to generate a `RecipientInfo` for each recipient/key type, which are packed into the PKCS#7 structure, and returned to the user.

The decryptor takes the PKCS#7 structure and the same key encryptor list, and returns the decrypted data. This function first does some sanity checks on the structure, and then runs each `RecipientInfo` in the structure through each given encryptor to try to decrypt the encrypted key. Once a valid key is decrypted, the data is decrypted using the nonce stored in the structure, the authentication tag is checked to verify authenticity, and the data is returned.

---------

Once again, I've been writing this for way too long, it's super late and I don't feel like writing more today. I'll pick it up again later with my struggles while testing, as well as PKCS#10 CSRs.