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

[Mike Hearn]

This message proposes a protocol for a TextSecure-like async mobile
messaging protocol, in which the central server does not learn who is
messaging who. Despite that, basic anti-abuse techniques are supported. Our
tools will be BBS group signatures, Chaumian blind signatures, Tor,
certificates and a few other misc things which are taken as given (e.g.
Axolotl).

At the end I'll describe why I think focusing on TextSecure/WhatsApp style
systems rather than email is the most productive direction for e2e efforts.


*Outline*

We start with the account registration process. The user submits their
phone number to the server, the server encrypts it and sends the last
digits of the encryption to that phone number. Phone numbers are assumed to
be an expensive, scarce resource that spammers have a hard time finding
lots of  (this is only somewhat true but it's the approach used by all
modern websites instead of captchas). The user submits their phone number
again with the verification digits. Doing it this way avoids server
resource consumption attacks. The user's client then proceeds as follows:

   1. A long term identity key is generated and a certificate for it signed
   by the server with CN=phone number. Obviously the phone number in the cert
   must match the one that was verified.

   2. A BBS group public key with, say, 200 member keys is generated and
   uploaded to the server. Note that there are schemes that elaborate on BBS
   to give dynamic groups but I'm not familiar with them. The size of this
   group is arbitrary and can be selected by the client at will.

   3. Five nonces are selected by the client and blind signed by the
   server. The size of this set is controlled by the server: it refuses to
   sign more than five and this can only be done during account setup.

The client contacts the server as per normal or uses a push system like
Google Cloud Messaging to receive encrypted messages. Sending a message is
more complicated:

   1. The client connects to the server via Tor. This is easily achieved
   with good performance in the Android world using Orchid. Especially with
   optimisations you can get this working in perhaps 5-8 seconds, which seems
   reasonable for an async messaging app.

   2. The client has not contacted the requested phone number before. It
   fetches the certificate for the phone number from the server, and encrypts
   a message containing its own certificate, its initial DH ratchet material,
   one of the group member private keys for its own group, and of course the
   initial text message itself. It then submits it to the server with the
   target phone number and one of the blind signed tokens it obtained during
   account registration.

   3. The server checks that the token submitted was indeed blind signed by
   itself, and thus that it was issued to some account, but it doesn't know
   which one. The token is marked as attached to the target phone number in
   the server's database and cannot be used again for now. It then sends the
   encrypted message to the recipients message queue, which can trigger cloud
   push or whatever mechanism is used to wake up the users device.

   4. The recipient's client downloads the encrypted message, decrypts it
   and verifies it was signed using a valid cert issued by the server i.e. it
   was not junk submitted by someone who doesn't have an account. The message
   is displayed and a new contact with the details taken from the cert
   installed.

   5. If the recipient chooses to reply they perform the same procedure in
   the opposite direction, except this time instead of using up one of their
   tokens they sign the encrypted message with the group member private key
   that was given to them by the sender. The server checks the signature
   against the group public key and thus knows the message is being sent by
   someone authorised by that account (but not who exactly), and so accepts
   the message without requiring a token be used up.

   6. At some randomised later time the recipient's app sends a message via
   an authenticated channel to the server (i.e. not via Tor) telling the
   server to release the token that was attached to their account.  This is
   effectively a "not spam" report and lets the user do more "cold calling".
   The server deletes the database entry and forgets the token exists. If the
   message *was* spam, then the user simply never replies and the token is
   never released. The spammer quickly runs out of tokens.

Five tokens may seem restrictive but should be plenty for the
person-to-person use case. An account which routinely had its tokens
returned to it could be granted more, to create a kind of basic reputation
system. If one desired bulk commercial messaging then we can easily imagine
an evolved scheme in which an EV SSL certificate is used as proof of
"something expensive to obtain", that would let you blind sign a lot more
tokens for faster bootstrapping.

The server should end up knowing only who is using it, and when they
received messages, but it should not learn any message contents nor who is
sending messages to whom.

*Anonymous contact discovery*

Text messaging apps need to intersect the users contact list with the
servers account list. Moxie has said that existing PIR protocols are
inadequate for this. Doing such lookups via Tor can be a good way to reduce
information leakage, but Moxie indicated the inability to rate limit would
be problematic. The blind signing technique can be used to implement rate
limiting, such that clients can only look up a fixed quantity of phone
numbers per unit time. The database would track which tokens have been used
and when, then release them after the time window has expired.

In this way lookups can be throttled and we can ensure they are only done
by registered users, whilst still disconnecting the actual lookups from the
account that's doing them.

*Why async mobile messaging is the place to be*

After writing my mail about spam, I spent a lot of time pondering the
consequences. Eventually I concluded that trying to solve E2E messaging for
email is biting off more than I can chew. But that's OK because E2E for
mobile text messaging is *way* more tractable:

   - User expectations for features are far lower. Mobile text messaging
   does not let you search 50GB of message history in a split second, nor do
   we need importance filtering, nor handling of bulk commercial mail, nor
   indeed any kind of filtering/labelling at all. Gmail has trained email
   users to expect a vast feature set, most of which is hard to implement in
   the E2E context.

   - WhatsApp has proven that people are willing to pay for mobile text
   messaging services that do not use advertising to support themselves. The
   same has not been proven in the consumer email space. Obviously people
   paying makes E2E crypto way more commercially viable.

   - Thanks to Moxie the crypto community has a professional open source
   text messaging app that you could actually give to your parents, and it's
   been able to grow a real user base of interesting size.

   - Despite the small feature set these apps handle vast amounts of
   sensitive and important personal communications. They are not toys or
   staging grounds, they are important fields of battle all by themselves.

   - Mobile messaging takes place via real apps and not web apps, which
   makes doing complex crypto things less painful. E.g. connecting to a site
   via Tor using Orchid/Java is just a few lines of code and doesn't break the
   download-size bank. It should be quite feasible to do on mobile. Doing
   complex algorithms in native code is easy.

   - These platforms are not constrained by legacy issues in the same way
   email is. Rapid protocol innovation is possible.

For this reason I think focusing on these platforms and then scaling up one
feature at a time is probably the most fruitful way to go.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20140929/286ee330/attachment.html>