A Protocol for Solving Certificate Poisoning for the OpenPGP Keyserver Network





OpenPGP, Web of Trust, Transitive trust models, Distributed trust, Certificate poisoning


The OpenPGP encryption standard builds on a transitive trust distribution model for identity assertion, using a non-authenticated, distributed keyserver network for key distribution and discovery. An attack termed “certificate poisoning”, surfaced in 2019 and consisting in adding excessive trust signatures from inexistent actors to the victim key so that it is no longer usable, has endangered the continued operation of said keyserver network. In this article, we explore a protocol modification in the key acceptance and synchronization protocol termed First-party attested third-party certification that, without requiring the redeployment of updated client software, prevents the ill effects of certificate poisoning without breaking compatibility with the OpenPGP installed base. We also discuss some potential challenges and limitations of this approach, providing recommendations for its adoption.


Download data is not yet available.


Arkko, J. and Nikander, P. (2004). Weak authentication: How to authenticate unknown principals without trusted parties. In Christianson, B., Crispo, B., Malcolm, J. A., and Roe, M., editors, Security Protocols, pages 5-19, Berlin, Heidelberg. Springer Berlin Heidelberg. DOI: 10.1007/978-3-540-39871-4_3.

Azul, Matuszewski, I., Winter, J., Michaelis, K., Walfield, N., Widdecke, N., and Kwapisiewicz, W. (2021). User manual: sq - a command-line frontend for sequoia, an implementation of openpgp. Available at: [link].

Borisov, N., Goldberg, I., and Brewer, E. (2004). Off-the-record communication, or, why not to use pgp. In Proceedings of the 2004 ACM workshop on Privacy in the electronic society, pages 77-84. Association for Computing Machinery. DOI: 10.1145/1029179.1029200.

Callas, J., Donnerhacke, L., Finney, H., Shaw, D., and Thayer, R. (2007). Openpgp message format. Internet Engineering Task Force (IETF), (4880). Available at: [link].

Conti, M., Dragoni, N., and Lesyk, V. (2016). A survey of man in the middle attacks. IEEE Communnications Surveys & Tutorials, 18(3):2027-2051. DOI: 10.1109/COMST.2016.2548426.

Hansen, R. J. (2019). Sks keyserver network under attack. Available at: [link].

Herzberg, A. and Leibowitz, H. (2016). Can johnny finally encrypt? evaluating e2e-encryption in popular im applications. In Proceedings of the 6th Workshop on Socio-Technical Aspects in Security and Trust, pages 17-28. DOI: 10.1145/3046055.3046059.

Huisman, M., Monti, R., Ulbrich, M., and Weigl, A. (2020). The verifythis collaborative long term challenge. In Ahrendt, W., Beckert, B., Bubel, R., Hähnle, R., and Ulbrich, M., editors, Deductive Software Verification: Future Perspectives: Reflections on the Occasion of 20 Years of KeY, volume 12345 of Lecture Notes in Computer Science, chapter 10, pages 246-260. Springer. DOI: 10.1007/978-3-030-64354-6_10.

Johansen, C., Mujaj, A., Arshad, H., and Noll, J. (2017). Comparing implementations of secure messaging protocols. Technical Report ISBN 97-82-7368-440-0, Universitetet i Oslo. Available at: [link].

