So why can't we deal with these types of attacks? IMO, the main reason is the the server code.
The author mentions that the sks keyserver is "written in an unusual programming language called OCaml", but IMO the language isn't the main issue. Here's a rundown of what I think the main issues are:
* Non-scalable database - SKS keyserver uses Berkeley DB as the database for storing keys, and bdb can't handle more than one connection at time. So, when huge keys with lots of spam signatures are being written to the database, it blocks all other transactions, including serving web requests (see issue #61[2]). The server needs to be re-written to use a database that can handle multiple connections (e.g. Postgres) so spam writes won't affect the web responses for unrelated keys. Unfortunately, the server is currently single-threaded and synchronous so it would have to be heavily re-written to add this kind of async scalability.
* Undocumented gossip protocol - The gossip protocol used is a very efficiency syncing algorithm that lets servers fill in the gaps for their databases from other servers. Unfortunately, the only documentation I can find on the gossip protocol is an academic paper[3]. This is a huge barrier for someone wanting to write a sks-compatible keyserver. You basically have to read the OCaml code (which doesn't have comments) to figure out how it works. For years I have wanted to try to write an alternative sks-compatible keyserver that could handle attacks like these better, but as it stands now, I'd have to spend a huge amount of time learning OCaml and reverse engineering the code just to understand how to write a compatible gossip implementation. Every once in a while I ask the mailing list for a mentor in helping teach me the gossip protocol[4], but so far either no one knows it or wants to teach it to me.
* Few validation and revocation features - OpenPGP is very flexible for how you can build public keys and signatures. I think there's a lot of creative things you can do with signature packets to let keyservers and public key owners clean spam out of their signatures. For example, OpenPGP signatures let you specify a "Signature Target"[5] in a signature, which could be used to let public key owners denote other signatures on their public key they wish to revoke, which the keyserver could then stop serving up to public requests. However, since the current server code is largely unmaintained, we can't implement some of these cleanup options.
Overall, I really love the idea of having a public, open, decentralized keyserver pool. Unfortunately, sks-keyserver wasn't written with much ability to scale (which was totally appropriate at the time), so it's in desperate need of being re-written. I'd love to do it, but simply haven't found the time to reverse engineer the gossip protocol. If someone out there wants to mentor me through it, I'd happily write an sks-compatible keyserver that could operate in the pool and also deal with these types of attacks.
[1]: https://sks.daylightpirates.org/ (currently down)
[2]: https://bitbucket.org/skskeyserver/sks-keyserver/issues/61/k...
[3]: http://ipsit.bu.edu/documents/ieee-it3-web.pdf
[4]: https://lists.nongnu.org/archive/html/sks-devel/2016-08/msg0...