, 11 tweets, 4 min read Read on Twitter
Recent reports on the #OpenPGP #keyserver certificate poisoning attacks have focused on the SKS keyserver implemented in OCaml, which is basically a replicated, censor-resistant, append-only database for unverified key material. But what about #gnupg's role in the attack? /thread
Historically, the PGP tool used the same OpenPGP data structure internally and externally: PGP Keys (public or secret) are a sequence of OpenPGP packets. First there is a signing key packet, then a user id packet, followed by a binding signature, and then web of trust signatures.
The old pubring.gpg is such a sequence of OpenPGP packets. All operations on the list of keys (looking up a key by id or user name, searching for a trust path in the web of trust, deleting a key, etc) require a linear scan, fully parsing every packet from the top down.
To speed this up, GnuPG uses pubring.kbx now, which is basically OpenPGP plus some extra metadata to allow fast-forwarding to the next key in the list without parsing it fully. It's a custom file format implemented in C, as all of GnuPG.
By the way, did you know GnuPG has a second PGP parser just for the keyring? This is because the normal parser can not be reused: It is spread all over the source code. All processing in GnuPG is a side effect of parsing OpenPGP data structures, so a second parser was needed.
Anyway, the keybox format is only a constant speed up, it still requires linear scanning of all keys. And to prevent race conditions, keys are appened by copying the whole file, then appending a single key. Key import is quadratic in disk I/O and runtime for the number of keys.
This not all, though. Parsing a single key builds up a data structure. Part of the data structure is a list of OpenPGP packets that make up the key. This list is implemented as a singly linked list, which is the simplest, but also slowest way to implement a list.
Here is how a new signature is appended to the list of packets (kbnodes) that make up the key. The packet is appended at the end of the list "root", but to find the end, the add_kbnode function iterates over the whole list every time. This is quadratic time in number of packets.
Simply caching the tail of the list would solve this, but because add_kbnode is called in many places, this can not be done safely without auditing a lot of code. I tried caching it in the import, and it made the import very fast, but then GnuPG would hang when doing other stuff.
To fix this properly, GnuPG should use a database library, such as #sqlite. There is a lot of reluctance relying on other people's code, which is why this did not happen. Although it's always a trade off, I would trust my life to sqlite (probably have already!), but not to GnuPG.
tl;dr: Don't use linked lists, don't implement your own data structures.
Missing some Tweet in this thread?
You can try to force a refresh.

Like this thread? Get email updates or save it to PDF!

Subscribe to Marcus Brinkmann
Profile picture

Get real-time email alerts when new unrolls are available from this author!

This content may be removed anytime!

Twitter may remove this content at anytime, convert it as a PDF, save and print for later use!

Try unrolling a thread yourself!

how to unroll video

1) Follow Thread Reader App on Twitter so you can easily mention us!

2) Go to a Twitter thread (series of Tweets by the same owner) and mention us with a keyword "unroll" @threadreaderapp unroll

You can practice here first or read more on our help page!

Follow Us on Twitter!

Did Thread Reader help you today?

Support us! We are indie developers!


This site is made by just three indie developers on a laptop doing marketing, support and development! Read more about the story.

Become a Premium Member ($3.00/month or $30.00/year) and get exclusive features!

Become Premium

Too expensive? Make a small donation by buying us coffee ($5) or help with server cost ($10)

Donate via Paypal Become our Patreon

Thank you for your support!