Subject: [Trans] Gossip protocol

From: Kurt Roeckx <[email-masked]>
Date: Wed, 19 Oct 2016 19:00:58 +0200

Hi,

I was reading the latest draft of the gossip protocol and I have
some concerns.

I've started monitoring the CT logs. I think that under the latest
draft I became an "auditor", but the graph also still mentions a
monitor. But I don't believe I'm a "trusted auditor". There at
least seems to be confusion about the terms.

I'm mostly interested in checking that the CT logs behave like
they should, and the draft doesn't seem to be covering this, or
I'm not understanding it. How can I find all the SCTs and STHs that
the log did send to someone but didn't send to me?

It seems that as auditor I would only talk to the CT logs and
"participating HTTPS servers". It's not clear to me how I would
disover those HTTPS servers. Is this related to the "trusted
auditor"? Would an auditor work for an HTTPS site? Or would both
clients and auditors have a list of those participating HTTPS
servers, and those HTTPS servers act like some lightweight
auditor?

An older draft had a way for monitors to talk to each other, but
that all seems to have been removed.

Kurt

---

From: Tom Ritter <[email-masked]>
Date: Wed, 19 Oct 2016 14:33:30 -0500

> least seems to be confusion about the terms.

You're correct. In our draft we refer to a 'Trusted Auditor' as some
third party who gets input from clients and then uses it to facilitate
log auditing.

Whereas in the CT draft, an Auditor is someone who observes the logs
and attempts to detect misbehavior.

Technically, our 'Trusted Auditor' does not have to do auditing! It
could collect, mix, and then release users' input to an 'Auditor' who
actually performs the auditing.  Perhaps we should rename our 'Trusted
Auditor' to something different.

> I'm not understanding it.

You're right - this draft doesn't proscribe actions for an 'Auditor',
it only attempts to answer the question "How does an auditor get data
from HTTPS Clients?"

> How can I find all the SCTs and STHs that
> disover those HTTPS servers.

That's fair, we don't really say I don't think. I expect practically
speaking, that web crawling will occur and people will circulate lists
of participating HTTPS servers. If an Auditor misses some servers that
do STH Pollination, it's not a big deal as that data will be
pollinated across HTTPS servers. In contrast, servers who do SCT
Feedback will be more likely to announce to auditors "Hey, I enabled
this, start polling me."  (In both instances, HTTPS servers can also
push to an Auditor if they choose.)

> Is this related to the "trusted

It's possible for HTTPS Servers to implement some amount of auditor
functionality, but we don't expect most to.

Actions for an auditor to take is a good thing to try and document
somewhere. We _could_ put it into Gossip, but it seems like a separate
draft to me.  Off the top of my head I think the main things it would
be checking are:
- Has the log always issued a STH within the MMD
- Can I resolve all inputs (SCTs, STHs) into a single STH via
inclusion/consistency proofs (to prevent split views)

-tom

---

From: Kurt Roeckx <[email-masked]>
Date: Wed, 19 Oct 2016 22:31:18 +0200

> - Has the log always issued a STH within the MMD

I didn't look up what the real definition of the MMD is, but what
I expect is that the time from the SCT being generated until that
STH being visible is important, not the time the STH is generated.

For instance I only see Digicert's STHs 12 hour later. With Google
it depends on the log, for Pilot and Aviator it averages around 25
minutes, for Rocketeer around 100 minutes.

> inclusion/consistency proofs (to prevent split views)

Which is why I started to collect all that I can see myself. But
I'm not sure yet if this proposal will let me find all of them, or
at least all that have been send to someone.

Kurt

---

From: Tom Ritter <[email-masked]>
Date: Wed, 19 Oct 2016 17:41:19 -0500

> minutes, for Rocketeer around 100 minutes.

Yes, you're right. It's time to get data included (merged) into the
tree after a promise (SCT) had been made.

I was thinking about it in terms of "Has the log not issued at least
one STH in an X-hour period" which is related to MDD, but not the
exact same.

> at least all that have been send to someone.

