Paper 2019/807

When PKI (finally) met Provable Security

Hemi Leibowitz and Amir Herzberg and Ewa Syta

Abstract

Public Key Infrastructure (PKI) schemes were first proposed in 1978 and standardized in 1988, yet, unlike most cryptographic schemes, PKI schemes were never rigorously defined. Achieving provable security for PKI is necessary and long overdue, as PKI provides the foundation for important applications of public key cryptography, such as TLS/SSL. In response, we present the first precise specifications of a secure PKI scheme, suitable for a variety of PKI designs. PKI schemes have significantly evolved since X.509, with more complex goals, e.g., transparency, to ensure security against corrupt issuers. In addition to the basic PKI properties, our definitions encompass these more recent and advanced aspects. Our results have important implications. First, our specifications allow a better scrutiny and comparison of the multitude of new PKI designs recently proposed, such as Google’s Certificate Transparency (CT) and related PKIs, as well as future designs. Second, the specifications facilitate proper analysis of protocols and systems that use PKI, such as TLS/SSL, code signing, IPsec, DNSSEC, RPKI, BGPsec, permissioned blockchains, voting, recommendations, which is of critical importance as most real-world security schemes inherently rely on PKI. Finally, we use our specifications to formalize and prove X.509 version 2 PKI, showing that provable security is achievable for ‘real’ PKI designs.

Note: Some of the work that was initially included in previous versions of this work resulted in separate publications. Namely: - MoSS: Modular Security Specifications Framework (https://eprint.iacr.org/2020/1040) - CTng: Secure Certificate and Revocation Transparency (https://eprint.iacr.org/2021/818)