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

[Martin Fick <mogulguy@xxxxxxxxx>]

--- On Fri, 10/2/09, Brian Mearns <bmearns@xxxxxxxx> wrote:

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

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

Yes.  In fact, that would probably be the criteria 
of a "perfect" hash, wouldn't it?  If not, your hash 
is biased, which has it's own set of problems.  If
the hash is biased, it is not an effective 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. 

Yes, or with a biased hash a few more combinations
(even 10x more is not many more)

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

No guarantees, but that is the objective of a
good hash.  It is the criteria by which the 
hash is evaluated.  A hash which simply returns
the same value on each input is a bad hash, but
it would make it hard to force a specific 
output if it were not that one value. :)

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

I assume you meant ~720?

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

I think you proved my point.  The "weakness" you 
are referring to is because your hash is biased.

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

No, you did not strengthen it, you weakened it
by further biasing it.  If you had strengthened
the hash, it would have been easier to get all
1024 values.


The biasing will indeed make it harder to select
certain nodes, but, of course, it will mean that
the other nodes will be biased and easier to 
select.  The more biasing, the more similar 
everyone's paths would be defeating the whole 
purpose of your proposal:  randomness.

It is an interesting idea to force randomness,
and it might have value in some cases (?),
but I do not think that this method could even
approach it.

Cheers,

-Martin




***********************************************************************
To unsubscribe, send an e-mail to majordomo@xxxxxxxxxxxxxx with
unsubscribe or-talk    in the body. http://archives.seul.org/or/talk/