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.
