Subject: [Trans] can CT defend against dual CA compromise?

From: Daniel Kahn Gillmor <[email-masked]>
Date: Sat, 20 Feb 2016 22:05:27 -0500

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

---

From: Ben Laurie <[email-masked]>
Date: Mon, 22 Feb 2016 11:01:27 +0000

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

Up to here, I agree.

> clients won't necessarily be warned off of C directly.

It seems to me there are multiple solutions here. The easiest is to not
blacklist A_X, but instead to blacklists A_X's subject, which will also
blacklist B_X.

To be more selective, blacklist the individual certs that were mis-issued
(we have a complete list, of course, in the logs) and stop accepting new
certs signed by X.

>    verification logic slightly more complicated.

Regardless of the argument above and mitigation thereof, I think this would
be a good idea.

>    security of the whole ecosystem if they decide to not drop a CA.

Not all that subtle, surely, and completely visible so we can see its going
on...

>    burn/expose them one spoofing attack at a time.

After a while, we would clearly decide that A is bad. :-)

> Any other ideas?  Any holes in the reasoning here?  I'd love for this

As I say, I think the problem is real, unfortunately. However, the
consequences don't seem quite as terrible as you think. I hope!

---

From: Rob Stradling <[email-masked]>
Date: Mon, 22 Feb 2016 11:49:06 +0000

On 22/02/16 11:01, Ben Laurie wrote:
<snip>
> blacklist A_X, but instead to blacklists A_X's subject, which will also

I think that blacklisting the shared issuer public key would be better 
than blacklisting the shared issuer name.

AIUI, MS CryptoAPI prefers to build certificate chains using the 
Authority/Subject Key Identifiers, and it only cares about whether or 
not the Issuer/Subject Names match if AKI/SKI are absent.

<snip>
> Regardless of the argument above and mitigation thereof, I think this
> would be a good idea.

If we expect to (eventually) have an effective revocation mechanism 
(e.g. blacklisting the issuer public key), then why would we need to 
increase the TLS handshake size (by sending additional SCTs/proofs) just 
so that we can solve the same problem twice?

If we do want CT to handle this though, then I suggest that we:
   - require intermediate certs to be logged in the same logs as the 
end-entity certs they issue.
   - don't require SCTs or inclusion proofs for intermediates to be sent 
by TLS servers (except for the name-constrained case).
   - say that TLS clients SHOULD fetch and verify inclusion proofs for 
all intermediate certs that they rely on.

<snip>

-- 
Rob Stradling
Senior Research & Development Scientist
COMODO - Creating Trust Online

---

From: Tom Ritter <[email-masked]>
Date: Tue, 23 Feb 2016 00:03:04 -0600

I'm interleving Ben's and Rob's responses here:

> [Ben]

Perhaps.

> [Rob]
> I think that blacklisting the shared issuer public key would be better than
> blacklisting the shared issuer name.

At first glance, I agree - but there is that annoying trick where you
can generate multiple (or at least two) public keys that all certify
the same signature. So I'm not sure this would actually work.

> [Rob]
> Authority/Subject Key Identifiers, and it only cares about whether or not
> the Issuer/Subject Names match if AKI/SKI are absent.

AKI would _not_ match on these trick public keys, but presumably the
algorithm would fall back to the Issuer name...?

> [Ben]

The "stop accepting new certs" thing might trip us up. We would like a
mechanism to track the misissued certs of a compromised CA. Trust
Stores have age. We don't distrust X all at once, and it'd be good to
know what X is doing so we can understand our risk on the older
devices.

> [Ben]

As I said above - up until here the CT logs have been a good viewpoint
on the CA ecosyetem. Aggressively removing CAs seems dangerous from a
"track the ecosystem and ensure accountability" perspective.

> [Rob]
>   - say that TLS clients SHOULD fetch and verify inclusion proofs for all
> intermediate certs that they rely on.

I'm nervous about this.

-tom

---

From: Rob Stradling <[email-masked]>
Date: Tue, 23 Feb 2016 10:41:00 +0000

On 23/02/16 06:03, Tom Ritter wrote:
<snip>
> the same signature. So I'm not sure this would actually work.

