Subject: [Trans] Name redacted pre-cert can correspond to multiple certs

From: Andrew Ayer <[email-masked]>
Date: Mon, 6 Jun 2016 10:29:35 -0700

When name redaction is used, certificates with different DNS names
(but which are otherwise identical) can have the same reconstructed
TBSCertificate, and can therefore be paired with an SCT for the
same pre-certificate.

This enables the following attack:

1. A CA issues a legitimate certificate for www1.example.com and logs a
pre-certificate for ?.example.com.  A monitor for example.com knows the
pre-certificate is legitimate because it matches a known certificate
for www1.example.com.

2. The CA misbehaves and issues an unauthorized certificate for
www2.example.com which, except for the DNS name, has exactly the same
details (including serial number and public key) as the certificate for
www1.example.com.  The CA does not log a certificate or pre-certificate.

3. An attacker serves the rogue certificate for www2.example.com along
with the SCT for the ?.example.com pre-certificate.  TLS clients accept
it because the TBSCertificate that is reconstructed from the certificate
matches the TBSCertificate of the pre-certificate.  Monitors have no
idea that there is a rogue certificate for www2.example.com.

Although this attack is limited because it requires the rogue
certificate to use the same key as the legitimate certificate, it's
still a problem. The private key for the legitimate certificate might
be controlled by a third party that is authorized to operate one
sub-domain of example.com not not another. It also means that the
compromise of one certificate's key could be used to attack other
sub-domains.

This should be fixed.  I'm implementing a monitor that supports name
redaction, and the only viable way I can find to handle name redacted
pre-certificates is to match them against a database of known
certificates.  Otherwise, the domain owner is left uncertain what the
redacted labels are.  If a pre-certificate can correspond to more than
one certificate, the uncertainty can never be eliminated.

One fix is to replace redacted labels not with '?' but with a salted
cryptographic hash of the label, with the salt specified in the
Redacted Labels Certificate Extension.  (This is similar to the
proposal by Peter Bowen to use CRC-32 two years ago[1], except a
cryptographic hash is used for pre-image resistance, and a salt is
used to prevent dictionary attacks.)  Unfortunately, this increases
complexity.

Regards,
Andrew

[1] https://mailarchive.ietf.org/arch/msg/trans/pbooERCZ9hAn8GmVVkWLKaDzq9Y

---

From: Paul Wouters <[email-masked]>
Date: Mon, 6 Jun 2016 13:52:57 -0400 (EDT)

> idea that there is a rogue certificate for www2.example.com.

That means the attacker has the private key?

I guess when the second certificate would be logged, this would show up
as mis-issued, and possibly both certificates would get revoked?

Wouldn't that be the system working as intended?

Paul

---

From: Andrew Ayer <[email-masked]>
Date: Mon, 6 Jun 2016 11:17:44 -0700

On Mon, 6 Jun 2016 13:52:57 -0400 (EDT)
Paul Wouters <[email-masked]> wrote:

> > 1. A CA issues a legitimate certificate for www1.example.com and
> > logs a pre-certificate for ?.example.com.  A monitor for
> > example.com knows the pre-certificate is legitimate because it
> > matches a known certificate for www1.example.com.
> >
> > www2.example.com which, except for the DNS name, has exactly the
> > same details (including serial number and public key) as the
> > certificate for www1.example.com.  The CA does not log a
> > certificate or pre-certificate.
> >
> > 3. An attacker serves the rogue certificate for www2.example.com
> > along with the SCT for the ?.example.com pre-certificate.  TLS
> > clients accept it because the TBSCertificate that is reconstructed
> > from the certificate matches the TBSCertificate of the
> > pre-certificate.  Monitors have no idea that there is a rogue
> > certificate for www2.example.com.
> 

Yes, but that only limits the attack, not eliminate it.  It means that
if the attacker gets the private key for one host, they can
(with CA collusion) pivot to attacking other hosts whose names match
the same redaction pattern.

> I guess when the second certificate would be logged, this would show
> up as mis-issued, and possibly both certificates would get revoked?

The second certificate would never be logged.  The way that logging is
enforced is that clients reject certificates that aren't accompanied by
a valid SCT.  But since an SCT for the first certificate's
pre-certificate can be used to prove that the second certificate was
logged, clients can be tricked into accepting the second certificate
even if it was never logged.

