Subject: [Trans] Evaluating the Gossip Draft

From: Tom Ritter <[email-masked]>
Date: Tue, 17 Jan 2017 10:03:05 -0600

Hi all,

The Gossip draft has been sitting for a bit, we've gotten a few
comments but we'd like more. I wanted to take this opportunity to
compare/contrast it with another draft. Google has a (public, although
not well-publicised) draft for something that is Gossip-like,
available at https://docs.google.com/document/d/1FP5J5Sfsg0OR9P4YT0q1dM02iavhi8ix1mZlZe_z-ls/edit?pref=2&pli=1#

I think it's pretty interesting, and even though they don't want to
consider it 'Gossip', the goal of log consistency checking is pretty
near and dear to Gossip. So I want to think about it and kind of do an
apple-to-orange comparison with the IETF draft we've been working on
and see if there are things we should incorporate or consider
incorporating in our draft or (and this would be better) there are
things we could remove from our draft. While it's been worked on for a
while, I'm not the author of the Google draft so I don't want to speak
for them in terms of their commitment to it, its status, or whatnot.
When I say things like "They are" or "Chrome will" please translate
that to "The draft proposes that Chrome do X". (It's also important to
note that they're taking a methodical, phased approach to
implementation, so while this is something they do now it doesn't mean
they won't build up on it later.)

Anyway, their draft takes a very reasonable phased approach to
consistency checking. Chrome will receive a push of fresh STHs from
Google once a day. When Chrome encounters SCTs during normal web
browsing, it will request an inclusion proof via DNS. From here, one
can speculate about what log consistency checking can do, but in the
initial deployment phase Chrome will just be collecting metrics to
answer questions like:
- How often do we encounter SCTs that haven't been included yet?
- How long might we have to queue these SCTs for later checking?
- How often do we get inclusion proof failures?
- How well does the STH push mechanism work?

First, let me analyze their proposal. This is touchy - I'm not asking
them to defend it really, I'm just trying to figure out why I may not
like it, and what things I consider to be problematic enough to stop
me from just scrapping ours and re-architecting it in a way that
resembles theirs...

First off, apparently we never defined the threat model we expected
our Gossip draft to defend against. (Well, we kind of buried it over
here: https://tools.ietf.org/html/draft-ietf-trans-gossip-03#section-10.3
but that's not very well-written.) I think I speak for my co-authors
when I say we assume the below. It's reasonable that Google's threat
model may not match ours and therefore evaluating their algorithm
against our threat model is kind of unfair... but I'm going to do it
anyway I guess.

a) An attacker can compromise a CA and get a mis-issued end entity
certificate (or subCA cert)
b) An attacker can compromise multiple logs, such that they can get
sufficient SCTs required to meet certificate acceptance policies
c) An attacker can compromise those logs to cause a split-view of the
log to be generated if desired
d) An attacker can perform a TLS MITM (using their cert and SCT) of a
client, for any individual or indeed all websites for a *limited*
period of time (meaning they cannot MITM a website forever)
e) An attacker can selectively _block_ network connections at will,
forever, based on direct identifiers like hostnames or using
heuristics.

f) Additionally, we would *like* to defend against an attacker who can
thoroughly compromise two CAs to do the 'Dual CA attack'. But this is
not a strict requirement.

Finally, we admit that there are (at least) two attacks in our threat
model the attacker could perform that we do not attempt to defend
against:
i) Blocking all software updates for a client (such as new CT
policies/code, removing compromised logs, removing compromised CAs)
[1]
ii) Performing a TLS MITM of a website, and then blocking the client
from communicating with that website ever again (in conjunction with
selective network blocking)

Security:

Google pushes STHs to clients. Any attempt at putting an individual
Chrome client onto a split view can be detected. But Google (and
therefore all Chrome clients) could be put on the same split view. Or,
on the other side of the view, the attacker simply doesn't attack
Chrome clients. Because it's unlikely that an attacker would decide to
attempt an attack that puts Google and all Chrome clients onto a
malicious side of the tree, I suppose this is acceptable for Google,
but I would prefer an ecosystem where different clients will share
data amongst themselves, resulting in true herd immunity, and not '5
herds, each with some level of immunity'.  (To be fair, this seems
like something that might be added in a later version and would be
explicitly excluded from initial deployment while one tests the
waters.)

Nothing in this proposal can detect a Dual CA Compromise, but that's
something that could be added later I suppose.

There are fixed-sized buffers with well-defined behaviors and no
randomization. (At least, going off the proposal.) This leads me to
believe it would be fairly easy to perform a flushing attack (or a
preload-the-cache attack) on a client which, when combined with a
strategy of 'delay all inclusion proof requests temporarily', would
lead to an undetectable attack on a client.

