Re: [Trans] Providing the history of STHs a log has issued (in 6962-bis)

[Eran Messeri <[e-mail]>]

Following an out-of-band discussion with Andrew (summarized below), I
propose the following, to make progress on 6962-bis:
* Add get-sths as a mandatory API.
* Defer discussion on chaining of STHs to a follow-up document: It's
evident that we need to do more thinking about it. Since we have an STH
extensions mechanism, an extension including a reference to a past STHs can
be added in a later document.

It seems to me that STH chaining is set out to achieve a goal that's
different than how CT currently operates; I'm also not confident it can
achieve this goal. Because further discussion on both topics is necessary,
I don't think it's right to add this feature to 6962-bis yet or gate
6962-bis on it.

CT's current design aims to detect a single log presenting different views
(i.e. different trees) to different parties by exchanging STHs between
observers.
A variant with stronger security guarantees aims to have individual clients
have the entire STH history so they cannot be presented with inclusion
proofs to different trees at different times. Chaining STHs aims to achieve
that (as far as I understand).

However it seems to me chaining STHs does not prevent a client, that
fetches STHs individually, from being tricked into accepting inclusion
proofs to different trees presented by the same log:

A log could produce the following chain of STHs:
STH 1 with root hash Z, then STH 2 with root hash Y = HASH(Z ||
hash(entry_1)), prev_hash = Z, then STH 3 with root hash X = HASH(Z ||
hash(entry_2)), prev_hash = Y (assuming the tree size with STH1 is an exact
power of 2, just for simplicity, as the new root hash would be exactly
HASH(0x01 || Z || hash(new entry))).
STH 1 chains to STH 2 that chains to STH 3, but STH 2 and STH 3 each have,
as their root hash, hash of Z, appending a different entry every time (the
tree is forked at root hash Z).
To the rest of the world, the log would present a chain of hashes that is
STH 1 and  STH 3' - which has the same root hash as STH 3 but prev_hash = Z.
The client could not know that it's being presented with a chain of STHs
that are for different trees unless it has consistency proofs between
(STH1, STH2) and (STH2, STH3).

It seems to me that:
- Clients still need to get (via push or pull) consistency proofs between
STHs and validate them.
- STHs still have to be gossiped for a single entity (monitor) to be in
possession of STHs that cannot be proven consistent.

But maybe there are other ways to chain STHs, so I'd like to follow up on
that independently of 6962-bis.

Eran


On Wed, May 17, 2017 at 6:17 AM, Andrew Ayer <[e-mail]> wrote:

> On Mon, 15 May 2017 17:18:22 +0100
> Eran Messeri <[e-mail]> wrote:
>
> > As it has been pointed out to me, the STH history API, even with the
> > proposed changes of adding a sequence number to issued STHs, or
> > requiring an STH refers to a previous STH, would not prevent
> > backdating of STHs in a meaningful way - see explanation below.
>
> This is not the only reason for a get-sths API.  The other reason is that
> it facilitates the prospective auditing model favored by Mozilla, which is
> why Richard Barnes has asked for it[1].
>
> There seems to be a general agreement that in the long term, TLS
> servers should send inclusion proofs due to the difficulty of auditing
> SCTs robustly and privately.  6962-bis already provides a way to embed
> inclusion proofs in the certificate, OCSP response, or TLS handshake.
> However, this is just shifting the problem to auditing STHs.
> Unfortunately, gossiping STHs or requesting consistency proofs has
> similar privacy problems[2].
>
> An alternative to auditing STHs on-the-fly is for clients to download and
> cache batches of every STH the log has produced.  An inclusion proof would
> be considered valid as long as it is based on one of the cached STHs.
>
> Currently, there are two obstacles to doing this:
>
> 1. Getting the STHs.  Calling get-sth repeatedly isn't robust, because an
> STH might be missed.  A get-sths endpoint allows all STHs to be obtained
> so they can be cached.
>
> 2. Auditing the STHs.  Obtaining consistency proofs for every STH would
> require a lot of bandwidth.  For this reason, Richard Barnes called
> for the use of a Haber-Stornetta hash chain[3], which would be a rather
> drastic change to the protocol.
>
> I have a simpler proposal: have each STH contain the hash of the previous
> STH.  This provides the same properties as a Haber-Stornetta hash chain
> while making only a modest, backwards-compatible change to the protocol.
> Clients need only gossip the latest STH to be confident that everyone
> has the same view of the log, including its entire STH history.  Therefore,
> there is no need for clients to audit the consistency of each STH, as this
> job can be left to auditors who are guaranteed to have the same view of
> the log's STH history.
>
> A get-sths endpoint, plus embedding the hash of the previous STH in each
> STH, plus the existing ability to embed inclusion proofs, will permit
> RFC6962-bis to be used with a robust, privacy-preserving, and prospective
> auditing model, while remaining conceptually backwards compatible with
> the auditing model of RFC6962. This seems like a win-win to me.
>
> Regards,
> Andrew
>
>
> [1] https://mailarchive.ietf.org/arch/msg/trans/
> Zm4NqyRc7LDsOtV56EchBIT9r4c
>
> [2] Although an STH doesn't uniquely identify a certificate like an SCT
> does, in practice a client auditing or gossiping a particular STH may
> be a very strong indicator that it just saw a particular certificate.
> For example, if 10 certificates embed an inclusion proof to STH X,
> but 9 of those certificates are expired or aren't used on the public
> Internet, then a client auditing STH X probably just connected to the
> server identified by the 10th certificate.
>
> [3] https://mailarchive.ietf.org/arch/msg/trans/gO_
> DFW3v9FmBCOek_hifZ6KL368
>