[p2p-hackers] Chord comments

[Roger Dingledine]

On Mon, Jul 30, 2001 at 03:59:32PM -0500, Brandon K. Wiley wrote:
> So given a fixed size keyspace (all IP4 addresses), you can do a
> precomputed dictionary attack. If you have a lot of IPs (a.k.a. money)
> then you can very quickly determine which of your IPs is best (since in
> Chord "best" is absolute within a given set of IPs and a given key) and
> then set up a node there. So the question of how useful this attack is
> depends on the distribution of keyspaces over the network.
> 
> My math is probably naive or just wrong, but my attempt at probability
> says that your probability of having the closest key is
> (evil / (good + evil)) ^ keys.
 
Consider that you have M honest machines around the ring already,
and you have N darts that you can throw into the ring. Your goal is to
get at least one dart into specific bins that you're trying to attack
(either so you can be the one responsible for a file you're attacking, or
so you can be the one that is closest to a finger for a given victim node.

Visualize it as a clock face (ie M=12), and you're trying to land at least
one of your darts (each dart thrown independently and uniformly randomly)
between the 12 and the 1. (I'm making the assumption here that anywhere
between the 12 and the 1 will do; I think that's an ok assumption.)

For more complex attacks, you need to collect a number of specific bins
(either to own all the fingers of a particular victim node, or to own
all the replicas of a particular victim file). Picture those as the area
between 1 o'clock and 2 o'clock, etc. The goal is to get at least one
dart into each target bin -- it doesn't matter which dart, or how many
more you get, etc.

So the chance of getting at least one dart in each of P specific bins
(places), given M honest machines already in the ring and given N darts
(new IPs) that you can try, is:

 sum over i from 0 to P of
 (-1)^i * (P Choose i) * ((M-i)/M)^N

I've included a quick perl script at the end of this post so you can play
with it; beware of overruns...factorials are messy things, and this is
a fragile script. But first, some sample situations:

Chance of winning 1 places amid 10000 machines with 1000 new IPs is 0.0951671064414438.
Chance of winning 1 places amid 10000 machines with 5000 new IPs is 0.393484504375222.
Chance of winning 14 places amid 10000 machines with 5000 new IPs is 2.10996882146536e-06.
(~14 fingers in 10K nodes)

Chance of winning 1 places amid 10000 machines with 50000 new IPs is 0.993263737389397.
Chance of winning 14 places amid 10000 machines with 50000 new IPs is 0.909710516660863.

Chance of winning 100 places amid 10000 machines with 50000 new IPs is 0.508637738432524.
(so a file replicated into 100 different places is still vulnerable)
Chance of winning 200 places amid 10000 machines with 50000 new IPs is 0.258652809279435.

> So if you have 65k addresses and the network has 65k nodes, then your odds
> of being closest for a given key are 50%. Your odds for winning on two
> keys are 25%, etc.. So if you have the entire IP resources of a
> university, you can *almost* be assured of censoring one file, but if you
> want to, say, censor 65k files (one file per node), then you get .5 ^ 65k,
> which is really small.

Chance of winning 1 places amid 65000 machines with 65000 new IPs is 0.632123388689125.
Chance of winning 2 places amid 65000 machines with 65000 new IPs is 0.399577896430526.
Chance of winning 3 places amid 65000 machines with 65000 new IPs is 0.252579901639995.
Chance of winning 4 places amid 65000 machines with 65000 new IPs is 0.159659167435841.
Chance of winning 5 places amid 65000 machines with 65000 new IPs is 0.100922190340699.

It's really a matter of beating the current number of active machines.

Chance of winning 1000 places amid 5000 machines with 50000 new IPs is 0.955655650413358.

Winning all 5000 places is .797.
 
Hope this helps. Note that this analysis completely ignores the more
realistic attack, which is calculate which IPs on the net would be better
for you, and break into them or some machine on their subnet. It also
doesn't consider whether it becomes harder to "reuse" the same address
space on future attacks.
--Roger
(Thanks to Eddy Karat for arguing the math with me, and giving me such a
clean summation. Do let me know if you fix it or improve on it, or if all
of my calculations here included overruns so the numbers are all wrong.)



#!/usr/bin/perl

# Calculate \Sigma_{i=0}^P
#   (-1)^i * (P Choose i) * ((M-i)/M)^N

# swiped and pruned from http://code.anapraxis.net/Math/Combinatorics.pm
#  get a better Choose function if you want better accuracy
sub Choose {
  my $n = shift;  die "N ($n) must be a positive integer" if $n < 1;
  my $r = shift;

     die "R must be 0 < R < N ($n) if there is no repetition"
          if ($r < 0 || $r > $n);
      my $c = 1;
      if ($r > $n/2) { $r = $n - $r }   # Take advantage of 2)
      for (1..$r) {
        $c *= $n--;                     # n! / (n-r)!
        $c /= $_;                       # c  / r!
      }
      return $c;

}

##########################

$n = 50000; # number of adversary machines
$m = 5000; # number of honest machines
$p = 200; # number of simultaneous attacks i must make

$sum = 0;

for($i=0;$i<=$p;$i++) {

  $sum += ( ((-1)**$i) * (Choose($p, $i)) * ((($m-$i)/$m)**$n) );

  print "sum at i=$i is $sum.\n";

}

print "Chance of winning $p places amid $m machines with $n new IPs is $sum.\n";