[messaging] Security arguments for read receipts

[Natanael]

First, regarding acknowledgements: the job of cryptography is not only to
keep secrets, but also to ensure that the receiver got the full message
exactly as we intended to, with nothing left out. Being able to detect if
something is left out can be crucial. Same with unpredictable ordering.

Den 3 nov 2015 18:52 skrev "Jeff Burdges" <burdges at gnunet.org>:
>
> On Tue, 2015-11-03 at 17:00 +0100, Ximin Luo wrote:
> > > There are a bunch of reasons for using a limited pool of tokens to
> > > authenticate delivery.  I'd imagine such systems might be slow to
> > retry
> > > dropped messages to avoid waisting the tokens, and they'd likely
> > burn
> > > several tokens before complaining that the message dropped, so
> > you've
> > > potentially hours of delay before the system colors your message as
> > > dropped.
> >
> > Not sure why you need a limited pool of tokens to authenticate
> > delivery?
>
> There are not many systems that satisfy both M0/M1 and R0 from :
>
> http://www.lothar.com/blog/53-petmail-delivery/

[...]

So the requirements as you see them are these:
* that each sender gets a token from the receiver that let them tell the
receiver AND the server that there's a valid message, but that only tell
the receiver from who.
* that the receiver can revoke / blacklist individual tokens reasonably
efficiently

So the message tags must be verifiable yet unlinkable to any other if you
lack the tokens, but revealing some knowledge/secret to the server or
replacing some verifier accessible to the server should let it filter out
revoked tokens.

Efficient Zero-knowledge proofs would make it easy. Compute a Merkle tree
hash (verifier) of the valid per-sender tokens (multi-use), let them HMAC
each message with with the tokens and provide a ZKP (unlinkable proof) for
that the token used in the HMAC is in the latest Merkle tree hash and that
the HMAC was computed from the message ciphertext. Revoke by either telling
the server the token for a quick blacklist (easy to do from the phone when
you don't have your full token list ready to create a new Merkle tree
hash), or replace the Merkle tree hash. This still let the senders know the
receiver is the same person (same Merkle tree hash).

Another approach that I came to think of but don't know if it is possible
is to have some RNG-like key derivation algorithm where having the full
original seed let you compute a certain set of keys/tokens, and any subset
/ derivation of that seed generates different (non-overlapping) subsets of
this set of keys. I came to think of this variant by thinking of Bitcoin
hierarchical deterministic wallets with hardened derivation as well as this:
Even more practical secure logging: Tree-based Seekable Sequential Key
Generators - https://eprint.iacr.org/2014/479
Maybe something could be done with ECC math for this? Or with threshold
cryptography? Lattice cryptography? The idea is that only I know what
sub-seeds I derived from the full seed, not the server, and the senders
know their sub-seeds but not the full seed. But I can tell the server what
sub-seeds whose numbers to reject.
If possible, this is simpler than ZKP by far, but also need "refills"
unless the RNG essentially can go on forever and you can shift the allowed
range of outputs forwards by time to limit the set of permissible keys at
any point in time. May also need replacement if you issue too many
sub-seeds to avoid overlap in outputs.

Monero also has some various ECDSA based key derivation and ring signature
algorithms to hide senders and receivers. Look up what they do.

There's also *selectively* linkable / accountable / traceable ring
signatures, where the receiver creates all the sender keypairs and creates
a ring public key from them all. A per-keypair secret is revealed to enable
accountability = linking together messages signed by the same keypair,
allowing for blacklisting. You can easily derive hundreds of keys in
advance (using a KDF and a seed you remember saves space), and each key can
be reused by the sender (until blacklisted). Can't find any good resources
right now though.

Another relevant system is libforwardsec:
https://github.com/imichaelmiers/libforwardsec/
They combine Identity Based Encryption (IBE) that provides one
(individually deletable) private keys per each time interval with a
puncturable algorithm that provides the ability to revoke your decryption
capability for any given set of messages, and lets you create a single
public key for it. If nothing else it will improve the deniability for
receivers. After the first message per sender-receiver pair you can move on
to an axolotl style key ratchet.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20151103/3dad4779/attachment.html>