As an auditor you would want to find all the servers who deploy STH
Pollination or SCT Feedback. [0] Once you do that, and start polling
from them, you'll be doing the best anyone can.

I'm not sure if there's a non-centralized, scalable way to make such a
list available to people like yourself. I mean obviously someone could
operate a public service and just collect sites that are found via
scanning or self-submitted - and I expect this will happen - but it's
not the sort of thing we'd put in a draft I don't think.

But we're open to suggestions if you have any particular ideas!

-tom

[0] You could also operate a user-facing 'Trusted Auditor' and feed
your own browsing history into it or convince others to do the same.

---

From: Paul Hadfield <[email-masked]>
Date: Tue, 25 Oct 2016 11:26:23 +0100

> one STH in an X-hour period" which is related to MDD, but not the

This is an important distinction.  For example, during the period where
Google’s Aviator log exceeded its MMD, it was still happily signing its
tree so new STHs were being produced … but it had got behind with
assigning unique sequence numbers to recently submitted certs, so
those certs were not present in the trees that had been signed, and
therefore were not reflected by the corresponding STHs. Eventually
sequencing caught up and the full backlog of certs was integrated. 

> But we're open to suggestions if you have any particular ideas!

This may be too late for 6962-bis:  I have been thinking about how an
auditor’s task might be easier if Logs were required to retain their
historic STHs and provide them on request.  It could be done by adding
an API along the lines of ‘get-sth-at-time’ or ‘get-sths-between-times’.
(where the first returns the STH with largest timestamp <= the timestamp
requested, and the second returns a list of STHs with timestamps in
the range requested).

Auditors could then retrieve the full STH history of a log without having
to have collected them over an extended period of time or having to
exchange them with other auditors - although verifying STHs gathered
by other parties is still worthwhile to detect split views.

---

From: Rob Stradling <[email-masked]>
Date: Tue, 25 Oct 2016 13:30:08 +0100

On 25/10/16 11:26, Paul Hadfield wrote:
<snip>
> This may be too late for 6962-bis:

Maybe.  Maybe not.  Let's discuss it anyway.  :-)

  I have been thinking about how an
> requested, and the second returns a list of STHs with timestamps in

Alternatively, historic STHs could be looked up by historic tree sizes.
My suggestion...

  - add an optional "tree_size" input to get-sth.

  - if the "tree_size" input is not specified, get-sth behaves as per
the current specification (i.e., it returns the very latest STH).

  - if the "tree_size" input is specified:
    - the "sth" output contains the latest STH that existed back when
the tree was that size.
    - a "next_tree_size" output is also returned, which an auditor could
then specify as the "tree_size" input to a further get-sth call.  (The
auditor would then call get-sth repeatedly until the "next_tree_size"
output is omitted, which would indicate that the very latest STH was
just returned).

> exchange them with other auditors

Indeed.  I think this would be a useful feature.

> - although verifying STHs gathered

Definitely.

-- 
Rob Stradling
Senior Research & Development Scientist
COMODO - Creating Trust Online

---

From: Kurt Roeckx <[email-masked]>
Date: Tue, 25 Oct 2016 14:57:57 +0200

> Alternatively, historic STHs could be looked up by historic tree sizes.

You can get multiple signatures for the same tree size / hash
currently. Do you want the first. the last, or some random STH in
that case?

> output is omitted, which would indicate that the very latest STH was

You can already ask for the latest one, not for the size of a
previous one.

What if there was no STH of that size? Give the larger? The
smaller? just the next / prev size?

Kurt

---

From: Rob Stradling <[email-masked]>
Date: Tue, 25 Oct 2016 14:23:59 +0100

> currently. Do you want the first. the last, or some random STH in

Ah, good point.

  "In general, there is no need to produce a new STH unless
   there are new entries in the log; however, in the unlikely event that
   it receives no new submissions during an MMD period, the log SHALL
   sign the same Merkle Tree Hash with a fresh timestamp.

