Guard selection time and expiry

[Paul Syverson]

On Tue, Jan 19, 2010 at 05:51:59PM +0100, Sebastian Hahn wrote:
>
> 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.

Umm. If the adversary can know that you just picked three guards
today, he doesn't need to do this analysis to learn that you picked
three guards sometime in a three day window. He knows what day today
is.  So that threat is moot. (I actually was thinking similarly at
first till this occurred to me, so don't feel bad. If I'm overlooking
something else, please don't make me feel bad ;>)

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

Again, if he knows when you picked them, he knows when you picked them;
he doesn't need to do any analysis to infer less than he already knows.


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

That's why my proposal avoids any false dates. The only way he gets
lucky is if you randomly just picked three timestamps that were close
to the current date and then he got your state file shortly thereafter.
If you want to prevent even that, just add a check when you are choosing
timestamps: if all are more recent than say 10 days, pick again.
Or do the check on the other two timestamps first and then force the pick
to be in the 10 to 30 day range. I'm not the coder and don't know the
advantages of one vs. the other in code simplicity vs. overhead, etc.

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

I assume they are (ir)regularly rotating. What is it that he is
supposed to learn of value from this (other than your guards themselves
of course)?

aloha,
Paul