[tor-dev] Introduction Points and their rotation periods (was Re: Hidden Service Scaling)

[Michael Rogers]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

On 11/05/14 17:36, George Kadianakis wrote:
>> I think it would be good for the performance of mobile hidden
>> services, but I'm concerned about the attack waldo described
>> eariler in this thread, in which a malicious IP breaks circuits
>> until the service builds a circuit through a malicious middle 
>> node, allowing the attacker to discover the service's entry
>> guard.
>> 
> 
> I couldn't find the attack you described in this thread. This
> thread is quite big.

The attack was described here:
https://lists.torproject.org/pipermail/tor-dev/2014-May/006807.html

> However, I'm not sure how rotating IPs _more frequently_ can help 
> against the guard discovery attack you described. It would seem to
> me that the contrary is true (the fewer IPs you go through, the
> less probability you have for one of them to be adversarial).

I'm not suggesting that fast rotation would be better than slow
rotation, but there are some possibilities that don't involve periodic
rotation at all.

One possibility (which might be the current behaviour?) is that if the
circuit to an IP fails, you build a new circuit to a new IP rather
than a new circuit to the same IP. Advantage: not vulnerable to
waldo's attack. Disadvantage: rapid turnover of IPs.

Another possibility is to rebuild the circuit through the same nodes
if possible, or if not, build an entirely new circuit to a new IP.
This would prevent waldo's attack, but it might still cause rapid
turnover of IPs unless all nodes in the circuit were chosen from the
high-uptime pool.

A third possibility (which might be the virtual circuits idea?) is to
reuse the nodes in the circuit up to the point of failure, and pick
new nodes beyond that point. But that would seem to be vulnerable to a
selective DoS attack where a bad node vetoes any attempt to extend the
circuit to a good node, thus causing any circuit that hits a bad node
to pass through bad nodes from that point on (similar to MorphMix).

A fourth possibility is to rank the candidate nodes for each position
in the circuit, and build the circuit through the highest-ranked
candidate for each position that's currently online. Thus whenever the
circuit's rebuilt it will pass through the same nodes if possible, or
mostly the same nodes if some of the favourite candidates are offline.
Over time the circuit will gradually move to new nodes due to churn -
but that will happen as slowly for this design as it can happen for
any design.

The ranking for each position should be secret so that if an attacker
knows what a client's favourite node is, she can't make one of her
nodes the second-favourite and wait for the favourite to fail. And the
ranking for different circuits should be independent so the client's
circuits don't leak information about each other.

One way to achieve those properties would be to generate a secret key
for each circuit and rank the candidates for each position according
to a pseudo-random function of the key, the candidate's fingerprint
and the position. The key wouldn't be shared with anyone, it would
just be used to rank the candidates.

A MAC function such as HMAC could serve as the pseudo-random function:
sort by HMAC(key,fingerprint|position). HASH(key|fingerprint|position)
would be another possibility, but MAC functions are explicitly
designed to keep the key secret.

The key would be preserved across sessions for as long as the circuit
was wanted - I guess the lifetime would be unlimited for IP circuits,
and application-determined for ordinary client circuits. It would be
great if an application could signal to the OP "this circuit belongs
to long-lived identity X" and get the same circuit (churn permitting)
that was previously used for identity X.

As far as I can see, the same entry guards should be used for all
circuits, regardless of application-layer identity - otherwise a local
observer watching a user could make observations like "Every Wednesday
morning, the user connects to guard Y" and correlate those with the
activity of a pseudonym (emails, blog updates, etc). So when choosing
nodes for a circuit, the candidates for the first position should be
the client's entry guards.

If this idea hasn't already been proposed, I suggest we call it
persistent circuits.

>> Perhaps the attack could be mitigated by keeping the same middle
>> node and IP for as long as possible, then choosing a new middle
>> node *and* a new IP when either of them became unavailable? Then
>> a malicious IP that broke a circuit would push the circuit onto a
>> new IP.
>> 
> 
> Also see 
> https://lists.torproject.org/pipermail/tor-dev/2013-October/005621.html
> .
> 
> Unfortunately, it seems to me that the 'virtual circuit' idea is 
> messier than we imagine, and taking the 'guard layers' approach
> might be less dangerous and easier to analyze.

Interesting, thanks for the link! Has anything been written about how
the guard layers approach would work other than Mike Perry's comment
on ticket #9001?

Cheers,
Michael
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)

iQEcBAEBCAAGBQJTclYpAAoJEBEET9GfxSfMoVYH/2Lg8C01QvpA3a2e4dVcptVJ
6caoQFY3ETfIZTWbNqyM6+q69PPDzzIRPYjjSW1Dt0b+9L6k0wRfrVD9Uqo3OjgC
C3KpitS2UtqKCELA8gukAB9QJWkW3HShrPNwildS53kOn/5iSulmb4W4kxu7rkJk
PHYlR8OiVIlNfpjI6DbLnLlZM/UoKZakf/m28BPO5T+0f4kCl5uLl8WXTp2C6656
m3/H0FJYCJEkFp08ovm/mwrbAiYAVpB1cx0uYgc/Oax0s6w0GuWpJVYb9EmkmS1M
l3H2iVzt5Irky2iNjbesU/St+5bB56sUe5FC/shAsHUielKykzOF01XGZKZ6l4w=
=Yt4u
-----END PGP SIGNATURE-----