Is it desirable to prevent users from choosing their own circuits?

[Brian Mearns]

On Thu, Oct 1, 2009 at 3:13 PM, Martin Fick <mogulguy at yahoo.com> wrote:
> --- On Thu, 10/1/09, Brian Mearns <bmearns at ieee.org> wrote:
>
>> My understanding is that Tor user's are responsible (via their client)
>> for creating their own circuit, and that this is typically
>> done at random. However, are there any safeguards in place to
>> ensure that it is random, and would this be desirable? I would imagine
>> that attackers might try to choose specific circuits in order to learn
>> more about particular nodes, and the network in general. Would
>> preventing this behavior be helpful, and if so, would it be helpful
>> enough to offset any disadvantage it causes for legit users?
>
> I do not think that this would be desirable, random circuits
> have their downfalls.  Other's can elaborate why better I am
> sure.

Ok, good to know. Maybe I'll peruse some more of the literature and
find out why this is a bad thing. Thanks for the response! (more
below).

>
>> My idea is pretty simple. Instead of creating the circuit
>> through black-box means (relying on their local RNGs, for
>> instance), the user would create some seed value S, and then
>> a list of random adjustment values, R0, R1, R2,..., one for
>> each relay in the circuit. The S value
>> would be used to enforce randomness in the circuit, but the
>> R values would be used to hide their circuit from relays as usual.
>>
>> Creating the onion, the user would put a different R value
>> into each layer, encrypted for that relay, of course. To create the
>> circuit, they would take a hash of S+R0 to get the address of the
>> first relay:
>> A1 = H(S+R0), and then hash this plus R1 to get the second
>> relay: A2 = H(H(S+R0)+R1)), and so on.
>
> Perhaps I don't understand your suggestion, but how
> would a hash translate to a relay address?  The
> maximum possible strength of a hash is related to the
> size of its address space, if this is limited to the
> number of relays available, it would be pretty weak.
> I would imagine that an 8 bit cpu is likely to be
> able to easily run through enough hash input
> combinations to get the address of any tor relay in
> the network, wouldn't they?
>
> -Martin
>[clip]

I'm no expert, but I'm pretty confident the hash is not weakened by
the limited address space, or at least not nearly as much as you seem
to think. One simple way you could use it (maybe not the most
practical) would be as follows: compile a list of all available nodes,
sorted by IP address or nickname or something. Take the output of the
hash as a value, and evaluate it modulus the size of the list: the
residue can be used to index into the list.

For instance, if the hash is 512 bits, but there are only 1024 nodes
in the list, is this as weak as a 10 bit hash? I don't think so. You
seem to be suggesting that an attacker (someone who wants to force a
certain circuit) could simply enumerate 1024 different input values
for the hash function, until they find the one that gives them the
node they want using the prescribed method of selecting. If the hash
is strong, I don't believe (again, not an expert on this) that there
is any guarantee that any particular set of 1024 different input
values will necessarily correspond to 1024 unique nodes. Every
different input will almost certainly have a different hash, but
taking these hashes mod 1024 may very well yield a number of
collisions. In other words, just because they tried 1024 different
input values, doesn't necessarily mean they will get 1024 different
output values (from the selection function, not the hash function
directly).

Of course, modulus probably isn't the best way to do this, since it's
slightly biased towards the beginning of the list in most cases. But
that's just a simple example of how you might choose a node from a
hash. I actually decided to run some tests just now to check on this.
Using a 512 bit hash (SHA-512) and a 1024 nodes, I enumerated through
some possible input values, starting with 0 and just going up by 1
each time. Just taking the hash mod 1024 to choose the nodes, I
enumerated the first 1024 input values and only selected 640 unique
nodes. Enumerating the first 2048 nodes got me up to 72 unique nodes,
and enumerating 4096 got very close to all of them at 1008 unique
selections. Obviously, that did significantly weaken the hash, but
still not as weak as a 10 bit hash. Also, I was able to strengthen it
slightly more just by breaking the hash into upper and lower 256-bit
values, adding them together, and then taking the sum modulus the
number of nodes. It was only a slight improvement, but it was also a
simple and not very well thought through modification. I'm guessing
that a smarter person that I could figure out a better selection
function.

I guess this is starting to get off topic, but I would very much love
it if anyone with more expertise on hashes can argue either for or
against my assertion that the reduced selection space does not
significantly weaken the hash.

Thanks,
-Brian

-- 
Feel free to contact me using PGP Encryption:
Key Id: 0x3AA70848
Available from: http://keys.gnupg.net
***********************************************************************
To unsubscribe, send an e-mail to majordomo at torproject.org with
unsubscribe or-talk    in the body. http://archives.seul.org/or/talk/