Reducing Trust in Automated Certificate Authorities via Proofs-of-Authentication

Automated certificate authorities (CAs) have expanded the reach of public key infrastructure on the web and for software signing. The certificates that these CAs issue attest to proof of control of some digital identity. Some of these automated CAs issue certificates in response to client authentication using OpenID Connect (OIDC, an extension of OAuth 2.0). This places these CAs in a position to impersonate any identity. Mitigations for this risk, like certificate transparency and signature thresholds, have emerged, but these mitigations only detect or raise the difficulty of compromise. Researchers have proposed alternatives to CAs in this setting, but many of these alternatives would require prohibitive changes to deployed authentication protocols. In this work, we propose a cryptographic technique for reducing trust in these automated CAs. When issuing a certificate, the CAs embed a proof of authentication from the subject of the certificate -- but without enabling replay attacks. We explain multiple methods for achieving this with tradeoffs between user privacy, performance, and changes to existing infrastructure. We implement a proof of concept for a method using Guillou-Quisquater signatures that works out-of-the-box with existing OIDC deployments for the open-source Sigstore CA, finding that minimal modifications are required.