Build your own: GPG

By: Andrew Halle Repo: byo-gpg Date: 2020-11-07

Part of build-your-own

Background

GPG (stands for Gnu Privacy Guard) is an implementation of PGP (which stands for Pretty Good Privacy), an open standard for encryption specified by RFC 4880. In this post, we'll build up a program in Rust that implements one part of the PGP standard, verifying cleartext signatures.

(note: I think it's hilarious that GPG is an implementation of PGP. The obvious right choice was to call it GPGP. I considered calling my tool PGPG, but ultimately decided on pgp-rs, because I'm boring.)

PGP supports a number of different cryptography suites, but the default cipher suite, and the one I'm most familiar with, is RSA cryptography. A quick review of RSA might be warranted (it certainly was for me).

RSA

RSA is a public-key cryptosystem (one in which parts of the key used for encryption are allowed to be non-secret) which relies on the impracticality of factoring very large (a normal figure is 2048 bits) composite numbers. Put another way, it is easy to find 3 large integers n, d, and e with the property that

but it's very difficult, given only m, e and n, to discover d. In this way, the tuple (e,n) forms the public key, which can be broadcast to the world, and the tuple (e,d,n) forms the private key, which is kept secret. Messages can be encrypted by computing the ciphertext C

C can then be decrypted by anyone with the corresponding private key by computing

So C forms a secret message that's only readable by the intended recipient. Similarly, the owner of the private key can compute a signature S

which can be verified by anyone with the public key by computing

In this way, the owner of the private key can create something that can be verified to be authentic.

GPG operation

GPG provides operations for generating and distributing keys, encrypting messages, and producing signatures. The particular operation we're interested in right now is producing a cleartext signature, one that includes the message for anyone to read, and an associated signature that confirms the message is from the owner of the private key.

In order to produce a cleartext signature, you must first generate a public/private key pair.

GPG will ask for some identifying information, generate a new key (RSA by default), and store it in the keyring. The key can be exported to a file (important for us to ingest it!) via

We'll get into the format of this key later.

With a key in hand, we can generate a cleartext signature via

(note: use bat! it's great)

This is the full signature of the text "hello world" using the keypair I generated for this blog post. We'll also get into the format of this signature later. You now as familiar with GPG as you need to be to go through the rest of this post. So, let's start writing some code!

Getting started

Dependencies

We start in the normal way

I'll go ahead and add all the dependencies we'll need upfront, just to get it out of the way.

we'll use

(note: phew)

CLI

Okay, with that out of the way, we can really start writing some code!

In main.rs we put our clap description of our CLI

I personally really like the macro method of specifying the CLI, but there are other methods. This defines an app (and its metadata) as well as a subcommand verify that takes two command line arguments, source which will be the cleartext signature we're verifying, and publicKey which will be the public key we use to verify it. After parsing the command-line arguments, and providing some sensible defaults, we call out to pgp_rs::verify_cleartext_message which we define in lib.rs (I'll stop including filenames from here on out, find the code in the repo!)

(note: this snippet of code uses types CleartextSignature and PublicKey which we haven't defined yet. I'm just sketching out the broad structure of this method to get the boring stuff out of the way first.)