SCTs in 6962-bis already contain the issuer_key_hash (which is the DER 
encoding of the issuer's SubjectPublicKeyInfo).  Is that enough to 
defeat your trick key attack?

Hmmm, I wonder if we need to add issuer_key_hash to inclusion proofs as 
well (i.e. the InclusionProofDataV2 struct) ?

> algorithm would fall back to the Issuer name...?

For Win2K and WinXP, it appears that it only attempts name matching if 
the AKI extension is absent.

"If there is no information in the AKI, or the AKI does not exist in the 
certificate being evaluated, a certificate whose subject name matches 
the evaluated certificate's issuer name will be chosen. This selection 
method is known as a name match."
https://technet.microsoft.com/en-us/library/cc700843.aspx

I can't find any more recent documentation.  :-(

<snip>
>> intermediate certs that they rely on.

Why so?  I wasn't suggesting a "MUST".  ;-)

---

From: Ben Laurie <[email-masked]>
Date: Tue, 23 Feb 2016 11:06:25 +0000

> the same signature. So I'm not sure this would actually work.

Hmm. That would be e and e + phi(n), I guess?

> know what X is doing so we can understand our risk on the older

Fair point. At least two ways of doing this:

a) Run a log that is not trusted for HTTPS connections.

b) Continue to accept certs from X, but don't allow SCTs after the last
good timestamp for X.

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Tue, 23 Feb 2016 17:59:05 -0800

> a) Run a log that is not trusted for HTTPS connections.

(trolling: i thought logs didn't have to be trusted...)

what encourages any party in the ecosystem to log in this untrutsed log?

> b) Continue to accept certs from X, but don't allow SCTs after the last

What does this buy us?  Can't an inclusion proof (post-MMD) from this
log perform the same role as the SCT?

        --dkg

---

From: Rob Stradling <[email-masked]>
Date: Wed, 24 Feb 2016 11:20:16 +0000

> well (i.e. the InclusionProofDataV2 struct) ?

