Subject: [Trans] Suggesting an alternative mechanism for name redaction

From: Eran Messeri <[email-masked]>
Date: Fri, 17 Jun 2016 12:02:12 +0100

This is a proposal for an alternative mechanism to redact domain names such
that would shift most of the implementation complexity from the client to
the issuer, while being functionally equivalent to the redaction mechanism
in the current draft.

In short: Rather than describe how the client should modify the labels in
SAN extension to get to the redacted form that was logged, the issuer will
generate the redacted SAN extension and log it, as a part of the
TBSCertificate submitted to the log.

Details:
- The issuer, when generating a TBSCertificate for submission to the log,
will add a "redacted SAN" X.509v3 extension with what the current draft
specifies should be in the SAN extension (i.e. dNSNames with redacted
labels, ?.example.com).
- The TBSCertificate to be submitted will *not* have a SAN extension
(thanks Rob for this suggestion).
- The log will issue an SCT that covers the submitted TBSCertificate (+
issuer key hash as currently described).
- The issuer then can issue the unredacted certificate by adding a SAN
extension with the unredacted names (and potentially embedding the obtained
SCTs).
- The client, when receiving the unredacted certificate, simply removes the
SAN extension (and the embedded SCTs extension, if present), then validates
the signature from the SCT over it.
- Then client can then extract the redacted domain names from the "redacted
SAN" extension, compare them to the unredacted domain names from the SAN
extension and apply a policy to determine if the redaction was appropriate.

Benefits:
- The only manipulation clients have to do to validate an SCT is to remove
another X.509 extension, which it already has to do for embedded SCTs
(eliminating both the error-prone process of reconstructing the redacted
labels and the need to re-assemble a TBSCertificate).
- Clients have both the redacted and unredacted domain names and can still
choose to apply any desired policy.

Disadvantages:
- The commonName in the subject field cannot be redacted this way.
- monitors will have to go through another hoop to make sense of the logged
entry (likely by assigning the value of the "redacted SAN" extension to the
SAN extension before using a standard parser to parse the TBSCertificate).

Assuming this mechanism is technically sound, I would not object to keeping
redaction in 6962-bis if implemented this way.

Eran

---

From: Andrew Ayer <[email-masked]>
Date: Fri, 17 Jun 2016 12:41:10 -0700

Hi Eran,

I really like your proposal.  I like it so much that I've implemented
the client-side functionality to reconstruct the TBSCertificate and
do basic policy checks on the redacted labels.  It took me about 45
minutes and I found it very straightforward.  (Note I didn't implement
the over-redaction check, but this requires the same code no matter
how redaction is defined.) I didn't get bogged down like I did with
my other implementation.  I think this is a huge win for reducing
client-side complexity.

I would still like to see the SCT reuse attack fixed.  Fortunately,
combined with your proposal I think the complexity of fixing the attack
is manageable.  Here's what I propose (I've implemented the client-side
parts of this too):

1. When issuing a redacted certificate, the issuer generates a random
128-bit SALT.  The issuer places this SALT in a "Redacted Labels
Salt" X.509v3 extension in the unredacted certificate, but not in the
logged TBSCertificate.

2. When redacting a LABEL in the "redacted SAN" extension, the issuer
replaces LABEL with "?"||HEX(HASH(SALT||LABEL)) instead of just "?" (|| is
string concatenation).

3. When reconstructing the TBSCertificate to verify the SCT, the client
removes the "Redacted Labels Salt" extension, just as it currently
removes the SAN extension and the Transparency Info extension.

4. If the client desires stronger SCT matching, it checks that each
redacted label in the redacted SAN extension matches the corresponding
label in the SAN extension, by computing HASH(SALT||LABEL), where SALT
is taken from the "Redacted Labels Salt" extension.

Complexity analysis:

1. There is additional complexity imposed on issuers, but only on
issuers who choose to offer redacted certificates, so I believe this is
justifiable.

2. Clients need to remove an additional extension when reconstructing
the TBSCertificate, but this is trivial and they already have to remove
two other extensions anyways.

