Subject: [Trans] Gossiping in CT

From: Linus Nordberg <[email-masked]>
Date: Sat, 27 Sep 2014 15:36:17 +0200

Hi,

This gossiping that people is talking about, what is it? Here's a
summary of what I think some people mean when they say gossip and what
problem this thing tries to solve. It's based on a few IETF-related
documents and not the full picture. I'd be interested to hear what other
people read into the concept of gossiping in CT

A CT log which is audited and monitored without complaints can still
mount a partitioning attack on its clients. The easiest case, from the
logs perspective, is to divide the clients in two sets and serve them
two different views of the log. So set A sees view A and set B sees view
B.

If a client in one set sees an STH from a view meant for another set, it
could conclude that the log is misbehaving since the log cannot produce
a consistency proof between STH(A) and STH(B). (Unless A and B are forks
from a tree splitting at the older of the two tree heads, but then
they'd technically not be different views.)

The same is true for a client seeing an SCT from one view and an STH
from another because the log cannot produce an inclusion proof of an
entry in A being part of STH(B).

Gossiping then is the spreading of information about a given log, aiming
to cross the potential boundaries between different sets of clients of
that log.

* Whom to gossip with

In order to maximise the chance of crossing a border between to sets of
clients in a partitioning attack, clients should try to talk with as
many different clients as possible.

* What to gossip

The more information shared, the better detection we seem to get. But
sharing information have privacy implications. It seems to me that
sharing STH's is much less problematic than sharing SCT's.

Showing someone an STH will reveal that you've been receiving data,
directly or indirectly, from a given log as late as 'timestamp'. (The
log is not identified more than with a tree hash and a signature but
that's enough for confirming a given log, given access to it and its
public key.) The increase in fingerprintability that CT gossiping of
STH's would add would depend on the deployment of CT support in browsers
and how browser vendors select which logs to use.

Showing someone an SCT will reveal that you've received data about a
given site (through the x509 certificate) from a given log (through the
LogID) no later than a given time (timestamp). This might be a strong
indication that you've visited that site but this depends on how other
clients behave.

It's been suggested that STH's are to be gossiped. The question about
which STH's to gossip about has not been answered.

* How to gossip

It's been suggested that web browsers should use TLS connections to web
servers for gossiping. One argument for that is that this makes the
attack of blocking the gossiping messages hard to get away with without
people noticing because it means blocking TLS to all servers
participating.

This can hopefully be useful as a starting point for discussing
gossiping in trans.

---

From: Tao Effect <[email-masked]>
Date: Sat, 27 Sep 2014 10:11:34 -0700

Dear Linus,

Thanks for starting this thread on Gossip!

> people noticing because it means blocking TLS to all servers

I just want to point out that successful gossip does not protect clients against MITM from mis-issued certificates. It also does not detect mis-issued certificates.

The selective partitioning of a log is one attack, but the standard attack that we have today, which doesn't require partitioning of a log, is not detected by CT's gossip as elaborated on in the "Threat model outline, attack model" thread, here (and in followup replies):

http://www.ietf.org/mail-archive/web/trans/current/msg00588.html

Kind regards,
Greg Slepak

--
Please do not email me anything that you are not comfortable also sharing with the NSA.

---

From: Love Hörnquist Åstrand <[email-masked]>
Date: Sat, 27 Sep 2014 18:23:02 +0000

> 27 sep 2014 kl. 19:11 skrev Tao Effect <[email-masked]>:
> 

- the CA is sloppy/forced to issue the cert to the attacker
- cert is injected into log
- cert have SCT
- client check the SCT with the logs the clients trust, like one the is not under the same control as the CA
- any other SCT in the cert is ignored by the client since they are not trusted.
- MITM happened
- Auditor finds the fraudulent issued cert
- public out roar 
- ca falls out from the public trust
- second ca will now refuse the attacker since they know the cost (loss of company)

Gossip is about not trusting log owners to keep them honest and unrelated to your attack.

until you have namecoin working and enabled on all running all TLS clients and servers, I find CT is a acceptable compromise.

Love

---

From: Tao Effect <[email-masked]>
Date: Sat, 27 Sep 2014 12:12:16 -0700

Dear Love,

> - Auditor finds the fraudulent issued cert

Exactly how will the Auditor do that?

Kind regards,
Greg

---

From: Love Hörnquist Åstrand <[email-masked]>
Date: Sat, 27 Sep 2014 21:03:00 +0000

> Exactly how will the Auditor do that?

By looking at logs that the clients care about. You claim that there will be thousands of logs, I somewhat don't think so since then there will be thousands of logs the ca will send the cert to be issuing it, and that is not reasonable.

So how do you keep the log honest and stop it from not adding the SCT to the log ?

Well, by using gossip about the logs.

You are claiming that PKIX and Internet roots are a hopeless endeavor, and I somewhat agree, you seem to want us to switch to namecoin and forget about Internet roots, and I see that as even more hopeless endeavor short term.

Short term CT will make a difference. If you disagree, then there is not much more we can do then agree to disagree.

Love

---

From: Tao Effect <[email-masked]>
Date: Sat, 27 Sep 2014 14:47:24 -0700

On Sep 27, 2014, at 2:03 PM, Love Hörnquist Åstrand <[email-masked]> wrote:

> By looking at logs that the clients care about.

Auditors do not look at the logs, Monitors do that.

> You claim that there will be thousands of logs, I somewhat don't think so since then there will be thousands of logs the ca will send the cert to be issuing it, and that is not reasonable.
> 

Sorry, don't quite understand what you're saying here...

Both SCTs (legitimate and otherwise) will happily be accepted by any log. Gossip won't help clients detect fraudulent certs issued by rogue CAs (as explained in the "Threat model" thread).

> You are claiming that PKIX and Internet roots are a hopeless endeavor, and I somewhat agree, you seem to want us to switch to namecoin and forget about Internet roots, and I see that as even more h…

Well, switch to a decent blockchain and using something like DNSChain to talk to it, yes. :)

