[messaging] Recognizing senders of metadata-hidden messages

[Brian Warner]

On 7/6/15 12:00 PM, Trevor Perrin wrote:

> I think the question here is:  if Alice sends Bob a message via some
> metadata-hiding system (e.g. anonymous remailers, or Pond), how does
> Bob know which key to decrypt with?

I was thinking about quantifying the "how many keys do I need" question.
I suppose the solution space includes questions like:

Q1: do senders get to know they're talking to the same person?
Q2: does it use interactive (ratchet) key rotation?
Q3: does it use non-interactive (k=H(k)) key rotation?
Q4: what are the responsibilities of a "mailbox server", if any?

Q1 is probably the most influential. If you choose to hide the recipient
this way, you need pairwise keys, which has deep effects on addressbook
management: you must interact with someone, to get the key, before you
can send anything to them, so you can't just type in something from a
business card or a search lookup (using forward-secure keys imposes a
similar constraint). Likewise to introduce two of your friends requires
your agents to make a couple of roundtrips.

On the other hand, pairwise is the only case where you could use
symmetric keys. OT3H, that makes forward-secrecy less reliable, since
you must depend upon the *sender* erasing a key too.

Petmail currently hides the recipient from senders (with pairwise
current+next pubkeys), but I'm increasingly uncertain that the
operational/UI challenges are worth it. I like the "default to unlinked,
but link if you want to" approach over "default to linked", but there
are too many ways to accidentally link your supposedly-distinct personas
when you use them in the same agent. Trevor has convinced me that it's
safer and just as easy for Carol to run two separate instances of her
agent (one for the persona she presents to Alice, and a second for Bob).

Pairwise keys also make the key rotation easier: you know the state of
the sender, so you can use (current+next) keys and rotate them
immediately each time you see evidence that the sender knows about the
new one (which is every message, if the messages don't overlap).

If you use the same keys for all senders, then this style of rotation
could be held up by *any* sender falling behind. I think you'd need
epoch-based rotation, where you deliver e.g. one pubkey for each of the
next 5 days, and messages which gets stalled for too long are just lost.
Or use Puncturable Encryption as a fancier variant.

The mailbox server might be responsible for:

* rejecting spam from unknown senders
* rejecting spam from recently-removed senders
* rejecting duplicates
* rejecting out-of-order messages
* *not* recognizing distinct senders

Rejecting messages is pretty easy if the server is allowed to
distinguish senders (you effectively just have a layer of
encrypt-on-the-wire to the server). If not, things are harder, and you
need a stash of tokens, or ring signatures, etc.

Petmail currently uses re-randomizable ElGamal encryption to let the
senders produce a unique per-message token. The server allocates a queue
id and a keypair, keeps the decryption key for itself, and sends the
queueid and encryption key to the recipient. The recipient randomizes
the queueid to get a base token for each sender, and gives them the
encryption key too. Each sender randomizes it *again* for each new
message, and the server decrypts that to get back the queue id and
figure out who the recipient is. Revocation is a drag, though, so I'll
probably be switching to a token stash too: much simpler to explain and
implement.

> so I wonder if tags could more directly indicate message decryption
> keys.

I guess the simplest and most forward-secure approach would be to give
each sender a stash of single-use pubkeys, and the mailbox server
H(pubkey) for each. Pros: recipient does a simple table lookup instead
of trial-decryption. Cons: fast message exchange could exhaust the
supply quickly, server must be updated frequently, server must learn
about the new token before it's safe to give it to the sender. Maybe
we'd send larger batches to the server ahead of time.

There's probably a hybrid Axolotl-ish approach where each pubkey can be
used multiple times, with k=H(k) -style rotation in between. In fact,
maybe we could skip the inter-ratchet rotation: I think I'm ok if the
forward-secrecy interval is larger than a single message, maybe up to a
couple of days long. Remember that we can't expire the key until the
user has read the message anyways. That doesn't help figure out what the
server-visible tokens should be, though.

The two agents must keep each other informed about their remaining keys,
and ask for a refill while they still can. Back in 2004 (in the original
Petmail) I drew up a scheme to do this with Mixminion's SURBs
(Single-Use Reply Blocks), where the threat of giving someone too many
was that they could send a big burst of messages to you and use the
resulting traffic pulse to trace your location. These days, if the stash
is merely being used to avoid DoSing the server, then handing out too
many doesn't matter so much, especially since the agent can cancel them
by talking to the server, and thus limit the total outstanding.

As a fallback, it might be useful to have a set of non-rotating keys
which are never used for human-authored messages, but can be used to ask
for new keys even after the stash has been exhausted.

cheers,
 -Brian