-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Matthew Toseland schrieb: | On Saturday 05 January 2008 05:15, Michael Rogers wrote: |> Matthew Toseland wrote: |>> The 50% chance of decrementing |>> at 10 means that 3 resets equals 6 nodes with HTL 10... |> It's more complicated than that... if the HTL is 10 and the closest |> location isn't the previous hop's location, then the attacker knows the |> previous hop doesn't decrement at 10. | | It's a function of the input node, not the output node. Although that's | problematic on rerouting, so we may change it to be a function of the input | node for the first node tried, and then a function of the output node... | Hmmm. Why did we want to choose it once per node again? I'm sure there was a | good reason, but I don't remember it... | |> Likewise if the HTL is 9 and the |> closest location isn't the previous hop's location, the previous hop |> decrements at 10. Either way, the attacker can use that knowledge for |> the rest of the session. | | Okay, so for a single request, if HTL is 10, and closestLocation is equal to | the node's location, the node could be the originator or it could have reset | it. If HTL is 10, and closestLocation is not equal to the node's location, | the node cannot be the originator and cannot have reset the HTL. | | So without keeping any state, we just look for requests which have | closestLocation equal to the previous node's location, and we have a 1 in (# | resets per request + 1) chance that it's the originator (1 in 4 on the | previous assumption). Ouch! I'm not sure how the additional state we could | keep from the above would help the attacker. | | For a non-resetting HTL, the odds are even worse, unless we have a long | probabilistic htl=max stage. So plainly a weighted coin would help | significantly. The problem is that a weighted coin would increase the | variance in path length *significantly*, cause more no-fault timeouts, cause | more no-fault failures (too short a path), make request coalescing extremely | difficult, and likewise with ULPRs. Is there an alternative? | | [snip]
How about a combination of HTL and weighted coin: We don't only decrement probabilisticly at 10 and 1 but on all the way down from 10 to 0 and flip the coin each time so no (100% sure) assumption can be made what we will do next time. In Order to travel not too far we weigh the coin (let's say at 80% for a decrement). If our location is closer than the closestLocation we don't set closestLocation to our actual location but to a location a little bit _closer_ (if we set it to a location more far away the next node knows we reset closestLocation), this is also done probabilistic, and set the HTL to a value between 8 and 10 (more likely to 10 than to 8 - maybe we could even set it to a value between 1 and 10 but make 1 extremely unlikely e.g. (int)(11-10*Math.pow(PROBABILITY_TUNER,(-Math.random()))) where PROBABILITY_TUNER is 10^(1/(1-(Probability of HTL=10))) ). To add even more fuzz we could even make the probabilities a partly random value. So every time the node is started it calculates the probabilities to decrement the HTL per possible HTL-value. Of course we had to limit that but again I would speak for letting them be everything but making it more likely to be a suitable value. If we do the above the attacker can't rely on anything being for sure, he can just estimate the probability, and even that does vary everytime the peer-node is restarted. But for routing purposes it should be reliable enough. If we get an data not found we just have to try again (If we decide that we still need it - - that could be not the case if we're searching for the next 5 USK-editions but find none of them, then we could just try the first again and if it's not found we assume we have found the last edition) and it will be likely that the data is found if it's present. regards Neo at NHNG -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFHjN3NPUBAMhFf+J4RAi9+AJoC/xo9SeMBSMJpdflevn02JyohzgCeNnPd myP+vfSnIsPF1FjYOrY7XUs= =Jea/ -----END PGP SIGNATURE-----
