[messaging] Message delivery and revocation in Pond etc

[Ximin Luo]

On 30/03/14 17:31, Trevor Perrin wrote:
> We've been discussing introductions in "unlinkable" aka "unobservable"
> messaging systems like Pond [1] or Petmail [2].
> 
> After the introduction completes, we want Alice to be able to send
> messages to Bob's server (and vice versa), such that:
>  - Bob's server learns the message is for Bob
>  - Bob's server doesn't learn who the message is from
>  - Bob's server can't recognize messages from the same sender
>  - Bob's server can't tamper with messages (e.g. can't make it appear
> that Alice is sending garbage)
>  - Bob can recognize who the message is from
>  - Bob can revoke any sender (e.g., if Alice starts spamming him)
> 
> (The messages are also encrypted, but those details aren't important here.)
> 
> In Pond, this is done with "BBS group signatures" [3,4]:  Alice can
> sign messages that the server can verify using the "group public key",
> but only Bob is able to "trace" the signature to Alice.  Bob can also
> update the group public key, and publish revocation data to the server
> that lets every other user (except the revoked one) update their
> signing key.
> 
> One downside:  After a revocation, the server can learn how many
> contacts Bob has by counting how many times someone tries to deliver a
> message signed with the old group key.
> 
> 
> Here's a proposed alternative (explained to me by someone else):
> 
> Bob and his server share an HMAC key k.  Bob distributes to each of
> his contacts a bunch of pairs (x, HMAC(k,y)) where (x,y) are a
> signature keypair (y=g^x).
> 
> Contacts then send (msg, y, HMAC(k,y), sig(msg, x)) to the server,
> which records used values of HMAC(k,y) and rejects them in future.
> 
> Bad:
> 
>  * Since the (x, HMAC(k,y)) pairs are one-time use, there must be
> periodic replies to a contact to refresh its store of pairs.
> 

I'm more and more favouring the idea that, in an end-to-end-secure system, you should *not* consider a message "definitely received" by the intended recipients, until you receive an ACK from them that strongly (but perhaps indirectly) refers to the message that you sent. (With email this is a no-no but here we've already authorized the sender.)

Under that assumption, requiring periodic replies wouldn't be too much of an overhead, assuming all of these auth-tokens can be stuffed into a message efficiently.

>  * The server's storage of used values is unlimited over time, but
> grows at a small rate, and could possibly be scoped by introducing
> more complexity (e.g. rotating epochs).
> 

Instead of storing used tokens, you could store *unused* tokens and delete used tokens. To authorize a sender, the server checks to see if their token is *in* its store, then deletes it if succesful. To revoke, Bob tells the server Alice's tokens as before, but now the server deletes them instead of storing them.

> Good:
> 
>  * Revoking Alice is just a matter of telling the server Alice's y
> values, and doesn't put non-revoked users through a rejection/update
> process.
> 
>  * Less computation than the pairing-based BBS signatures.
> 
> 
> Thoughts?
> 

This reminded of a ratchet system, where you're continually sending crypto material between each other. I was thinking of ways for the receiver to generate a chain of auth-tokens that can be revoked at the root-token (like the chain-ratchet within Axolotl), but unfortunately this would let the server see which messages are sent by the same person.

In summary, to achieve "Bob's server can't recognize messages from the same sender" we have two broad options:

- every messages looks to be from the same sender (group sigs)
- every messages looks to be from a new sender (send auth-tokens)

From a not-too-deep think through, I'm not sure there are other options.

X

> 
> Trevor
> 
> [1] https://pond.imperialviolet.org/
> [2] https://github.com/warner/petmail
> [3] https://pond.imperialviolet.org/tech.html
> [4] http://www.robotics.stanford.edu/~xb/crypto04a/groupsigs.pdf

-- 
GPG: 4096R/1318EFAC5FBBDBCE
git://github.com/infinity0/pubkeys.git

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 880 bytes
Desc: OpenPGP digital signature
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20140331/2243ffe6/attachment.sig>