  Public Key Infrastructures (PKIs) with their trusted Certificate Authorities
(CAs) provide the trust backbone for the Internet: CAs sign certificates which
prove the identity of servers, applications, or users. To be trusted by
operating systems and browsers, a CA has to undergo lengthy and costly
validation processes. Alternatively, trusted CAs can cross-sign other CAs to
extend their trust to them. In this paper, we systematically analyze the
present and past state of cross-signing in the Web PKI. Our dataset (derived
from passive TLS monitors and public CT logs) encompasses more than 7 years and
225 million certificates with 9.3 billion trust paths. We show benefits and
risks of cross-signing. We discuss the difficulty of revoking trusted CA
certificates where, worrisome, cross-signing can result in valid trust paths to
remain after revocation; a problem for non-browser software that often blindly
trusts all CA certificates and ignores revocations. However, cross-signing also
enables fast bootstrapping of new CAs, e.g., Let's Encrypt, and achieves a
non-disruptive user experience by providing backward compatibility. In this
paper, we propose new rules and guidance for cross-signing to preserve its
positive potential while mitigating its risks.
