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

[Al Cutter <[e-mail]>]

On Fri, May 19, 2017 at 3:49 PM, Eran Messeri <[e-mail]> wrote:

> 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.
>

In the ticket you said:
"The problem it [get-sths API] solves is the lack of ability to verify that
the log did not breach the MMD throughout its lifetime: A submission's
timestamp is available via get-entries, but unless a monitor has observed
STHs issued by the log around the time an entry was created for it, there's
no proof that the entry was incorporated within the MMD."

but you later acknowledged that a get-sths API without some extra sprinkles
*somewhere* doesn't actually solve that problem because there's nothing
stopping a Log from going back and creating a few extra "old" STHs to
cover, say, a period when its signing infrastructure was down, which it'll
happily return to you when you call get-sths at a later date.

I admit I'm not really that familiar with process of defining RFCs, but it
seems weird to me to add a mandatory API, which, as defined in the standard
which makes it mandatory, doesn't solve the problem it was added to solve...


> 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.
>

The hash chaining is only a commitment to a claim of which blob is the
immediate predecessor of this other blob, you still need to verify the
correctness of the blobs in context, of course.

At least for the monitoring-MMD use-case, it seems like a similar thing
could be achieved by requiring Logs to also log their own STHs, even
allowing for the vagaries of pending queues that'd put an MMD-sized window
on how far back in time a log could create old STHs to cover up MMD-blown
fails.

The monitors wouldn't then need a get-sths call (although if there were
other use cases for that API then the results from it would at least be
verifiable by monitors).
A thought is that you'd then have the ability to query a Log using
get-proof-by-hash for an STH you're holding to see if it can prove it was
logged, I'm not sure if that's useful at the moment, but my Friday evening
brain finds it amusing for some reason.

The obvious next step would be to require Logs to log their STHs with a
quorum of other Logs. Assuming all Logs are not collaborating, that makes
it quite a lot harder for anyone to pull off split views, and of course you
can now do the same get-proof-by-hash call for your STH on other logs now,
if you didn't mind trying a a number of logs (or if you already knew in
which Logs to look*).

*perhaps the set of target logs for a given STH could be defined by some
function of the day or week that the STH timestamp corresponds to -
something which changes infrequently enough that Logs can't simply not
issue an STH during that period or they'd blow their MMD - the intention
being to narrow the set of logs you'd have to look in, but also make it
harder to to choose colluding Logs.



> 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/Zm4NqyRc7LDsOtV5
>> 6EchBIT9r4c
>>
>> [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
>>
>
>
> _______________________________________________
> Trans mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/trans
>
>