[messaging] replay protection in asynchronous mixnets with high throughput

[str4d]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

Jeff Burdges wrote:
> 
> I donno if this decay operation is a standard practice around
> Bloom filters, but it presumably works as follows.
> 
> If you've two filters with *distinct* hash functions on the same 
> elements, rather than new elements, then together they act like a
> bloom filter with twice the bit width as many hash functions, which
> should remain optimal*, but you could now throw away the second
> filter to save memory and increase your false positive rate.
> 
> You'd probably "freeze" the first filter and use only the second 
> freshly cleaned filter for writing, so you membership test
> switches from being in both filters (and) to being in either one
> (or).

This is what I2P does in DecayingBloomFilter - one filter is
read-write, the other is is read-only. The two filters are swapped
every 10 minutes, which is the lifetime of a tunnel. The lifetime of a
message ID in the DecayingBloomFilter is therefore 10-20 minutes,
which ensures that duplicates can be detected for any tunnel
regardless of when it is created relative to the decay cycle.

str4d

> 
> I could imagine doing this if traffic on the old server key slowed
> down as it approaches expiry.  You go from dropping only p^2 false
> replay drops to between p and 1-(1-p)^2 as the second filter fills
> up, where p is the false drop for one filter.
> 
> Sounds reasonable, Jeff
> 
> *  In the naive analysis, if I've two distinct filters on the same 
> elements with the same values for p and m/n, then together they've 
> effectively p^2 and 2*m/n because 2 ln(p) = ln(p^2), so trashing
> one gives you one filter with parameters p and m/n.  I've sen
> articles that improve on the usual analysis for Bloom filters.  If
> I recall, they show that you lose some efficiency doing this, but
> probably not enough to care about.  It's maybe another reason why
> you'd only want to decay once though.
> 
> 
> 
> 
> 
> 
> On Fri, 2015-10-09 at 21:10 +0000, str4d wrote:
>> Jeff Burdges wrote:
>>> 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.
>> 
>> Quoting that documentation page:
>> 
>> "Even though the tunnels within I2P bear a resemblance to a
>> circuit switched network, everything within I2P is strictly
>> message based - tunnels are merely accounting tricks to help
>> organize the delivery of messages. No assumptions are made
>> regarding reliability or ordering of messages, and
>> retransmissions are left to higher levels (e.g. I2P's client
>> layer streaming library). This allows I2P to take advantage of 
>> throttling techniques available to both packet switched and
>> circuit switched networks."
>> 
>> In I2P's case, replay protection is a) good for the routers, and
>> b) necessary to prevent certain classes of attacks. It does put
>> upper limits on the bandwidth that routers can share with the
>> network, so to balance the Bloom filter memory requirements we
>> adjust the parameters depending on what the router is configured
>> to share. Our absolute maximum was 4MBps for a long time, but
>> after requests from users that were filling that easily, our
>> current maximum shared bandwidth is 16MBps .
>> 
>> See [0] for our Bloom filter impl, and an analysis of false
>> positive rates. See [1] for how we select the size of the Bloom
>> filter based on the shared bandwidth and configured memory. See
>> [2] for the decaying hash set that we use in several other places
>> instead of a Bloom filter.
>> 
>> str4d
>> 
>> [0] 
>> https://github.com/i2p/i2p.i2p/blob/master/router/java/src/net/i2p/ro
>>
>> 
ute
>> r/util/DecayingBloomFilter.java [1] 
>> https://github.com/i2p/i2p.i2p/blob/master/router/java/src/net/i2p/ro
>>
>> 
ute
>> r/tunnel/BloomFilterIVValidator.java [2] 
>> https://github.com/i2p/i2p.i2p/blob/master/router/java/src/net/i2p/ro
>>
>> 
ute
>> r/util/DecayingHashSet.java 
>> _______________________________________________ Messaging mailing
>> list Messaging at moderncrypto.org 
>> https://moderncrypto.org/mailman/listinfo/messaging
>> 
>> 
>> _______________________________________________ Messaging mailing
>> list Messaging at moderncrypto.org 
>> https://moderncrypto.org/mailman/listinfo/messaging
-----BEGIN PGP SIGNATURE-----

iQIcBAEBCgAGBQJWGZSgAAoJEBO17ljAn7PgM1AQAIg1GUs3a6NsUMCVyG5nxgVy
FvP9pnVogjE1ghhuqadVofeIPl8ijXjfhhiZz9Ex+py9H1Tk84AXRaa1Sw/v8llL
T4uB4yEN/Vv2d2AwmtgmX6PNxRwtDbaCjtv2/wPYf+3s5O0QMgxyjvULGYXefr9D
8nBmwneg1oWsclttCRYRNRjMQns3qwigAqviIBJ0mIhN8XtOQ6kjgkdbnKAelmIj
bjH8HtwZAsVt0phruJ8qHuDszYJPjFvArFLScgQ2u9eYnLH/VwVNfB8LoxY0qysu
7p3y4jwDcLS6c3F6FWMuCuTghAV7lqZWg74gl8Liy7aR7IFpiL/FLRiH4GR9OTiX
32WYTA9bXi9Ef61tSq2U1l4XPFN4FAriJQURuB/S+tKc7Wm4HCM8GS8e3AwE9Iwq
79KRjLD+cT/9ZHiuo53opWoGYzVVr8N0EjXih0lAAkBKv1oooRMyz2UUEmXMS/Gm
PLZoJz/qL5RTP2aAmN0uhBUZoiy7eMNRXVbL4x8RQueLCMXYdU/wEvWi4E2bFpfj
kPWP1NJYM6o56kUMnh4kLxBmqn7l8kzbQF1d/6Fw/NOJBZZe920wzatrRwEdSuYO
i5U6VxpjktuxtFA14+eAWxBFGWlYjV7cqQ6lhcvhK04kXW1WSK8qAogpE2FetHNd
F+uOgKx5y/Bu1us2ZF5n
=gD1k
-----END PGP SIGNATURE-----