If Google wanted to make that a reality in the short term, they could.

Kind regards,
Greg Slepak

---

From: Tao Effect <[email-masked]>
Date: Sat, 27 Sep 2014 16:10:35 -0700

Dear Linus,

Paul Wouters brought up the idea of sharing certs on [metzdowd], and I guess that's the same thing as gossiping SCTs, right?

I think that could actually be very useful for detecting a MITM, here's my reply to him there:

http://www.metzdowd.com/pipermail/cryptography/2014-September/023037.html

> sharing STH's is much less problematic than sharing SCT's.

Why do you think sharing SCTs is problematic, and what privacy implications does it pose?

If the SCTs are shared over an encrypted connection, only the server, the client, and the potential MITM will know about them.

Any time a cert changes, the client would tell the server about that change over the established TLS connection.

When MITM leaves, the server would find out that a fraudulent cert had been generated for their website, and could then identify the CA responsible.

Kind regards,
Greg Slepak

---

From: Linus Nordberg <[email-masked]>
Date: Mon, 29 Sep 2014 14:20:06 +0200

Tao Effect <[email-masked]> wrote
Sat, 27 Sep 2014 14:47:24 -0700:

| On Sep 27, 2014, at 2:03 PM, Love Hörnquist Åstrand <[email-masked]> wrote:
| 
| > So how do you keep the log honest and stop it from not adding the
| > SCT to the log ?
| > 
| > Well, by using gossip about the logs.
| 
| Sorry, don't quite understand what you're saying here...
| 
| Both SCTs (legitimate and otherwise) will happily be accepted by any
| log. Gossip won't help clients detect fraudulent certs issued by rogue
| CAs (as explained in the "Threat model" thread).

This is hard to follow. SCT's are not added to nor accepted by
logs. They are the response to a log submission. An SCT is a promise
from a log that a given certificate will be included in said log within
some time.

Detecting of fraudulent certs is done by the particular type of CT
client called a monitor.

Successful gossiping will help detecting logs presenting different views
to different clients, among them monitors. This includes malicious log
operators as well as attackers able to mount man-in-the-middle (or
man-on-the-side) attacks who are also able to sign as the log (for
example by having a copy of the logs private key).

---

From: Linus Nordberg <[email-masked]>
Date: Mon, 29 Sep 2014 14:50:53 +0200

Tao Effect <[email-masked]> wrote
Sat, 27 Sep 2014 16:10:35 -0700:

| Paul Wouters brought up the idea of sharing certs on [metzdowd], and I guess that's the same thing as gossiping SCTs, right?

That's not how I read that. The suggestion seems to be sharing
information about seeing two different certificates with the same CN
within some period of time. That's not what an SCT carry. 

| > The more information shared, the better detection we seem to get. But
| > sharing information have privacy implications. It seems to me that
| > sharing STH's is much less problematic than sharing SCT's.
| 
| Why do you think sharing SCTs is problematic, and what privacy implications does it pose?
| 
| If the SCTs are shared over an encrypted connection, only the server, the client, and the potential MITM will know about them.

The fear is that the web server would get a good idea about what sites
the client has visited. If clients would gossip sufficiently about
_other_ clients SCT:s _and_ there would be no way of linking an SCT to a
given client, this might be less of a problem. Can we do this?

| Any time a cert changes, the client would tell the server about that change over the established TLS connection.
| 
| When MITM leaves, the server would find out that a fraudulent cert had been generated for their website, and could then identify the CA responsible.

Here is the cert change again. I'll leave it to others to explain more
about that idea. Sounds interesting.

---

From: Gervase Markham <[email-masked]>
Date: Mon, 29 Sep 2014 14:03:59 +0100

> people read into the concept of gossiping in CT

It seems that your summary might have one misapprehension. As I
understand it, gossiping is not something that clients (in the web
browser sense) do. After all, one point of CT is to avoid extra network
requests at connection time. Gossiping is a log-to-log concept, where a
group of logs can determine that a particular log is rogue because of
what they hear about what it's saying, and any inconsistencies in that.

Gerv

---

From: Ben Laurie <[email-masked]>
Date: Mon, 29 Sep 2014 14:19:48 +0100

> what they hear about what it's saying, and any inconsistencies in that.

We imagine _all_ participants in the protocol gossiping. Yes,
gossiping STHs in the current plan does introduce a small amount of
extra overhead into the connection, but it really is small.