[messaging] replay protection in asynchronous mixnets with high throughput

[Jeff Burdges]

Appears there is a choice of parameters that allows replay protection
even under high load with a simple Bloom filter, assuming routers have
a reasonable schedule for rotating their temporary public keys.  I'll
explain..


There is always some risk that packets do not reach their destination,
at least due to churn in the network if nothing else.  We could thus
use a Bloom filter where the probability p of a false positive was
below the probability of a packet being dropped due to churn.

If we (a) fix a desired false positive probability p like this, and (b)
assume that the number of hash functions was chosen to minimize the
false positive probability, then the desired length m of a Bloom filter
to achieve false probability p is proportionate to the number of
elements n being added.  We're not actually scaling storage here, but
assigning enough to handle all the possible traffic in the first place.
The actual equation is 
        m/n = - ln(p) / ln(2)^2
where m/n means Bloom filter bit width per expected message.

Just a quick table :
 p       m/n
0.05     6.235
0.01     9.585
0.005   11.028
0.001   14.378
0.0005  15.82
0.0001  19.17
0.00005 20.613
0.00001 23.963

We could for example allocate two bytes of memory per expected packet
so that we'd drop 1 in 2000 messages.  I think that's already 20 time
better than good quality UDP for audio.  We could step it up to 3 bytes
per message for a drop rate of only 1 in 100,000 messages.

In fact, we're doing better than that because our 0.05% drop rate
occurs towards the end of our Bloom filter's time time.  I'd need to
work this out more carefully to amortize it, but if mix nodes using
overlapping temporary key time intervals then we could use full filters
for low priority traffic and use fresh ones for user's messages.  Also,
one can simply freeze a full Bloom filter, halting new additions but
continuing to check it, and start a new one for additions.

We do need to allocate all this memory up front, which kinda sucks, but
okay.  I suppose Bloom filters are unfriendly to CPU cache, but
presumably anything doing this job has that property. 

Appears the fastest Tor routers push about 50 MB/s, according to 
https://torstatus.blutmagie.de/index.php?SR=Bandwidth&SO=Desc
We desire significantly higher latency than Tor, but high throughput
remains desirable, so 50MB/s sounds reasonable.  If we imagine 16k
messages like Pond, then that's around 400 messages per second, or
about 1.5 million messages per hour.  We therefore want around 3 megs
of RAM per hour of temporary key lifetime, for a 0.05% dropped rate, or
about 4.5 megs for 0.001% dropped.


We've occasionally mentioned this notion of "dialing" from the Vuvuzela paper, presumably elsewhere too.  It says that one should not expect to use the same transport for talking to people you spoke with recently as for starting conversations.  I suspect this notion of "dialed" connection will dictate the minimum lifetime of a temporary key.

In other words, if we're currently speaking repeatedly, then we should have our own "dialed" route through the network with different bi-directional anonymity properties than our regular undialed route.  It's unclear if the dialed channel should go through a mailbox server at all, but definitely not our usual mailboxes.  If the dialed channel does not use a mailbox then, after some hours, any message sent along the dialed channel that remain unacked should be resent along the undialed channel. 

We can safely assume that people sleep, so 24 hours should be a safe interval for expiring temporary public keys, so that's 72 or 108 megs for one key at 0.05% or 0.001% dropped, respectively.  If we start a new key every 8 hours, expire keys after 24 hours, and keep an extra-Bloom filter to let us freeze the oldest one, then that's 288 megs or 432 megs, respectively.  

By comparison, that's about how much ram it costs to delay the same 50 MB/s by 1 minute. 

All this does assume that I'm willing to give my contacts the identity of some node where they can send me undialed messages, but okay.  


Apologies if this rambled slightly, but I wanted to correct my earlier concerns that replay protection was hard for a network using Sphinx.  It's not hard if we restrict to "dialed" connections, existing Tor speeds, and Pond-like message sizes. 

Jeff

p.s.  After writing this, I noticed that bizarrely I2P actually does
roughly this :
https://geti2p.net/en/docs/tunnels/implementation
It seems odd to do so since they've circuits, but maybe messages can
get out of order in their tunnels or something.  Or maybe they're being
unclear.

p.s.  The HORNET paper wants like 100 Gb/s throughput and smaller
packet sizes.  I donno if people really want to put a terabyte of ram
into a router, but maybe applications could put a request for replay
protection and delay into the packet, so only important packets got
replay protection plus delays, and they only got it at some routers. 




On Wed, 2015-09-23 at 16:36 +0200, Jeff Burdges wrote:
> 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.
...
-------------- 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/20151009/c4ae13f0/attachment.sig>