That's basically the crux of the problem - with name redaction, SCTs do
not prove that a certificate was logged, they only prove that some
pre-certificate matching the name redacted pattern was logged.  I argue
that for monitoring to be useful, SCTs need to prove that a
pre-certificate matching the exact name was logged.

Regards,
Andrew

---

From: Rob Stradling <[email-masked]>
Date: Thu, 9 Jun 2016 16:43:48 +0100

> pre-certificate matching the exact name was logged.

If a wildcard cert for *.example.com is logged, it can be used for 
https://www1.example.com, https://www2.example.com and 
https://anythingyoulike.example.com.

How does name redaction make the situation any worse than that?

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

---

From: Andrew Ayer <[email-masked]>
Date: Thu, 9 Jun 2016 11:44:14 -0700

On Thu, 9 Jun 2016 16:43:48 +0100
Rob Stradling <[email-masked]> wrote:

> > Yes, but that only limits the attack, not eliminate it.  It means
> > that if the attacker gets the private key for one host, they can
> >> I guess when the second certificate would be logged, this would
> >> show up as mis-issued, and possibly both certificates would get
> >> revoked?
> >
> > The second certificate would never be logged.  The way that logging
> > is enforced is that clients reject certificates that aren't
> > accompanied by a valid SCT.  But since an SCT for the first
> > certificate's pre-certificate can be used to prove that the second
> > certificate was logged, clients can be tricked into accepting the
> > second certificate even if it was never logged.
> >
> > That's basically the crux of the problem - with name redaction,
> > SCTs do not prove that a certificate was logged, they only prove
> > that some pre-certificate matching the name redacted pattern was
> > logged.  I argue that for monitoring to be useful, SCTs need to
> > prove that a pre-certificate matching the exact name was logged.
> >
> > Regards,
> > Andrew
> 

If a domain owner requests a wildcard certificate for *.example.com,
they are accepting the possibility that the certificate can be used
with any sub-domain.  It's expected.

If a domain owner requests a certificate for www1.example.com, the
expectation is that the certificate only works with www1.example.com.
But if the domain owner requests redaction, they are now making it
possible for the CA is misbehave and issue certificates for hosts
besides www1.example.com that will be accepted by clients and not
detected by the domain owner's monitor.  That seems like a violation of
user expectation.

It also seems like a violation of a core principle of CT: that
clients will only accept a cert if the cert is logged.  However, when
redaction is used, clients will accept a cert even if it was actually a
different cert which was logged[1], as long as the two certs redact down
to the same pre-cert TBSCertificate.

Regards,
Andrew

[1] Technically, a pre-cert was logged, but a pre-cert is just a proxy
for a cert.

---

From: Rob Stradling <[email-masked]>
Date: Fri, 10 Jun 2016 15:16:43 +0100

> detected by the domain owner's monitor.  That seems like a violation of

I think it's fair enough to say that if you withhold information from 
CT, CT won't help you as much as it otherwise would have done.

I see the attraction of replacing "redacted labels not with '?' but with 
a salted cryptographic hash of the label, with the salt specified in the 
Redacted Labels Certificate Extension", but I'd prefer to avoid 
increasing complexity.

---

From: Ben Laurie <[email-masked]>
Date: Wed, 15 Jun 2016 09:58:20 +0100

> detected by the domain owner's monitor.  That seems like a violation of

That is still no different from the wildcard example, though - the CA
can also issues a "second" cert for *.example.com (it is the same
cert, of course) and mount the same attack.

> _______________________________________________
> Trans mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/trans

---

From: Ben Laurie <[email-masked]>
Date: Wed, 15 Jun 2016 10:00:27 +0100

On 10 June 2016 at 15:16, Rob Stradling <[email-masked]> wrote:
> I think it's fair enough to say that if you withhold information from CT, CT
> won't help you as much as it otherwise would have done.
>
> I see the attraction of replacing "redacted labels not with '?' but with a
> salted cryptographic hash of the label, with the salt specified in the
> Redacted Labels Certificate Extension", but I'd prefer to avoid increasing
> complexity.

I also like this suggestion. It does have the obvious downside that
dictionary attacks work, though they can be made expensive.

