Subject: [Trans] STH Discipline & Security Considerations

From: Richard Barnes <[email-masked]>
Date: Fri, 3 Mar 2017 13:24:51 -0500

Hey all,

I wanted to follow up on my earlier comments and a bunch of side
conversations
I've had with people since then with a revised change proposal that I think
can
get -rfc6962-bis to a point we can live with.

tl;dr:
1. We/Mozilla can live with the Merkle tree for now, though we/community
might
   ultimately want something different later
2. At a systemic level, we need to move toward servers providing inclusion
   proofs, but -rfc6962-bis provides sufficient tools for this
3. We need to better document "STH discipline", and define a "canonical STH"
   for each element in the log
4. We need to update the security considerations to describe more clearly
the
   implications of various levels of auditing

I'm willing to write up a PR for (2); EKR has volunteered for (3).

# Auditing Models

There are basically two approaches to auditing available to clients:

1. Prospective: Browser does auditing checks at TLS connection time
2. Retrospective: Browser does auditing checks after TLS connection time

Prospective checking provides better assurance than retrospective, since it
prevents any harm that would come from a mis-issued, improperly-attested
certificate.  The cost is that the server has to send enough information the
cert and the browser has to cache enough information about the log that the
two
can be married up without further requests.

In practice, however, it looks like some degree of retrospective checking
will
be necessary even in browsers that support the cache enough information for
prospective checking.  On the one hand, if an inclusion proof can't be
embedded
in a cert, then we can't count on all server operators providing it (via
OCSP /
TLS).  On the other hand, including proofs in certs imposes issuance delays
that will not be acceptable in many circumstances, even if it is O(minutes).

And given Eran's SSL proxy proposal, with the amendments I suggested, I'm
now
pretty well convinced that the fetches you need for retrospective validation
can be done privately with something short of Tor (just).  The scalability
problems are bad, but probably ultimately workable.

It should be clear that either of these models work much better if the
server
provides inclusion proofs.  Together with the STH discipline notions below,
this would enable prospective auditing for all but very new certificates if
a
browser is willing to cache STHs.  Even in cases where CT information must
be
fetched, having the server send an inclusion proof would mean that the only
fetch would be for consistency, which is a less privacy-sensitive, more
cacheable query.

# STH Discipline

Either style of auditing also works better if logs have a notion of "STH
discipline", in the following sense:

1. The official state of the log comprises a sequence of STHs issued at
   specified intervals.

2. For each certificate in the log, there is a single "canonical STH" to
which
   the log will produce an inclusion proof.  Proofs to other STHs are done
by
   adding a consistency proof to the inclusion proof.

This property makes things work more smoothly in both auditing models:

- If the browser is willing to cache STHs, this tells the browser exactly
which
  STHs it needs to cache in order to validate all inclusion proofs.

- Everything is more cacheable, since there's only one inclusion proof per
  certificate, and a limited set of heads among which consistency needs to
be
  calculated.

- Cacheability means that the fetches of inclusion proofs get greater
privacy
  benefit from caching, since they depend only on the certificate, not the
STH
  that the client is using.  Likewise for consistency proofs, because of the
  reduced variety.

>From a protocol point of view, I haven't done a thorough evaluation of the
document, but there are at least a few things you would want to make this
model
work:

- Prose that articulates the above bounds on logs / inclusion proofs / STHs.
  Probably a notion of "STH issuance frequency" parallel to MMD.

- A field in an SCT that indicates the canonical STH for the certificate in
  question.  Possibly a serial number in STH that SCTs could refer to.

- An API endpoint for fetching STHs in the official sequence (in addition to
  the current one, which is the only option right now).

If this line of thinking sounds generally sane to people, I'll take a pass
through the document and make some concrete proposals.

Thanks,
--Richard

---

From: Andrew Ayer <[email-masked]>
Date: Fri, 3 Mar 2017 11:09:50 -0800

On Fri, 3 Mar 2017 13:24:51 -0500
Richard Barnes <[email-masked]> wrote:

> # STH Discipline
> 
> Either style of auditing also works better if logs have a notion of
> "STH discipline", in the following sense:
> 
> 1. The official state of the log comprises a sequence of STHs issued
> at specified intervals.
> 
> 2. For each certificate in the log, there is a single "canonical STH"
> to which
>    the log will produce an inclusion proof.

To be clear, would there still be a way to get inclusion proofs to
non-canonical STHs?  Clients wouldn't have to use them if they didn't
want to.

> Proofs to other STHs are
> done by
> - If the browser is willing to cache STHs, this tells the browser
> exactly which
> - Everything is more cacheable, since there's only one inclusion
> proof per certificate, and a limited set of heads among which
> consistency needs to be
>   calculated.
> 
>   benefit from caching, since they depend only on the certificate,
> not the STH
>   that the client is using.  Likewise for consistency proofs, because
> of the reduced variety.
> 
> document, but there are at least a few things you would want to make
> this model
> work:
> 
> - Prose that articulates the above bounds on logs / inclusion
> proofs / STHs. Probably a notion of "STH issuance frequency" parallel
> to MMD.
> 
> - A field in an SCT that indicates the canonical STH for the
> certificate in question.  Possibly a serial number in STH that SCTs
> could refer to.

