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? Tunnels, on the other hand, could avoid a lot of these problems. Once the request is out of the tunnel, it can be happily coalesced etc. And for very popular keys, ULPRs will work well even with tunnels; for less popular keys obviously what you gain in anonymity you lose in reliability. > > > When an attacker gets a tunneled request, he knows 1) there is a 20% chance > > that the node is the originator, and 2) that he is close to the originator, > > because he is early on the route: the tunnel is only active at the beginning. > > Longer tunnels would help in both cases (at a cost, of course). Ideally > the tunnels would be long enough to reach any node with equal > probability, but maybe that's not realistic... > > Let's say we need an average of 10 hops. A weighted coin gives an > exponential hop count distribution (actually geometric but close > enough), so 25% of tunnels will have <= 2.9 hops, 50% will have <= 6.9 > hops, 75% will have <= 13.9 hops. Likewise the attacker will know > there's a 25% chance the initiator is within 2.9 hops, etc. (Not sure > how to handle the rounding here but you get the picture.) And a 10% chance of being directly connected. Right. 10 hops is quite expensive... do we want to have it customisable-per-request? Paranoid requestors would then stick out... OTOH this might be best, 99% of people will use the default setting. > > > For a regular request, the HTL can be 10 much later on in the request. In > > which case the predecessor sample is useless, and the key is likely close to > > the location of the attacker. > > Good point about the distance - can the attacker give less weight to > samples where the requested key is close to the attacker, on the > assumption that they're more likely to have travelled several hops already? Seems plausible. > > > Somewhere on this thread you said that the probability of two related tunnels > > coming from the same node is independant of that node being the originator. I > > don't understand that. > > I didn't mean that exactly - the fact that both tunnels pass through X > *does* suggest that X is the initiator, I'm just saying it's irrelevant > where they go after leaving X. An attacker doesn't learn any more by > linking two tunnels that pass from X to different neighbours than he > learns by linking two tunnels that pass from X to the same neighbour, > because the paths of the tunnels are independent, so the fact that they > did or didn't part company at X doesn't tell the attacker anything about > where they originated. It was a minor point really. Ok, this is true. How much information does an attacker gain from linking two tunnels from the same X ? A fairly high confidence that X is the originator, surely? Higher than the 10% or 20% we're talking about above...? -------------- next part -------------- A non-text attachment was scrubbed... Name: not available Type: application/pgp-signature Size: 189 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/devl/attachments/20080111/dc0bf15e/attachment.pgp>
