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

[Nick Sullivan <[e-mail]>]

On Fri, May 19, 2017 at 10:44 AM Al Cutter <[e-mail]> wrote:

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

This is prevented by requiring the get STHs endpoint to provide a
consistent sequence of entries over time and making sure that auditors
track it. Alternatively, the chaining idea also achieves this, and so does
logging STHs as you suggest.

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