---

From: Andrew Ayer <[email-masked]>
Date: Wed, 15 Jun 2016 10:56:58 -0700

On Wed, 15 Jun 2016 10:00:27 +0100
Ben Laurie <[email-masked]> wrote:

> > I think it's fair enough to say that if you withhold information
> > from CT, CT won't help you as much as it otherwise would have done.
> >
> > I see the attraction of replacing "redacted labels not with '?' but
> > with a salted cryptographic hash of the label, with the salt
> > specified in the Redacted Labels Certificate Extension", but I'd
> > prefer to avoid increasing complexity.
> 

A sufficiently-long random salt makes dictionary attacks infeasible.
Since the salt is only specified in the certificate, anyone who knows
the salt knows the unredacted labels already.

Regards,
Andrew

---

From: Jeremy Rowley <[email-masked]>
Date: Wed, 15 Jun 2016 18:43:13 +0000

I'm in favor of keeping redaction in, even with the added complexity.
Considering the number of enterprises that currently use domain names as a
directory, I think redaction is the difference between wide spread adoption
v. a single implementation for EV certificates. Since the intended
beneficiaries of CT are primarily the website owners, giving them insight on
certs issued to domains, it's up to the domain owner to have a policy for or
against redaction of their domain names.   

-----Original Message-----
From: Trans [mailto:[email-masked]] On Behalf Of Andrew Ayer
Sent: Wednesday, June 15, 2016 11:57 AM
To: Trans <[email-masked]>
Subject: Re: [Trans] Name redacted pre-cert can correspond to multiple certs

A sufficiently-long random salt makes dictionary attacks infeasible.
Since the salt is only specified in the certificate, anyone who knows the
salt knows the unredacted labels already.

Regards,
Andrew

---

From: Andrew Ayer <[email-masked]>
Date: Wed, 15 Jun 2016 12:08:10 -0700

On Wed, 15 Jun 2016 09:58:20 +0100
Ben Laurie <[email-masked]> wrote:

> >> >>> 1. A CA issues a legitimate certificate for www1.example.com
> >> >>> and logs a pre-certificate for ?.example.com.  A monitor for
> >> >>> www2.example.com which, except for the DNS name, has exactly
> >> >>> the same details (including serial number and public key) as
> >> >>> the certificate for www1.example.com.  The CA does not log a
> >> >>> 3. An attacker serves the rogue certificate for
> >> >>> www2.example.com along with the SCT for the ?.example.com
> >> >>> pre-certificate.  TLS clients accept it because the
> >> >>> TBSCertificate that is reconstructed from the certificate
> >> >>> matches the TBSCertificate of the pre-certificate.  Monitors
> >> >>> have no idea that there is a rogue certificate for
> >> >>> www2.example.com.
> >> >>
> >> > (with CA collusion) pivot to attacking other hosts whose names
> >> > match the same redaction pattern.
> >> >
> >> > The second certificate would never be logged.  The way that
> >> > logging is enforced is that clients reject certificates that
> >> > aren't accompanied by a valid SCT.  But since an SCT for the
> >> > first certificate's pre-certificate can be used to prove that
> >> > the second certificate was logged, clients can be tricked into
> >> > accepting the second certificate even if it was never logged.
> >> >
> > expectation is that the certificate only works with
> > www1.example.com. But if the domain owner requests redaction, they
> > are now making it possible for the CA is misbehave and issue
> > certificates for hosts besides www1.example.com that will be
> > accepted by clients and not detected by the domain owner's
> > monitor.  That seems like a violation of user expectation.
> 

I suppose that one's perspective on this matter depends on what
information they think a logged redacted pre-certificate should be able
to convey to the domain owner.

If an unredacted, non-wildcard pre-cert is logged, everybody knows what
DNS name the cert is used with.

If a wildcard pre-cert is logged, nobody knows what DNS name the cert
is used with.

I think that redacted pre-certs should occupy a middle ground: the
domain owner (given the right information) knows what DNS name the cert
is used with, but no one else does.

This is why I think my attack is a problem.  But if one thinks a
redacted pre-cert shouldn't convey any more information to a domain
owner than a wildcard pre-cert, then the attack is not a big deal.

Regards,
Andrew