[messaging] Metadata free instant messaging protocol, with basic spam throttling
mike at plan99.net
Mon Sep 29 14:48:23 PDT 2014
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.
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.
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
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
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
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...
More information about the Messaging