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

[Trevor Perrin]

On Tue, Sep 30, 2014 at 9:15 AM, Mike Hearn <mike at plan99.net> wrote:
> Yes that scheme does look better, although the "store all used
> values" part would seem to be a deal killer for TextSecure.

The server storage for Pond-like one-time delivery tokens could be
reduced (bitmasks [1], whitelists [2], epochs), but not eliminated.
Also, correspondents have to resupply each other with tokens by
including them in messages, which could have a painful effect on
message size.

Group signatures don't have those costs, but they also don't allow
receivers to rate-limit senders by rationing delivery tokens.

And both group sigs and delivery tokens reduce the server's ability to
rate-limit based on sender reputation.

So I wonder if something simpler can be done first.  I think there's 3
things you're trying to achieve:
 (A) resist the server recognizing messages between the same correspondents
 (B) resist the server recognizing messages to different recipients
that share an (unidentified) sender
 (C) resist the server linking an unidentified sender to a registered user

(A) requires every message have its sender anonymized (e.g. Tor and
delivery tokens or group sigs).  But (B) and (C) are easier and could
be done in phases:

1) On registration Alice gets a blind-signature (her "alias").  She
sends this to the server whenever she sends a message (her connection
to the server is encrypted, so she can use the alias like a password).
The server can apply its existing reputation-tracking / rate-limiting,
using the alias instead of the registered identity.  The server still
learns the sender's IP, so this isn't great, but it's easy and could
be rolled out widely.

2) Alice sends messages via Tor.  At this point we're somewhat
achieving (C), though it would be possible to deanonymize aliases with
a little research, based on who they're contacting.

3) Allow Alice to register multiple aliases, and stripe her contacts
across them.  To mitigate the risk of Alice getting 100 aliases and
then spamming, she might have to pay for this level of service.  I
don't know if a price exists that would balance the risk of spam while
still attracting users, but it's possible that users like journalists
might pay to get a unique-alias-per-contact, at which point they've
achieved (B) and (C).

So that's punting (A) on the theory that (B) and (C) are easier to
tackle first, as they just build on existing rate-limiting /
reputation stuff.  Thoughts?

Trevor

[1] https://moderncrypto.org/mail-archive/messaging/2014/000413.html
[2] https://moderncrypto.org/mail-archive/messaging/2014/000266.html