[messaging] Metadata free instant messaging protocol, with basic spam throttling

[Moxie Marlinspike]

On 09/30/2014 03:50 AM, Mike Hearn wrote:
> Token reuse: tokens are only used when introducing yourself to a new
> contact for the first time. If the client cycles through the tokens then
> only every 5th new contact is linkable. I think your suggestion of
> simply rotating keys every N hours and having clients refresh the tokens
> is reasonable. N could be adaptive to let operators trade off CPU vs
> disk time on the server dynamically.

I think every 5th contact being linkable is likely problematic.  Or at
least, I don't know how to effectively communicate that to set user
expectations.

Also, it seems plausible that someone could install TextSecure and want
to send an "I'm on TextSecure!" message to more than 5 people before any
of them respond.  Preventing them from sending a message to a 6th person
before one of the initial 5 responds would be kind of weird.  What if
they never respond?

We could hand out more initial tokens, but some of the rate limits that
we want to impose would suffer.  For instance, the rate limit on
requesting multiple prekeys from a single user is very tight.  If
someone had 100 tokens, there's no way to enforce a tight limit if those
tokens aren't linked.

If we're alright with linkability, then I think I'd rather just issue a
single blind token to a user at registration time, and use that
identically to how the client's authenticated identifier is currently
used for rate limiting.  If we're not alright with linkability, then I
think we need something else.

> Deniability:   I must admit I never convinced myself as to the value of
> this. I find it hard to imagine a real world scenario in which someone
> says "ah ha! i will ignore this otherwise solid evidence against you
> because it's possible that the evidence was forged!".   Does deniability
> ever come up outside of hypothetical court cases? If so, surely police
> routinely present evidence that could theoretically have been forged but
> which is admitted anyway, because in practice forgery of evidence is
> rare? My intuition would be that deniability is perhaps worth discarding
> to get other kinds of privacy features.

I do personally find some comfort in sending messages that aren't signed
with my identity.  More importantly, though, I think that we should
strive to do the best that we can within the domain we're working in,
and if we can provide deniability, we should.  Compromising on it
certainly isn't out of the question, but it's not a decision that I
would make super lightly.

> Periodic tasks:   good smearing can make this load more or less
> constant, but I don't know anything about TextSecure's cost models or
> budgetary constraints so can't comment much on this.

For 10MM users, a periodic task every 24 hours is 116 requests/second.
My recollection is that blind Schnorr signatures are actually a
multi-step protocol, so that would more likely be at least 232
requests/second of cpu-bound work.  That's not impossible or anything,
but it's just worth considering the request load that we're setting
ourselves up for just to tread water (before anyone even starts using
the app).  We've already got one periodic task for contact intersection,
so we just have to think carefully about every additional one that we add.

- moxie

-- 
http://www.thoughtcrime.org