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

[Brian Mearns <bmearns@xxxxxxxx>]

On Fri, Oct 2, 2009 at 12:26 PM, Martin Fick <mogulguy@xxxxxxxxx> wrote:
> --- 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
[clip]

Thank you very much for the additional feedback. I hadn't really
considered that this was a criteria of a hashing function, but I guess
it makes sense: if it's biased when fairly mapped to a smaller domain,
it would be biased in the full domain as well. For what it's worth, I
was using SHA-512.

Interestingly, "Applied Cryptography" (by Bruce Schneier) briefly
discusses a distributed timestamping protocol that uses a hash of the
content to be stamped in order to select which nodes will provide the
stamp, the idea being that the requester can't simply choose to use
nodes he controls in order to forge the timestamp. The details are not
given, but it is mentioned that the hash is used to seed a PRNG, the
output of which is used to pick the nodes. I suppose this would suffer
from the same weakening effects of mapping the output into a smaller
domain. If there are only 2^N nodes to choose from, an attacker should
be able to get the one he wants by enumerating through about that many
different inputs. Of course, if he needs to choose 2 nodes, then I
guess he would need to enumerate through 2^(2N) input values to be
almost-guaranteed a hit (or maybe 2^(2N-1), since order doesn't
matter?) I suppose that's where the security comes from in that case.

Regards,
-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@xxxxxxxxxxxxxx with
unsubscribe or-talk    in the body. http://archives.seul.org/or/talk/