Is this necessary?  Why not define the canonical STH as the first STH
issued after the SCT (based on timestamp)?

> - An API endpoint for fetching STHs in the official sequence (in
> addition to the current one, which is the only option right now).

+1. I think any privacy-preserving auditing mechanism will need such an
endpoint so that STHs can be reliably distributed to clients.

Regards,
Andrew

---

From: Al Cutter <[email-masked]>
Date: Fri, 3 Mar 2017 19:53:27 +0000

On Fri, Mar 3, 2017 at 6:24 PM, Richard Barnes <[email-masked]> wrote:

> I've had with people since then with a revised change proposal that I
> think can
> cert and the browser has to cache enough information about the log that
> the two
> this would enable prospective auditing for all but very new certificates
> if a

Here's a half-baked idea for a third (well, kinda), following on from
today's theme of embedded proofs + STH, and an ecosystem with more open
logs.

Can we trust that some fraction of the logs in the ecosystem are honest?
If so, then it feels like mostly the danger comes come allowing an issuer
of cert to select which logs they want to log to, because they can choose
their naughty log operator friends who'll collude.

How about if we reduce the choice of logs, for example:
1. we define a function of, say, the hash of the log's public key to
determine which of a fixed number of "groups" each log belongs to
2. we define a function of the hash of a precert (might be the same as [1])
which returns 1 (or perhaps several) groups to which that precert must be
logged.
2. anyone creating a precert must log to the logs in the group(s) defined
by the function in [2]
3. logs & CAs do their thing, proofs + STHs are embedded, certs are built,
and websites updated.
4. the RP can verify the validity of the proofs, and the sigs on the STHs,
but they can also verify that the STHs are from the set of logs the well
known function [2] says they should for the precertificate they
re-construct from the cert they were served (similar to how embedded SCTs
are verified currently)

IANAC, but I'm thinking that perhaps if the functions in [1] and [2] are
sufficiently indistinguishable from random the client has reasonable
confidence (given that we trust some fraction of the ecosystem is honest)
that a bad cert will be detected by monitors and the game's up, and no need
to talk to anyone (unless the proofs/sigs don't work and they want to tell
someone about it).

I suspect this precise scheme might be weak because of the low number of
groups; perhaps it's too easy to "mine" log keys and percerts to line up
groups, but maybe there are mitigations for that (e.g. making the hashing
more expensive*, and/or requiring the not_before to be within some window
of the embedded SCT timestamps so your mining work is wasted if you take
too long, or maybe the groups functions also take issuance time into
account, or only takes the domain from the first SAN, or the OU, or ... - I
dunno, I said it was half-baked! Anyway, I'm sure there are people here who
know a lot more about this sort of thing than I do.

Perhaps you can pull a similar trick for logs too - forcing logs to commit
to tree timelines in a set of locations defined by a function of the hash
tree root from the STH they're logging (this is really a tweak to an idea
Ben had about gossip a while back).

* On the expensive hashing, I realise that it'd be undesirable for some
classes of UAs (mobiles in particular) to have to perform the expensive
hashing to verify the set of logs, but since I'm rattling on anyway, I
vaguely recall a scheme from somewhere else (I don't remember where, sadly)
which was cute:  we define the hashing function to be, say, 100,000,000
rounds of SHA256 where each round is SHA256(hash_n-1||precert hash), then
we embed the 99,999,999th hash somewhere in the cert so that the client can
recalculate the last round using that and the reconstructed precert and
verify the STHs come from the right group(s) - expensive for the logger,
but cheap for the verifier.

Ok, I'll stop now.
Have a nice weekend, all.

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

---

From: Richard Barnes <[email-masked]>
Date: Mon, 6 Mar 2017 14:12:37 -0500

> non-canonical STHs?  Clients wouldn't have to use them if they didn't

I could go either way.  My preference would probably be to make it OPTIONAL
for a log to provide such proofs, because caching.  The client can always
just fetch the canonical proof and consistency.  (Maybe that needs to be a
new endpoint.)

> issued after the SCT (based on timestamp)?

The reason you want an indicator in the SCT is so that you know which STH
to ask for, e.g., if you're fetching a consistency proof.  Otherwise, you
have to scan around for the right one.

> endpoint so that STHs can be reliably distributed to clients.

Thanks for the feedback!

--Richard

---

From: Ben Laurie <[email-masked]>
Date: Tue, 7 Mar 2017 18:10:20 +0000

> issued after the SCT (based on timestamp)?

That doesn't work - the cert may not have been included in the log by then.

That said, not sure how Richard's proposal works, either - in general, the
front-end that returns the SCT cannot know when the cert will be included,
and hence cannot predict the relevant STH.

Not entirely sure I agree with the initial premise anyway.

---

From: Richard Barnes <[email-masked]>
Date: Tue, 7 Mar 2017 14:00:01 -0500

> and hence cannot predict the relevant STH.

Yes, this proposal would require that there be enough coordination between
log ingress and storage that the front-end could know under which STH a
cert would land.  I realize that might not be the case now, but is it
unachievable?

--Richard