3. Clients which desire stronger SCT matching have to examine the
"Redacted Labels Salt" extension and compute some hashes, which adds
modest complexity.  However, if a client doesn't desire the stronger SCT
matching or can't handle the added complexity for some reason, they can
skip this step (they'd ignore everything after the ? in a redacted
label) and have exactly the same complexity and security properties as
without my proposal.

If I'm not mistaken, your proposal plus my proposal address all the
technical/implementation concerns that have been raised with
redaction.  There will still be policy concerns, such as whether
redaction is even a good idea, but those can be fleshed out by
clients.  I think 6962-bis would be delivering a solid technical
solution for redaction with these changes.

Regards,
Andrew

P.S. My implementation is here: https://github.com/AGWA-labs/ctredactionexperiment

The diff to implement Eran's proposal on top of the RFC6962-compliant
code I already had:
https://github.com/AGWA-labs/ctredactionexperiment/commit/fbeaa9f3d91ebfd1eb614a657009222b25f37724

The diff to implement my proposal for hash-based label redaction on top
of Eran's proposal:
https://github.com/AGWA-labs/ctredactionexperiment/commit/d46cfee8eb4374e87c601317f6faa98c4f2e189e

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Fri, 17 Jun 2016 17:33:30 -0400

> TBSCertificate submitted to the log.

I like this proposal.

A clarification:

It took me a second to realize that the "redacted SAN extension" is
*also* present in the issued certificate, alongside the normal SAN
extension.  the SCT is only over the TBSCertificate without the normal
SAN extension.

> - The commonName in the subject field cannot be redacted this way.

This is not a problem.  the CA/Browser Forum Baseline requirements say
that the commonName in the Subject field is "Deprecated (Discouraged,
but not prohibited)"

A user who really cares about redaction can simply leave out the
commonName in the Subject field.

I also think Andrew Ayer's extension of this proposal (the "Redacted
Labels Salt" extension) is an elegant fix to the remaining technical
concern about redacted SCT abuse.

I would support their inclusion in 6962-bis.

           --dkg

---

From: Rob Stradling <[email-masked]>
Date: Mon, 20 Jun 2016 14:39:00 +0100

I think Eran's proposal is a definite improvement (compared to the 
current 6962-bis redaction mechanism), because it makes client 
implementation simpler and more robust.

I agree that Andrew's extension of Eran's proposal is an elegant fix to 
the SCT re-use attack.  However, I'd like to propose an alternative...

1. When redacting a LABEL in the "redacted SAN" extension, the issuer 
replaces LABEL with "?"||HEX(HASH(SERIAL_NUMBER||LABEL)) instead of just 
"?".

2. If the client desires stronger SCT matching, it checks that each 
redacted label in the redacted SAN extension matches the corresponding 
label in the SAN extension, by computing HASH(SERIAL_NUMBER||LABEL), 
where SERIAL_NUMBER is the serial number of the certificate.

Advantages:
   - Slightly simpler than Andrew's proposal.  (i.e. no SALT needs to be 
generated, put into a certificate extension, then removed to reconstruct 
the TBSCertificate).
   - Provides a (partial) technical solution to 'un'redaction (which is 
something that needs to be addressed before Chrome will ever support 
redaction [1]): If a domain owner's certificate team observes an 
unexpected precertificate, they can calculate HASH(SERIAL_NUMBER||LABEL) 
for all of the LABELs they manage.

Disadvantages:
   - A dictionary attack might reveal the LABEL.  It wouldn't be 
possible to compute a rainbow table to generalize this attack, because 
the SERIAL_NUMBER is different for each certificate.

If there's an effective way to solve the 'un'redaction problem purely 
via policy, then I'd say Andrew's proposal is superior.  However, if 
there isn't, then perhaps my proposal is a necessary compromise.

[1] 
https://groups.google.com/a/chromium.org/d/msg/ct-policy/vsTzv8oNcws/imuC3iloBwAJ

-- 
Rob Stradling
Senior Research & Development Scientist
COMODO - Creating Trust Online
Office Tel: +44.(0)1274.730505
Office Fax: +44.(0)1274.730909
www.comodo.com

