[tor-dev] Next version of the algorithm

[Ola Bini]

Hi there,

Thanks again! Really appreciate you spending so much time with us fine
tuning this.

> > The full algorithm is referred to as ALGO_CHOOSE_ENTRY_GUARD. It is divided
> > into three components, such that the full algorithm is implemented by first
> > invocing ALGO_CHOOSE_ENTRY_GUARD_START, then repeatedly calling
> > ALGO_CHOOSE_ENTRY_GUARD_NEXT and finally calling ALGO_CHOOSE_ENTRY_GUARD_END.
> >
>
> That's helpful. Maybe we can also put the pseudocode that you posted in a
> previous mail in the appendix to provide more context?
Yep, absolutely.

> It would be nice to know if the security/performance tradeoff here is
> acceptable. Simulations might help, or we will have to learn it the hard way
> when we implement the algorithm and try it out in various types of
> networks.
Yes, interesting. Hmm. I'll try to come up with an unreachable measure
that sits outside of the algorithm, and see if we can simulate both alternatives.

>
> >         If a new consensus has arrived:
> >             Update all guard profiles with new bad/non-bad information
> >             If any PRIMARY_GUARDS have become bad:
> >                 re-add to the list of PRIMARY_GUARDS using the same procedure
>
> And also remove the primary guard that has become bad, right?
Yes, corrected.

> >             If any USED_GUARDS have become non-bad:
> >                 add it back to PRIMARY_GUARDS at the place it would have been if it was non-bad when running ALGO_CHOOSE_ENTRY_GUARD_START. If this results in PRIMARY_GUARDS being larger than N_PRIMARY_GUARDS, remove from the end of the list until the list is N_PRIMARY_GUARDS long
>
> How do we know that a guard in USED_GUARDS that just became non-bad deserves to
> be a primary guard? Even if it's the first guard in the USED_GUARDS list, how
> do we know whether it has priority over the last guard of the PRIMARY_GUARDS
> list?  Do we need to keep state of previous PRIMARY_GUARDS sets?
Well, my understanding is this - under ideal circumstances, the first
guards in USED_GUARDS will always be the same as PRIMARY_GUARDS -
since PRIMARY_GUARDS is a temporary abstraction only used inside of
the algorithm. So based on that, USED_GUARDS is all the persistent
state we have.

> Isn't this implicit in "Update all guard profiles with new bad/non-bad information"?
> Maybe these can be merged into a single step that explicitly
> mentions the guardlists that need to be updated.
Yes, removed that.

> >         STATE_TRY_UTOPIC:
> >             for each entry in TRIED_GUARDS that was marked as unreachable more than 20 minutes ago
> >                 add it back to REMAINING_UTOPIC_GUARDS
> >             return each remaining entry from USED_GUARDS in turn
>
> What does "remaining" means here? Is it the next USED_GUARDS entry that has not
> been marked as unreachable?
Changed it to read like this:
   "return each entry from USED_GUARDS not in PRIMARY_GUARDS in turn"
hope that is clearer.

>
> >                 for each entry, if algorithm doesn't terminate
> >                     mark entry as "unreachable"
> >                     add entry to TRIED_GUARDS
> >                     if the number of entries in TRIED_GUARDS that were tried within GUARDS_TRY_THRESHOLD_TIME is larger than GUARDS_TRY_THRESHOLD, return failure from ALGO_CHOOSE_ENTRY_GUARD.
> >                     if the number of entries in TRIED_GUARDS is larger than a GUARDS_FAILOVER_THRESHOLD proportion of UTOPIC_GUARDS, set state = STATE_TRY_DYSTOPIC
>
> I wonder if returning failure and exiting the algorithm is the right thing to do in this case.
>
> Basically, we just connected to too many different guards and we want to stop
> exposing ourselves to more of the network. This is something that can happen
> during an attack, but also something that happens naturally all the time when
> the network is down. So we can't just have Tor exit().
>
> Instead, we probably want to keep our guardlist and continue connecting to the
> guards we already have till the network comes up again.
>
> If we return failure here and exit the algorithm, then when we restart the
> algorithm we will have forgetten the TRIED_GUARDS list and hence all the guards
> that we tried in our previous run. Then we will attempt to connect to
> GUARDS_TRY_THRESHOLD new guards again. Which is probably exactly what the
> adversary wants.
>
> So maybe failure is not an option here, and instead we should massage our
> current guardlist and start from the beginning without adding more guards?
>
> What do you think?
Ugh. You're completely right. Not a good idea. OK - so what if we
instead of returning failure enter a new state where we only ever
retry guards in TRIED_GUARDS?

> >                     if the number of entries in TRIED_GUARDS that were tried within GUARDS_TRY_THRESHOLD_TIME is larger than GUARDS_TRY_THRESHOLD, return failure from ALGO_CHOOSE_ENTRY_GUARD.
> >                     if the number of entries in TRIED_GUARDS is larger than a GUARDS_FAILOVER_THRESHOLD proportion of UTOPIC_GUARDS, set state = STATE_TRY_DYSTOPIC
> >
>
> Also, I'm not sure I understand the precise security properties that the above two
> checks provide us with. Are both checks needed? Could you explain
> them to me please?
The first one is to make it possible to constrain how many guards we
ever try to connect to, in order to minimize our exposure in a shorter
amount of time.

The second one is to switch over from utopic conditions to dystopic
conditions. IF we are in dystopic conditions, then this heuristic will
make it more likely we will faster find a guard to connect to.


> >     ALGO_CHOOSE_ENTRY_GUARD_END:
> >         If circuit is set up correctly, let algorithm know
> >             Algorithm marks the guard chosen as used and makes sure it is in USED_GUARDS
> >
>
> Maybe instead of "makes sure it is in" we should say "adds it in"?
> It has not been added in a previous step from what I see.
Well, since USED_GUARDS is persistent, the guard could have been added
in a previous run of the Tor client - that's why I said "makes sure it
is in". If you disagree, I can change the language. =)

Cheers
-- 
 Ola Bini (https://olabini.se)

 "Yields falsehood when quined" yields falsehood when quined.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 931 bytes
Desc: not available
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20160211/d793375b/attachment.sig>