[messaging] Recognizing senders of metadata-hidden messages (was: MPHFs for public key lookup?)

[Trevor Perrin]

On Mon, Jul 6, 2015 at 12:00 PM, Trevor Perrin <trevp at trevp.net> wrote:
>
> Brian and Michael suggest a clever "tag" approach:
>  - The message contains a one-way function of the message key [tag = PRF(k)]
>  - The recipient can then recognize the key with a single lookup
>
> This could still be a lot of key tags to store on the recipient side
> (1000s of potential senders multiplied by 10s or 100s of message
> numbers?)  I think Brian's Petmail only has a current/next key, which
> reduces the number, but Michael's Briar I think tags every message
> key.
>
> One alternative would be to tag a "header key" that changes less
> frequently than the message keys, and encrypts a header containing the
> message number.  E.g. Pond's header key is changed on every
> round-trip, but not on every message, so you'd only have to tag 2 keys
> (current/next header key)


Oops, sorry: If you reuse tags the messages will be linked which
violates metadata-hiding.

And I wasn't that accurate about Petmail [1] and Briar [2].  They
generate tags based on a single key and the message number, so
different tags recognize the same underlying key.  For Petmail this
key (CIDKey) is fixed between correspondents, for Briar the tag key
changes each time period.

An alternative would be to associate each tag directly to a message
decryption key, so that key could be deleted after processing the
message.

I guess Petmail avoids that because it only wants to check a single
tag per correspondent, then fall back to trial decryption using
CIDKey?  Briar is willing to use a rolling window of tags, so I wonder
if tags could more directly indicate message decryption keys.


Trevor


[1] https://github.com/warner/petmail/blob/master/docs/mailbox.md#sender-flow
[2] https://code.briarproject.org/akwizgran/briar/wikis/BTP