[messaging] Recognizing senders of metadata-hidden messages

[Trevor Perrin]

On Mon, Jul 27, 2015 at 11:07 PM, Brian Warner <warner at lothar.com> wrote:
>
>
> Since Trevor suggested that we might combine the delivery token with the
> ratchet, I went ahead and wrote up what an all-token protocol would look
> like, where each (single-use) token is used both for mailbox delivery
> and recipient key selection:
>
>  http://www.lothar.com/blog/53-petmail-delivery/
>
> It assumes Curve25519 keypairs are cheap, and tries to minimize each
> side's obligation to model the other's ratchet state ("did they see my
> new key yet? can I get rid of my old privkey yet?"). The basic flow
> would be:
>
> * Recipient maintains a set of a few thousand Curve25519 keypairs. For
>   each one, they derive privkey -> pubkey -> HMAC key -> HKID (mostly by
>   hashing), and remember a table that maps HKID->(senderid, privkey).
>   Each is single-use, and it creates more to replace them as they get
>   used up.
>
> * Recipient gives the HMAC keys to the Mailbox server, keeping it
>   up-to-date as new ones are created. Mailbox maintains a table mapping
>   HKID->(HMAC key, recipient).
>
> * Recipient gives some pubkeys to each sender, keeping them stocked with
>   maybe 20 at a time.


For comparison, the Pond delivery-token scheme was sketched here:

https://moderncrypto.org/mail-archive/messaging/2014/000409.html

One thing I prefer about it is that the message is signed by a
one-time private key that the recipient gives to the sender.  If the
recipient receives a junk message that fails to decrypt she can
distinguish whether the sender actually sent junk (valid signature),
or the mailbox provider tampered with the message (invalid signature).
Your scheme can't distinguish these.

A more debateable difference is that in the Pond scheme the server
maintains a blacklist of tokens that were seen or revoked.  In your
scheme the client gives the server a whitelist of tokens.  The Pond
scheme has less recipient<->mailbox communication, but at the cost of
a growing blacklist.  We've discussed these tradeoffs, and
optimizations for the blacklist, before:

https://moderncrypto.org/mail-archive/messaging/2014/000266.html
https://moderncrypto.org/mail-archive/messaging/2014/000292.html
https://moderncrypto.org/mail-archive/messaging/2014/000413.html


A downside of both schemes is the cost of sending your correspondents
new tokens.  In your scheme tokens are 32 bytes (an EC public key).
In the Pond scheme you need to give each correspondent a one-time-use
private EC key and an HMAC over the corresponding public key.
Depending on your willingness to truncate these, this could be 24-48
bytes per token:

https://moderncrypto.org/mail-archive/messaging/2015/001651.html

That could be costly, particularly for lightweight protocols (text
messaging), bandwidth-limited protocols (Pond), or if you have to
retransmit tokens to deal with lost messages.


One way to shrink this might be to use the Pond scheme but derive the
one-time signing private keys from some ratchet protocol, so
correspondents would only need to distribute the MAC (say, 8 bytes)
per token.

For example, consider a SCIMP-like protocol where each party
"ratchets" their encryption key for sending via k=H(k).  This could be
augmented to derive a per-message signing private key x: (x,k) = H(k).

Your mailbox server only accepts messages if they are accompanied by:
 - a public key y = g^x
 - a signature by y over the message
 - a never-seen-before MAC over y by your "token key" (the token key
is only shared between each recipient and their mailbox server)

Since each side can predict the future signing keys the other party
will use, the parties just have to replenish each other with MACs.

This could also be added to the Axolotl ratchet, but it's not as
simple - you'd have to derive the one-time signing keys from the
header keys, and synchronize delivery of tokens with DH key changes, I
think.


Trevor