Jøsang, A. (1999). An algebra for assessing trust in certification chains. In Proc. Network and Distributed Systems Security Symposium, 1999 (NDSS'99). The Internet Society. Available at: [link].

Kahn Gillmor, D. (2019a). Abuse-resistant openpgp keystores. Internet-Draft draft-dkg-openpgp-abuse-resistant-keystore-04, Internet Engineering Task Force. Available at: [link].

Kahn Gillmor, D. (2019b). Openpgp certificate flooding. Available at: [link].

Kahn Gillmor, D. (2023). First-party attested third-party certifications in openpgp. Internet-draft, Internet Engineering Task Force. Available at: [link].

Koch, W. (2021). OpenPGP Web Key Directory. Internet-Draft draft-koch-openpgp-webkey-service-12, Internet Engineering Task Force. Available at: [link].

Koch, W., Huigens, D., Winter, J., and Niibe, Y. (2022). Openpgp message format. Internet-Draft draft-ietf-openpgp-crypto-refresh-06, Internet Engineering Task Force. Available at: [link].

Krekel, H., McKelvey, K., and Lefherz, E. (2018). How to fix email: Making communication encrypted and decentralized with autocrypt. XRDS: Crossroads, The ACM Magazine for Students, 24(4):37–39. DOI: 10.1145/3220565.

Marlinspike, M. (2016). Whatsapp's signal protocol integration is now complete. Available at: [link].

Marshall, C. (2015). Hockeypuck. Available at: [link].

Mauriés, J. R. P., Krol, K., Parkin, S., Abu-Salma, R., and Sasse, M. A. (2017). Dead on arrival: Recovering from fatal flaws in email encryption tools. In The LASER Workshop: Learning from Authoritative Security Experiment Results (LASER 2017), pages 49-57. USENIX Association. Available at: [link].

Minsky, Y. M. (2002). Spreading rumors cheaply, quickly, and reliably. PhD thesis, Cornell University. Available at: [link].

Palfrader, P., Berg, C., and Moulin, G. (2020). Caff: Certificate authority fire and forget. Available at: [link].

PGP Global Directory (2004). Pgp global directory verified key service. Available at: [link].

Pham, V. and Aura, T. (2011). Security analysis of leap-of-faith protocols. In International Conference on Security and Privacy in Communication Systems, pages 337-355. Springer. DOI: 10.1007/978-3-642-31909-9_19.

Pramberger, P. (2010). Keyserver.pramberger.at terminating. Available at: [link].

Renaud, K., Volkamer, M., and Renkema-Padmos, A. (2014). Why doesn't jane protect her privacy? In De Cristofaro, E. and Murdoch, S. J., editors, Privacy Enhancing Technologies PETS 2014, volume 8555 of Lecture Notes in Computer Science, pages 244-262. Springer International Publishing. DOI: 10.1007/978-3-319-08506-7_13.

Rescorla, E. (2018). The transport layer security (tls) protocol, version 1.3. Internet Engineering Task Force (IETF), (8446). Available at: [link].

Sharma, R., Dangi, S., and Mishra, P. (2021). A comprehensive review on encryption based open source cyber security tools. In 2021 6th International Conference on Signal Processing, Computing and Control (ISPCC), pages 614-619. DOI: 10.1109/ISPCC53510.2021.9609369.

Shaw, D. (2003). The openpgp http keyserver protocol (hkp). Internet-Draft draft-shaw-openpgp-hkp-00, Internet Engineering Task Force. Available at: [link].

Sheng, S., Broderick, L., Koranda, C. A., and Hyland, J. J. (2006). Why johnny still can’t encrypt: evaluating the usability of email encryption software. In Symposium On Usable Privacy and Security, pages 3-4. ACM. Available at: [link].

Walfield, N. H. (2019). Hagrid: A new verifying key server built on sequoia. Available at: [link].

Walfield, N. H. and Koch, W. (2016). Tofu for openpgp. In EuroSec’16: Proceedings of the 9th European Workshop on System Security, pages 1-6. DOI: 10.1145/2905760.2905761.

Whitten, A. and Tygar, J. D. (1999). Why johnny can't encrypt: A usability evaluation of pgp 5.0. In USENIX Security Symposium, volume 348, pages 169-184. Available at: [link].

Wolf, G. and Gallegos, G. (2017). Strengthening a curated web of trust in a geographically distributed project. Cryptologia, 41(5):459-475. DOI: 10.1080/01611194.2016.1238421.

Wolf, G. and Quiroga, V. G. (2018). Insights on the large-scale deployment of a curated web-of-trust: the debian project’s cryptographic keyring. Journal of Internet Services and Applications, 9(1):1-12. DOI: 10.1186/s13174-018-0082-7.

Woo, W. K. (2006). How to exchange email securely with Johnny who still can’t encrypt. PhD thesis, University of British Columbia. Available at: [link].

Wouters, P. (2016). Dns-based authentication of named entities (dane) bindings for openpgp. Internet Engineering Task Force (IETF), (7929). Available at: [link].

Yakamo, K. (2018). Are sks keyservers safe? do we need them? Available at: [link].

Yamane, S., Wang, J., Suzuki, H., Segawa, N., and Murayama, Y. (2003). Rethinking openpgp PKI and openpgp public keyserver. CoRR, cs.CY/0308015. DOI: 10.48550/arXiv.cs/0308015.

Zimmermann, P. (1999). Why i wrote pgp. Available at: [link].




How to Cite

Wolf, G., & Ortega-Arjona, J. L. (2024). A Protocol for Solving Certificate Poisoning for the OpenPGP Keyserver Network. Journal of Internet Services and Applications, 15(1), 46–58. https://doi.org/10.5753/jisa.2024.3810



Research article