[messaging] Message delivery and revocation in Pond etc

[Ximin Luo]

On 01/04/14 23:17, Trevor Perrin wrote:
> On Mon, Mar 31, 2014 at 12:11 PM, Ximin Luo <infinity0 at pwned.gg> wrote:
>> On 30/03/14 17:31, Trevor Perrin wrote:
>>
>>>  * 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.
> 
> That's interesting.  It solves the "unbounded storage" problem, but it
> also means Bob can't just share a MAC key with his server, he has to
> tell it in advance about all the one-time signing keys he's
> distributed.
> 
> And if Bob isn't careful, the rate at which he publishes new keys to
> his server might reveal new contacts, or the rate at which contacts
> are sending to him.
> 
> Hmm.
> 

Instead of leaking "number of contacts you have", we would be leaking roughly "number of messages we expect to receive across all contacts". I'm not sure which is better. However, unless we have private information transfer[1], the server is always going to know the rate of message receipt (since it is receiving the actual messages), so the best we can hope for is to not reveal more information than that.

One thing you could do to improve on the leak, is generate $MANY tokens at once, send them all to the server, then later separately hand them out to contacts (either for new contacts or to refresh existing contacts' token pools).

> 
>> 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.
> 
> Note that just sending unique auth-tokens alongside the message isn't
> enough, I think the tokens need to be public-key signatures over the
> message, so that the mailbox server can't make it appear that a
> contact is spamming you by associating junk messages with valid
> tokens.
> 

I was thinking of this as two separate problems. Each token only authorises a message to be stored at the server, but the authenticity of the message still needs to be checked by the client. Assuming that the server is ok to store opaque blobs, I think this incomplete scheme could work:

- Bob randomly generates (i, ks), and confidentially gives them to both Alice and the server.
- Alice sends to the server (i, MacWithOrig(ks, blob))
- "blob" would be anything that would be considered safe to be attacked by an adversary, that hides Alice's identity except to Bob, e.g. MacWithOrig(k1, Enc(k2, message)).

Notes:

- There is no point in Bob verifying the mac from ks, since the server can forge a correct one anyway. He wants to decrypt-verify "blob" instead.
- The server can make up fake blobs and spam Bob, but he can do that in any circumstance - the server-faked blobs cannot be verified to a contact, so Bob can discard them.
- As per vital security practise (and as not done in PGP-encrypted email) by "message" I mean including all the metadata, e.g. {to: [Bob, other recipients], body}
- The {i}s are only to help the server find the right ks to verify the mac, so can be quite short. (I thought a random one would be less easy to fingerprint than an incremental counter.)

(The above may well contain flaws, it's just a sketch to demonstrate the separation of purpose.)

X

[1] Not sure if "PIT" is a common phrase, but the others I know about don't fit:
- PIR, private information retrieval = recipient (client) knows, sender (server) doesn't know
- OT, oblivious transfer = sender doesn't know, recipient knows
- we want = sender (client) knows, recipient (server) doesn't know

-- 
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/20140403/18e7c913/attachment.sig>