[messaging] pond alike lists (was: Re: pond alike group messaging)

[Jeff Burdges]

On Wed, 2015-06-17 at 16:57 +0000, azul wrote:
> >> The server could get some information about which connections come from
> >> the same user by observing the messages requested. 
> > 
> > Yes, clients must request their own messages back from the server.  
> > 
> > Also, the server can count the number of participants, unless the
> > clients rate limit themselves, which makes big lists unusable.
> I'm looking at rate limits similar to those pond uses. That would still
> allow for receiving a lot of messages per day.

If you've multiple machines checking a single mailbox then you'll tend
to reveal the number of machines.  

If one adds many independent identically distributed random variables,
like waiting times, then they converge to a normal distribution, by the
Central Limit Theorem.  You therefore cannot have delays the server sees
be exponentially distributed like Pond does, not without breaking the
independence assumption via planning, collusion, etc.  

If you could make it work, like by convincing yourself to use normally
distributed waiting times, then you'd need to reduce how frequently
people checked their mailboxes.  Pond contacts the server on average
every 5 minutes.  If I check the same mailbox from two machines then I
must check on average every 10 minutes.  In fact, it's worse than that
because pond always checks at least once every half hour, which messes
up the distribution.

In any case, If I check the mailbox from 200 machines then I'm only
allowed to check the list's mailbox at most once per day!

> So my main worry with pair wise pond is sending the message to all the
> different recipients. Say you have a list with 100 users and send a
> message every 6 minutes on average. So it would take 10 hours for it to
> get distributed.

Yes, Pond is much too slow for large scale group messaging.

> I would love forward secrecy. But frankly... on a list with 100
> participants message content secrecy is limited. 

We should not give us so easily since SCIMP style hash iteration
ratchets provide some forward secrecy.  I'm too tired to think through
this clearly right now, but one idea :

- Send the group a chain key ck using an underlying pairwise channel
protected by Axolotl.  Redo this operation occasionally.

- Iterate the chain key ck using a hash operation.  Obtain the message
encryption keys from ck using a different hash operation.  And obtain
message sender ids from ck using a third different hash operation.  

- A message header is a hash of the sender id, and an HMAC of the
message with another hash of the sender id. 

If you're on the list then you can impersonate anyone else on the list,
but your victim's client will see the impersonation attempt and issue a
retraction.

We could issue temporary signing keys with ck to prevent impersonation,
but that violates deniability.  We could instead issue different
secondary chain keys to different parts of the list so that any
individual on the list could only impersonate you to less than half the
list.  

Jeff

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: This is a digitally signed message part
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20150617/9e673972/attachment.sig>