[messaging] replay protection is asynchronous mixnets with high throughput

[Jeff Burdges]

Any thoughts on doing replay protection in an asynchronous mixnet?  Any
favorite reply protection schemes?  What if we've relatively high load?

I think the Sphinx paper merely specifies that replay protection should
be done, presumably by remembering the ECDH values, and doing key
rotation.  Amusingly, the HORNET paper specifies that replay protection
should not be done for performance reasons, but anyone I've seen discuss
applying HORNET assumed they need to add replay protection. 

Afaik there is no sense in deploying a mixnet without near perfect
replay protection because replays are a form of tagging.  Just attack a
user by arranging with their ISP to be their guard, and have enough
nodes in the network to see where the replays go.  Attacks on hidden
services are even easier to launch, but require analogous work on the
recipient end.  

If near perfect replay protection were not required, then one could
imagine using a sequence of bloom filters so that every n-th replay of
the same message got caught, and some replays got caught sooner.  
There is no obvious combination of mixnet properties that clearly makes
such schemes viable though.  Although there might be interesting results
using n=2, rapid key rotation, and adding some dummy replays, not sure.

It's almost like synchronous and asynchronous mixnets have really
different failure modes or something. 

Tor provides replay protection by building circuits using live DH
handshakes and giving packets sequence numbers.  In Tor, these high
performance circuits expose the user to correlation attacks, but perhaps
a higher latency mixnets could still build circuits using semi-live DH
handshakes, thereby defending against correlation attacks.  

Tor relays may otoh freely observe the traffic pattern on any particular
circuit.  There are ways to mitigate the risks from analysis of traffic
patterns, like keeping a constant traffic profile, as in Pond, but if
one carries on this line of though then one again arrives at an
asynchronous mixnet situation.  

There might be asynchronous solutions that employ an alternative
distribution scheme for node's ephemeral key material and sequence
numbers attached to specific ephemeral key.  

Example :  Use essentially Sphinx but with two DH operations.  First, we
pair the packet's ephemeral key with the node's long term key to select
the node's quasi-ephemeral key and give a sequence number.  Second, we
pair the packet's ephemeral key with the node's quasi-ephemeral key and
combine both operations to get the packet body key.  User nodes trade
quasi-ephemeral keys and sequence numbers amongst themselves, so that
any particular node sees a bunch of traffic from different users on the
same quasi-ephemeral key.  

It's unclear if this would be all that much better than simply asking
for new ephemeral keys lots.  And it creates a new style of denial of
service attack on the network. 

Thoughts?
Jeff

p.s.   One could imagine using a partial order in place of sequence
numbers, or maybe some sort of pairing based cryptography, but any
schemes I've thought up kinda suck.