Actually, issuer_key_hash is already included in the 
TimestampedCertificateEntryDataV2 structure from which leaf hashes are 
calculated.  I think that's sufficient to guard against inclusion proofs 
being considered valid in conjunction with a trick issuer public key 
(but please correct me if I'm wrong!)

---

From: Ben Laurie <[email-masked]>
Date: Wed, 24 Feb 2016 14:15:40 +0000

> (trolling: i thought logs didn't have to be trusted...)

:-)

It is a fair point, though - perhaps a better way to express it would be
"not used by browsers for transparency".

> what encourages any party in the ecosystem to log in this untrutsed log?

We log all the certs we see. I think we are not the only ones. But agreed,
this is not as robust as a system which requires logging in order for certs
to be accepted. Given that the whole point is not to accept further certs,
this seems tricky to solve!

> log perform the same role as the SCT?

Not sure I understand what you mean by this?

---

From: Tom Ritter <[email-masked]>
Date: Wed, 24 Feb 2016 08:16:45 -0600

Not interleaving this time, but batch-replying:

On 23 February 2016 at 04:41, Rob Stradling <[email-masked]> wrote:
> encoding of the issuer's SubjectPublicKeyInfo).  Is that enough to defeat
> your trick key attack?

Yes.

> For Win2K and WinXP, it appears that it only attempts name matching if the
> AKI extension is absent.
>
> certificate being evaluated, a certificate whose subject name matches the
> evaluated certificate's issuer name will be chosen. This selection method is
> known as a name match."

That's beneficial for our purposes though.

> Why so?  I wasn't suggesting a "MUST".  ;-)

What's the risk to clients who don't?

Currently, in gossip clients who don't want to fetch proofs (because
it's unacceptable to them privacy-wise or whatever) can use SCT
Feedback. (If they talk to a site that doesn't use SCT Feedback, then
they're sunk, but we hope this and other incentives will encourage
uptake of SCT Feedback.)

Because the say the client MUST submit the full chain in SCT
Feedback... I think SCT Feedback does actually cover the clients who
don't get the inclusion proof for the intermediate.  And it would be
simple enough to add the SHOULD to STH Pollination to grab a STH for
the intermediate cert and pollinate that. So now I'm less worried.

> Hmm. That would be e and e + phi(n), I guess?

This is a good walkthrough:  http://crypto.stackexchange.com/q/8902

> what encourages any party in the ecosystem to log in this untrutsed log?

Technically we don't need CAs to log to that log, the community can
log to it. Google Crawler, the EFF's Distributed HTTPS Observatory,
Firefox plugins, replication from other logs...

On 24 February 2016 at 05:20, Rob Stradling <[email-masked]> wrote:
> being considered valid in conjunction with a trick issuer public key (but
> please correct me if I'm wrong!)

To be 100% honest I have not tracked -bis as closely as I should have.
So I need to take a pass through gossip and make sure that the types
of things I expect 'intuitively' from bis align with what it provides.

---

From: Tom Ritter <[email-masked]>
Date: Wed, 24 Feb 2016 09:35:41 -0600

On 24 February 2016 at 08:15, Ben Laurie <[email-masked]> wrote:

Sorry, this is complicated. I type a lot when it's complicated.

Thinking about the public key trick more... I don't think it would work.
R -> I -> L

Goal is to match a signature on L by making a new I' and then getting
a client to accept the chain. Changing the public key in I' will
invalidate the signature by R. So while I can mint a new certificate
I' that makes a valid subchain - it won't chain all the way up.

The public key of the fraudulent Intermediate should be blacklisted.
Blacklisting the Subject of the intermediate is a poor choice for the
same reason that using serial number in CRLs/OCSP is a poor choice.
The smart attacker will collide the serial/Subject with an existing
Intermediate that is nigh-unrevokable (because it breaks the
internet).

We need to use something that asserts cryptographic uniqueness for
practical purposes - but it can't be _too_ unique or an attacker uses
a trick to get around it.[0] SPKI seems like the mechanic of choice...

Do crlsets and OneCRL have the ability to blacklist on SPKI? Or do
they use serials or fingerprints?  =)

So a software update blacklists the SPKI of the fradulent
intermediate, which will block A_X and B_X.  (We only know about A_X
though, so A gets the heat while B is still unknown-compromised.)

The problem isn't that an attacker can continue to issue certs off A_X
and log them - the problem is the attacker may be able to continue to
issue *Intermediates* off of A (and B silently & simultaneously) and
log certificates off the new intermediate A_Y (of which the SCT would
be valid for B_Y also.)  The community sees A_Y and doesn't really
flinch/understand the implications w.r.t a future world where SCTs are
required for all connections.

In that world, we would need to blacklist all new SPKIs (in software)
issued by A as they pop up on the offchance they've also been minted
under B.  This seems less than ideal because the smart attacker would
issue so many intermediates that Browsers could not realistically
blacklist them all.  (And blacklisting A doesn't help.) More
engineering would be needed to accomodate all the intermediates, it
would delay the deployment... meanwhile the attacker uses B_746385 to
attack users. This is a failing of CT, in that it puts us back in the
days of "If someone is owned, we don't know."

Ben gave two ways of fixing this, I'll reword/expand:

a) Run a log that tracks everything (including a new A_Y and
A_Y-issued certs) but isn't used in browsers. I'll expand this:

Do not issue SCTs from any other log used by browsers if the
issuer_key_hash matches an intermediate issued by A. In browser
software, blacklist the SPKI of A_X at least, perhaps also A (one
would hope).

I think this would work - but it introduces a complicated new function
for log operators. They need to be able to look at an issuing_key_hash
and reject submissions if that matches a blacklist but fulfills the
root store whitelist (as opposed to currently only checking roots on a
whitelist.)

If they omit this, or fail to update the blacklist, AND an auditor
remembers this attack and implements a check for it (is anyone adding
this to any long-term storage? the Threat Analysis doc?) - we can
retroactively detect the attack again (after some users could be
attacked.)

If they implement this check the log SHOULD raise giant alarms if it
gets a submission that fulfills the root store whitelist but matches
the blacklist.

b) Continue to accept certs from A_X and A in the main logs, but don't
allow SCTs for certs chaining to either A_X (or A depending on the
investigation - but definetly A as soon as a new A_Y pops up).  Ben
said something involving timestamps - but I don't think that could
work because we have to assume the attacker can backdate anything they
want...

So in this case the certs issued by A_X and A are in the log, and can
have inclusion proofs but they were never given a SCT.  This seems
strange to me (and dkg.) But at the moment I'm not sure if an
inclusion proof is equiavlent to a SCT and would enable an attacker to
do anything. I guess it depends on how we require future validation in
client software and if we were ever to say "An inclusion proof is
acceptable in place of an SCT".  I'm not sure if we want to commit
ourselves to rejecting that equivalence for all time...

