Guard selection time and expiry

[Sebastian Hahn]

On Jan 19, 2010, at 5:25 PM, Paul Syverson wrote:

> 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.

I think the idea is like this: Today is January 14, and you choose  
according to method 3. You pick Jan 2, Jan 6 and Jan 27. The attacker  
now knows that you picked guards in a timeframe between Jan 13-15,  
because otherwise you couldn't have picked those three dates.

> 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.

This scheme shares a similar problem: Today is Jan 28, and you pick  
Jan 4, Jan 12 and Jan 26. The attacker now knows that the timeframe is  
Jan 26 to Feb 1.

I wonder how much this actually matters, though. Both of Roger's  
schemes pick dates that might be in the future (up to two weeks for  
scheme 3, up to one month for scheme 2), so if an adversary gets a  
hold of your state file, the dates are obviously false. After two and  
a half months (or less time), though, our guard selection changes, so  
it seems that with a good probability, the adversary will learn  
something valuable from our state file regardless.

Am I missing something?

Sebastian