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

From: Eran Messeri <[email-masked]>
Date: Thu, 4 May 2017 13:41:59 +0100

I'm looking for feedback on the proposal to add an API endpoint which would
provide access to historical STHs issued by the log (
https://trac.ietf.org/trac/trans/ticket/163).

I personally think it's a good idea to have such an API since it'd allow
auditing a log for past compliance with the MMD requirement.

Rob Stradling has sent a PR
<https://github.com/google/certificate-transparency-rfcs/pull/200/> for
this.

Eran

---

From: Paul Hadfield <[email-masked]>
Date: Thu, 4 May 2017 14:01:49 +0100

I support the addition of this API; Rob's PR
<https://github.com/google/certificate-transparency-rfcs/pull/200/> was
created in response to my original proposal
<https://mailarchive.ietf.org/arch/msg/trans/AsxrWg9L1hgxt-g3PSlip73DvYs>
for this made Oct, 25 2016.

As the operator of a CT Monitor, I could use the STH history API to perform
historic analysis of the logs my monitor visits. This includes
determination of whether MMD violations occurred in the past.

Without this API, CT Monitors that ingest a log's entries from STHm to STHn
(n>m) could incorrectly identify an MMD violation, as it is possible for
them to have missed an STH that sits between m and n.

With this API, a log operator that is incorrectly called out for a MMD
violation has the ability to demonstrate that the monitor drew an incorrect
conclusion as a consequence of not observing the log's complete STH
sequence.

Paul

On Thu, May 4, 2017 at 1:41 PM, Eran Messeri <[email-masked]> wrote:

> I'm looking for feedback on the proposal to add an API endpoint which
> would provide access to historical STHs issued by the log (

---

From: Andrew Ayer <[email-masked]>
Date: Thu, 4 May 2017 08:26:36 -0700

On Thu, 4 May 2017 13:41:59 +0100
Eran Messeri <[email-masked]> wrote:

> I personally think it's a good idea to have such an API since it'd
> allow auditing a log for past compliance with the MMD requirement.
> 
> <https://github.com/google/certificate-transparency-rfcs/pull/200/>
> for this.

I support adding this endpoint, and I think it should be mandatory.

In addition to helping monitors, this endpoint would allow a TLS client
vendor (e.g. Mozilla) to aggregate all the STHs for a log and ship them
in bulk to clients so that clients can easily verify a stapled
inclusion proof without needing to make any network access.  That
should please Mozilla.

Regards,
Andrew

---

From: Nick Sullivan <[email-masked]>
Date: Thu, 04 May 2017 19:20:47 +0000

I'm also in favor of this change. I would further suggest that this list be
required to be consistent, monotonically increasing and that the results of
this API be something that monitors exchange information about.

On Thu, May 4, 2017 at 8:28 AM Andrew Ayer <[email-masked]> wrote:

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

---

From: Andrew Ayer <[email-masked]>
Date: Thu, 4 May 2017 12:34:47 -0700

On Thu, 04 May 2017 19:20:47 +0000
Nick Sullivan <[email-masked]> wrote:

> I'm also in favor of this change. I would further suggest that this
> list be required to be consistent, monotonically increasing and that
> the results of this API be something that monitors exchange
> information about.

Hi Nick,

Could you explain what you mean by "consistent"?

As for monotonically increasing, does the following language in Rob's
PR match what you mean?

"These STHs SHALL be ordered chronologically by timestamp, oldest
first, beginning with the earliest STH in the specified range."

The gossip draft defines an STH pollination mechanism that monitors can
use to exchange STHs that they observe.  Would this work, or were you
thinking about something else?

Regards,
Andrew

---

From: Nick Sullivan <[email-masked]>
Date: Thu, 04 May 2017 20:58:16 +0000

By consistent I mean that if a sequence of STHs such as (A, B, C) are
presented on day 1, that a different sequence is not presented on day 2 (A,
C) or (A, D, B, C).

Rob's language works in term of chronological order.

STH pollination could be a way to support auditing this, but I don't think
it's sufficiently robust as currently defined. To prevent STHs from going
missing, or for new STHs to appear after the fact, STHs should be exchanged
along with metadata indicating the previous and (if it exists yet) the next
STH in the tree.

---

From: Andrew Ayer <[email-masked]>
Date: Fri, 5 May 2017 10:09:10 -0700

On Thu, 04 May 2017 20:58:16 +0000
Nick Sullivan <[email-masked]> wrote:

> presented on day 1, that a different sequence is not presented on day
> 2 (A, C) or (A, D, B, C).

The PR doesn't currently say the log must retain and return all STHs
it has ever signed.  That should be added.  Such language, plus the
existing chronological ordering requirement, plus the requirement that
STH timestamps be unique ("Each subsequent timestamp MUST be more
recent than the timestamp of the previous update") should ensure
consistency, right?

> STH pollination could be a way to support auditing this, but I don't
> think it's sufficiently robust as currently defined. To prevent STHs
> from going missing, or for new STHs to appear after the fact, STHs
> should be exchanged along with metadata indicating the previous and
> (if it exists yet) the next STH in the tree.

To be an effective auditing mechanism, this information needs to be
signed by the log.  Otherwise, a monitor could lie about what it has
seen.  Perhaps the STH could contain the timestamp of the previous
STH.  If it did, I believe that STH pollination would be sufficient for
detecting STHs that go missing or appear after the fact.

That said, is there a compelling security need for this to be
auditable?

Regards,
Andrew

---

From: Brian Smith <[email-masked]>
Date: Fri, 5 May 2017 15:21:55 -1000

> them to have missed an STH that sits between m and n.

Wouldn't this require the monitor to know what time the claimed
in-between STH was generated?

Cheers,
Brian
-- 
https://briansmith.org/

---

From: Linus Nordberg <[email-masked]>
Date: Tue, 09 May 2017 01:08:36 +0200

Andrew Ayer <[email-masked]> wrote

> That said, is there a compelling security need for this to be

I'm probably missing something crucial here but if it's not auditable,
what use does it have?

It seems to me that you're transcending towards a log of STHs, which I
wouldn't mind thinking about but probably not as an ad-hoc addon to a
new get-sths API.

For the record, I'd like to express hesitance about adding an STH
history API until I understand the problem better, with apologies for
not being fully up to speed at the moment.

---

From: Eran Messeri <[email-masked]>
Date: Mon, 15 May 2017 17:18:22 +0100

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.

Because of that, I'm not sure it'll add anything to have this API - and if
we do add it, it should be an optional one.

Note that the threat I’m focusing on is detection of MMD breach: Where the
log hasn’t incorporated an entry corresponding to an issued SCT for more
than the MMD, _and a monitor could feasibly observe evidence of it_.

Here’s why, I think, adding references to past STHs wouldn’t improve the
situation:

Currently, clients cannot prove that a log has misbehaved, by serving an
STH that’s more than an MMD old. A client can claim that at a given time
the log has served it an STH that’s MMD + delta hours old, but cannot prove
it.

Additionally, close monitoring of a log can identify an MMD breach, but
only until 2*MMD - (some delta, marked d in the diagram) time has passed:
(Note in this diagram STH1 is on a tree that does not yet contain the SCT;
Only STH2 is).

Because the RFC requires an incorporation within the MMD, yet allows
serving an STH that’s up to MMD old, a log could incorporate an SCT within
the MMD but it would only be evident after more than MMD of the submission
time has passed - or it could backdate inclusion by backdating issuance of
an STH that includes the entry[0].

AFAICT requiring that STHs refers to previous ones does not change that in
any way - it does not prevent any backdating that’s now possible, nor does
it make it easier for a client to detect backdating:
* When a cunning log realises that it will fail to incorporate a pending
entry for longer than the MMD, it can immediately generate a back-dated STH
that shows it was included within the MMD, and an “innocent looking” STH
(timestamped ‘now’), that refers to the back-dated STH.
* A failure by the log to provide an STH in the “chain” of STHs (should
STHs include reference to previous ones) is equivalent to a failure by the
log to provide an STH that proves an inclusion of a particular entry: In
both cases the evidence would be STHs surrounding the entry that was not
incorporated.
* If a monitor has observed an STH that’s more than MMD old and does not
include an entry for a particular SCT, this is evidence enough for
misbehaviour.

So my concrete suggestion is then to not add get-sths entirely or make it
an optional API (because a log can only use it to incriminate itself, not
prove that it behaved).

[0] Note that backdating of selective submissions is not possible either
with or without back-references in STHs: A single submission that hasn’t
been incorporated cannot be retroactively incorporated, once the MMD has
passed, if other entries have been incorporated.

---

From: Andrew Ayer <[email-masked]>
Date: Tue, 16 May 2017 22:17:17 -0700

On Mon, 15 May 2017 17:18:22 +0100
Eran Messeri <[email-masked]> wrote:

> 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

---

From: Eran Messeri <[email-masked]>
Date: Fri, 19 May 2017 15:49:38 +0100

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

---

From: Al Cutter <[email-masked]>
Date: Fri, 19 May 2017 18:44:31 +0100

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

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

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

---

From: Brian Smith <[email-masked]>
Date: Fri, 19 May 2017 10:23:18 -1000

> which makes it mandatory, doesn't solve the problem it was added to solve...

I agree with this. This is an extra hoop for logs to jump through that
doesn't add significant value.

There are lots of ways to improve CT beyond this RFC. Things like
this, if they should be standardized at all, should go into their own
RFCs that update or even obsolete 6962-bis. Perhaps a 6962-bis-bis.

Cheers,
Brian
--
https://briansmith.org/

---

From: Nick Sullivan <[email-masked]>
Date: Fri, 19 May 2017 20:45:00 +0000

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

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

>> 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.
>> 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).
>>> [1]
>>> https://mailarchive.ietf.org/arch/msg/trans/Zm4NqyRc7LDsOtV56EchBIT9r4c
>>>
>>> [3]
>>> https://mailarchive.ietf.org/arch/msg/trans/gO_DFW3v9FmBCOek_hifZ6KL368
>>>
>>
>>

---

From: Matt Palmer <[email-masked]>
Date: Sat, 20 May 2017 11:55:56 +1000

> logging STHs as you suggest.

If you're already requiring auditors to remember what they've seen before,
why not just get them to remember the STHs they've seen, rather than having
to remember that they've seen an additive sequence of previous STHs and
verified that nothing's magically appeared?

I think the proposal to log STHs is a good one.  It provides several advantages:

* it prevents the need to have a separate "enumerate all
  prior STHs" (because you can get them all by walking the log);

* it naturally discourages a log from issuing huge numbers of STHs (for
  tracking purposes) because it bloats the log, and is extremely visible;

* it provides cryptographic proof of malfeasance (attempted tracking)
  if someone can provide an STH that isn't in the log;

* it provides cryptographic proof of blowing an MMD if the difference
  between the STH timestamp in the logged entry and the first STH that
  includes that entry are too far apart.

- Matt

-- 
"I'm a manager.  I don't do maths."
		-- Jeff Waugh, DebSIG

---

From: Brian Smith <[email-masked]>
Date: Sat, 20 May 2017 12:48:43 -1000

> verified that nothing's magically appeared?

In CT, CAs issue certificates that certify a binding of a name to a
public key. From the CT logs' perspective, the CAs are untrusted and
so we don't rely on them to provide a log of certificates they've
issued. Instead, we have CT logs maintain such logs.

Similarly, a CT log issues STHs that certify the state of the log.
>From the auditors' perspective, the CT log is untrusted. Thus, the
auditors' shouldn't rely on the CT logs to log all their STHs.
Instead, the auditors should maintain such logs. In other words, the
CT auditors should operate CT logs that operate on "certificates" that
are actually STHs.

Cheers,
Brian
-- 
https://briansmith.org/

---

From: Linus Nordberg <[email-masked]>
Date: Mon, 22 May 2017 15:49:50 +0200

Al Cutter <[email-masked]> wrote

> which makes it mandatory, doesn't solve the problem it was added to solve...

+1

> on how far back in time a log could create old STHs to cover up MMD-blown

What about requiring logs to add an entry containing the timestamp of
the STH they're about to issue? This can be thought of as a "pre-STH"
and could also include the tree size of the STH to be issued (even if
that's implied by the entries position in the log) but obviously not
tree head, nor signature. (It could include the tree size of the
previous "pre-STH" as well, for efficient retrieval of all (information
regarding) STH's.)

A reason for requiring this is that it makes the log commit to each and
every STH it's issuing, helping clients to make sure a log doesn't
violate its STH frequency count. At the time of receiving the STH, no
less.

A reason for at least _allowing_ this is that it makes it possible for
log implemenations to not have to remember another piece of data across
disk crashes, network failures, etc. In our particular case, the only
data we can remember with certainty are submitted cert chains and the
tree, besides log configuration.

This can of course be combined with adding the whole STH, including the
actual signature, _after_ it has been minted and published through
get-sth, if that's useful.

> harder to to choose colluding Logs.

Requiring STH's to be logged in other logs is interesting. It would
change a bunch of things for logs, like adding another configuration
item as well as require logs to make outbound connections. Possibly
neglectable, but in need of analysis also from an operations
perspective.

While useful, none of the above is strictly required for 6962bis in my
opinion.