[Trans] can CT defend against dual CA compromise?

[Daniel Kahn Gillmor <[e-mail]>]

CT currently focuses on logging end-entity (leaf) certs; as a result, i
think that an attacker who can compromise two CAs can keep one of those
compromises secret from the CT ecosystem.

Consider an attacker who has compromised two widely-accepted root CAs, A
and B, and wants to mint usable credentials for host Z.

The root CAs each control multiple intermediate authorities: A controls A_1,
A_2, etc; B controls B_1, B_2, etc.

The attacker creates a new secret key X and using A and B creates two
new intermediate authorities A_X and B_X, which both have the same
Subject, the same public key, and the same Subject Key Identifier
extension.  The intermediate authority certs themselves differ, however,
because of their issuers.

The attacker generates a new end entity secret key Y and produces a cert
C (Subject = Z, Public Key = Y), issued by X.

Now we have two possible chains:

  A -> A_X -> C

  B -> B_X -> C

The attacker logs one of those chains and gets an SCT for cert C.  For
this example, let's say the A chain gets logged.

If C is discovered and exposed as a forgery, then root CA A takes the
heat.  Either they disavow/revoke their sub-CA A_X or they are rejected
From TLS client root stores.

However, the attacker can still use C in the wild, by supplying the B
chain.

Note that in this scenario, it's unlikely that space-constrained
blacklist-style client updates (e.g. CRLset) will include every leaf
certificate that chains to A after A is known-compromised.  So TLS
clients won't necessarily be warned off of C directly.

The B chain (and B_X in particular) won't ever surface in the logs'
audit trails, though, because C has already been logged; this looks to
me like CT will fail at its goal of detecting misissuance by B.

Consider this scenario over time, as well.  Once A is publicly-known to
be compromised, the attacker can impersonate new targets with the same
approach: mint a new leaf cert using X (perhaps fiddling with the
validity dates), submit to the logs (and get the SCT) with the A chain,
and then deploy with the B chain.

How to fix this?  A few ideas come to mind, but i'm not convinced of
either of them yet:

 * recommend that clients who care about transparency should expect that
   all intermediate certs themselves are logged -- 6962bis already
   permits this, though it seems to be mainly in contemplation of
   name-constrained intermediate authorities.  This expands the number
   of SCTs or inclusion proofs that need to accompany a chain, and makes
   verification logic slightly more complicated.

 * logs could refuse to log any certs that chain back to a known-failed
   CA (or through a known-bad intermediate CA).  This would constrain a
   dual-compromise attacker from minting new certs after the first CA is
   known to be compromised.  This seems like a useful mitigation, but
   it's also complictated and delicate.  What does "known-failed" mean?
   What if there is a dispute over the validity of a cert, with one
   party claiming that it was misissued, and the CA claiming its
   legitimacy?  What if some browser vendors have dropped the CA, and
   others have not?  This puts the logs in a position of being some kind
   of arbiter of the root store, with very subtle knock-on effects to
   security of the whole ecosystem if they decide to not drop a CA.

   Even more subtly, if the public narrative of the compromise ends up
   being "A_X is bad" (include the intermediate cert in client
   blacklists and refuse to log things that chain through it) instead of
   "A is bad" (include the root cert in client blacklists and refuse to
   log things that chain to it), then the attacker can simply mint
   multiple intermediate keys (X_0, X_1, etc) and corresponding
   intermediate certificates at the time of the compromise, and
   burn/expose them one spoofing attack at a time.

Any other ideas?  Any holes in the reasoning here?  I'd love for this
analysis to be mistaken.

         --dkg