We parse the cleartext signature and the key, and then verify the signature with the key. If the signature fails to verify with the key, we return an error so the program exits with an error code (I'll ignore the modules set up in this snippet for the rest of the write-up).

Now, we can get into the meat of this code, the parsing functions. In order to do that however, we have to take a brief detour INTO THE RFC. Take this ::<>, it's dangerous to go alone.

Implementation

The RFC containing the details of PGP is RFC 4880. The main sections of the RFC we'll need to deal with in this blog post are sections 3.2, 4, 5.2.3, 5.2.4, 5.5.1.1, 6.1, 6.2, and 7.

Cleartext signatures

The functionality of PGP that we're implementing is validating cleartext signatures (described in section 7 of the RFC). A cleartext signature is a signature that embeds the text being signed in a readable way into the signature itself. It has several parts:

We'll talk about parsing ASCII armor in the next section, but we have enough information to parse most of this already. In order to recognize a cleartext signature, we need to first look for the header, followed by a Hash: <alg> (alg in this case will be SHA256, but there are other options), an empty line, the cleartext, then finally the signature.

The cleartext will be in form called "dash-escaped", which is described in the RFC. Dash-escaped text is the same as normal text, but if the line starts with a literal -, then it is prefixed by a dash, followed by a space. We'll know when we're done with parsing the cleartext because the ASCII armor always starts with a line beginning with 5 dashes, which we will recognize as not being dash-escaped.

I'll be using nom to build all the different parsers we'll need. Nom is a parser combinator library. Parser combinators are a technique for writing parsers where simple parsers (say, for recognizing a literal word, or a string of characters which are all a) are combined to form more complex parsers. All nom parsers have the signature

where T is the raw type we're parsing from (usually &str or &[u8]) and U is the type we're parsing. The parser either succeeds or fails, and if it succeeds, it returns a tuple of (T, U) where the first entry of the tuple is the remaining input, and the second entry of the tuple is what was parsed. For example, a simple parser that parses a Color enum from a string could look like

This example defines 3 parsers, parse_red, parse_green, and parse_blue, which look for a literal string, and if it's found, return the associated Color variant. If the input does not contain the string literal, the parser fails (that's why we can ignore the result of the tag parser, we know what it was, and we can return the built value we wanted). parse_color is then built from these basic blocks using the alt combinator, which succeeds if one of the parsers passed to it in a tuple succeeds, and it succeeds with that result. The main function then parses a single color from the string "Green123", leaving the 123 string remaining.

Now to parse a cleartext signature using nom, we first define a struct to parse into

The hash field will hold the hash variant we're using (could have been an enum if we were being rigorous, or supporting more than just SHA256), the cleartext (after we remove the dash-escaping), and then the signature (which we'll get to later).

The parser for our cleartext signature will look like the following

This parser first recognizes the header, then the hash variant, then the cleartext, then the parts of the ASCII armor. It also enforces that there's no more input to consume using the all_consuming parser. Assuming all that is successful, we return the pieces we need to assemble the cleartext signature.

Drilling down into the methods we decreed must exist

alphanumeric1 is a parser included with nom that recognizes at least one alphanumeric character. preceded is a parser that takes two parsers as argument, it returns as a success the result of the second parser, if both succeed. terminated is a parser that takes two parsers as argument, and returns as success the result of the first parser, if both are successful. So, the parse_hash_armor_header function recognizes an alphanumeric1 string preceded by Hash: and returns it, ignoring any trailing newlines.

parse_possibly_dash_escaped_chunk uses a helper I wrote fold_into_string which takes a parser that parses a single line of text and runs it repeatedly (until it fails), collecting the results into a String. We then pop() the last character off the string, because we don't need the last newline.

parse_possibly_dash_escaped_line uses the alt combinator we've already seen to either parse a line beginning with no dash, or a line beginning with a dash-space. parse_line_newline_inclusive is a helper to grab a string slice including the last newline. Because nom parsers can recognize up to the newline, but not go past it in the same breath, I needed an unsafe function to consume the newline, and then modify the resulting string slice to be 1 byte longer, which is safe because I know the next byte was a newline (or the parser would have failed).

Now, we can go back up and see the Cleartext::parse function

Not every line of this is clear yet. We haven't talked about ASCII armor or PGP packets at all yet. Nonetheless, the high-level idea is clear. This parses the parts of the cleartext signature using the function we just built, does some extra work with the ASCII armor (which we'll talk about in the next section) and then returns the Cleartext signature or an Err. Note that this function, even though it's named parse does more work than just parsing. Because of that, I chose to have it return a normal Result (actually an anyhow::Result for simplicity) rather than a nom IResult, because errors that can occur in this function aren't strictly parsing errors. Another error that could occur is the ASCII armor contained doesn't have a valid checksum. That's a nice segue into the next section, parsing and validating ASCII armor.

