Subject: [Trans] Tracking via multiple STHs (was Call for adoption, draft-linus-trans-gossip-ct)

From: Tom Ritter <[email-masked]>
Date: Wed, 26 Aug 2015 07:15:16 -0500

On 25 August 2015 at 03:56, Ben Laurie <[email-masked] <javascript:;>>
wrote:
>
>
> On Thu, 13 Aug 2015 at 01:34 Tom Ritter <[email-masked] <javascript:;>>
wrote:
>>
>> On 8 August 2015 at 12:25, Bryan Ford <[email-masked]
<javascript:;>> wrote:
>> > [Many good things]
>>
>> Okay.  If I simplify unfairly I think I agree with many of the root
>> points of your email.
>>
>> 1) Yes, more logs plus even a weeks worth of STHs probably affords too
>> much ability for tracking. Releasing a STH will have some sort of
>> probability attached to it, but again 'statistics'[0]. I've open a
>> ticket to make sure we don't lose this.
>
>
> I've been thinking about this for a while now, and I'd like to know how
this
> attack works.
>
> When a client communicates with a log, assuming it manages to do so
> completely anonymously, it reveals at most two STHs it knows (i.e. if it
> asks for an STH consistency proof).
>
> A week's worth of STHs gives me ~10,000 pairs. Assuming, say, 1B people
who
> visit sites using CT in that week, that puts each person into an anonymity
> set of size 100,000, assuming the attacker has full control over STHs the
> user caches. Which he doesn't.
>
> Also, once the attacker has narrowed the user to this set, what has he
> learnt? Nothing, since he already knew the 2 STHs the user had cached (he
> supplied them). Those two STHs are correlated with nothing else. What's
> more, one of them is now going to be removed from the cache (the older
one),
> moving the user into a  really large anonymity set. In practice, the user
> will soon replace that STH with a more recent one, and different users
will
> replace with different STHs, causing the set to become even larger over
> time. Anyway, now you can determine that one of at least 10M people
visited
> some particular website. I find it hard to get excited about that.
>
> In order to further narrow the user down, or to learn anything correlated
> with the smaller (two STH) anonymity set, the attacker needs some other
> persistent marker so he can correlate other requests. But if he has that
> persistent marker, what is the STH marker for?
>
> In short: I am not seeing how this represents a privacy problem. Perhaps
I'm
> missing something?

So in your thought process the attacker is a log colluding with a website
to track a user? I imagined in a different way.

Two independent sites A and B want to collaborate to track a user
cross-origin.  A feeds a client Carol some N specific STHs from the M logs
Carol trusts, chosen to be older and less common, but still in the validity
window.  Carol visits B and chooses to release some of the STHs she has
stored, according to some policy.

If we were able to model a representation for how common older STHs are in
the pools of clients, then for a given policy of how to choose which of
those STHs to send to B I think we could calculate some statistics about
how likely it is that Carol looks like someone else when talking to B and
how useful/accurate such a tracking mechanism is.

That's the concern I had in my head, others may have different variants .

-tom

---

From: Ben Laurie <[email-masked]>
Date: Wed, 26 Aug 2015 13:47:56 +0000

On Wed, 26 Aug 2015 at 13:15 Tom Ritter <[email-masked]> wrote:

> On 25 August 2015 at 03:56, Ben Laurie <[email-masked]> wrote:
> >
> >
> > On Thu, 13 Aug 2015 at 01:34 Tom Ritter <[email-masked]> wrote:
> >>
> >> On 8 August 2015 at 12:25, Bryan Ford <[email-masked]> wrote:
> >> > [Many good things]
> >>

Right, I was thinking (as a log operator!) about what clients reveal to
logs, but you are right that they may reveal more to websites via gossip. I
think you are right that we need to model to be able to reason about that
variant.