Censorship:

Consider an attack on CT: Mallory compromises a CA to sign a cert, and
N logs to get N SCTs for the cert. (SCTs which are never included in
the log.)

I do not see a way with this proposal, or an obvious extension of it
that preserves privacy, to detect the attack when the attacker also
blocks (some or all) DNS inclusion proof requests. DNS filtering is in
use all over the place, in both known-censored countries like those in
the Middle East, but also in place in 'free' European countries like
Switzerland, Sweden, Norway, Belgium, Denmark, and Estonia. Therefore,
I think it's reasonable to assume a threat model where the attacker
can block selected DNS queries effectively forever.

Defending against this is a pain in the butt. Some solution(s) to this
problem are:
- Send proof requests over a different channel. Tor. Or use
DNS-over-TLS or DNS-over-QUIC or something similar for all DNS - but
this requires your DNS endpoint to not be run by your adversary (the
ISP probably)
- The main one: use SCT Feedback. (Obviously requires opt-in by the
website under attack)
- Use a Trusted Auditor (undesirable for a number of reasons)

Privacy:

There may not be any consideration given to how inclusion request
ordering and clustering discloses information to logs. It implies the
SCTs will be entered into an (ordered?) de-duplicated queue.

Okay, now I want to compare it to our draft
https://tools.ietf.org/html/draft-ietf-trans-gossip-04

I'm going to extrapolate the current proposal into one that does the
following: If an inclusion proof is received that chains to a STH the
client doesn't know about, and the STH is reported to be within the
timeframe that the client should know 'all' the STHs - the STH is
reported to Google. This still isn't Gossip, but it does start doing
and reporting on actual log consistency check and might catch a
malicious or compromised log. I don't know if this is Google's plan,
but it seems like a natural extension of it...

First off, Google's plan is so much less complex than ours. This comes
from a few places:
1) There's nothing about 'Trusted Auditors'. Google obviously has some
trusted auditor implementation in their crawler, but its
privacy/security considerations and API format are omitted.
2) It omits SCT Feedback.
3) I am assuming it takes a 'Report weird STHs to Google' approach
instead of the STH Pollination approach we define. The assumption I
make I am actually okay with privacy/security wise although I prefer
the Pollination approach as a more open and interacting ecosystem
notion.
4) It omits talking about defenses against flushing attacks.

What should we take away from this?

Firstly, no one *likes* Trusted Auditors. I mean it'd be good to
standardize an API for it, but maybe we should remove it from the
draft and say 'We'll work on this in a different draft later?'

Secondly, while I prefer STH Pollination, it could be replaced by
Google's idea (and my extrapolation) of pushing STHs to clients and
reporting weird ones up to the client vendor. This has the
disadvantage of causing the 'multiple herds' situation, but has the
advantage of requiring less work from site operators and pushes less
total data around the internet. It would be necessary that the 'report
weird STHs' mechanism be sufficiently protected against
heuristic-based blocking though.

However, because of the censorship concerns I raised, I am not eager
to remove SCT Feedback...

Something I am unsure about is how Google plans to handle the case of
'Requesting an inclusion proof for this SCT always fails'. Clearly
'Send the SCT to the Google' is easy but... not very privacy
preserving. Maybe failure rates will indicate that this happens so
infrequently that it is acceptable privacy wise?[2] In our draft we
propose that one MUST NOT do this and that if the site does not
support SCT Feedback... Thinking about this more, this seems like a
pretty big failure scenario. We definitely want to detect SCTs that
are not included in logs - that's probably the easiest possible log
compromise but right now we have only a mediocre answer to it (since
SCT Feedback will not be deployed by many or most websites.) I'd love
to hear people's thoughts here.

I've realized some additional things about the current gossip draft:

- As mentioned in the paragraph above, we don't have a good story
about SCTs we fail to get inclusion proofs for.
- It de-facto requires resolving proofs over DNS (I'd prefer Tor but
I'm being realistic), but the only provider of this functionality is
Google. This isn't a good ecosystem.
- Proof requests are a good target for DNS reflection attacks :-/
- We haven't done a good job of considering all the client
implementations of Gossip, in particular how our proposal maps to
Mobile. Which security guarantees will be de-facto relaxed, and to
what degree, by the constraints of mobile?
- As I mentioned above, we never put a well-described threat model
into the document.

-tom

[1] Such an attack can be detected, using something like The Update
Framework, but the behavior of a client when it knows it is being
blocked is an open problem. Do you just show the user an error like
"Sorry, I've decided to stop working for you. Good luck figuring out
how to update me"?
[2] Although such a decision would lead to de-anonymization attacks
possible by logs!