[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
Re: Is it desirable to prevent users from choosing their own circuits?
- To: or-talk@xxxxxxxxxxxxx
- Subject: Re: Is it desirable to prevent users from choosing their own circuits?
- From: Martin Fick <mogulguy@xxxxxxxxx>
- Date: Fri, 2 Oct 2009 09:26:32 -0700 (PDT)
- Delivered-to: archiver@xxxxxxxx
- Delivered-to: or-talk-outgoing@xxxxxxxx
- Delivered-to: or-talk@xxxxxxxx
- Delivery-date: Fri, 02 Oct 2009 12:26:35 -0400
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s1024; t=1254500792; bh=1vhTLvwXoFAMqjFKH0Y102NEiOL44NPX1rL22C0/jMc=; h=Message-ID:X-YMail-OSG:Received:X-Mailer:Date:From:Subject:To:In-Reply-To:MIME-Version:Content-Type:Content-Transfer-Encoding; b=51jWZFty14UgPFc+qSSUPG1GKMgq/Y9GKMQlcj7E/6DyFoF77uGG0YaBVym8elrSAWPZoT3OfaQ5ceAcNX9MxGP2tb/e+CqTatoMi579gbyIDktTny/RCVezY1nMbC/hkJaLE2H7Z5J3+ERdTSQMP7twSvckDmqWX4PdimzXdu4=
- Domainkey-signature: a=rsa-sha1; q=dns; c=nofws; s=s1024; d=yahoo.com; h=Message-ID:X-YMail-OSG:Received:X-Mailer:Date:From:Subject:To:In-Reply-To:MIME-Version:Content-Type:Content-Transfer-Encoding; b=5hxq3eOQarRhDfqiPm1ENwdJdy8Fm5CrYxtUk/z0phL7j0gn2J3XOVgDXNVyYtqvEkoD58+dGOPe4OVdDXC20RNXCzpimoYofKbSw/wG2gQ+n6KT1MCRoJB9u3YmNYhbar1cwFmCAkade4LUAUkCv04O2pIpi1MSe9girIkXO3g=;
- In-reply-to: <4df3a1330910020605n20b28e2x9db176c28f6042cc@xxxxxxxxxxxxxx>
- Reply-to: or-talk@xxxxxxxxxxxxx
- Sender: owner-or-talk@xxxxxxxxxxxxx
--- 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
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
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
To unsubscribe, send an e-mail to majordomo@xxxxxxxxxxxxxx with
unsubscribe or-talk in the body. http://archives.seul.org/or/talk/