[messaging] SURBs (was: Replacing group signatures with HMAC in Pond)

[Brian Warner]

Late to the party, but I thought I'd mention one thing:

On 5/26/14 5:28 PM, Adam Langley wrote:

> Rather than using group signatures, a user and their home server share
> a HMAC key, k. During the introduction protocol, a number of pairs are
> exchanged. Each pair contains a private key, x, and HMAC(k, y), where
> y is the public key for x.

This "refillable pool of tickets" scheme reminded me of something I
worked on in the original Petmail (10 years ago now), when Mixminion
looked promising and included "SURBs": Single-Use Reply Blocks. Each
SURB contained an encrypted onion path, with per-hop serial numbers that
ensured single-use, to prevent the sender from learning the network
location of the recipient's server. The Petmail sender would be given a
stash of SURBs, spend one for each message, and hopefully the recipient
would re-stock them before they ran out.

If the SURB included some message-size limits, then the recipient could
choose their own tradeoff between bandwidth and resistance to
large-bursts-of-traffic attacks (where the malicious sender sends large
messages and a global passive eavesdropper watches the encrypted "bump"
travel through the network to locate the recipient).

I think SURBs fell out of favor in the Mixminion world (even before
Mixminion stalled altogether), maybe because they weren't confident that
SURBs were safe enough. But it seems like there's some useful
parallelism between "single use thingy that convinces a server to accept
your message" and "single use thingy that convinces the network to
deliver your message".

Knowing that a SURB had really been spent was non-trivial, though (an
intermediate node failure would render the SURB useless for the sender,
but wouldn't notify the recipient that it was spent). If someone were to
build SURBs into a new generation of mix network, it'd be nice if they
automatically expired after some period of time.

As agl pointed out, Pond server HMACs could suffer from the same problem
(and might benefit from the same solution), but the fact that the HMACs
can be revoked directly (or even have their status queried) should make
them easier to manage.

cheers,
 -Brian