ASCII Armor

PGP defines a number of data structures for implementations to use. ASCII armor is a method of communicating those data structures, which are expressed as bytes, between implementations. ASCII armor makes use of base64 text and special headers to communicate those raw bytes and their meaning.

Let's start by writing a nom parser for base64 text. I'll use the fact that my PGP implementation writes out base64 chunks in lines of 64 characters (I believe all implementations would do this, but I couldn't find a quick reference for it in the RFC. I don't consider it an important detail).

We start in the same way we started previously, when we were parsing a chunk of dash-escaped text

parse_base64 is a nom parser which returns an owned String if successful. It uses the same fold_into_string helper from the last section, and the parser passed to that function is parse_base64_line which takes one line of length 64 characters which is made up entirely of base64 characters. Then, parse_base64 takes whatever remaining base64 characters that were not on a whole line. It will not take a line that begins with a = (I'll explain this later). Then, it returns the chunk of base64 that was parsed. parse_base64_line is given by

(note: there's a bug in these two functions in that something like a=a=a=a= would be allowed, even though that's not valid base64. it would be caught in the next section when we turn that base64 string into bytes, but if I were to re-write this, I would make the parser aware of the fact that once it sees any = to stop parsing, by parsing sequences of 4 characters, either of the form aaa=, aa==, or aaaa. The reason that these are the only possibilities is that 4 base64 characters represent 3 bytes, with each character representing 6 bits. If we have 1 byte of data and 2 bytes of padding, the last 2 bits from our 8-bit byte leak into the second character, so the most padding we can have is two =.)

With our base64 parsing functions in hand, we can look at the structure of the ASCII armor given in the RFC.

The armor checksum is a quick checksum over the data encoded by the ASCII armor. It is produced by the CRC-24 algorithm, a C version of which is given in the RFC. Here is a direct translation of that code into Rust.

In order to parse ASCII armor, let's start with a struct to parse into.

The kind field will store the type of header/tail we parsed, the data field will hold the bytes of the data contained by the ASCII armor, and the checksum field will hold the checksum bytes. In the last section, we decided that we should have separate AsciiArmor::from_parts and AsciiArmor::verify functions, which makes sense because an invalid checksum is not really a parsing error, so we want to return that error separately. The parsing function is given below

We start by recognizing the header (we'll only need signature and public key types for our purposes), then a base64 chunk, then a single =, then another base64 chunk. This is why we didn't allow any lines to begin with = in our parse_base64_line function, a line that begins with an equal sign marks the start of the checksum. The parse_ascii_armor_parts function is called from CleartextSignature::parse, and we pass the parts into AsciiArmor::from_parts. We then use AsciiArmor::verify to verify that the checksum is valid (see last section for the usages). Those functions are given by

There's one more function that we specified in the last section that we would need, AsciiArmor::into_pgp_packets. In order to implement that function, let's discuss the data structures that are described in the RFC, PGP packets.

PGP Packets

A PGP message consists of a sequence of data structures known as packets. Each packet contains a particular piece of information required for the particular PGP function. In our program, we'll only concern ourselves with signature packets and public key packets, but some other types of packets are "User ID Packet" (for communicating information about who a key belongs to) and "Compressed Data Packet" (for actual encrypted data).

All PGP packets begin with the same header which gives information about what type of packet is contained and how big it is. There are two types of header, new format and old format. In this post, we only implement parsing old format packets (because that's all GPG seems to produce on my system).

First, we'll make an enum for PGP packets.

I've made SignaturePacket and PublicKeyPacket hold their data in separate structs with the same name (I'll cover those structs in future sections). I've included variants for UserIdPacket and PublicSubkeyPacket because my GPG produces these packets, so I want to recognize them and ignore them.

Packets are formed from sequences of bytes. Because of this, our nom parsers for packets will have a different form than our parsers have thus far. Up to now, we've been using parsers of the form

Our packet parsers will have the form

so that we can work with the raw bytes. The top-level function we'll need is a nom parser to turn bytes into a sequence of packets (I'll use Vec<PgpPacket> and copy data to avoid ownership issues).

all_consuming(many0(/**/)) repeatedly calls parse_pgp_packet, puts each packet parsed into a Vec, and ensures that no input remains. parse_pgp_packet is given by

This is a longer function, so let's take it section by section. The first section parses the packet tag (what type of packet it is) and the length type. bits turns a byte-oriented nom parser into a bit-oriented nom parser, which is important because multiple pieces of information are contained in one byte of the header. We also define the enum PgpPacketTag for simplicity

we also implement the From<u8> for the new enum, so we can easily get a packet tag from a byte. In the next section of parse_pgp_packet, we get the length of the packet based on the length type. The length type indicates how many bytes comprise the length, and we use the byteorder crate to read those bytes as a big-endian number. We then parse length bytes, and pass those bytes to a particular subparser based on the packet tag. parse_user_id_packet and parse_public_subkey_packet are dummy functions that will just parse all the bytes, for the purposes of explicitly ignoring those packet types. We'll implement parse_signature_packet and parse_public_key_packet in the next couple of sections.

(note: I found pgpdump very useful while implementing this section. pgpdump is a tool for dumping the contents of PGP packets, like so

Here we see a dumped signature packet, which is the next thing we'll parse...)

Signature Packets

Signature packets contain a signature over some data for some key. In our case, they contain RSA signatures, but other signatures are possible. Some key pieces of data that the signature packet might contain are

Looking at the RFC, we can glean the following important pieces of information that will be important for our parser

A multiprecision integer (MPI) is a number format defined in the RFC (3.2) for communicating very large numbers. A MPI is a length followed by a big-endian number. We begin by writing a parser for MPIs.

parse_mpi is a byte-oriented parser that first takes a 2 byte length, then interprets length bytes as a big-endian BigUint (from the num crate).

(note: it is not lost on me that major parts of my program are formed by the crates nom and num. perhaps I should have called my crate n.m)

We'll use this parser in parse_signature_packet which we alluded to in the previous section. First, we define the SignaturePacket struct

(note: if I were more interested in some of the initial fields like version and signature_type, I might have made these enums like I did with packet_tag. Additionally, I would have parsed hashed_subpacket_data and unhashed_subpacket_data into subpacket structs)

The struct has the obvious form direct from the RFC. One interesting thing to note is that signature packets have both hashed and unhashed subpackets. The hashed subpackets are included in the hashing process, and are therefore protected. The unhashed subpackets are not included, and can be modified. The signature is a Vec<BigUint> because the RFC specifies that there can be one or more, but for our purposes, there will only ever be one.

We can now write parse_signature_packet

This uses the helper take_single_byte to parse the version, signature_type, public_key_algorithm, and hash_algorithm fields. Then, we use parse_length_tagged_data to parse Vec<u8> that are preceeded by their length. Finally, we use the nom combinator many1 (which runs its argument parser at least once until it fails, and puts the results in a Vec). We assemble these parts into the signature packet.

That completes the signature packet. We have almost everything we need to actually verify a signature. Now, we just need to parse public key packets.

Public Key packets

Public Key packets contain the information that comprises the public key for the particular cryptosystem in use. For RSA, this is the tuple of (n,e) where n is a very large integer. Here is a pgpdump of the public key I have been using for this post

As we can see from the dump, a public key message is made up of a sequence of packets. The first packet is a Public Key Packet (tag 6). This packet contains the tuple (n,e). The second packet is a User ID Packet (tag 13). This contains information about whose public key this is. The User ID Packet is followed by a signature packet, which signs the key. This is followed by a Public Subkey Packet (tag 14) and another signature packet that signs it. A subkey is identical to a regular public key packet, but it may be used for different purposes. For additional security, GPG will generate a public key that is actually comprised of two keys, one used for signing messages, and one used for encrypting and decrypting messages. Since I am only interested in verifying signatures in this post, I will only parse the public key packet (which is used for the signature on my GPG) and ignore the subkey packet.

In order to parse the public key, we first define the structure we will parse into, PublicKeyPacket.

Here, I define separate structures PublicKey and PublicKeyPacket. Though they have the same representation, I do so to illustrate that in general they may not, and indeed, if I were parsing all of the Public Key Packet, it would have much more data than we need.

The nom parser parse_public_key_packet alluded to previously is then given by

This parser skips over the first few fields (in a desperate attempt to finish this post), then parses two MPI which form the tuple (n,e). Finally, a PgpPacket::PublicKeyPacket is returned.

(note: the // skip the rest line may look odd. at the time this parser is called, input will only contain data for one packet, because we previously parsed the length of the packet in parse_pgp_packet, so this is really just a safeguard that we consume everything we need to and satisfy the all_consuming parser in the parent function. this is the reason why parse_user_id_packet and parse_public_subkey_packet are trivial to implement as ignoring parsers, they simply take the length of their input.)

That's it for parsers! I also add a method for getting a PublicKey from an ASCII-armored string, as the PublicKey is what we'll actually use in the next section.

This function parses AsciiArmor from a string, converts it to a Vec<PgpPacket>, gets the first packet (if it's a PublicKeyPacket), and returns a PublicKey. We also need to implement AsciiArmor::into_pgp_packets at this point, which is not hard.

We now have a CleartextSignature waiting to be verified, and a PublicKey with which to verify it. Let's do that!

Putting it all together

Let's write the key method of the whole program, CleartextSignature::verify. I'll take this a section at a time, to fully explain each part.

We define the verify method as a function on CleartextSignature. We instantiate a Sha256 hasher which we'll use to compute the digest.

The RFC specifies that the message should be canonicalized by converting LF to CRLF.

The RFC specifies that part of the signature packet (up to the end of the hashed subpacket data) is included in the hash. Additionally, a trailer of [0x04 0xff] is included for v4 packets.

Finally, we compute the signature by finalizing the hash, and getting a BigUint from the bytes. We compare this to the signature contained in our signature packet. We compute

and parse the resulting bytes as a PKCS1 signature (I lied! There's one more parser for us to write. I don't fully understand PKCS1, I only implemented enough to get a good result). parse_pkcs1 is implemented as

These apparently magic bytes come from the RFC. PKCS1 is a standard way to encode a signature, and I won't fully dig into it.

With that, we have a functioning tool to verify PGP cleartext signatures! It's a little rough around the edges, and a little locked into the specific setup on my local system, but it works! You can generate a new GPG key, sign a message, verify that message, make a minor change to the message, and check that it no longer verifies!

Going forward

If I were to continue this project, I would certainly implement encryption and decryption of PGP messages next. In an early commit, you may notice that I implemented some RSA functionality in anticipation of this, but decided the most interesting thing to me was writing parsers for PGP itself. One thing I did not get to present was a beautifully parallel large random prime generator that used rayon. Additionally, I would implement more of the PGP specification, which is large and complex.

Overall, I would rate RFC 4880 as a good one to start with if you've never implemented an RFC before. I found it to be more readable that previous attempts of mine to better understand some common protocol which I've taken for granted before. The RFC has a lot of information, but taking it in small chunks as I did really aids with understanding. This was the first project where I made a conscious effort to work on it a little bit at a time, at least 3 days a week, and I feel like I got a lot more done than I normally would on a personal project. Finally, narrowing the scope to just cleartext signatures really focused me as the requirements for success were clear.