[messaging] Vuvuzela: Scalable Private Messaging Resistant to Traffic Analysis

[Trevor Perrin]

On Sat, Jun 20, 2015 at 7:25 AM, carlo walentiny <cajw1 at web.de> wrote:
>
> "This paper presents Vuvuzela, a system that provides
> scalable private point-to-point text messaging.
> Vuvuzela ensures that no adversary will learn
> which pairs of users are communicating,
[...]
> http://jelle.vandenhooff.name/vuvuzela.pdf


Thanks for the link!  Seems cool:

In traditional anonymous remailer systems (Mixmaster, Mixminion)
senders deliver messages to recipient mailboxes through a mix network.

(A mix net is a bunch of servers, or "mixes", similar to Tor relays in
that they unwrap layers of encryption.  They're different in that
mixes also delay or batch input messages, and output them in random
order.  So mixes add more latency than relays, but they also add more
protection against network observers.)

The Vuvuzela paper assumes a "mix cascade", i.e. a fixed sequence of
mixes.  Unlike Tor, security in a mix cascade doesn't depend on
selecting diverse paths, but on there being at least one honest mix in
the path.  The example system in the paper has a cascade of 3 mixes.

So far, this is standard.  The innovation is that Vuvuzela messages
aren't delivered to the recipient's mailbox.  Instead, each pair of
correspondents does something similar to "frequency hopping".  They
have a shared secret and for each time interval (e.g. 1 minute) they
use the secret to generate a large pseudorandom mailbox number.  They
then send a message and its mailbox number through the mix cascade to
the last mix, which I'll call a "reflector".

As the message is decrypted by each mix it builds a temporary circuit
which can send a message in the reverse direction (back to the
sender).  If 2 messages arrive at the reflector in the same round with
the same mailbox number, the reflector sends each message back through
the cascade to the other party.  If only 1 arrives, the reflector
sends an empty message back to the sender.

Without permanent mailboxes, there are no arrival events that might
leak info; every round you receive back as many messages as you send,
and that's all.  It's easy for senders and mixes to add dummy traffic
that gets discarded at the reflector or reflected back to them.  And
it's impossible to DoS a target's permanent mailbox, as that doesn't
exist.


But there's a downside to the lack of permanent mailboxes:  You can
only receive a message from a correspondent if you send them a message
(or empty message) in that round.  Suppose you have hundreds of
correspondents, but only want to send one 512-byte message per round
(e.g. per minute).  What do you do?

The Vuvuzela decision seems weird to me:  the authors add back
permanent mailboxes, but only use them for "dialing" messages which
are sent prior to conversation messages, and encrypt the shared secret
to the recipient's public key.  Each dialing mailbox is shared by a
bunch of users.  Users download their dialing mailbox periodically and
use trial decryption to recognize their dialing messages.

The authors argue permanent mailboxes work OK here since dialing
messages are smaller and less frequent than conversation messages.
But in their example, users send a 512 byte conversation message every
minute, and download an average of 2 MB (!) of dialing messages.  This
also adds back denial-of-service risk, since a large number of
messages could be directed at a single dialing mailbox.

I'm not sure what the alternatives are.  Maybe if the shared secret
could be established some other way (like Pond's PANDA, or DH between
long-term keys), then it could be used to derive time slots where the
correspondents try to communicate?

Anyways, I'm sure there's more to be said here, but this looks like a
neat concept that points towards more practical mix-net systems.


Trevor