Please execute "s/tree_size/timestamp/" on my previous post (which makes
it functionally equivalent to Paul's get-sth-at-time proposal, except
that my proposal merges that API into get-sth).

<snip>

-- 
Rob Stradling
Senior Research & Development Scientist
COMODO - Creating Trust Online
Office Tel: +44.(0)1274.730505
Office Fax: +44.(0)1274.730909
www.comodo.com

COMODO CA Limited, Registered in England No. 04058690
Registered Office:
  3rd Floor, 26 Office Village, Exchange Quay,
  Trafford Road, Salford, Manchester M5 3EQ

This e-mail and any files transmitted with it are confidential and
intended solely for the use of the individual or entity to whom they are
addressed.  If you have received this email in error please notify the
sender by replying to the e-mail containing this attachment. Replies to
this email may be monitored by COMODO for operational or business
reasons. Whilst every endeavour is taken to ensure that e-mails are free
from viruses, no liability can be accepted and the recipient is
requested to use their own virus checking software.

---

From: Paul Hadfield <[email-masked]>
Date: Tue, 25 Oct 2016 15:03:56 +0100

On Tue, Oct 25, 2016 at 2:23 PM, Rob Stradling <[email-masked]>
wrote:

> Yes, I suggested get-sth-by-timestamp for that reason.  It's not at all
uncommon
for some of the smaller logs, or logs which are quite new and not widely
used, to
go through one or more signings with no tree growth.

Merging get-sth-at-timestamp into get-sth, with an optional parameter,
makes sense.

What about get-sths-between-times?  It's not just an optimisation: without
it. a client
wanting to ingest all a log's historic STHs has to pick some time interval
and then
issue a range of probing calls.  They cannot be sure not to have missed an
STH
somewhere.

(Although the optimisation is worthwhile: Aviator for example has O(45k)
historic STHs)

---

From: Rob Stradling <[email-masked]>
Date: Tue, 25 Oct 2016 15:10:57 +0100

On 25/10/16 15:03, Paul Hadfield wrote:
<snip>
> What about get-sths-between-times?  It's not just an optimisation:
> without it. a client wanting to ingest all a log's historic STHs has to
> pick some time interval and then issue a range of probing calls.
> They cannot be sure not to have missed an STH somewhere.
> 

Hmmm, good point.  I agree that it would be useful to have an API that
returns all STHs within a specified time range.  I think it could be
called simply "get-sths", with the "-between-times" aspect made obvious
by the names of the inputs to the API.

---

From: Paul Hadfield <[email-masked]>
Date: Tue, 25 Oct 2016 15:12:11 +0100

On Tue, Oct 25, 2016 at 3:10 PM, Rob Stradling <[email-masked]>
wrote:

> Sounds fair enough.  Naming things is hard :)
Implementations may want to limit the number of STHs they return, similarly
to get-entries.

---

From: Andrew Ayer <[email-masked]>
Date: Tue, 25 Oct 2016 10:34:56 -0700

On Tue, 25 Oct 2016 13:30:08 +0100
Rob Stradling <[email-masked]> wrote:

> > Auditors could then retrieve the full STH history of a log without
> > having to have collected them over an extended period of time or
> > having to exchange them with other auditors
> 

+1

Regards,
Andrew

---

From: Benjamin Kaduk <[email-masked]>
Date: Tue, 25 Oct 2016 19:44:04 -0400 (EDT)

> Indeed.  I think this would be a useful feature.

It does seem like a useful feature, yes.  But that utility should probably
be weighed against the added cost for the log operator, which now has to
retain STH history and provide code to service the new requests.

That extra cost is probably not very large, but it would nice to have
other opinions confirming that.

-Ben

---

From: Rob Stradling <[email-masked]>
Date: Fri, 28 Oct 2016 15:05:55 +0100

> other opinions confirming that.

I don't yet know if this can be considered for 6962-bis, but I've gone
ahead and created an issue and proposed a PR:

https://trac.tools.ietf.org/wg/trans/trac/ticket/160

https://github.com/google/certificate-transparency-rfcs/pull/200