There's got to be more solutions....

c) Log signs the exact chain. Client must build this same chain and
match it. This would fix everything, but it requires strict path
building by the client, which won't happen.

d) Log signs the chain but the client uses this as a _hint_. If it
builds a path that it deems is 'wrong' based on the hint (e.g. the
hint says Federal PKI but the chain I built uses CNNIC) then reject
it. This would require complicated logic that's probably impossible to
get right more than 80% of the time.

e) The issuer_key_hash is not over the SPKI but the certificate -
including the signature by that issuer's issuer.  This would... also
break path building? Because of cross signatures?  I guess I'm still
confused about those. If R is cross-signed by another CA, C. There are
two R's right? R-self-signed and R-signed-by-C.  Or in Let's Encrypt's
case there are two intermediate certs I: I-signed-by-Lets-Encrypt and
I-signed-by-Identrust?

I guess I know there's more solutions, but isn't there another that's workable?

-tom

[0] What do I mean by this? Say you used a cert fingerprint. Using BER
tricks, you has, in the past, been able to change the fingerprint
without invalidating the signature:
https://git.openssl.org/?p=openssl.git;a=commitdiff;h=684400ce192dac51df3d3e92b61830a6ef90be3e

---

From: Ben Laurie <[email-masked]>
Date: Wed, 24 Feb 2016 22:27:34 +0000

> they use serials or fingerprints?  =)

https://github.com/agl/crlset-tools (answer: yes, crlsets can blacklist on
SPKI).

> retroactively detect the attack again (after some users could be

Surely no-one has to remember anything ... if a browser-used log logs a
cert that is for a domain that wasn't expecting that cert to be issued,
then action needs to be taken.

Eventually, presumably, everyone will get bored of taking action on every
cert issued by the compromised CA and deal with the problem in a more
fundamental way. Such as blacklisting the SPKI.

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Fri, 26 Feb 2016 06:02:00 +0100

> https://github.com/agl/crlset-tools (answer: yes, crlsets can blacklist on

good, i'm glad to hear it.

> Surely no-one has to remember anything ... if a browser-used log logs
> a cert that is for a domain that wasn't expecting that cert to be
> issued, then action needs to be taken.

Sure, but if that action is nothing because "meh, this particular
browser-used log just hasn't rejected certs that chain back to A yet,
and we know that A is bad, so we can just ignore this leaf cert", then
we're in the situation that CT is supposed to prevent.

OTOH, If we expect all browser-used logs to immediately refuse to serve
SCTs that chain to a given root (A) whenever any of A's intermediates
(A_X) is shown to have misissued anything (how do we prove a
misissuance, as opposed to compromise or organizational failure of the
end entity itself again?), then we get to try to coordinate a new set of
multiple parties during an apparent CA compromise (logs this time, in
addition to browser vendors), and log operators themselves need to make
potentially-political decisions about which roots or intermediates to
blacklist and which to continue logging.

More generally, I'm quite concerned that we seem to be adding a second
category of log to the CT ecosystem in an attempt to have an analysis
that doesn't have this dual-CA-compromise issue.

The CT ecosystem is complicated and hard to analyze with only one kind
of log, and now it seems that we have:

 * browser-used logs
 * non-browser-used logs

What are the different requirements of each kind of log?  What kinds of
decisions do the different kinds of log operators need to make?  What
additional data structures do they need to maintain for correct
operation?  How does the ecosystem as a whole depend on them doing their
specific work?  what happens if they fail?  what incentives do people
have to offer one kind of log or another?  Do auditors need to look at
both kinds of logs, or only one?

> Eventually, presumably, everyone will get bored of taking action on
> every cert issued by the compromised CA and deal with the problem in a
> more fundamental way. Such as blacklisting the SPKI.

Who blacklists the SPKI?  All browser vendors?  browser-used logs?
non-browser-used logs?  which SPKI gets blacklisted?  blacklisting the
SPKI of the intermediate cert doesn't work if the root CA is compromised
-- the attacker can just issue a new intermediate.  how many compromised
intermediates does a log need to see before it decides to blacklist the
root CA itself?  Does it need to coordinate such a blacklist with the
browser vendors?  with all of them, or just some of them?

sorry for being all questions and no answers, but this still doesn't
seem resolved to me.

        --dkg