COMODO CA Limited, Registered in England No. 04058690
Registered Office:
   3rd Floor, 26 Office Village, Exchange Quay,
   Trafford Road, Salford, Manchester M5 3EQ

This e-mail and any files transmitted with it are confidential and 
intended solely for the use of the individual or entity to whom they are 
addressed.  If you have received this email in error please notify the 
sender by replying to the e-mail containing this attachment. Replies to 
this email may be monitored by COMODO for operational or business 
reasons. Whilst every endeavour is taken to ensure that e-mails are free 
from viruses, no liability can be accepted and the recipient is 
requested to use their own virus checking software.

---

From: Andrew Ayer <[email-masked]>
Date: Mon, 20 Jun 2016 21:35:31 -0700

Hi Rob,

On Mon, 20 Jun 2016 14:39:00 +0100
Rob Stradling <[email-masked]> wrote:

> replaces LABEL with "?"||HEX(HASH(SERIAL_NUMBER||LABEL)) instead of
> just "?".
> 
> redacted label in the redacted SAN extension matches the
> corresponding label in the SAN extension, by computing HASH
> (SERIAL_NUMBER||LABEL), where SERIAL_NUMBER is the serial number of
> the certificate.

I'm a little uneasy about using the serial number, because of
the ways that serial numbers can be, and are, incorrectly encoded (e.g.
not minimally encoded, or a "positive" integer with the MSB set).  I
think it's simpler and more robust for the client to take the salt out
of an extension, so it can be treated as an opaque blob and therefore
be unaffected by the vagaries of parsers.

> unexpected precertificate, they can calculate HASH(SERIAL_NUMBER||
> LABEL) for all of the LABELs they manage.

Another way to support "un-redaction" is to just leave the salt
extension in the pre-certificate instead of removing it.  I'd prefer
that approach if this style of un-redaction is desired.

Regards,
Andrew

---

From: Steve <[email-masked]>
Date: Tue, 21 Jun 2016 15:56:59 +0000

If a client can un-redact, what's the point of redaction?

Kind regards,
Steve

On Tue, Jun 21, 2016, 12:35 AM Andrew Ayer <[email-masked]> wrote:

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

---

From: Eran Messeri <[email-masked]>
Date: Tue, 21 Jun 2016 17:16:08 +0100

FYI proposed text for this change (unreviewed) is in
https://github.com/google/certificate-transparency-rfcs/pull/175

> If a client can un-redact, what's the point of redaction?
A  monitor of the log which observes a certificate with redacted dNSName
fields and has a list of subdomains for that domain (for example, because
it is operated by the legitimate domain owner who knows about all the
subdomains registered under this domain) can distinguish between a redacted
cert for one of the known subdomains and a redacted cert for an unknown
subdomain.
TLS clients have to receive the un-redacted certificate, but having the
redacted dNSNames alongside the unredacted ones allows clients to apply a
policy for determining whether the redaction is acceptable or not.

> Per this feedback, the proposed text requires the use of all bytes used to
encode the serial number, including the tag and length bytes.

> The reason I'm uneasy with the salt as a separate extension is it adds
some complications (another extension to remove, another thing to get right
when matching the redacted labels with unredacted ones). As far as I can
tell, the serial number could serve the same purpose.

---

From: Steve <[email-masked]>
Date: Tue, 21 Jun 2016 16:26:44 +0000

So a real world situation has been brought forward that requires CT to care
about visibility of subdomains when ownership of name property is granted
from ICANN at the level of the visible content in a redacted name?

On Tue, Jun 21, 2016, 9:16 AM Eran Messeri <[email-masked]> wrote:

>> Per this feedback, the proposed text requires the use of all bytes used
> to encode the serial number, including the tag and length bytes.
>
>>

---

From: Rob Stradling <[email-masked]>
Date: Wed, 22 Jun 2016 13:56:23 +0100

> be unaffected by the vagaries of parsers.

Hi Andrew.  I agree that incorrect encodings of the serial number are a 
concern.

What if we say that SERIAL_NUMBER must consist of the INTEGER tag, 
length and contents (rather than just the 
potentially-encoded-differently contents)?