Guard selection time and expiry

[Paul Syverson]

Hi Roger et al.,

On Tue, Jan 19, 2010 at 12:29:34AM -0500, Roger Dingledine wrote:
> 
> Option 2: Rather than writing "2010-01-01 00:00:00", pick a random time
> in January. Then expire the guard 45 days after this random time. Minimum
> time to keep a guard is 0.5 months (on Jan 31 I randomly choose to record
> Jan 1, and then I discard it on Feb 15), maximum time is 2.5 months (on
> Jan 1 I write down Jan 31, and discard it on Mar 15), expected time is
> 1.5 months.
> 
> Option 3: When recording the selection time for the guard, pick a random
> timestamp from two weeks in the past to two weeks in the future. Then
> discard the guard 45 days after the timestamp. Minimum time is 1 month,
> maximum time 2 months, expected time 1.5 months.
> 
> Option 2 has the disadvantage of a wider time distribution (if that's
> a disadvantage). Other than that, it seems to share exactly whatever
> privacy properties we get from Option 1.
> 
> Option 3 matches the distribution time, but it has a potential privacy
> problem: if I pick three guards at once, somebody examining my state
> file can bound the true timeframe. That makes me nervous because it
> sounds like one of those messy anonymity issues that gets messier the
> more you look at it.
> 
> So I'm going to go with option 2. Unless anybody else has clever ideas?
> 

Ideas, probably not clever. I'm confused by the potential problem you
cite for option 3. In option 2, somebody examining your state file
will know that these three guards were chosen during January.  If the
file is examined on January 2, for example, the attacker will know
exactly what day the nodes were picked. And he can also bound the true
timeframe for any date in January later than the actual date.  By
contrast, in option 3, the best he can do is know that the nodes were
chosen not more than two weeks in the past. So with option 2 he could
potentially know more. He also knows what time of the month these
attacks are most effective.

Why not combine the two options?
Pick a random timestamp during the last four weeks and an expiry 45
days in the future of the timestamp. (Or if you don't like the resulting
expected expiry time or range, make it 60 days or some other time
after the timestamp.) Note that if your timestamps just happen to all
be recent, he will know that, but with option 2 there are times when
this is guaranteed to work rather than just occasional luck. If you
want to make even this less likely you could add a check that at least
one timestamp must be more than some amount old and then throw out the
the third chosen guard's timestamp if none are old enough and pick
again. Don't know if that seems to complex, and this is after reading
your message and responding immediately. Might be problems if I
thought about it more.

HTH,
Paul