daystamp attacks

[Roger Dingledine <arma@mit.edu>]

Right now we've got a 'daystamp' in each message, to indicate on which
day it will be valid. Mixes must drop a message which arrives with a
daystamp that isn't today. This will interact in unintuitive ways with
the fact that our mix-net is not zero-latency.

Scenario: Alice sends a message at 10pm Tuesday, through 4 hops. Each
hop delays for around an hour. Her message doesn't get through.

Alice could fix this by tagging her first two hops Tuesday, and the
next two Wednesday. If the timing works out, her mail will arrive
normally. "If" -- since Alice doesn't know the delay on a given hop,
she can't really be very sure.

Alice could fix this by sending her mail sufficiently before midnight that
it will probably make it through. That kind of sucks.

The mixes now have a new traffic analysis attack to perform as well:
they can partition the set of messages they get into those labelled
before midnight and those labelled after. This presumably gives some
information about when the sender thought they'd be getting there. Eg,
a mail dated tomorrow was probably sent relatively recently.

The solution is to make the daystamp only loosely enforced: mails are
still valid if it's within a day of the daystamp on either side. This
gets rid of the 11:59 vs 12:01 fencepost.

But it still leaves some tricky attacks. For instance, what daystamp(s)
should Alice use if she sends her mail at 11pm and it uses 5 hops? If she
dates them all Tuesday, then mixes toward the end of her path can still
partition the 'Tuesday' messages and consider them separately. Should
she date them randomly? With some distribution? I imagine there are also
intentional-delaying attacks that will make certain messages expire,
not expire, etc, all leaking information.

And reply blocks need to have these daystamps too. If we assume that
messages are fully delivered within 24 hours, and we allow the one day
buffer on the daystamp, is it sufficient to just bundle which day it's
valid for along with the reply block?

Hm.
--Roger